Conditional Swap Regret and Conditional Correlated Equilibrium

Mehryar Mohri, Scott YangNeurIPS 2014 · OpenReview

In the realm of online learning and game theory, evaluating the performance of decision-making algorithms is traditionally done using "regret" measures. However, standard regret metrics often fail to capture temporal patterns in decision-making. This paper, authored by Mehryar Mohri and Scott Yang, introduces a significant advancement by moving beyond "static" regret measures to ones that account for recent history.

The authors introduce conditional swap regret, a novel metric that evaluates an algorithm against competitors capable of swapping actions based on the player's recent action history. Alongside this metric, they provide efficient algorithms to minimize this regret and prove that when all players in a game minimize it, the system converges to a stricter type of equilibrium known as conditional correlated equilibrium.

The Gap in Traditional Regret Measures

In the standard online learning framework, a player chooses an action, an adversary reveals the associated losses, and the player attempts to minimize regret over time. Historically, research has focused on two primary types of regret:

  1. External Regret: Comparing your algorithm's performance to the single best fixed action chosen in hindsight.
  2. Swap Regret: Comparing performance to a competitor who could have consistently swapped every instance of one action for another (e.g., "Every time I bought Microsoft, I should have bought IBM").

The Problem: Both of these measures are inherently "memoryless." They do not account for correlations or patterns over time. For instance, in a volatile financial market, a trader might want to swap "buy stocks" for "buy bonds" only if they had bought stocks in the immediately preceding time step. Standard swap regret cannot express this conditional, time-dependent logic. This paper bridges that gap by allowing action modifications to be conditioned on a history of $k$ previous steps.

Algorithmic Approach: $k$-gram Conditional Swap Regret

To solve this, the authors define the $k$-gram conditional swap regret class. This class comprises functions that map the current action and the previous $k-1$ actions to a new, optimized action.

Key Methodological Innovations

  • Meta-Algorithm Construction: In the "full information" setting (where the player sees all possible losses after making a choice), the authors construct a meta-algorithm. For a bigram case (history of 1 step), it initializes $N^2$ separate "external regret" algorithms as subroutines, where $N$ is the number of possible actions.
  • Markov Chain Integration: To determine the next action, the algorithm constructs a transition matrix—effectively a Markov chain—based on the weights of these subroutines. It then finds the stationary distribution of this chain. This critical step ensures the algorithm's action distribution remains consistent with the history-dependent swaps it aims to outperform.
Markov chain transition diagrams illustrating memoryless vs. history-dependent action selection.
  • Bandit Extension: The authors successfully extend this logic to the more challenging "bandit" setting, where the player only observes the loss of the specific action they took. They achieve this by utilizing the well-known Exp3 algorithm as a base learner.
  • State-Dependent Bounds: To mitigate computational complexity, they introduce a method to consider conditional swaps only for a specific subset of critical historical states, rather than the entire history space.

Key Insights and Theoretical Results

The paper relies on rigorous mathematical proofs and algorithmic analysis to establish several foundational insights for machine learning and game theory:

  • The Limits of Memory (No-Free-Lunch): The authors prove that it is mathematically impossible to achieve sublinear regret against a competitor equipped with infinite memory. However, by bounding the memory to a finite $k$ steps, sublinear regret becomes achievable.
  • Conditional Correlated Equilibrium (CCE): In traditional game theory, if all players minimize standard swap regret, the game converges to a "Correlated Equilibrium." This paper demonstrates that minimizing conditional swap regret leads to a stricter Conditional Correlated Equilibrium (CCE). In a CCE, no player has an incentive to deviate from their strategy, even when factoring in the specific sequence of actions taken in previous rounds.
  • Regret Bounds:
    • Bigram Bound: For a history length of 1 ($k=2$), the algorithm achieves a regret bound of $O(N \sqrt{T \log N})$. As time ($T$) approaches infinity, the average regret per step approaches zero.
  • General $k$-gram Bound: For a history of length $k-1$, the regret is bounded by $O(\sqrt{N^{k+1} T \log N})$.
  • Bandit Scenario: Even with limited bandit feedback, a sublinear regret bound of $O(\sqrt{N^{k+1} T \log N})$ is proven possible.
  • Computational Efficiency: The bigram algorithm operates with a per-round computational complexity of $O(N^3)$, which remains highly manageable for environments with a reasonable number of discrete actions.

Limitations and Future Directions

While theoretically robust, the framework presents clear computational trade-offs. The "curse of dimensionality" is evident, as both complexity and regret bounds grow exponentially with $N^k$. Consequently, the approach is currently most practical for very short memories (like bigrams or trigrams).

Furthermore, much of the paper's analysis assumes an "oblivious adversary" (one who determines all losses in advance). While the authors propose "batching" techniques to potentially handle adaptive adversaries, a comprehensive exploration of non-oblivious settings is left for future work. Finally, while financial markets serve as a compelling conceptual motivator, future research will need to empirically demonstrate how these conditional swap algorithms perform on real-world, noisy time-series data.

Summary updated

Abstract

We introduce a natural extension of the notion of swap regret, conditional swap regret, that allows for action modifications conditioned on the player’s action history. We prove a series of new results for conditional swap regret minimization. We present algorithms for minimizing conditional swap regret with bounded conditioning history. We further extend these results to the case where conditional swaps are considered only for a subset of actions. We also define a new notion of equilibrium, conditional correlated equilibrium, that is tightly connected to the notion of conditional swap regret: when all players follow conditional swap regret minimization strategies, then the empirical distribution approaches this equilibrium. Finally, we extend our results to the multi-armed bandit scenario.
BibTeX
@inproceedings{mohri2014conditional,
  author = {Mehryar Mohri and Scott Yang},
  title = {{Conditional Swap Regret and Conditional Correlated Equilibrium}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2014},
  url = {https://openreview.net/forum?id=S1-9UwZuWS},
}
Figure