Near-Optimal Reinforcement Learning with Self-Play

Introduction

A wide range of modern artificial intelligence challenges can be cast as a multi-agent reinforcement learning (multi-agent RL) problem, in which more than one agent performs sequential decision making in an interactive environment. Multi-agent RL has achieved significant recent success on traditionally challenging tasks, for example in the game of GO , Poker , real-time strategy games , decentralized controls or multiagent robotics systems , autonomous driving , as well as complex social scenarios such as hide-and-seek . In many scenarios, the learning agents even outperform the best human experts .

Despite the great empirical success, a major bottleneck for many existing RL algorithms is that they require a tremendous number of samples. For example, the biggest AlphaGo Zero model is trained on tens of millions of games and took more than a month to train . While requiring such amount of samples may be acceptable in simulatable environments such as GO, it is not so in other sample-expensive real world settings such as robotics and autonomous driving. It is thus important for us to understand the sample complexity in RL—how can we design algorithms that find a near optimal policy with a small number of samples, and what is the fundamental limit, i.e. the minimum number of samples required for any algorithm to find a good policy.

Can we design algorithms with near-optimal sample complexity for learning Markov games?

Apart from finding Nash equilibria, we prove that learning the best responses of fixed opponents in Markov games is as hard as learning parity with noise—a notoriously difficult problem that is believed to be computationally hard (Section 5). As a corollary, this hardness result directly implies that achieving sublinear regret against adversarial opponents in Markov games is also computationally hard, a result that first appeared in . This in turn rules out the possibility of designing efficient algorithms for finding Nash equilibria by running no-regret algorithms for each player separately.

In addition to above contributions, this paper also features a novel approach of extracting certified policies—from the estimates produced by reinforcement learning algorithms such as Nash Q-learning and Nash V-learning—that are certified to have similar performance as Nash equilibrium policies, even when facing against their best response (see Section 3 for more details). We believe this technique could be of broader interest to the community.

2 Related Work

Markov games (or stochastic games) are proposed in the early 1950s . They are widely used to model multi-agent RL. Learning the Nash equilibria of Markov games has been studied in classical work , where the transition matrix and reward are assumed to be known, or in the asymptotic setting where the number of data goes to infinity. These results do not directly apply to the non-asymptotic setting where the transition and reward are unknown and only a limited amount of data are available for estimating them.

A recent line of work tackles self-play algorithms for Markov games in the non-asymptotic setting with strong reachability assumptions. Specifically, Wei et al. 2017 assumes no matter what strategy one agent sticks to, the other agent can always reach all states by playing a certain policy, and Jia et al. 2019, Sidford et al. 2019 assume access to simulators (or generative models) that enable the agent to directly sample transition and reward information for any state-action pair. These settings ensure that all states can be reached directly, so no sophisticated exploration is not required.

Very recently, study learning Markov games without these reachability assumptions, where exploration becomes essential. However, both results suffer from highly suboptimal sample complexity. We compare them with our results in Table 1. The results of also applies to the linear function approximation setting. We remark that the R-max algorithm does provide provable guarantees for learning Markov game, even in the setting of playing against the adversarial opponent, but using a definition of regret that is weaker than the standard regret. Their result does not imply any sample complexity result for finding Nash equilibrium policies.

Adversarial MDP

Another line of related work focuses on provably efficient algorithms for adversarial MDPs. Most work in this line considers the setting with adversarial rewards , because adversarial MDP with changing dynamics is computationally hard even under full-information feedback . These results do not directly imply provable self-play algorithms in our setting, because the opponent in Markov games can affect both the reward and the transition.

Single-agent RL

Preliminaries

We consider zero-sum Markov Games (MG) , which are also known as stochastic games in the literature. Zero-sum Markov games are generalization of standard Markov Decision Processes (MDP) into the two-player setting, in which the max-player seeks to maximize the total return and the min-player seeks to minimize the total return.

A Markov policy $\mu$ of the max-player is a collection of $H$ functions $\{\mu_{h}:\mathcal{S}\rightarrow\Delta_{\mathcal{A}}\}_{h\in[H]}$, which maps from a state to a distribution of actions. Here $\Delta_{\mathcal{A}}$ is the probability simplex over action set $\mathcal{A}$. Similarly, a policy $\nu$ of the min-player is a collection of $H$ functions $\{\nu_{h}:\mathcal{S}\rightarrow\Delta_{\mathcal{B}}\}_{h\in[H]}$. We use the notation $\mu_{h}(a|s)$ and $\nu_{h}(b|s)$ to present the probability of taking action $a$ or $b$ for state $s$ at step $h$ under Markov policy $\mu$ or $\nu$ respectively.

for all $(s,a,b,h)\in\mathcal{S}\times\mathcal{A}\times\mathcal{B}\times[H]$. We define $V^{\mu,\nu}_{H+1}(s)=0$ for all $s\in\mathcal{S}_{H+1}$.

Best response and Nash equilibrium

For any Markov policy of the max-player $\mu$, there exists a best response of the min-player, which is a Markov policy $\nu^{\dagger}(\mu)$ satisfying $V_{h}^{\mu,\nu^{\dagger}(\mu)}(s)=\inf_{\nu}V_{h}^{\mu,\nu}(s)$ for any $(s,h)\in\mathcal{S}\times[H]$. Here the infimum is taken over all possible policies which are not necessarily Markovian (we will define later in this section). We define $V_{h}^{\mu,\dagger}\mathrel{\mathop{:}}=V_{h}^{\mu,\nu^{\dagger}(\mu)}$. By symmetry, we can also define $\mu^{\dagger}(\nu)$ and $V_{h}^{\dagger,\nu}$. It is further known (cf. ) that there exist Markov policies $\mu^{\star}$, $\nu^{\star}$ that are optimal against the best responses of the opponents, in the sense that

We call these optimal strategies $(\mu^{\star},\nu^{\star})$ the Nash equilibrium of the Markov game, which satisfies the following minimax equation: The minimax theorem here is different from the one for matrix games, i.e. $\max_{\phi}\min_{\psi}\phi^{\top}A\psi=\min_{\psi}\max_{\phi}\phi^{\top}A\psi$ for any matrix $A$, since here $V^{\mu,\nu}_{h}(s)$ is in general not bilinear in $\mu,\nu$.

