Timezone: »

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

Tue Dec 09 04:00 PM -- 08:59 PM (PST) @ Level 2, room 210D
in Poster Session »

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.

[ PDF] 

Author Information

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

More from the Same Authors