V-Learning -- A Simple, Efficient, Decentralized Algorithm for Multiagent RL

Introduction

A wide range of modern artificial intelligence challenges can be cast as multi-agent reinforcement learning (MARL) problems, in which agents learn to make a sequence of decisions in the presence of other agents whose decisions will influence the outcome and can adapt to the strategies of the agents. Modern MARL systems have achieved significant success recently on a rich set of traditionally challenging tasks, including 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 . While single-agent RL has been the focus of recent intense theoretical study, MARL has been comparatively underexplored, which leaves several fundamental questions open even in the basic model of Markov games with finitely many states and actions.

One such unique challenge of MARL is the curse of multiagents—let $A_{i}$ be the number of actions for the $i^{\text{th}}$ player, then the number of possible joint actions (as well as the number of parameters to specify a Markov game) scales with $\prod_{i=1}^{m}A_{i}$, which grows exponentially with the number of agents $m$. This remains to be a bottleneck even for the best existing algorithms for learning Markov games. In fact, a majority of these algorithms adapt the classical single-agent algorithms, such as value iteration or Q-learning, into the multiagent setting , whose sample complexity scales at least linearly with respect to $\prod_{i=1}^{m}A_{i}$. This is prohibitively large in practice even for fairly small multiagent applications, say only ten agents are involved with ten actions available for each agent.

Another challenge of the MARL is to design decentralized algorithms. While a centralized algorithm requires the existence of a centralized controller which gathers all information and jointly optimizes the policies of all agents, a decentralized algorithm allows each agent to only observe her own actions and rewards while optimizing her own policy independently. Decentralized algorithms are often preferred over centralized algorithms in practice since (1) decentralized algorithms are typically cleaner, easier to implement; (2) decentralized algorithms are more versatile as the individual learners are indifferent to the interaction and the number of other agents; and (3) they are also faster due to less communication required. While several provable decentralized MARL algorithms have been developed [see, e.g., 57, 40, 13], they either have only asymptotic guarantees or work only under certain reachability assumptions (see Section 1.1). The existing provably efficient algorithms for general Markov games (without further assumptions) are exclusively centralized algorithms .

This motivates us to ask the following open question:

Can we design decentralized MARL algorithms that break the curse of multiagents?

This paper addresses both challenges mentioned above, and provide the first positive answer to this question in the basic setting of tabular episodic Markov games. We propose a new class of single-agent RL algorithms—V-learning, which converts any adversarial bandit algorithm with suitable regret guarantees into a RL algorithm. Similar to the classical Q-learning algorithm, V-learning also performs incremental updates to the values. Different from Q-learning, V-learning only maintains the V-value functions instead of the Q-value functions. We remark that the number of parameters of Q-value functions in MARL is $\mathcal{O}(S\prod_{i=1}^{m}A_{i})$, where $S$ is the number of states, while the number of parameters of V-value functions is only $\mathcal{O}(S)$. This key difference allows V-learning to be readily extended to the MARL setting by simply letting all agents run V-learning independently, which gives a fully decentralized algorithm.

In this section, we focus our attention on theoretical results for the tabular setting, where the numbers of states and actions are finite. We acknowledge that there has been much recent work in RL for continuous state spaces [see, e.g., 21, 23, 56, 24, 55, 25], but this setting is beyond our scope.

Markov Game (MG), also known as stochastic game , is a popular model in multi-agent RL . Early works have mainly focused on finding Nash equilibria of MGs under strong assumptions, such as known transition and reward , or certain reachability conditions (e.g., having access to simulators ) that alleviate the challenge in exploration.

A recent line of works provide non-asymptotic guarantees for learning two-player zero-sum tabular MGs without further structural assumptions. Bai and Jin and Xie et al. develop the first provably-efficient learning algorithms in MGs based on optimistic value iteration. Liu et al. improves upon these works and achieve best-known sample complexity for finding an $\epsilon$-Nash equilibrium—$\mathcal{O}(H^{3}SA_{1}A_{2}/\epsilon^{2})$ episodes.

For multiplayer general-sum tabular MGs, Liu et al. is the only existing work that provides non-asymptotic guarantees in the exploration setting. It proposes centralized model-based algorithms based on value-iteration, and shows that Nash equilibria (although computationally inefficient), CCE and CE can be all learned within $\mathcal{O}(H^{4}S^{2}\prod_{j=1}^{m}A_{j}/\epsilon^{2})$ episodes. Note this result suffers from the curse of multiagents.

V-learning—initially coupled with the FTRL algorithm as adversarial bandit subroutine—is firstly proposed in the conference version of this paper , for finding Nash equilibria in the two-player zero-sum setting. During the preparation of this draft, we note two very recent independent works , whose results partially overlap with the results of this paper in the multiplayer general-sum setting. In particular, Mao and Başar use V-learning with stablized online mirror descent as adversarial bandit subroutine, and learn $\epsilon$-CCE in $\mathcal{O}(H^{6}SA/\epsilon^{2})$ episodes, where $A=\max_{j\in[m]}A_{j}$. This is one $H$ factor larger than what is required in Theorem 6 of this paper. Song et al. considers similar V-learning style algorithms for learning both $\epsilon$-CCE and $\epsilon$-CE. For the latter objective, they require $\mathcal{O}(H^{6}SA^{2}/\epsilon^{2})$ episodes which is again one $H$ factor larger than what is required in Theorem 7 of this paper. Song et al. also considers Markov potential games, which is beyond the scope of this paper. We remark that both parallel works have not presented V-learning as a generic class of algorithms which can be coupled with any adversarial bandit algorithms with suitable regret guarantees in a black-box fashion.

Strategic games.

Strategic game is one of the most basic game forms studied in the game theory literature . It can be viewed as Markov games without state and transition. The fully decentralized algorithm that breaks the curse of multiagents is known in the setting of strategic games. By independently running no-regret (or no-swap-regret) algorithm for all agents, one can find Nash Equilibria (in the two-player zero-sum setting), correlated equilibria and coarse correlated equilibria (in the multiplayer general-sum setting) in a number of samples that only scales with $\max_{i\in[m]}A_{i}$ . However, such successes do not directly extend to the Markov games due to the additional temporal structures involving both states and transition. In particular, there is no computationally efficient no-regret algorithm for Markov games .

Extensive-form games.

There is another long line of research on MARL based on the model of extensive-form games (EFG) [see, e.g., 26, 14, 59, 7, 8, 9]. EFGs can be viewed as special cases of Markov games where any state at the $h^{\text{th}}$ step can be reached from only one state at the $(h-1)^{\text{th}}$ step (due to tree structure of the game). Therefore, results on learning EFGs do not directly imply results for learning MGs.