Intuitively, a Nash equilibrium gives a solution in which no player has anything to gain by changing only her own policy. We further abbreviate the values of Nash equilibrium $V_{h}^{\mu^{\star},\nu^{\star}}$ and $Q_{h}^{\mu^{\star},\nu^{\star}}$ as $V_{h}^{{\star}}$ and $Q_{h}^{{\star}}$. We refer readers to Appendix A for Bellman optimality equations for values of best responses or Nash equilibria.

General (non-Markovian) policy

For a pair of general policy $(\mu,\nu)$, we can still use the same definitions (1) to define their value $V_{1}^{\mu,\nu}(s_{1})$ at step $1$. We can also define the best response $\nu^{\dagger}(\mu)$ of a general policy $\mu$ as the minimizing policy so that $V_{1}^{\mu,\dagger}(s_{1})\equiv V_{1}^{\mu,\nu^{\dagger}(\mu)}(s_{1})=\inf_{\nu}V_{h}^{\mu,\nu}(s_{1})$ at step 1. We remark that the best response of a general policy is not necessarily Markovian.

Learning Objective

There are two possible learning objectives in the setting of Markov games. The first one is to find the best response for a fixed opponent. Without loss of generality, we consider the case where the learning agent is the max-player, and the min-player is the opponent.

For an opponent with an fixed unknown general policy $\nu$, a general policy $\hat{\mu}$ is the $\epsilon$-approximate best response if $V^{\dagger,\nu}_{1}(s_{1})-V^{\hat{\mu},\nu}_{1}(s_{1})\leq\epsilon$.

The second goal is to find a Nash equilibrium of the Markov games. We measure the suboptimality of any pair of general policies $(\hat{\mu},\hat{\nu})$ using the gap between their performance and the performance of the optimal strategy (i.e. Nash equilibrium) when playing against the best responses respectively:

A pair of general policies $(\hat{\mu},\hat{\nu})$ is an $\epsilon$-approximate Nash equilibrium, if $V^{\dagger,\hat{\nu}}_{1}(s_{1})-V^{\hat{\mu},\dagger}_{1}(s_{1})\leq\epsilon$.

Loosely speaking, Nash equilibria can be viewed as “the best responses to the best responses”. In most applications, they are the ultimate solutions to the games. In Section 3 and 4, we present sharp guarantees for learning an approximate Nash equilibrium with near-optimal sample complexity. However, rather surprisingly, learning a best response in the worst case is more challenging than learning the Nash equilibrium. In Section 5, we present a computational hardness result for learning an approximate best response.

Optimistic Nash Q-learning

In this section, we present our first algorithm Optimistic Nash Q-learning and its corresponding theoretical guarantees.

Our algorithm Optimistic Nash Q-learning (Algorithm 1) is an optimistic variant of Nash Q-learning . For each step in each episode, it (a) takes actions according to the previously computed policy $\pi_{h}$, and observes the reward and next state, (b) performs incremental updates on Q-values, and (c) computes new greedy policies and updates $V$-values. Part (a) is straightforward; we now focus on explaining part (b) and part (c).

In part (b), the incremental updates on Q-values (Line 8, 9) are almost the same as standard Q-learning , except here we maintain two separate Q-values—$\overline{Q}_{h}$ and $\underline{Q}_{h}$, as upper and lower confidence versions respectively. We add and subtract a bonus term $\beta_{t}$ in the corresponding updates, which depends on $t=N_{h}(s_{h},a_{h},b_{h})$—the number of times $(s_{h},a_{h},b_{h})$ has been visited at step $h$. We pick parameter $\alpha_{t}$ and $\beta_{t}$ as follows for some large constant $c$ , and log factors $\iota$:

In part (c), our greedy policies are computed using a Coarse Correlated Equilibrium (CCE) subroutine, which is first introduced by to solve Markov games using value iteration algorithms. For any pair of matrices $\overline{Q},\underline{Q}\in[0,H]^{A\times B}$, $\textsc{CCE}(\overline{Q},\underline{Q})$ returns a distribution $\pi\in\Delta_{\mathcal{A}\times\mathcal{B}}$ such that

It can be shown that a CCE always exists, and it can be computed by linear programming in polynomial time (see Appendix B for more details).

Now we are ready to state an intermediate guarantee for optimistic Nash Q-learning. We assume the algorithm has played the game for $K$ episodes, and we use $V^{k},Q^{k},N^{k},\pi^{k}$ to denote values, visitation counts, and policies at the beginning of the $k$-th episode in Algorithm 1.

For any $p\in(0,1]$, choose hyperparameters $\alpha_{t},\beta_{t}$ as in (3) for a large absolute constant $c$ and $\iota=\log(SABT/p)$. Then, with probability at least $1-p$, Algorithm 1 has following guarantees

$\overline{V}_{h}^{k}(s)\geq V^{\star}_{h}(s)\geq\underline{V}_{h}^{k}(s)$ for all $(s,h,k)\in\mathcal{S}\times[H]\times[K]$.

$(1/K)\cdot\sum_{k=1}^{K}(\overline{V}_{1}^{k}-\underline{V}_{1}^{k})(s_{1})\leq\mathcal{O}{\left(\sqrt{H^{5}SAB\iota/K}\right)}$.

Lemma 3 makes two statements. First, it claims that the $\overline{V}_{h}^{k}(s)$ and $\underline{V}_{h}^{k}(s)$ computed in Algorithm 1 are indeed upper and lower bounds of the value of the Nash equilibrium. Second, Lemma 3 claims that the averages of the upper bounds and the lower bounds are also very close to the value of Nash equilibrium $V_{1}^{\star}(s_{1})$, where the gap decrease as $1/\sqrt{K}$. This implies that in order to learn the value $V_{1}^{\star}(s_{1})$ up to $\epsilon$-accuracy, we only need $\mathcal{O}(H^{5}SAB\iota/\epsilon^{2})$ episodes.

However, Lemma 3 has a significant drawback: it only guarantees the learning of the value of Nash equilibrium. It does not imply that the policies $(\mu^{k},\nu^{k})$ used in Algorithm 1 are close to the Nash equilibrium, which requires the policies to have a near-optimal performance even against their best responses. This is a major difference between Markov games and standard MDPs, and is the reason why standard techniques from the MDP literature does not apply here. To resolve this problem, we propose a novel way to extract a certified policy from the optimistic Nash Q-learning algorithm.

Algorithm part II: certified policies

We describe our procedure of executing the certified policy $\hat{\mu}$ of the max-player is described in Algorithm 2. Above, $\mu^{k}_{h},\nu^{k}_{h}$ denote the marginal distributions of $\pi^{k}_{h}$ produced in Algorithm 1 over action set $\mathcal{A},\mathcal{B}$ respectively. We also introduce the following quantities that directly induced by $\alpha_{t}$:

whose properties are listed in the following Lemma 11. Especially, $\sum_{i=1}^{t}\alpha_{t}^{i}=1$, so $\{\alpha_{t}^{i}\}_{i=1}^{t}$ defines a distribution over $[t]$. We use $k^{m}_{h}(s,a,b)$ to denote the index of the episode where $(s,a,b)$ is observed in step $h$ for the $m$-th time. The certified policy $\hat{\nu}$ of the min-player is easily defined by symmetry. We note that $\hat{\mu},\hat{\nu}$ are clearly general policies, but they are no longer Markov policies.

The intuitive reason why such policy $\hat{\mu}$ defined in Algorithm 2 is certified by Nash Q-learning algorithm, is because the update equation in line 8 of Algorithm 1 and equation (5) gives relation:

This certifies the good performance against the best responses if the max-player plays a mixture of policies $\{\mu_{h+1}^{k_{h}^{i}(s,a,b)}\}_{i=1}^{t}$ at step $h+1$ with mixing weights $\{\alpha_{t}^{i}\}_{i=1}^{t}$ (see Appendix C.2 for more details). A recursion of this argument leads to the certified policy $\hat{\mu}$—a nested mixture of policies.

We now present our main result for Nash Q-learning, using the certified policies $(\hat{\mu},\hat{\nu})$.

For any $p\in(0,1]$, choose hyperparameters $\alpha_{t},\beta_{t}$ as in (3) for large absolute constant $c$ and $\iota=\log(SABT/p)$. Then, with probability at least $1-p$, if we run Nash Q-learning (Algorithm 1) for $K$ episodes where

the certified policies $(\hat{\mu},\hat{\nu})$ (Algorithm 2) will be $\epsilon$-approximate Nash, i.e. $V^{\dagger,\hat{\nu}}_{1}(s_{1})-V^{\hat{\mu},\dagger}_{1}(s_{1})\leq\epsilon$.

Theorem 4 asserts that if we run the optimistic Nash Q-learning algorithm for more than $\mathcal{O}(H^{5}SAB\iota/\epsilon^{2})$ episodes, the certified policies $(\hat{\mu},\hat{\nu})$ extracted using Algorithm 2 will be $\epsilon$-approximate Nash equilibrium (Definition 2).

We make two remarks. First, the executions of the certified policies $\hat{\mu},\hat{\nu}$ require the storage of $\{\mu^{k}_{h}\}$ and $\{\nu^{k}_{h}\}$ for all $k,h\in[H]\times[K]$. This makes the space complexity of our algorithm scales up linearly in the total number of episodes $K$. Second, Q-learning style algorithms (especially online updates) are crucial in our analysis for achieving sample complexity linear in $S$. They enjoy the property that every sample is only been used once, on the value function that is independent of this sample. In contrast, value iteration type algorithms do not enjoy such an independence property, which is why the best existing sample complexity scales as $S^{2}$ . Despite provides techniques to improve the sample complexity from $S^{2}$ to $S$ for value iteration in MDP, the same techniques can not be applied to Markov games due to the unique challenge that, in Markov games, we aim at finding policies that are good against their best responses.

Optimistic Nash V-learning

Nash V-learning combines the idea of Follow-The-Regularized-Leader (FTRL) in the bandit literature with the Q-learning algorithm in reinforcement learning. This algorithm does not require extra information exchange between players other than standard game playing, thus can be ran separately by the two players. We describe the max-player version in Algorithm 3. See Algorithm 7 in Appendix D for the min-player version, where $\underline{V}_{h}$, $\underline{L}_{h}$, $\nu_{h}$, $\underline{\eta}_{t}$ and $\underline{\beta}_{t}$ are defined symmetrically.

Here $\mu_{0}$ is the uniform distribution over all actions $\mathcal{A}$. Solving above minimization problem gives the update equation as in Line 12 in Algorithm 3. In multi-arm bandit, FTRL can defend against adversarial losses, with regret independent of the number of the opponent’s actions. This property turns out to be crucial for Nash V-learning to achieve sharper sample complexity than Nash Q-learning (see the analog of Lemma 3 in Lemma 15).

Similar to Nash Q-learning, we also propose a new algorithm (Algorithm 4) to extract a certified policy from the optimistic Nash V-learning algorithm. The certified policies are again non-Markovian. We choose all hyperparameters as follows, for some large constant $c$ , and log factors $\iota$.

We now present our main result on the sample complexity of Nash V-learning.

For any $p\in(0,1]$, choose hyperparameters as in (6) for large absolute constant $c$ and $\iota=\log(SABT/p)$. Then, with probability at least $1-p$, if we run Nash V-learning (Algorithm 3 and 7) for $K$ episodes with

its induced policies $(\hat{\mu},\hat{\nu})$ (Algorithm 4) will be $\epsilon$-approximate Nash, i.e. $V^{\dagger,\hat{\nu}}_{1}(s_{1})-V^{\hat{\mu},\dagger}_{1}(s_{1})\leq\epsilon$.

Hardness for Learning the Best Response

In this section, we present a computational hardness result for computing the best response against an opponent with a fixed unknown policy. We further show that this implies the computational hardness result for achieving sublinear regret in Markov games when playing against adversarial opponents, which rules out a popular approach to design algorithms for finding Nash equilibria.

We first remark that if the opponent is restricted to only play Markov policies, then learning the best response is as easy as learning a optimal policy in the standard single-agent Markov decision process, where efficient algorithms are known to exist. Nevertheless, when the opponent can as well play any policy which may be non-Markovian, we show that finding the best response against those policies is computationally challenging.

We say an algorithm is a polynomial time algorithm for learning the best response if for any policy of the opponent $\nu$, and for any $\epsilon>0$, the algorithm finds the $\epsilon$-approximate best response of policy $\nu$ (Definition 1) with probability at least $1/2$, in time polynomial in $S,H,A,B,\epsilon^{-1}$.

We can show the following hardness result for finding the best response in polynomial time.

There exists a Markov game with deterministic transitions and rewards defined for any horizon $H\geq 1$ with $S=2$, $A=2$, and $B=2$, such that if there exists a polynomial time algorithm for learning the best response for this Markov game, then there exists a polynomial time algorithm for learning parity with noise (see problem description in Appendix E).

We remark that learning parity with noise is a notoriously difficult problem that has been used to design efficient cryptographic schemes. It is conjectured by the community to be hard.

There is no polynomial time algorithm for learning party with noise.

