Repeated Games against Budgeted Adversaries

Jacob D. Abernethy, Manfred K. WarmuthNeurIPS 2010 · OpenReview

In the world of online learning, "Nature" is often treated as an all-powerful adversary trying to maximize our loss. But what if the adversary operates on a budget? This paper by Jacob Abernethy and Manfred Warmuth explores a deep connection between game theory, Monte Carlo methods, and optimal prediction. They prove that for a broad class of repeated zero-sum games with a budgeted adversary, the minimax optimal strategy is exactly a "random playout" (Monte Carlo) technique. This provides a unified, efficient framework for solving diverse problems like cost-sensitive learning, Metrical Task Systems, and combinatorial prediction markets.

The Budgeted Adversary Problem

Most online learning algorithms (like the famous "Hedge" or Weighted Majority algorithm) are designed to minimize regret against an arbitrary sequence of outcomes. However, these algorithms often ignore specific constraints on the adversary.

Imagine a game that ends once the adversary has "spent" a certain amount of cost. If one expert is much more "expensive" for the adversary to use than another, a standard algorithm that treats all experts equally will be suboptimal. The authors tackle the Budgeted Adversary problem: how should a player move if they know the game will terminate based on a monotonic cost function applied to the adversary's actions?

Methodology: Random Playouts and Expected Game Length

The authors formalize the Budgeted Adversary Game, defined by a loss matrix $M$, a cost function, and a budget $k$. The core of their approach relies on a function $\Phi(\rho)$, which represents the expected remaining length of the game if both players were to play a specific randomized strategy from the current state $\rho$.

Instead of complex dynamic programming over exponential state spaces, the player estimates $\Phi(\rho)$ by simulating the rest of the game using random sequences (Monte Carlo sampling). The optimal strategy dictates that the player's weight on action $i$ is set proportional to the difference between the current expected game length and the expected length if action $i$ is chosen, normalized by the cost:

Optimal strategy weight calculation

Using a recurrence relation, the authors prove that this strategy is not just a good heuristic (like its traditional use in games with massive state spaces, such as Go), but is actually minimax optimal for diagonal loss matrices.

Key Insights and Results

  • Monte Carlo is Optimal: The most striking insight is that the "random playout" technique is the mathematically perfect strategy for budgeted online learning.
  • Budget as a Stopping Criterion: By viewing the "good expert" assumption as a budget constraint on Nature, the authors successfully unify several disparate fields of online algorithms.
  • The "Expected Length" Intuition: The optimal move is essentially determined by how much that move "shrinks" the adversary's remaining options. The goal is to play in a way that forces the adversary to spend their budget as quickly as possible while minimizing immediate loss.
  • Cost-Sensitive Hedge: The paper provides the first optimal strategy for the "Hedge" setting where different experts have different cost ranges (e.g., one expert's errors are more "expensive" to the adversary than another's).
  • Weighted-Star MTS: They derive a simple, minimax optimal algorithm for Metrical Task Systems on weighted-star metrics, a problem that had previously required complex primal-dual machinery.
  • Combinatorial Markets: The framework is flexible enough to design prediction markets for complex outcomes (like "subset betting") by simply modifying the budget's cost function.

Limitations and Future Work

While the framework is powerful, it has a few limitations. The current proof of optimality primarily covers diagonal matrices and "inverse-nonnegative" matrices, which does not encompass every possible zero-sum game. Additionally, while Monte Carlo sampling is "efficient" compared to exhaustive search, we still lack closed-form expressions for the expected game length $\Phi$ in many complex settings.

The authors conclude by posing an open challenge: Can an efficient minimax algorithm be found for arbitrary payoff matrices $M$ in the budgeted setting? This remains an unsolved gap between repeated games and one-shot linear programming.

Summary updated

Abstract

We study repeated zero-sum games against an adversary on a budget. Given that an adversary has some constraint on the sequence of actions that he plays, we consider what ought to be the player's best mixed strategy with knowledge of this budget. We show that, for a general class of normal-form games, the minimax strategy is indeed efficiently computable and relies on a random playout" technique. We give three diverse applications of this algorithmic template: a cost-sensitive "Hedge" setting, a particular problem in Metrical Task Systems, and the design of combinatorial prediction markets."
BibTeX
@inproceedings{abernethy2010repeated,
  author = {Jacob D. Abernethy and Manfred K. Warmuth},
  title = {{Repeated Games against Budgeted Adversaries}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2010},
  url = {https://openreview.net/forum?id=Jy9Nh2uMdpR},
}
Figure