Decentralized MARL

There is a long line of empirical works on decentralized MARL [see, e.g., 31, 18, 49, 39, 46]. A majority of these works focus on the cooperative setting. They additionally attack the challenge where each agent can only observe a part of the underlying state, which is beyond the scope of this paper. For theoretical results, Zhang et al. consider the cooperative setting while Sayin et al. study the two-player zero-sum Markov games. Both develop decentralized MARL algorithms but provide only asymptotic guarantees. Daskalakis et al. analyze the convergence rate of independent policy gradient method in episodic two-player zero-sum MGs. Their result requires the additional reachability assumptions (concentrability) which alleviates the difficulty of exploration.

Single-agent RL

Preliminaries

A (random) policy $\pi_{i}$ of the $i^{\rm th}$ player is a set of $H$ maps \pi_{i}\mathrel{\mathop{:}}=\big{\{}\pi_{i,h}:\Omega\times(\mathcal{S}\times\mathcal{A})^{h-1}\times\mathcal{S}\rightarrow\mathcal{A}_{i}\big{\}}_{h\in[H]}, where $\pi_{i,h}$ maps a random sample $\omega$ from a probability space $\Omega$ and a history of length $h$—say $\tau_{h}:=(s_{1},\bm{a}_{1},\cdots,s_{h})$, to an action in $\mathcal{A}_{i}$. To execute policy $\pi_{i}$, we first draw a random sample $\omega$ at the beginning of the episode. Then, at each step $h$, the $i^{\text{th}}$ player simply takes action $\pi_{i,h}(\omega,\tau_{h})$. We note here $\omega$ is shared among all steps $h\in[H]$. $\omega$ encodes both the correlation among steps and the individual randomness of each step. We further say a policy $\pi_{i}$ is deterministic if $\pi_{i,h}(\omega,\tau_{h})=\pi_{i,h}(\tau_{h})$ which is independent of the choice of $\omega$.

An important subclass of policy is Markov policy, which can be defined as \pi_{i}\mathrel{\mathop{:}}=\big{\{}\pi_{i,h}:\Omega\times\mathcal{S}\rightarrow\mathcal{A}_{i}\big{\}}_{h\in[H]}. Instead of depending on the entire history, a Markov policy takes actions only based on the current state. Furthermore, the randomness in each step of Markov policy is independent. Therefore, when it is clear from the context, we write Markov policy as \pi_{i}\mathrel{\mathop{:}}=\big{\{}\pi_{i,h}:\mathcal{S}\rightarrow\Delta_{\mathcal{A}_{i}}\big{\}}_{h\in[H]}, where $\Delta_{\mathcal{A}_{i}}$ denotes the simplex over $\mathcal{A}_{i}$. We also use notation $\pi_{i,h}(a|s)$ to denote the probability of the $i^{\text{th}}$ agent taking action $a$ at state $s$ at step $h$.

A joint (potentially correlated) policy is a set of policies $\{\pi_{i}\}_{i=1}^{m}$, where the same random sample $\omega$ is shared among all agents, which we denote as $\pi=\pi_{1}\odot\pi_{2}\odot\ldots\odot\pi_{m}$. We also denote $\pi_{-i}=\pi_{1}\odot\ldots\pi_{i-1}\odot\pi_{i+1}\odot\ldots\odot\pi_{m}$ to be the joint policy excluding the $i^{\text{th}}$ player. A special case of joint policy is the product policy where the random sample has special form $\omega=(\omega_{1},\ldots,\omega_{m})$, and for any $i\in[m]$, $\pi_{i}$ only uses the randomness in $\omega_{i}$, which is independent of remaining $\{\omega_{j}\}_{j\neq i}$, which we denote as $\pi=\pi_{1}\times\pi_{2}\times\ldots\times\pi_{m}$.

We define the value function $V^{\pi}_{i,1}(s_{1})$ as the expected cumulative reward that the $i^{\text{th}}$ player will receive if the game starts at initial state $s_{1}$ at the $1^{\text{st}}$ step and all players follow joint policy $\pi$:

where the expectation is taken over the randomness in transition and the random sample $\omega$ in policy $\pi$.

Best response and strategy modification

For any strategy $\pi_{-i}$, the best response of the $i^{\text{th}}$ player is defined as a policy of the $i^{\text{th}}$ player which is independent of the randomness in $\pi_{-i}$, and achieves the highest value for herself conditioned on all other players deploying $\pi_{-i}$. In symbol, the best response is the maximizer of $\max_{\pi^{\prime}_{i}}V_{i,1}^{\pi^{\prime}_{i}\times\pi_{-i}}(s_{1})$ whose value we also denote as $V_{i,1}^{\dagger,\pi_{-i}}(s_{1})$ for simplicity. By its definition, we know the best response can always be achieved at deterministic policies.

A strategy modification $\phi_{i}$ for the $i^{\text{th}}$ player is a set of maps $\phi_{i}:=\{\phi_{i,h}:(\mathcal{S}\times\mathcal{A})^{h-1}\times\mathcal{S}\times\mathcal{A}_{i}\rightarrow\mathcal{A}_{i}\}$,Here, we only introduce the deterministic strategy modification for simplicity of notation, which is sufficient for discussion in the context of this paper. The random strategy modification can also be defined by introducing randomness in $\phi_{i}$ which is independent of randomness in $\pi_{i}$ and $\pi_{-i}$. It can be shown that the best strategy modification can always be deterministic. where $\phi_{i,h}$ can depend on the history $\tau_{h}$ and maps actions in $\mathcal{A}_{i}$ to different actions in $\mathcal{A}_{i}$. For any policy of the $i^{\text{th}}$ player $\pi_{i}$, the modified policy (denoted as $\phi_{i}\diamond\pi_{i}$) changes the action $\pi_{i,h}(\omega,\tau_{h})$ under random sample $\omega$ and history $\tau_{h}$ to $\phi_{i}(\tau_{h},\pi_{i,h}(\omega,\tau_{h}))$. For any joint policy $\pi$, we define the best strategy modification of the $i^{\text{th}}$ player as the maximizer of $\max_{\phi_{i}}V_{i,1}^{(\phi_{i}\diamond\pi_{i})\odot\pi_{-i}}(s_{1})$.