Theorem 6 with Conjecture 7 demonstrates the fundamental difficulty—if not strict impossibility—of designing a polynomial time for learning the best responses in Markov games. The intuitive reason for such computational hardness is that, while the underlying system has Markov transitions, the opponent can play policies that encode long-term correlations with non-Markovian nature, such as parity with noise, which makes it very challenging to find the best response. It is known that learning many other sequential models with long-term correlations (such as hidden Markov models or partially observable MDPs) is as hard as learning parity with noise .

Theorem 6 directly implies the difficulty for achieving sublinear regret in Markov games when playing against adversarial opponents in Markov games. Our construction of hard instances in the proof of Theorem 6 further allows the adversarial opponent to only play Markov policies in each episode. Since playing against adversarial opponent is a different problem with independent interest, we present the full result here.

Without loss of generality, we still consider the setting where the algorithm can only control the max-player, while the min-player is an adversarial opponent. In the beginning of every episode $k$, both players pick their own policies $\mu^{k}$ and $\nu^{k}$, and execute them throughout the episode. The adversarial opponent can possibly pick her policy $\nu^{k}$ adaptive to all the observations in the earlier episodes.

We say an algorithm for the learner is a polynomial time no-regret algorithm if there exists a $\delta>0$ such that for any adversarial opponent, and any fixed $K>0$, the algorithm outputs policies $\{\mu^{k}\}_{k=1}^{K}$ which satisfies the following, with probability at least $1/2$, in time polynomial in $S,H,A,B,K$.

Theorem 6 directly implies the following hardness result for achieving no-regret against adversarial opponents, a result that first appeared in .

There exists a Markov game with deterministic transitions and rewards defined for any horizon $H\geq 1$ with $S=2$, $A=2$, and $B=2$, such that if there exists a polynomial time no-regret algorithm for this Markov game, then there exists a polynomial time algorithm for learning parity with noise (see problem description in Appendix E). The claim remains to hold even if we restrict the adversarial opponents in the Markov game to be non-adaptive, and to only play Markov policies in each episode.

Similar to Theorem 6, Corollary 8 combined with Conjecture 7 demonstrates the fundamental difficulty of designing a polynomial time no-regret algorithm against adversarial opponents for Markov games.

Corollary 8 also rules out a natural approach for designing efficient algorithms for finding approximate Nash equilibrium through combining two no-regret algorithms. In fact, it is not hard to see that if the min-player also runs a non-regret algorithm, and obtain a regret bound symmetric to (7), then summing the two regret bounds shows the mixture policies $(\hat{\mu},\hat{\nu})$—which assigns uniform mixing weights to policies $\{\mu^{k}\}_{k=1}^{K}$ and $\{\nu^{k}\}_{k=1}^{K}$ respectively—is an approximate Nash equilibrium. Corollary 8 with Conjecture 7 claims that any algorithm designed using this approach is not a polynomial time algorithm.

Conclusion

In this paper, we designed first line of near-optimal self-play algorithms for finding an approximate Nash equilibrium in two-player Markov games. The sample complexity of our algorithms matches the information theoretical lower bound up to only a polynomial factor in the length of each episode. Apart from finding Nash equilibria, we also prove the fundamental hardness in computation for finding the best responses of fixed opponents, as well as achieving sublinear regret against adversarial opponents, in Markov games.

References

Appendix A Bellman Equations for Markov Games

In this section, we present the Bellman equations for different types of values in Markov games.

For any pair of Markov policy $(\mu,\nu)$, by definition of their values in (1) (2), we have the following Bellman equations:

for all $(s,a,b,h)\in\mathcal{S}\times\mathcal{A}\times\mathcal{B}\times[H]$, where $V^{\mu,\nu}_{H+1}(s)=0$ for all $s\in\mathcal{S}_{H+1}$.

Best responses.

For any Markov policy $\mu$ of the max-player, by definition, we have the following Bellman equations for values of its best response:

for all $(s,a,b,h)\in\mathcal{S}\times\mathcal{A}\times\mathcal{B}\times[H]$, where $V^{\mu,\dagger}_{H+1}(s)=0$ for all $s\in\mathcal{S}_{H+1}$.

Similarly, for any Markov policy $\nu$ of the min-player, we also have the following symmetric version of Bellman equations for values of its best response:

for all $(s,a,b,h)\in\mathcal{S}\times\mathcal{A}\times\mathcal{B}\times[H]$, where $V^{\dagger,\nu}_{H+1}(s)=0$ for all $s\in\mathcal{S}_{H+1}$.

Nash equilibria.

Finally, by definition of Nash equilibria in Markov games, we have the following Bellman optimality equations:

for all $(s,a,b,h)\in\mathcal{S}\times\mathcal{A}\times\mathcal{B}\times[H]$, where $V^{{\star}}_{H+1}(s)=0$ for all $s\in\mathcal{S}_{H+1}$.

Appendix B Properties of Coarse Correlated Equilibrium

Recall the definition for CCE in our main paper (4), we restate it here after rescaling. For any pair of matrix $P,Q\in^{n\times m}$, the subroutine $\textsc{CCE}(P,Q)$ returns a distribution $\pi\in\Delta_{n\times m}$ that satisfies:

We make three remarks on CCE. First, a CCE always exists since a Nash equilibrium for a general-sum game with payoff matrices $(P,Q)$ is also a CCE defined by $(P,Q)$, and a Nash equilibrium always exists. Second, a CCE can be efficiently computed, since above constraints (8) for CCE can be rewritten as $n+m$ linear constraints on $\pi\in\Delta_{n\times m}$, which can be efficiently resolved by standard linear programming algorithm. Third, a CCE in general-sum games needs not to be a Nash equilibrium. However, a CCE in zero-sum games is guaranteed to be a Nash equalibrium.

Let $\pi=\textsc{CCE}(Q,Q)$, and $(\mu,\nu)$ be the marginal distribution over both players’ actions induced by $\pi$. Then $(\mu,\nu)$ is a Nash equilibrium for payoff matrix $Q$.

Let $N^{\star}$ be the value of Nash equilibrium for $Q$. Since $\pi=\textsc{CCE}(Q,Q)$, by definition, we have:

Intuitively, a CCE procedure can be used in Nash Q-learning for finding an approximate Nash equilibrium, because the values of upper confidence and lower confidence—$\overline{Q}$ and $\underline{Q}$ will be eventually very close, so that the preconditions of Proposition 9 becomes approximately satisfied.

Appendix C Proof for Nash Q-learning

