Conditional Swap Regret and Conditional Correlated Equilibrium
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.
This paper discusses a type of swap regret which is conditioned on past actions of the user. They connected this concept with a new type of correlated equilibria. They designed hardness results for having the behavior conditional on the whole past, and came up with an algorithm which minimized the new type of regret. Finally, it showed how to deal with this type of regret in a bandit setting.First of all, I think that this is an interesting area of research. However, I didn't see what I look for in new concepts of equilibrium, namely whether one can cooperate with one's opponent and still minimize regret. Secondly, I found that the paper was unclear when it could have been done so much more cleanly. Specifically, instead of a convoluted description of interleaving multiple regret algorithms, they could have simply started from the algorithms based upon regret matching and swap regret.Specifically, you can break down the regret into "regret on time T from playing action i after action j instead of action k".r^T_{i,j,k}=p^T_i p^{T-1}_j (f^T_i - f^T_k)Then, define the total regret as:R^T_{i,j,k}=\sum_{t=2}^T r^t_{i,j,k}Then, bigram swap regret is:Regret_T=\sum_{i} \max_{k} R^T_{i,j,k}Thus, if all of the R^T_{i,j,k} are increasing sublinearly, you're good. Define:R^{T,+}_{i,j,k}=max(0, R^T_{i,j,k})Blackwell's approachability theorem needs:\sum_{i,j,k} r^{T+1}_{i,j,k} R^{T,+}_{i,j,k} \leq 0which implies:\sum_{i,j,k} p^{T+1}_i p^{T}_j (f^{T+1}_i - f^{T+1}_k) R^{T,+}_{i,j,k} \leq 0We know p^T and R^{T,+}, so we pull that to the right:\sum_{i,k} p^{T+1}_i (f^{T+1}_i - f^{T+1}_k) \sum_j p^{T}_j R^{T,+}_{i,j,k} \leq 0You can define a value:R^{T,+}_{i,k} = \sum_j p^{T}_j R^{T,+}_{i,j,k}So, our new desired inequality is:\sum_{i,k} p^{T+1}_i (f^{T+1}_i - f^{T+1}_k) R^{T,+}_{i,k} \leq 0This is exactly swap regret. Moreover, it extends to n-grams easily (r^T_{i,j,k,l}=p^T_i p^{T_1}_j p^{T-2}_k (f_l - f_i) for trigams). If you don't care about a particular transition in a particular state (as in state-dependent bounds), you can zero out that R^T_{i,j,k}.T_{i,j,k}. So, this seems like a much simpler way to do what they are trying to do.