Different from the best response, which is completely independent of the randomness in $\pi_{-i}$, the best strategy modification changes the policy of the $i^{\text{th}}$ player while still utilizing the shared randomness among $\pi_{i}$ and $\pi_{-i}$. Therefore, the best strategy modification is more powerful than the best response: formally one can show that $\max_{\phi_{i}}V_{i,1}^{(\phi_{i}\diamond\pi_{i})\odot\pi_{-i}}(s_{1})\geq\max_{\pi^{\prime}_{i}}V_{i,1}^{\pi^{\prime}_{i}\times\pi_{-i}}(s_{1})$ for any policy $\pi$.

1 Learning objectives

A special case of Markov game is Markov Decision Process (MDP). One can show there always exists an optimal policy $\pi^{\star}=\mathop{\rm argmax}_{\pi}V^{\pi}_{1}(s_{1})$. Denote the value of the optimal policy as $V^{\star}$. The objective of learning MDPs is to find an $\epsilon$-optimal policy $\pi$, which satisfies $V^{\star}_{1}(s_{1})-V^{\pi}_{1}(s_{1})\leq\epsilon$.

For Markov games, there are three common learning objectives in the game theory literature—Nash Equilibrium, Correlated Equilibrium (CE) and Coarse Correlated Equilibrium (CCE).

First, a Nash equilibrium is defined as a product policy where no player can increase her value by changing only her own policy. Formally,

A product policy $\pi$ is a Nash equilibrium if $\max_{i\in[m]}{(V_{i,1}^{{\dagger},\pi_{-i}}-V_{i,1}^{\pi})}(s_{1})=0$. A product policy $\pi$ is an $\epsilon$-approximate Nash equilibrium if $\max_{i\in[m]}{(V_{i,1}^{{\dagger},\pi_{-i}}-V_{i,1}^{\pi})}(s_{1})\leq\epsilon$.

We remark that, except for the special case of two-player zero-sum Markov games where reward $r_{2,h}=-r_{1,h}$Technically, to ensure $r_{2,h}\in$, we choose $r_{2,h}=1-r_{1,h}$. We note that adding a constant to the reward function has no effect on the equilibria, which is our learning objective. for any $h\in[H]$, the Nash equilibrium in general has been proved PPAD-hard to compute . Therefore, we only present results for finding Nash equilibria in two-player zero-sum MGs in this paper.

Second, a coarse correlated equilibrium is defined as a joint (potentially correlated) policy where no player can increase her value by playing a different independent strategy. In symbol,

A joint policy $\pi$ is a CCE if $\max_{i\in[m]}{(V_{i,1}^{{\dagger},\pi_{-i}}-V_{i,1}^{\pi})}(s_{1})=0$. A joint policy $\pi$ is a $\epsilon$-approximate CCE if $\max_{i\in[m]}{(V_{i,1}^{{\dagger},\pi_{-i}}-V_{i,1}^{\pi})}(s_{1})\leq\epsilon$.

The only difference between Definition 1 and Definition 2 is that Nash equilibrium requires the policy $\pi$ to be a product policy while CCE does not. Thus, it is clear that CCE is a relaxed notion of Nash equilibrium, and a Nash equilibrium is always a CCE.

Finally, a correlated equilibrium is defined as a joint (potentially correlated) policy where no player can increase her value by using a strategy modification. In symbol,

A joint policy $\pi$ is a CE if $\max_{i\in[m]}\max_{\phi_{i}}{(V_{i,1}^{(\phi_{i}\diamond\pi_{i})\odot\pi_{-i}}-V_{i,1}^{\pi})}(s_{1})=0$. A joint policy $\pi$ is a $\epsilon$-approximate CE if $\max_{i\in[m]}\max_{\phi_{i}}{(V_{i,1}^{(\phi_{i}\diamond\pi_{i})\odot\pi_{-i}}-V_{i,1}^{\pi})}(s_{1})\leq\epsilon$.

In Markov games, we also have that a Nash equilibrium is a CE, and a CE is a CCE (see Proposition 9 in Appendix A for more details).

V-Learning Algorithm

In this section, we introduce V-learning algorithm as a new class of single-agent RL algorithms, which converts any adversarial bandit algorithm with suitable regret guarantees into a RL algorithm. We also present its theoretical guarantees for finding a nearly optimal policy in the single-agent setting.

To begin with, we describe the V-learning algorithm (Algorithm 1). It maintains a value $V_{h}(s)$, a counter $N_{h}(s)$, and a policy $\pi_{h}(\cdot|s)$ for each state $s$ and step $h$, and initializes them to be the max value, , and uniform distribution respectively. V-learning also instantiates $S\times H$ different adversarial bandit algorithms—one for each $(s,h)$ pair. At each step $h$ in each episode $k$, the algorithm performs three major steps:

Policy execution (Line 5-6): the algorithm takes action $a_{h}$ according to the maintained $\pi_{h}$, then observes the reward $r_{h}$ and the next state $s_{h+1}$, and increases the counter $N_{h}(s_{h})$ by $1$.

$V$-value update (Line 7-8): the algorithm performs incremental update to the value function:

Policy update (Line 9): the algorithm feeds the action $a_{h}$ and its “loss” $\frac{H-r_{h}+V_{h+1}(s_{h+1})}{H}$ to the $(s_{h},h)^{\text{th}}$ adversarial bandit algorithm, and receives the updated policy $\pi_{h}(\cdot|s_{h})$.

Throughout this paper, we will always use the following learning rate $\alpha_{t}$. We also define an auxiliary sequence $\{\alpha_{t}^{i}\}_{i=1}^{t}$ based on the learning rate, which will be frequently used across the paper.

We remark that our incremental update (2) bears significant similarity to Q-learning, and our choice of learning rate is precisely the same as the choice in Q-learning . However, a key difference is that the V-learning algorithm maintains V-value functions instead of Q-value functions. This is crucial when extending V-learning to the multiplayer setting where the number of parameters of Q-value functions becomes $\mathcal{O}(HS\prod_{i=1}^{m}A_{i})$ while the number of parameters of V-value functions is only $\mathcal{O}(HS)$. Since V-learning does not use action-value functions, it resorts to adversarial bandit algorithms to update its policy.

2 Output policy