In this section, we present proofs for results in Section 3.

We will use the following notations several times later: suppose $(s,a,b)$ was taken at the in episodes $k^{1},k^{2},\ldots$ at the $h$-th step. Since the definition of $k^{i}$ depends on the tuple $(s,a,b)$ and $h$, we will show the dependence explicitly by writing $k_{h}^{i}(s,a,b)$ when necessary and omit it when there is no confusion. We also define $N_{h}^{k}(s,a,b)$ to be the number of times $(s,a,b)$ has been taken at the beginning of the $k$-th episode. Finally we denote $n_{h}^{k}=N_{h}^{k}\left(s_{h}^{k},a_{h}^{k},b_{h}^{k}\right)$.

The following lemma is a simple consequence of the update rule in Algorithm 1, which will be used several times later.

Let $t=N_{h}^{k}\left(s,a,b\right)$ and suppose $(s,a,b)$ was previously taken at episodes $k^{1},\ldots,k^{t}<k$ at the $h$-th step. The update rule in Algorithm 1 is equivalent to the following equations.

We begin an auxiliary lemma. Some of the analysis in this section is adapted from which studies Q-learning under the single agent MDP setting.

([14, Lemma 4.1]) The following properties hold for $\alpha_{t}^{i}$:

$\frac{1}{\sqrt{t}}\leq\sum_{i=1}^{t}\frac{\alpha^{i}_{t}}{\sqrt{i}}\leq\frac{2}{\sqrt{t}}$ for every $t\geq 1$.

$\max_{i\in[t]}\alpha^{i}_{t}\leq\frac{2H}{t}$ and $\sum_{i=1}^{t}(\alpha^{i}_{t})^{2}\leq\frac{2H}{t}$ for every $t\geq 1$.

$\sum_{t=i}^{\infty}\alpha^{i}_{t}=1+\frac{1}{H}$ for every $i\geq 1$.

Here we prove a stronger version of the first claim by induction: for any $(s,a,b,h,k)\in\mathcal{S}\times\mathcal{A}\times\mathcal{B}\times[H]\times[K]$,

Suppose the guarantee is true for $h+1$, then by the above concentration result,

where $\overline{Q}_{h}^{k}(s,a,b)\geq Q_{h}^{\star}(s,a,b)$ has just been proved. The other direction is proved similarly.

Now we continue with the proof of the second claim. Let $t=n_{h}^{k}$ and define $\delta_{h}^{k}:=\left(\overline{V}_{h}^{k}-\underline{V}_{h}^{k}\right)\left(s_{h}^{k}\right)$, then by definition

where $(i)$ is by taking the difference of equation (9) and equation (10) and

Taking the summation w.r.t. $k$, we begin with the first two terms,

where $(i)$ is by changing the order of summation and $(ii)$ is by Lemma 11.

Recursing this argument for $h\in[H]$ gives

with high probability. The proof is completed by putting everything together.

C.2 Certified policies

Algorithm 1 only learns the value of game but itself cannot give a near optimal policy for each player. In this section, we analyze the certified policy based on the above exploration process (Algorithm 2) and prove the sample complexity guarantee. To this end, we need to first define a new group of policies $\hat{\mu}_{h}^{k}$ to facilitate the proof , and $\hat{\nu}_{h}^{k}$ are defined similarly. Notice $\hat{\mu}_{h}^{k}$ is related to $\hat{\mu}$ defined in Algorithm 2 by $\hat{\mu}=\frac{1}{k}\sum_{i=1}^{k}{\hat{\mu}_{1}^{i}}$.

We also define $\hat{\mu}_{h+1}^{k}[s,a,b]$ for $h\leq H-1$, which is na intermediate algorithm only involved in the analysis. The above two policies are related by $\hat{\mu}_{h+1}^{k}\left[s,a,b\right]=\sum_{i=1}^{t}{\alpha_{t}^{i}}\hat{\mu}_{h+1}^{k}$ where $t=N_{h}^{k}\left(s,a,b\right)$. $\hat{\nu}_{h+1}^{k}[s,a,b]$ is defined similarly.

Since the policies defined in Algorithm 5 and Algorithm 6 are non-Markov, many notations for values of Markov policies are no longer valid here. To this end, we need to define the value and Q-value of general policies starting from step $h$, if the general policies starting from the $h$-th step do not depends the history before the $h$-th step. Notice the special case $h=1$ has already been covered in Section 2. For a pair of general policy $(\mu,\nu)$ which does not depend on the hostory before the $h$-th step, we can still use the same definitions (1) and (2) to define their value $V_{h}^{\mu,\nu}(s)$ and $Q_{h}^{\mu,\nu}(s,a,b)$ at step $h$. We can also define the best response $\nu^{\dagger}(\mu)$ of a general policy $\mu$ as the minimizing policy so that $V_{h}^{\mu,\dagger}(s)\equiv V_{h}^{\mu,\nu^{\dagger}(\mu)}(s)=\inf_{\nu}V_{h}^{\mu,\nu}(s)$ at step $h$. Similarly, we can define $Q_{h}^{\mu,\dagger}(s,a,b)\equiv Q_{h}^{\mu,\nu^{\dagger}(\mu)}(s,a,b)=\inf_{\nu}Q_{h}^{\mu,\nu}(s,a,b)$. As before, the best reponse of a general policy is not necessarily Markovian.

It should be clear from the definition of Algorithm 5 and Algorithm 6 that $\hat{\mu}_{h}^{k}$, $\hat{\nu}_{h}^{k}$, $\hat{\mu}_{h+1}^{k}[s,a,b]$ and $\hat{\nu}_{h+1}^{k}[s,a,b]$ does not depend on the history before step $h$, therefore related value and Q-value functions are well defined for the corresponding steps. Now we can show the policies defined above are indeed certified.

For any $p\in(0,1)$, with probability at least $1-p$, the following holds for any $(s,a,b,h,k)\in\mathcal{S}\times\mathcal{A}\times\mathcal{B}\times[H]\times[K]$,

because $\pi_{H}^{k}$ is CCE, and by definition $\hat{\nu}_{H}^{k}=\nu_{H}^{k}$.

