In a game in which, at each time step, a player declares a mixed strategy, then an adversary assigns a cost to each of that player's pure strategies, and then the mixed strategy is applied and that player realizes the cost of the strategy sampled from their mixture, this professor makes the claim that one should not use that player's cost as a benchmark of an algorithm, but rather that player's external regret.

On one hand, this is incredibly intuitive, as it at least apparently aligns with a piece of strategic advice human experts in real games often give; namely, to focus on the aspects of gameplay over which you as a player have control, and not on the aspects over which you have no control. On the other hand, something feels vaguely suspicious here.

The objective of a player in game theory has always been to minimize cost (or, equivalently, maximize payoff). Switching benchmarks feels like too much latitude to afford a player. It should be trivial to formulate a strategy to outsmart an adversary in any game given this amount of latitude. For example, the player could just declare indifference toward the outcome of the game, and any strategy would become weakly optimal. Even if we subjectively seek a benchmark which is a bit more motivated than that, it feels like qualitative conclusions discovered in that benchmark space could end up being artifacts of the benchmark rather than objective features of a game-strategy pair.

Perhaps confounding this confusion is the fact that the professor uses the interval between $0$ and $1$ as the scale over which both the per-day cost and per-day external regret range, and I can't tell if these are supposed to be "the same interval from $0$ to $1$," or if there is some silent asymmetric rescaling of utilities being assumed.

In what sense if at all are cost and external regret quantities comparable? Is there an easy way to see that decreasing a player's external regret always (monotonically?) decreases that player's cost function if it indeed does, or are the two only related heuristically? Are there constraints in more general contexts on what can and cannot be a benchmark?



Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.