We define the final output policy $\hat{\pi}$ of V-learning by how to execute this policy (see Algorithm 3). Let $V^{k},N^{k},\pi^{k}$ be the value, counter and policy maintained by V-learning algorithm at the beginning of episode $k$. The output policy maintains a scalar $k$, which is initially uniformly sampled from $[K]$. At each step $h$, after observing $s_{h}$, $\hat{\pi}$ plays a mixture of policy $\{\pi_{h}^{k^{i}}(\cdot|s_{h})\}_{i=1}^{t}$ with corresponding probability $\{\alpha_{t}^{i}\}_{i=1}^{t}$ defined in (3). Here $t=N_{h}^{k}(s_{h})$ is the number of times $s_{h}$ is visited at step $h$ at the beginning of episode $k$, and $k^{i}$ is short for $k^{i}_{h}(s_{h})$ which is the index of the episode when $s_{h}$ is visited at step $h$ for the $i^{\text{th}}$ time. After that, $\hat{\pi}$ sets $k$ to be the index $k^{i}_{h}(s_{h})$ whose policy is just played within the mixture, and continue the same process for the next step. This mixture form of output policy $\hat{\pi}$ is mainly due to the incremental updates of V-learning. One can show that, if omitting the optimistic bonus, $V^{K}_{1}(s_{1})$ computed in the V-learning algorithm is a stochastic estimate of the value of policy $\hat{\pi}$.

We remark that $\hat{\pi}$ is not a Markov policy, but a general random policy (see Definition in Section 2), which can be written as a set of maps $\{\pi_{h}:\Omega\times\mathcal{S}^{h}\rightarrow\mathcal{A}_{i}\}$. The choice of action at each step $h$ depends on a joint randomness $\omega\in\Omega$ which is shared among all steps, and the history of past states $(s_{1},\ldots,s_{h})$. In Section 6, we will further introduce a simple monotone technique that allows V-learning to output a Markov policy in both the single-agent and the two-player zero-sum setting.

3 Single-agent guarantees

We first state our requirement for the adversarial bandit algorithm used in V-learning, which is to have a high probability weighted external regret guarantee as follows. The weights $\{\alpha_{t}^{i}\}_{i=1}^{t}$ are defined in (3).

We further assume the existence of an upper bound $\Xi(B,t,\log(1/\delta))\geq\sum_{t^{\prime}=1}^{t}\xi(B,t^{\prime},\log(1/\delta))$where (i) $\xi(B,t,\log(1/\delta))$ is non-decreasing in $B$ for any $t,\delta$; (ii) $\Xi(B,t,\log(1/\delta))$ is concave in $t$ for any $B$, $\delta$.

Assumption 1 can be satisfied by modifying many existing algorithms with unweighted external regret to the weighted setting. In particular, we prove that the Follow-the-Regularized-Leader (FTRL) algorithm (Algorithm 5) satisfies the Assumption 1 with bounds $\xi(B,t,\log(1/\delta))\leq\mathcal{O}(\sqrt{HB\log(B/\delta)/t})$ and $\Xi(B,t,\log(1/\delta))\leq\mathcal{O}(\sqrt{HBt\log(B/\delta)})$. The $H$ factor comes into the bounds because our choice of weights $\{\alpha^{i}_{t}\}$ in (3) involves $H$. We refer readers to Appendix F for more details.

We are now ready to introduce the theoretical guarantees of V-learning for finding near-optimal policies in the single-agent setting.

In particular, when instantiating subroutine Adv_Bandit_Update by FTRL (Algorithm 5), we can choose $\beta_{t}=c\cdot\sqrt{H^{3}A\iota/t}$ for some absolute constant $c$, where $V_{1}^{\star}(s_{1})-V_{1}^{\hat{\pi}}(s_{1})\leq\mathcal{O}(\sqrt{H^{5}SA\iota/K})$.

While V-learning seems to be no better than classical value iteration or Q-learning in the single-agent setting, its true power starts to show up in the multiagent setting: Value iteration and Q-learning require highly nontrivial efforts to adapt them to the multiagent setting, and by design they suffer from the curse of multiagents . In the following sections, we will show that V-learning can be directly extended to the multiagent setting by simply letting all agents run V-learning independently. Furthermore, V-learning breaks the curse of multiagents.

Two-player Zero-sum Markov Games

In this section, we provide the sample efficiency guarantee for V-learning to find Nash equilibria in two-player zero-sum Markov games.

In the two-player zero-sum setting, we have two agents whose rewards satisfy $r_{1,h}=-r_{2,h}$ for any $h\in[H]$. Our algorithm is simply that both agents run V-learning (Algorithm 1) independently with learning rate $\alpha_{t}$ as specified in (3). Each player $j$ will uses her own set of bonus $\{\beta_{j,t}\}$ that depends on the number of her actions and will be specified later. To execute the output policy, both agents simply execute Algorithm 3 independently using their own intermediate policies computed by V-learning.

We have the following theorem for V-learning. For clean presentation, we denote $A=\max_{j\in}A_{j}$.

When instantiating Adv_Bandit_Update by FTRL (Algorithm 5), we can choose $\beta_{j,t}=c\cdot\sqrt{H^{3}A_{j}\iota/t}$ for some absolute constant $c$, which leads to $\max_{j\in}[V_{j,1}^{{\dagger},\hat{\pi}_{-j}}(s_{1})-V_{j,1}^{\hat{\pi}}(s_{1})]\leq\mathcal{O}(\sqrt{H^{5}SA\iota/K})$.

We remark that V-learning only performs $\mathcal{O}(1)$ operations and calls subroutine Adv_Bandit_Update once every time a new sample is observed. As long as the adversarial bandit algorithm used in V-learning is computationally efficient (which is the case for FTRL), V-learning itself is also computationally efficient.

Multiplayer General-sum Markov Games

In multiplayer general-sum games, finding Nash equilibria is computationally hard in general (which is technically PPAD-complete ). In this section, we focus on finding two commonly-used alternative notions of equilibria in the game theory—coarse correlated equilibria (CCE), and correlated equilibria (CE). Both are relaxed notions of Nash equilibira.

The algorithm for finding CCE is again running V-learning (Algorithm 1) independently for each agent $j$ with learning rate $\alpha_{t}$ (as specified in (3)) and bonus $\{\beta_{j,t}\}$ (to be specified later). The major difference from the case of finding Nash equilibria is that CCE and CE require the output policy to be joint correlated policy. We achieve this correlation by feeding the same random seed to all agents at the very beginning when they execute the output policy according to Algorithm 3. That is, while training can be done in the fully decentralized fashion, we require one round of communication at the beginning of the execution to broadcast the shared random seed. After that, each agent can simply execute her own output policy independently. During the execution, since the states visited are shared among all agents, shared random seed allows the same index $i$ to be sampled across all agents in the Step 4 of Algorithm 3 at every step. We denote this correlated joint output policy as $\hat{\pi}=\hat{\pi}_{1}\odot\ldots\odot\hat{\pi}_{m}$.

