Conditional Swap Regret and Conditional Correlated Equilibrium
Mehryar Mohri · Scott Yang

Tue Dec 9th 07:00 -- 11:59 PM @ Level 2, room 210D #None

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.

Author Information

Mehryar Mohri (Courant Inst. of Math. Sciences & Google Research)
Scott Yang (D. E. Shaw & Co.)

More from the Same Authors