Now suppose the claim is true for $h+1$, consider the $h$ case. Consider a fixed tuple $(s,a,b)$ and let $t=N_{h}^{k}\left(s,a,b\right)$. Suppose $(s,a,b)$ was previously taken at episodes $k^{1},\ldots,k^{t}<k$ at the $h$-th step. Let $\mathcal{F}_{i}$ be the $\sigma$-algebra generated by all the random variables in until the $k^{i}$-th episode. Then $\{\alpha_{t}^{i}[r_{h}(s,a,b)+V_{h+1}^{{\dagger},\hat{\nu}_{h+1}^{k^{i}}}(s_{h+1}^{k^{i}})+\beta_{i}]\}_{i=1}^{t}$ is a martingale differene sequence w.r.t. the filtration $\{\mathcal{F}_{i}\}_{i=1}^{t}$. By Azuma-Hoeffding and the definition of $b_{i}$,

with high probability. Combining this with the induction hypothesis,

where we have taken the maximum operator out of the summation in $(i)$,which does not increase the sum.

where $(i)$ is by the definition of CCE and $(ii)$ is the induction hypothesis. The other direction is proved by performing smilar arguments on $\underline{Q}_{h}^{k}(s,a,b)$, $Q_{h}^{\hat{\mu}_{h+1}^{k}[s,a,b],{\dagger}}(s,a,b)$, $\underline{V}_{h}^{k}(s)$ and $V_{h}^{\hat{\mu}_{h}^{k},{\dagger}}(s)$. ∎

Finally we give the theoretical guarantee of the policies defined above.

and Lemma 3 upper bounds this quantity by

By definition of the induced policy, with probability at least $1-p$, if we run Nash Q-learning (Algorithm 1) for $K$ episodes with

its induced policies $(\hat{\mu},\hat{\nu})$ (Algorithm 2) will be $\epsilon$-optimal in the sense $V^{\dagger,\hat{\nu}}_{1}(s_{1})-V^{\hat{\mu},\dagger}_{1}(s_{1})\leq\epsilon$. ∎

Appendix D Proof for Nash V-learning

We will use the following notations several times later: suppose the state $s$ was visited at episodes $k^{1},k^{2},\ldots$ at the $h$-th step. Since the definition of $k^{i}$ depends on the state $s$ , we will show the dependence explicitly by writing $k_{h}^{i}(s)$ when necessary and omit it when there is no confusion. We also define $N_{h}^{k}(s)$ to be the number of times the state $s$ has been visited at the beginning of the $k$-th episode. Finally we denote $n_{h}^{k}=N_{h}^{k}\left(s_{h}^{k}\right)$. Notice the definitions here are different from that in Appendix C.

The following lemma is a simple consequence of the update rule in Algorithm 3, which will be used several times later.

Let $t=N_{h}^{k}\left(s\right)$ and suppose $s$ was previously visited at episodes $k^{1},\ldots,k^{t}<k$ at the $h$-th step. The update rule in Algorithm 3 is equivalent to the following equations.

We first give Algorithm 7: the min-player counterpart of Algorithm 3. Almost everything is symmetric except the definition of loss function to keep it non-negative.

D.2 Learning values

As usual, we begin with learning the value $V^{\star}$ of the Markov game. We begin with an auxiliary lemma, which justifies our choice of confidence bound.

Let $t=N_{h}^{k}\left(s\right)$ and suppose state $s$ was previously taken at episodes $k^{1},\ldots,k^{t}<k$ at the $h$-th step. Choosing $\overline{\eta}_{t}=\sqrt{\frac{\log A}{At}}$ and $\underline{\eta}_{t}=\sqrt{\frac{\log B}{Bt}}$, with probability $1-p$, for any $(s,h,t)\in\mathcal{S}\times[H]\times[K]$, there exist a constant $c$ s.t.

We prove the first inequality. The proof for the second inequality is similar. We consider thoughout the proof a fixed $(s,h,t)\in\mathcal{S}\times[H]\times[K]$. Define $\mathcal{F}_{i}$ as the $\sigma$-algebra generated by all the random variables before the $k_{h}^{i}$-th episode. Then $\{r_{h}(s,a_{h}^{k^{i}},b_{h}^{k^{i}})+\overline{V}_{h+1}^{k^{i}}(s_{h+1}^{k^{i}})\}_{i=1}^{t}$ is a martingale sequence w.r.t. the filtration $\{\mathcal{F}_{i}\}_{i=1}^{t}$. By Azuma-Hoeffding,

where $R^{\star}_{t}$ is the weighted regret in the first $t$ times of visiting state $s$, with respect to the optimal policy in hindsight, in the following adversarial bandit problem. The loss function is defined by

with weight $w_{i}=\alpha^{i}_{t}$. We note the weighted regret can be rewrite as $R_{t}^{\star}=\sum_{i=1}^{t}{w_{i}\left<\mu_{h}^{\star}-\mu_{h}^{k_{i}},l_{i}\right>}$ where $\mu_{h}^{\star}$ is argmax for (13), and the loss function satisfies $l_{i}(a)\in[0,H]$

Therefore, Algorithm 3 is essentially performing follow the regularized leader (FTRL) algorithm with changing step size for each state to solve this adversarial bandit problem. The policy we are using is $\mu_{h}^{k^{i}}\left(s,a\right)$ and the optimistic biased estimator

A more detailed discussion on how to solve the weighted adversarial bandit problem is included in Appendix F. Note that $w_{i}=\alpha_{t}^{i}$ is monotonic inscreasing, i.e. $\max_{i\leq t}w_{i}=w_{t}$. By Lemma 17, we have

with probability $1-p/(SHK)$. Finally by a union bound over all $(s,h,t)\in\mathcal{S}\times[H]\times[K]$, we finish the proof. ∎

We now prove the following Lemma 15, which is an analoge of Lemma 3 in Nash Q-learning.

For any $p\in(0,1]$, choose hyperparameters as in (6) for large absolute constant $c$ and $\iota=\log(SABT/p)$. Then, with probability at least $1-p$, Algorithm 3 and 7 will jointly provide the following guarantees

$\overline{V}_{h}^{k}(s)\geq V^{\star}_{h}(s)\geq\underline{V}_{h}^{k}(s)$ for all $(s,h,k)\in\mathcal{S}\times[K]\times[H]$.

$(1/K)\cdot\sum_{k=1}^{K}(\overline{V}_{1}^{k}-\underline{V}_{1}^{k})(s_{1})\leq\mathcal{O}{\left(\sqrt{H^{6}S(A+B)\iota/K}\right)}$.