We remark that to specify a correlated policy in general, we need to specify the probability for taking all action combinations $(a_{1},\ldots,a_{m})$ for each $(s,h)$. This requires at least $\Omega(HS\prod_{j=1}^{m}A_{j})$ space, which grows exponentially with the number of agents $m$. The way V-learning specifies the joint policy only requires agents to store their own intermediate counters and policies computed during training. This only takes a total of $\mathcal{O}(HSK(\sum_{j=1}^{m}A_{j}))$ space, which scales only linearly with the number of agents. Our approach dramatically improve over the former approach in space complexity when the number of agents is large.

We now present the guarantees for V-learning to learn a CCE as follows. Let $A=\max_{j\in[m]}A_{j}$.

When instantiating Adv_Bandit_Update by FTRL (Algorithm 5), we can choose $\beta_{j,t}=c\cdot\sqrt{H^{3}A_{j}\iota/t}$ for some absolute constant $c$, which leads to $\max_{j\in[m]}[V_{j,1}^{{\dagger},\hat{\pi}_{-j}}(s_{1})-V_{j,1}^{\hat{\pi}}(s_{1})]\leq\mathcal{O}(\sqrt{H^{5}SA\iota/K})$.

2 Finding correlated equilibria

The algorithm for finding CE is almost the same as the algorithm for finding CCE except that we now require a different Adv_Bandit_Update subroutine, which has the following high probability weighted swap regret guarantee.

We assume the existence of an upper bound $\Xi_{\text{sw}}(B,t,\log(1/\delta))\geq\sum_{t^{\prime}=1}^{t}\xi_{\text{sw}}(B,t^{\prime},\log(1/\delta))$where (i) $\xi_{\text{sw}}(B,t,\log(1/\delta))$ is non-decreasing in $B$ for any $t,\delta$; (ii) $\Xi_{\text{sw}}(B,t,\log(1/\delta))$ is concave in $t$ for any $B$, $\delta$.

Here $\Psi$ denotes the set $\{\psi:\mathcal{B}\rightarrow\mathcal{B}\}$ which consists of all maps from actions in $\mathcal{B}$ to actions in $\mathcal{B}$. Meanwhile, for any $\theta\in\Delta_{\mathcal{B}}$, the term $\psi\diamond\theta\in\Delta_{\mathcal{B}}$ denotes the distribution over actions where $\psi\diamond\theta(b)=\sum_{b^{\prime}:\psi(b^{\prime})=b}\theta(b^{\prime})$. We note that bounded swap regret is a stronger requirement compared to bounded external regret as in (4), since by maximizing over a subset of functions in $\Psi$ which map all actions in $\mathcal{B}$ to one single action, we recover the external regret by (5).

Assumption 2 can be satisfied by modifying many existing algorithms with external regret to the swap regret setting. In particular, we prove that the Follow-the-Regularized-Leader for swap regret (FTRL_swap) algorithm (Algorithm 6) satisfies Assumption 2 with bounds $\xi_{\text{sw}}(B,t,\log(1/\delta))\leq\mathcal{O}(B\sqrt{H\log(B/\delta)/t})$ and $\Xi_{\text{sw}}(B,t,\log(1/\delta))\leq\mathcal{O}(B\sqrt{Ht\log(B/\delta)})$. Both bounds have one extra $\sqrt{B}$ factor comparing to the counterparts in external regret. We refer readers to Appendix G for more details.

We now present the guarantees for V-learning to learn a CCE as follows. Let $A=\max_{j\in[m]}A_{j}$.

When instantiating Adv_Bandit_Update by FTRL_swap (Algorithm 6), we can choose $\beta_{j,t}=c\cdot A_{j}\sqrt{H^{3}\iota/t}$ for some absolute constant $c$, which leads to $\max_{j\in[m]}\max_{\phi_{j}}[V_{j,1}^{\phi_{j}\diamond\hat{\pi}}(s_{1})-V_{j,1}^{\hat{\pi}}(s_{1})]\leq\mathcal{O}(A\sqrt{H^{5}S\iota/K})$.

Monotonic V-Learning

In the previous sections, we present the V-learning algorithm whose output policy (Algorithm 3) is a nested mixture of Markov polices. Storing such a output policy requires $\mathcal{O}(HSA_{j}K)$ space for the $j^{\text{th}}$ player. In Section 5, we argue this approach has a significant advantage over directly storing a general correlated policy when the number of agents is large. Nevertheless, this space complexity can be undesirable when the number of agents is small.

In this section, we introduce a simple monotonic techique to V-learning, which allows each agent to output a Markov policy when finding Nash equilibria in the two-player zero-sum setting. Storing a Markov policy only takes $\mathcal{O}(HSA_{j})$ space for the $j^{\text{th}}$ player. A similar result for the single-agent setting can be immediately obtained by setting the second player in the Markov game to be a dummy player with only a single action to choose from.

Monotonic V-learning is almost the same as V-learning with only the Line 8 in Algorithm 1 changed to

This step guarantees $V_{h}(s_{h})$ to monotonically decrease at each step. This is helpful because in two-player zero-sum Markov games, all Nash equilibria share a unique value which we denote as $V^{\star}$. By design, we can prove that the V-values maintained in V-learning are high probability upper bounds of $V^{\star}$ (Lemma 18). This monotonic update allows our V-value estimates to always get closer to $V^{\star}$ after each update, which improves the accuracy of our V-value estimates.

Markov output policy

For an arbitrary fixed $(s,h)\in\mathcal{S}\times[H]$, let $t_{1}$ be the last episode when the value ${V}_{1,h}(s)$ is updated (i.e., strictly decreases), and let $t_{2}$ be the last episode when the value ${V}_{2,h}(s)$ is updated. Then the output policy for this $(s,h)$ has the following form.

Theorem 8 asserts that V-learning can be modified to output Markov policies when finding Nash equilibria of two-player zero-sum Markov games. As a special case, the same technique and results directly apply to the single-agent setting.

Conclusion

In this paper, we develop the first decentralized algorithm that breaks the curse of multiagents for learning general Markov games. Behind this new result is a new class of single-agent RL algorithms—V-learning, which converts any adversarial bandit algorithm with suitable regret guarantees into a RL algorithm. A remarkable advantage of V-learning is its effortless extension to the multiagent setting while having much preferred theoretical guarantees over existing methods: by simply running V-learning independently for all agents, we find Nash equilibria (for two-player zero-sum games), CCE, and CE in a number of samples that scales with only $\max_{j\in[m]}A_{j}$, in contrast to existing algorithms whose number of samples scales with $\prod_{j\in[m]}A_{j}$.