We proof the first claim by backward induction. The claim is true for $h=H+1$. Asumme for any s, $\overline{V}_{h+1}^{k}(s)\geq V_{h+1}^{\star}\left(s\right)$, $\underline{V}_{h+1}^{k}(s)\leq V_{h+1}^{\star}\left(s\right)$. For a fixed $(s,h)\in\mathcal{S}\times[H]$ and episode $k\in[K]$, let $t=N_{h}^{k}\left(s\right)$ and suppose $s$ was previously visited at episodes $k^{1},\ldots,k^{t}<k$ at the $h$-th step. By Bellman equation,

Comparing with the decomposition of $\overline{V}_{h}^{k}(s)$ in Equation (11) and use Lemma 14, we can see if $\overline{\beta}_{t}=c\sqrt{AH^{4}\iota/t}$, then $\overline{V}_{h}^{k}(s)\geq V_{h}^{\star}\left(s\right)$. Similar by taking $\underline{\beta}_{t}=c\sqrt{BH^{4}\iota/t}$, we also have $\underline{V}_{h}^{k}(s)\leq V_{h}^{\star}\left(s\right)$.

The second cliam is to bound $\delta_{h}^{k}:=\overline{V}_{h}^{k}(s_{h}^{k})-\underline{V}_{h}^{k}(s_{h}^{k})\geq 0$. Similar to what we have done in Nash Q-learning analysis, taking the difference of Equation (11) and Equation (12),

Taking the summation w.r.t. $k$, we begin with the first two terms,

where $(i)$ is by changing the order of summation and $(ii)$ is by Lemma 11. Putting them together,

Recursing this argument for $h\in[H]$ gives

Expanding this formula repeatedly and apply pigeonhole argument we have

D.3 Certified policies

As before, we construct a series of new policies $\hat{\mu}_{h}^{k}$ in Algorithm 8. Notice $\hat{\mu}_{h}^{k}$ is related to $\hat{\mu}$ defined in Algorithm 4 by $\hat{\mu}=\frac{1}{k}\sum_{i=1}^{k}{\hat{\mu}_{1}^{i}}$. Also we need to consider value and Q-value functions of general policies which does not depend on the hostory before the $h$-th step. See Appendix C.2 for details. Again, we can show the policies defined above are indeed certified.

For any $p\in(0,1)$, with probability at least $1-p$, the following holds for any $(s,a,b,h,k)\in\mathcal{S}\times\mathcal{A}\times\mathcal{B}\times[H]\times[K]$,

We prove one side by induction and the other side is similar. The claim is trivially satisfied for $h=H+1$. Suppose it is ture for $h+1$, consider a fixed state $s$. Let $t=N_{h}^{k}\left(s\right)$ and suppose $s$ was previously visited at episodes $k^{1},\ldots,k^{t}<k$ at the $h$-th step. Then using Lemma 13,

where $(i)$ is by using Lemma 14 and the definition of $\overline{\beta}_{i}$, and $(ii)$ is by induction hypothesis. ∎

Equipped with the above lemmas, we are now ready to prove Theorem 5.

and Lemma 15 upper bounds this quantity by

By definition of the induced policy, with probability at least $1-p$, if we run Nash V-learning (Algorithm 3) for $K$ episodes with

its induced policies $(\hat{\mu},\hat{\nu})$ (Algorithm 4) will be $\epsilon$-optimal in the sense $V^{\dagger,\hat{\nu}}_{1}(s_{1})-V^{\hat{\mu},\dagger}_{1}(s_{1})\leq\epsilon$. ∎

Appendix E Proofs of Hardness for Learning the Best Responses

In this section we give the proof of Theorem 6, and Corollary 8. Our proof is inspired by a computational hardness result for adversarial MDPs in [37, Section 4.2], which constructs a family of adversarial MDPs that are computationally as hard as an agnostic parity learning problem.

Section E.1, E.2, E.3 will be devoted to prove Theorem 6, while Corollary 8 is proved in Section E.4. Towards proving Theorem 6, we will:

(Section E.2) Define a series of problems where a solution in problem implies another.

(Section E.3) Based on the believed computational hardness of learning paries with noise (Conjecture 7), we conclude that finding the best response of non-Markov policies is computationally hard.

We now describe a Markov game inspired the adversarial MDP in [37, Section 4.2]. We define a Markov game in which we have $2H$ states, $\left\{i_{0},i_{1}\right\}_{i=2}^{H}$, $1_{0}$ (the initial state) and $\bot$ (the terminal state) In the states are denoted by $\left\{i_{a},i_{b}\right\}_{i=2}^{H}$ instead. Here we slightly change the notation to make it different from the notation of the actions. In each state the max-player has two actions $a_{0}$ and $a_{1}$, while the min-player has two actions $b_{0}$ and $b_{1}$. The transition kernel is deterministic and the next state for steps $h\leq H-1$ is defined in Table 2:

At the $H$-th step, i.e. states $H_{0}$ and $H_{1}$, the next state is always $\bot$ regardless of the action chosen by both players. The reward function is always $0$ except at the $H$-th step. The reward is determined by the action of the min-player, defined by

At the beginning of every episode $k$, both players pick their own policies $\mu_{k}$ and $\nu_{k}$, and execute them throughout the episode. The min-player can possibly pick her policy $\nu_{k}$ adaptive to all the observations in the earlier episodes. The only difference from the standard Markov game protocol is that the actions of the min-player except the last step will be revealed at the beginning of each episode, to match the setting in agnostic learning parities (Problem 2 below). Therefore we are actually considering a easier problem (for the max-player) and the lower bound naturally applies.

E.2 A series of computationally hard problems

We first introduce a series of problems and then show how the reduction works.

Problem 2

Let $x=\left(x_{1},\cdots,x_{n}\right)$ be a vector in $\left\{\text{0,}1\right\}^{n}$, $T\subseteq\left[n\right]$ and $0<\alpha<1/2$.The parity of $x$ on $T$ is the boolean function $\phi_{T}\left(x\right)=\oplus_{i\in T}x_{i}$. In words, $\phi_{T}\left(x\right)$ outputs $0$ if the number of ones in the subvector $(x_{i})_{i\in T}$ is even and $1$ otherwise. A uniform query oracle for this problem is a randomized algorithm that returns a random uniform vector $x$, as well as a noisy classification $f(x)$ which is equal to $\phi_{T}(x)$ w.p. $\alpha$ and $1-\phi_{T}(x)$ w.p. $1-\alpha$. All examples returned by the oracle are independent. The learning parity with noise problem consists in designing an algorithm with access to the oracle such that,

We remark that Problem 2.3 is the formal definition of learning parity with noise [20, Definition 2], which is conjectured to be computationally hard in the community (see also Conjecture 7).

Problem 2.3 reduces to Problem 2.2

Step 2: Construct estimators using $N$ additional data ${(x^{(j)},y^{(j)})}_{j=1}^{N}$,

Pick $\hat{i}=\mathop{\rm argmin}_{i}\hat{\rm err}_{i}$. When $N\geq\log(1/p)/\epsilon^{2}$, with probability at least $1-p/2$, we have

Problem 2.2 reduces to Problem 2.1:

Problem 2.1 reduces to Problem 1:

Consider the Markov game constructed above with $H-1=n$. The only missing piece we fill up here is the policy $\nu$ of the min-player, which is constructed as following. The min-player draws a sample $(x,y)$ from the uniform query oracle, then taking action $b_{0}$ at the step $h\leq H-1$ if $x_{h}=0$ and $b_{1}$ otherwise. For the $H$-th step, the min-player take action $b_{0}$ if $y=0$ and $b_{1}$ otherwise. Also notice the policy $\hat{\mu}$ of the max-player can be descibed by a set $\hat{T}\subseteq[H]$ where he takes action $a_{1}$ at step $h$ if $h$ and $a_{0}$ otherwise. As a result, the max-player receive non-zero result iff $\phi_{\hat{T}}(x)=y$.

by the $\epsilon$-approximation guarantee.

E.3 Putting them together

So far, we have proved that Solving Problem 1 implies solving Problem 2.3, where Problem 1 is the problem of learning $\epsilon$-approximate best response in Markov games (the problem we are interested in), and Problem 2.3 is precisely the problem of learning parity with noise . This concludes the proof.

E.4 Proofs of Hardness Against Adversarial Opponents

Corollary 8 is a direct consequence of Theorem 6, as we will show now.

We only need to prove a polynomial time no-regret algorithm also learns the best response in a Markov game where the min-player following non-Markov policy $\nu$. Then the no-regret guarantee implies,

where $\mu_{k}$ is the policy of the max-player in the $k$-th episode. If we choose $\hat{\mu}$ uniformly randomly from ${\left\{\mu_{k}\right\}}_{k=1}^{K}$, then

Choosing $\epsilon={\rm poly}(S,H,A,B)K^{-\delta}$, $K={\rm poly}(S,H,A,B,1/\epsilon)$ and the running time of the no-regret algorithm is still ${\rm poly}(S,H,A,B,1/\epsilon)$ to learn the $\epsilon$-approximate best response.

To see that the Corollary 8 remains to hold for policies that are Markovian in each episode and non-adaptive, we can take the hard instance in Theorem 6 and let $\nu^{k}$ denote the min-player’s policy in the $k$-th episode. Note that each $\nu^{k}$ is Markovian and non-adaptive on the observations in previous episodes. If there is a polynomial time no-regret algorithm against such ${\left\{\nu^{k}\right\}}$, then by the online-to-batch conversion similar as the above, the mixture of ${\left\{\mu_{k}\right\}}_{k=1}^{K}$ learns a best response against $\nu$ in polynomial time.

Appendix F Auxiliary Lemmas for Weighted Adversarial Bandit

In this section, we formulate the bandit problem we reduced to in the proof of Lemma 14. Although the machnisms are already well understood, we did not find a good reference of Follow the Regularized Leader (FTRL) algorithm with

For completeness, we give the detailed derivation here.

Define the filtration $\mathcal{F}_{t}$ by the $\sigma$-algebra generated by $\{a_{i},l_{i}\}_{i=1}^{t-1}$. Then the regret can be defined as

We can easily check the definitions here is just an abstract version of that in the proof of Lemma 14 with rescaling. To state the regret guarantee, we also define $\iota=\log(p/AK)$ for any $p\in(0,1]$. Now we can upper bound the regret by

Following Algorithm 9, with probability $1-3p$, for any $\theta^{*}\in\Delta^{A}$ and $t\leq K$ we have

The regret $R_{t}(\theta^{*})$ can be decomposed into three terms

and we bound $(A)$ in Lemma 19, $(B)$ in Lemma 20 and $(C)$ in Lemma 21.

Setting $\eta_{t}=\gamma_{t}=\sqrt{\frac{\log A}{At}}$, the conditions in Lemma 19 and Lemma 21 are satisfied. Putting them together and take union bound, we have with probability $1-3p$

The rest of this section is devoted to the proofs of the Lemmas used in the proofs of Lemma 17. We begin the following useful lemma adapted from Lemma 1 in , which is crucial in constructing high probability guarantees.

For any sequence of coefficients $c_{1},c_{2},\ldots,c_{t}$ s.t. $c_{i}\in[0,2\gamma_{i}]^{A}$ is $\mathcal{F}_{i}$-measurable, we have with probability $1-p/AK$,

Define $w=\max_{i\leq t}w_{i}$. By definition,

where $(i)$ is because $\frac{z}{1+z/2}\leq\log\left(1+z\right)$ for all $z\geq 0$.

where $(i)$ is because $z_{1}\log\left(1+z_{2}\right)\leq\log\left(1+z_{1}z_{2}\right)$ for any $0\leq z_{1}\geq 1$ and $z_{2}\geq-1$. Here we are using the condition $c_{i}\left(a\right)\leq 2\gamma_{i}$ to guarantee the condition is satisfied.

Equipped with the above bound, we can now prove the concentration result.

The claim is proved by taking the union bound. ∎

Using Lemma 18, we can bound the $(A)(B)(C)$ separately as below.

If $\eta_{i}\leq 2\gamma_{i}$ for all $i\leq t$, with probability $1-p$, for any $t\in[K]$ and $\theta^{*}\in\Delta^{A}$,

We use the standard analysis of FTRL with changing step size, see for example Exercise 28.13 in . Notice the essential step size is $\eta_{t}/w_{t}$,

where $(i)$ is by using Lemma 18 with $c_{i}(a)=\eta_{i}$. The any-time guarantee is justifed by taking union bound. ∎

With probability $1-p$, for any $t\in[K]$,

With probability $1-p$, for any $t\in[K]$ and any $\theta^{*}\in\Delta^{A}$, if $\gamma_{i}$ is non-increasing in $i$,

Then for all the $j\in[A]$, apply Lemma 18 with $c_{i}=\gamma_{t}e_{j}$. Sine now $c_{i}(a)\leq\gamma_{t}\leq\gamma_{i}$, the condition in Lemma 18 is satisfied. As a result,

Since any $\theta^{*}$ is a convex combination of $\left\{e_{j}\right\}_{j=1}^{A}$, by taking the union bound over $j\in[A]$, we have