References

Appendix A Notations and Basic Lemmas

In this subsection, we introduce some notations that will be frequently used in appendixes. Recall that we use $V^{k},N^{k},\pi^{k}$ to denote the value, counter and policy maintained by V-learning algorithm at the beginning of the episode $k$.

We also introduce a new policy $\hat{\pi}_{h}^{k}$ for a single agent (defined by its execution in Algorithm 4), which can be viewed as a part of the output policy in Algorithm 3. The definition of $\hat{\pi}_{h}^{k}$ is very similar to $\hat{\pi}$ except two differences: (1) $\hat{\pi}_{h}^{k}$ is a policy for step $h,\ldots,H$ while $\hat{\pi}$ is a policy for step $1,\ldots,H$; (2) in $\hat{\pi}$ the initial value of $k$ is sampled uniformly at random from $[K]$ at the very beginning while in $\hat{\pi}_{h}^{k}$ the initial value of $k$ is given.

We remark that $\hat{\pi}_{h}^{k}$ is a non-Markov policy that does not depends on history before to the $h^{\text{th}}$ step. In symbol, we can express this class of policy as $\pi_{j}\mathrel{\mathop{:}}=\{\pi_{j,h^{\prime}}:\Omega\times(\mathcal{S}\times\mathcal{A})^{h^{\prime}-h}\times\mathcal{S}\rightarrow\mathcal{A}_{j}\}_{h^{\prime}=h}^{H}$. We call this class of policy the policy starting from the $h^{\text{th}}$ step, and denote it as $\Pi_{h}$. Similar to Section 2, we can also define joint policy $\pi=\pi_{1}\odot\ldots\odot\pi_{m}$ and product policy $\pi=\pi_{1}\times\ldots\times\pi_{m}$ for policies in $\Pi_{h}$. We can also define value $V^{\pi}_{h}(s)$ for joint policy $\pi\in\Pi_{h}$ as

This allows us to define the corresponding best response of $\pi_{-i}$ as the maximizer of $\max_{\pi^{\prime}_{i}\in\Pi_{h}}V_{i,h}^{\pi^{\prime}_{i}\times\pi_{-i}}(s)$. We also denote this maximum value as $V_{i,h}^{\dagger,\pi_{-i}}(s)$. We define the strategy modification for policies starting from the $h^{\text{th}}$ step as $\phi_{i}:=\{\phi_{i,h^{\prime}}:(\mathcal{S}\times\mathcal{A})^{h^{\prime}-h}\times\mathcal{S}\times\mathcal{A}_{i}\rightarrow\mathcal{A}_{i}\}_{h^{\prime}=h}^{H}$, and denote the set of such strategy modification as $\Phi_{h}$.

for any value function $V$, $Q$ and any one-step Markov policy $\pi$.

A.2 Basic lemmas

We first present a proposition which clarify the relations among the three different kind of equilibria. In particular, we show that, similar to strategic games, we also have Nash $\subset$ CE $\subset$ CCE in Markov games.

In Markov games, any $\epsilon$-approximate Nash equilibrium is an $\epsilon$-approximate CE, and any $\epsilon$-approximate CE is an $\epsilon$-approximate CCE.

For Nash $\subset$ CE, let $\pi=\pi_{1}\times\pi_{2}\times\cdots\pi_{m}$ be an $\epsilon$-approximate Nash equilibrium, then

Step (a) is because that $\pi$ is a product policy, where the randomness of different agents are completely independent. In this case, maximizing over strategy modification $\phi_{i}$ is equivalent to maximizing over a new independent policy. Step (b) directly follows from $\pi$ being an $\epsilon$-approximate Nash equilibrium. By definition, this proves that $\pi$ is also an $\epsilon$-approximate CE.

For CE $\subset$ CCE, let $\pi=\pi_{1}\odot\pi_{2}\odot\cdots\pi_{m}$ be an $\epsilon$-approximate CE, then we have

Step (c) is because by definition of strategy modification $\phi_{i}:=\{\phi_{i,h}:(\mathcal{S}\times\mathcal{A})^{h-1}\times\mathcal{S}\times\mathcal{A}_{i}\rightarrow\mathcal{A}_{i}\}$, we can consider a subset of strategy modification $\phi^{\prime}_{i}:=\{\phi^{\prime}_{i,h}:(\mathcal{S}\times\mathcal{A})^{h-1}\times\mathcal{S}\rightarrow\mathcal{A}_{i}\}$ which modifies the policy ignoring whatever the action $\pi_{i}$ takes. It is not hard to see that maxmizing over the strategy modification in this subset is equivalent to maximizing over a new independent policy $\pi_{i}^{\prime}$. Therefore, maximizing over all strategy modification is greater or equal to maximizing over $\pi_{i}^{\prime}$. Finally, step (d) follows from $\pi$ being an $\epsilon$-approximate CE. By definition, this proves that $\pi$ is also an $\epsilon$-approximate CCE. ∎

Next, we present some basic lemmas that will be used in the proofs of different theorems. We start by introducing some useful properties of sequence $\{\alpha_{t}^{i}\}$ defined in (3).

([22, Lemma 4.1],[50, Lemma 2]) 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}}$ and $\frac{1}{t}\leq\sum_{i=1}^{t}\frac{\alpha^{i}_{t}}{i}\leq\frac{2}{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$.

The proof follows directly from the update rule in Line 7 Algorithm 1. Note that $\alpha_{t}^{0}$ is equal to zero for any $t>1$ and equal to one for $t=0$. ∎

Appendix B Proofs for Computing CCE in General-sum MGs

In this section, we give complete proof of Theorem 6. To avoid repeatedly state the condition of Theorem 6 in each lemma, we will use

Condition of the adversarial bandit sub-procudure (Assumption 1) and

Set the bonus $\{\beta_{j,t}\}_{t=1}^{K}$ of the $j^{\text{th}}$ player so that $\sum_{i=1}^{t}\alpha_{t}^{i}\beta_{j,i}=\Theta(H\xi(A_{j},t,\iota)+\sqrt{H^{3}\iota/t})$ for any $t\in[K]$.

The following Lemma is a direct consequence of Assumption 1, which will play an important role in our later analysis.

Under Assumption 1, the following event is true with probability at least $1-\delta$: for any $(s,h,k)\in\mathcal{S}\times[H]\times[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, then for all $j\in[m]$

By Assumption 1 and the adversarial bandit update step in Algorithm 1, we have that with probability at least $1-\delta$, for any $(s,h,k)\in\mathcal{S}\times[H]\times[K]$,

which implies the desired result by simple algebraic transformation. ∎

Then we show $V$ is actually an optimistic estimation of the value function of player $j$’th best response to the output policy.

For any $\delta\in(0,1]$, with probability at least $1-\delta$, for any $(s,h,k,j)\in\mathcal{S}\times[H]\times[K]\times[m]$, $V_{j,h}^{k}(s)\geq V_{j,h}^{{\dagger},\hat{\pi}_{-j,h}^{k}}(s)$.

where $(i)$ is by martingale concentration and Lemma 2, $(ii)$ is by Lemma 12, $(iii)$ is by the definition of ${\beta}_{j,i}$, and $(iv)$ is by induction hypothesis.

Finally, we remark that $(v)$ is not directly from Bellman equation since $\hat{\pi}_{-j,h}^{k}$ is non-Markov policy, and the best reponse of a non-Markov policy is not necessary a Markov policy. We prove $(v)$ as follows. Recalls definitions for policies in $\Pi_{h}$ as in Appendix A, by the definition, we have

where $V_{j,h+1}^{\pi}(s,\bm{a},s^{\prime})$ for policy $\pi\in\Pi_{h}$ is defined as:

Step (a) uses the relation between $\hat{\pi}_{-j,h}^{k}$ and $\{\hat{\pi}_{-j,h+1}^{k^{i}}\}_{i}$. Step (b) pushes $\max$ inside summation and expectation. Step (c) is because the Markov nature of Markov game and that $\{\hat{\pi}_{-j,h+1}^{k^{i}}\}_{i}$ are policies that does not depend on history at step $h$, we know the maximization over $\mu_{(h+1):H}$ is achieved at policies in $\Pi_{h+1}$. This finishes the proof. ∎

Equipped with the lower estimations, we are ready to lower bound $V_{j,h}^{\hat{\pi}_{h}^{k}}$.

For any $\delta\in(0,1]$, with probability at least $1-\delta$, the following holds for any $(s,h,k,j)\in\mathcal{S}\times[H]\times[K]\times[m]$ and any player $j$, $\underline{V}_{j,h}^{k}(s)\leq V_{j,h}^{\hat{\pi}^{k}_{h}}(s)$.

where $(i)$ is by martingale concentration, $(ii)$ is by the definition of ${\beta}_{j,i}$, and $(iii)$ is by induction hypothesis. ∎

To prove Theorem 6, it remains to bound the gap $\sum_{k=1}^{K}\max_{j}(V_{1,j}^{k}-\underline{V}_{1,j}^{k})(s_{1})$.

Consider player $j$, we define $\delta_{j,h}^{k}:=V_{j,h}^{k}(s_{h}^{k})-\underline{V}_{j,h}^{k}(s_{h}^{k})\geq 0$. The non-negativity here is a simple consequence of the update rule and induction. We want to bound $\delta_{h}^{k}:=\max_{j}\delta_{j,h}^{k}$. Let $n_{h}^{k}=N_{h}^{k}\left(s_{h}^{k}\right)$ and suppose $s_{h}^{k}$ was previously visited at episodes $k^{1},\ldots,k^{n_{h}^{k}}<k$ at the $h$-th step. Now by the update rule of $V_{j,h}^{k}(s_{h}^{k})$ and $\underline{V}_{j,h}^{k}(s_{h}^{k})$,

where in the last step we have used $\sum_{i=1}^{t}\alpha_{t}^{i}\beta_{j,i}=\Theta(H\xi(A_{j},t,\iota)+\sqrt{H^{3}\iota/t})$.

Now by taking maximum w.r.t. $j$ on both sides and notice $\xi(B,t,\iota)$ is non-decreasing in $B$, we have

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

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

where in the last step we have used concavity.

Finally take the sum w.r.t. $h\in[H]$ we have

Appendix C Proofs for Computing CE in General-sum MGs

In this section, we give complete proof of Theorem 7. To avoid repeatedly state the condition of Theorem 7 in each lemma, we will use

Condition of the adversarial bandit sub-procudure (Assumption 2) and

Set the bonus $\{\beta_{j,t}\}_{t=1}^{K}$ of the $j^{\text{th}}$ player so that $\sum_{i=1}^{t}\alpha_{t}^{i}\beta_{j,i}=\Theta(H\xi_{\text{sw}}(A_{j},t,\iota)+\sqrt{H^{3}\iota/t})$ for any $t\in[K]$.

We begin with a swap regret version of Lemma 12.

The following event is true with probability at least $1-\delta$: for any $(s,h,k)\in\mathcal{S}\times[H]\times[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, then for all $j\in[m]$

By Assumption 2 and the adversarial bandit update step in Algorithm 1, we have that with probability at least $1-\delta$, for any $(s,h,k)\in\mathcal{S}\times[H]\times[K]$,

We begin with proving $V$ is actually an optimistic estimation of the value function under best response.

For any $\delta\in(0,1)$, with probability at least $1-\delta$, the following holds for any $(s,h,k,j)\in\mathcal{S}\times[H]\times[K]\times[m]$, $V_{j,h}^{k}(s)\geq\max_{\phi_{j}}V^{(\phi_{j}\diamond\hat{\pi}^{k}_{j,h})\odot\hat{\pi}^{k}_{-j,h}}_{j,h}(s)$.

where $(i)$ is by martingale concentration and Lemma 2, $(ii)$ is by Lemma 15, $(iii)$ is by the definition of ${\beta}_{j,i}$, and $(iv)$ is by induction hypothesis. Finally, $(v)$ follows from a similar reasoning as in the proof of Lemma 13, which we omit here. ∎

For any $\delta\in(0,1)$, with probability at least $1-\delta$, the following holds for any $(s,h,k,j)\in\mathcal{S}\times[H]\times[K]\times[m]$, $\underline{V}_{j,h}^{k}(s)\leq V_{h}^{\hat{\pi}_{h}^{k}}(s)$.

where $(i)$ is by martingale concentration, $(ii)$ is by the definition of ${\beta}_{j,i}$, and $(iii)$ is by induction hypothesis. ∎

To prove Theorem 7, it remains to bound the gap $\sum_{k=1}^{K}\max_{j}(V_{1,j}^{k}-\underline{V}_{1,j}^{k})(s_{1})$.

Consider player $j$, we define $\delta_{j,h}^{k}:=V_{j,h}^{k}(s_{h}^{k})-\underline{V}_{j,h}^{k}(s_{h}^{k})\geq 0$. The non-negativity here is a simple consequence of the update rule and induction. We want to bound $\delta_{h}^{k}:=\max_{j}\delta_{j,h}^{k}$. Let $n_{h}^{k}=N_{h}^{k}\left(s_{h}^{k}\right)$ and suppose $s_{h}^{k}$ was previously visited at episodes $k^{1},\ldots,k^{n_{h}^{k}}<k$ at the $h$-th step. Now by the update rule of $V_{j,h}^{k}(s_{h}^{k})$ and $\underline{V}_{j,h}^{k}(s_{h}^{k})$,

where in the last step we have used $\sum_{i=1}^{t}\alpha_{t}^{i}\beta_{j,i}=\Theta(H\xi_{\text{sw}}(A_{j},t,\iota)+\sqrt{H^{3}\iota/t})$.

Now by taking maximum w.r.t. $j$ on both sides and notice $\xi_{\text{sw}}(B,t,\iota)$ is non-decreasing in $B$, we have

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

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

where in the last step we have used concavity.

Finally take the sum w.r.t. $h\in[H]$ we have

Appendix D Proofs for MDPs and Two-player Zero-sum MGs

In this section, we prove the main theorems for V-learning in the setting of single-agent (MDPs) and two-player zero-sum MGs.

To begin with, we notice an equivalent definition of two-player zero-sum MGs is that the reward function satisfies $r_{1,h}=1-r_{2,h}$ for all $h\in[H]$. The reason we use this definition instead of the common version $r_{1,h}=-r_{2,h}$ is we want to make it consistent with our assumption that the reward function takes value in $$for any player. Although this definition does not satisfy the zero-sum condition, its Nash equilibria are the same as those of the zero-sum version because adding a constant to the reward function of player$2$ per step will not change the dynamics of the game.

In order to show $\hat{\pi}=\hat{\pi}_{1}\times\hat{\pi}_{2}$ is an approximate Nash policy, it suffices to control

Since $r_{1,h}=1-r_{2,h}$ for all $h\in[H]$, with probability at least $1-\delta$

where the last inequality follows from Theorem 6. The reason we can use Theorem 6 here is the precondition of Theorem 5 is a special case of the precondition of Theorem 6. ∎

Since MDPs is a subclass of two-player zero-sum MGs by simply choosing the action set of the second player to be a singleton, it suffices to only prove Theorem 5, from which the single-agent guarantee, Theorem 4 trivially follows. ∎

Appendix E Proofs for Monotonic V-learning

In this section, we prove Theorem 8. The algorithm is V-learning with monotonic update, and the setting we consider is two-player zero-sum Markov games. As before, we assume $r_{1,h}(s,a)=1-r_{2,h}(s,a)$ for all $s,a,h$. The reason for assuming $r_{1,h}(s,a)=1-r_{2,h}(s,a)$ instead of $r_{1,h}(s,a)=-r_{2,h}(s,a)$ can be found in Appendix D.

For two player zero-sum MGs, we can define its minimax value function (Nash value function) by the following Bellman equations

With probability at least $1-\delta$, for any $(s,h,k,j)\in\mathcal{S}\times[H]\times[K]\times$,

where $V^{\star}_{j,h}$ is the minimax (Nash) value function defined above.

By the monotonicity of ${V}$ and Lemma 18

where the first equality follows from the definition of two-player zero-sum game, i.e., $r_{1,h}=1-r_{2,h}$.

Let $n_{h}^{k}=N_{h}^{k}\left(s_{h}^{k}\right)$ and suppose $s_{h}^{k}$ was previously visited at episodes $k^{1},\ldots,k^{n_{h}^{k}}<k$ at the $h$-th step. By Lemma 11 and the fact that $r_{1,h}=1-r_{2,h}$ for all $h$, we have

where in the last step we used $\sum_{i=1}^{t}\alpha_{t}^{i}\beta_{j,i}=\Theta(H\xi(A_{j},t,\iota)+\sqrt{H^{3}\iota/t})$.

The remaining steps follow exactly the same as the proof of Theorem 6. As a result, we obtain

Appendix F Adversarial Bandit with Weighted External Regret

In this section, we present a Follow-the-Regularized-Leader (FTRL) style algorithm that achieves low weighted (external) regret for the adversarial bandit problem. Although FTRL is a classial algorithm in the adversarial bandit literature, we did not find a good reference of FTRL with changing step size, weighted regret and high probability bound. For completeness of this work, we provide detailed derivations here.

By choosing hyperparameter $w_{t}=\alpha_{t}\left(\prod_{i=2}^{t}{\left(1-\alpha_{i}\right)}\right)^{-1}$ and $\eta_{t}=\gamma_{t}=\sqrt{\frac{H\log B}{Bt}}$, FTRL (Algorithm 5) satisfies Assumption 1 with

To prove Corollary 19, we show a more general weighted regret guarantee which works for any set of weights $\{w_{i}\}_{i=1}^{\infty}$ in addition to $\{\alpha_{t}^{i}\}_{i=1}^{t}$. In particular, a general weighted regret is defined as

For any $t\leq K$, following Algorithm 5, if $\eta_{i}\leq 2\gamma_{i}$ and $\eta_{i}$ is non-increasing for all $i\leq t$, let $\iota=\log(B/\delta)$ , then with probability $1-3\delta$, we have

We postpone the proof of theorem 20 to the end of this section. We first show how to obtain Corollary 19 from Theorem 20.

The weights $\{w_{t}\}_{t=1}^{K}$ we choose satisfy a nice property: for any $t$ we have

We prove this for $i\leq j$ and the other case is similar. By definition,

We can easily verify that the RHS are the same.

By choosing $\eta_{t}=\gamma_{t}=\sqrt{\frac{H\log B}{Bt}}$ and using Lemma 10, we can further upper bound the regret by

To further simplify the above upper bound, consider two cases:

Finally, we pick $\xi(B,t,\log(1/\delta)):=10\sqrt{HB\iota/t}$, which is non-decreasing in $B$. Since $\sum_{t^{\prime}=1}^{t}\xi(B,t,\log(1/\delta))\leq 20\sqrt{HBt\iota}$, we choose $\Xi(B,t,\log(1/\delta))=20\sqrt{HBt\iota}$, which is concave in $t$. ∎

To prove Theorem 20, we first note that the weighted regret (14) can be decomposed into three terms

The rest of this section is devoted to bounding three terms above. We begin with the following useful lemma adapted from Lemma 1 in , which is crucial in achieving high probability guarantees.

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

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

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

where $(i)$ follows from $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$. Note that here we are using the condition $c_{i}\left(b\right)\leq 2\gamma_{i}$ for all $b\in[B]$.