PaperlayerView exact revision on arXiv

Source-linked AI summary

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

Chi Jin, Qinghua Liu, Yuanhao Wang, Tiancheng Yu

arXiv:2110.14555v1cs.LGcs.AIcs.GTcs.MAstat.ML

TL;DR

MARL faces an exponential joint-action-space bottleneck, and the paper develops decentralized V-learning to address it in episodic Markov games. By having agents run V-learning independently, the method learns several equilibrium notions with sample complexity governed by the largest individual action space rather than the joint action space, within a finite tabular scope.

  • Problem

    MARL algorithms face a curse of multiagents because joint actions scale exponentially with the number of agents, creating a bottleneck even in finite-state, finite-action settings.

  • Method

    V-learning converts adversarial bandit algorithms with suitable regret guarantees into single-agent value-learning algorithms that maintain V-values, then lets agents run them independently.

  • Results

    V-learning provably learns Nash equilibria for two-player zero-sum games and CE or CCE for multiplayer general-sum games with sample complexity scaling with A = max_i A_i rather than the joint action space.

  • Takeaways & Limitations

    The approach breaks the curse of multiagents for these equilibrium objectives while retaining a fully decentralized training procedure.

  • Takeaways & Limitations

    The theoretical results are for tabular finite-state, finite-action Markov games, and the output-policy space complexity can be undesirable when the number of agents is small.

Abstract

from arXiv · show

A major challenge of multiagent reinforcement learning (MARL) is the curse of multiagents, where the size of the joint action space scales exponentially with the number of agents. This remains to be a bottleneck for designing efficient MARL algorithms even in a basic scenario with finitely many states and actions. This paper resolves this challenge for the model of episodic Markov games. We design a new class of fully decentralized algorithms -- V-learning, which provably learns 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$, where $A_i$ is the number of actions for the $i^{\rm th}$ player. This is in sharp contrast to the size of the joint action space which is $\prod_{i=1}^m A_i$. V-learning (in its basic form) is a new class of single-agent RL algorithms that convert any adversarial bandit algorithm with suitable regret guarantees into a RL algorithm. Similar to the classical Q-learning algorithm, it performs incremental updates to the value functions. Different from Q-learning, it only maintains the estimates of V-values instead of Q-values. This key difference allows V-learning to achieve the claimed guarantees in the MARL setting by simply letting all agents run V-learning independently.

1 Introduction

The paper targets MARL’s exponential joint-action bottleneck and asks whether decentralized algorithms can avoid it. V-learning answers positively in tabular episodic Markov games, achieving equilibrium-learning guarantees that depend on the largest individual action space rather than the joint action space.

  • Motivation: The curse of multiagents arises because joint actions scale as the product of agents’ action counts, making many existing algorithms prohibitively expensive even for modest systems.Existing approaches adapted from value iteration or Q-learning have sample complexity at least linear in the joint-action-space size.
  • Contribution: V-learning converts adversarial bandit algorithms with suitable regret guarantees into incremental value-learning algorithms that maintain V-values instead of Q-values.This reduces the relevant value-function parameterization from O(S product_i A_i) for Q-values to O(S) for V-values.
  • Contribution: V-learning finds Nash equilibria in two-player zero-sum games, and CCEs and CEs in multiplayer general-sum games, with sample complexity scaling only with A = max_i A_i rather than the number of agents.The bounds are approximately O~(H^5SA/ε^2) for Nash and CCE, and O~(H^5SA^2/ε^2) for CE.
  • Scope and related work: The paper provides the first positive answer in tabular episodic Markov games while focusing on finite-state, finite-action settings rather than continuous state spaces.Prior work includes centralized or asymptotic approaches, while continuous-state reinforcement learning is explicitly outside scope.

2 Preliminaries

The paper studies tabular episodic Markov games in which agents act simultaneously, receive individual rewards, and transition through finite states. It distinguishes Nash, coarse correlated, and correlated equilibria by the allowed policy structure and deviation rule.

  • Markov games: A tabular episodic Markov game has finite states and action spaces, horizon H, transition matrices, and possibly arbitrary relationships among players’ rewards.The model therefore includes both cooperative and competitive interactions.
  • Markov games: Each episode begins from a fixed initial state; agents observe the current state, act simultaneously, receive their own rewards, and induce the next state through the transition kernel.The results also extend to an initial state sampled from a fixed initial distribution, and V-learning does not require observing other players’ actions.
  • Equilibrium concepts: Nash equilibrium uses a product policy and forbids profitable unilateral policy changes, whereas CCE permits correlation and forbids profitable independent strategy changes.A Nash equilibrium is consequently also a CCE.
  • Equilibrium concepts: Except for two-player zero-sum Markov games, computing multiplayer general-sum Nash equilibria is PPAD-hard, motivating the paper’s separate treatment of Nash, CE, and CCE objectives.The two-player zero-sum case assumes the second player’s reward is the negative of the first player’s reward.
  • Equilibrium concepts: Correlated equilibrium permits a joint correlated policy but requires that no player benefit from a history-dependent strategy modification.In Markov games, the equilibrium notions are nested: Nash implies CE, and CE implies CCE.

3 V-Learning Algorithm

V-learning converts adversarial bandit algorithms into single-agent RL through incremental V-value updates, avoiding the joint-action-sized Q-value representation. Its output-policy construction and guarantees support efficient learning while preserving this compact representation.

  • 3 V-Learning Algorithm: V-learning converts adversarial bandit algorithms with suitable regret guarantees into an RL algorithm for learning near-optimal policies.It maintains V-values, counters, and policies while using one adversarial bandit instance per state-step pair.
  • 3.1 Training algorithm: Each episode executes the maintained policy, updates the V-value incrementally with a learning rate and exploration bonus, then updates the corresponding adversarial bandit policy.The observed action and loss H−r_h+V_{h+1}(s_{h+1}) are fed to the state-step bandit algorithm.
  • 3.1 Training algorithm: Unlike Q-learning, V-learning maintains V-value functions, reducing parameters from O(HS∏ᵢAᵢ) to O(HS) in multiplayer settings.Because it does not use action-value functions, policy updates are delegated to adversarial bandit algorithms.
  • 3.2 Output policy: The output policy samples an episode index and mixes intermediate policies according to state visitation histories, producing a general random policy rather than a Markov policy.Without the optimistic bonus, the initial V-value is a stochastic estimate of the output policy’s value.
  • 3.3 Single-agent guarantees: The framework requires a weighted external-regret adversarial bandit subroutine, and FTRL satisfies the needed assumption with an explicit regret bound.The bound includes an H factor arising from the chosen learning-rate weights.
  • 3.3 Single-agent guarantees: V-learning obtains an ϵ-optimal single-agent policy in ˜O(H^5SA/ϵ^2) episodes, although this is H^2 above the information-theoretic lower bound.The paper attributes one extra H factor to incremental updates and the Q-learning-style learning rate, while another may be improved with refined regret bounds.

4 Two-player Zero-sum Markov Games

In two-player zero-sum Markov games, both agents independently run V-learning with their own bonuses and policies. The resulting fully decentralized method finds approximate Nash equilibria with sample complexity linear in the maximum action count.

  • 4.1 Finding Nash equilibria: Both zero-sum agents run V-learning independently, using individual action-dependent bonuses and independently computed intermediate policies.The output policy is executed by having both agents independently apply the output-policy procedure.
  • 4.1 Finding Nash equilibria: The theorem’s guarantee applies under a suitable adversarial-bandit update subroutine and specified learning-rate and bonus choices.With probability at least 1−δ, the resulting product policy satisfies the theorem’s equilibrium condition after K episodes.
  • 4 Two-player Zero-sum Markov Games: V-learning finds an ϵ-approximate Nash equilibrium in ˜O(H^5SA/ϵ^2) episodes, depending linearly on A=max_j A_j rather than the product of action counts.The paper contrasts this with value-iteration and Q-learning methods requiring at least Ω(H^3SA_1A_2/ϵ^2) episodes.
  • 4.1 Finding Nash equilibria: The algorithm is fully decentralized and, according to the paper, is the only method then known to achieve sample complexity linear in A for this Nash-equilibrium problem.Its implementation performs only constant-time operations and calls the adversarial-bandit subroutine once per new sample.

5 Multiplayer General-sum Markov Games

In multiplayer general-sum Markov games, V-learning targets CCE and CE while avoiding joint-action and centralized-policy representations. Its guarantees use the maximum individual action count, with CE requiring an extra action factor relative to CCE.

  • 5.1 Finding coarse correlated equilibria: The algorithm obtains correlation by giving all agents the same random seed when they execute their output policies.Each agent otherwise runs V-learning independently, using a suitable adversarial-bandit subroutine.
  • 5.1 Finding coarse correlated equilibria: V-learning avoids explicit joint-policy storage: its representation uses O(HSK(∑_j A_j)) space, which scales linearly with the number of agents.A general correlated policy would require specifying probabilities for all action combinations at each state and step.
  • 5.1 Finding coarse correlated equilibria: V-learning finds an ǫ-approximate CCE in ˜O(H5SA/ǫ2) episodes, using A = max_j∈[m] A_j rather than the joint action count.The result is stated under the theorem's adversarial-bandit update assumptions.
  • 5.1 Finding coarse correlated equilibria: The CCE and CE guarantees improve over prior value-iteration methods requiring at least Ω(H4S2(∏_j A_j)/ǫ2) episodes.The paper presents these results as breaking the curse of multiagents for both equilibrium notions.
  • 5.2 Finding correlated equilibria: V-learning finds an ǫ-approximate CE in ˜O(H5SA2/ǫ2) episodes, where A = max_j∈[m] A_j.The extra A factor reflects that CE is a subset of CCE and is therefore expected to be more difficult to find.

6 Monotonic V-Learning

Monotonic V-learning modifies V-learning so agents can output Markov policies for two-player zero-sum Markov games. The modification preserves the theoretical guarantees while reducing policy-storage requirements, though computing the policies requires limited communication between players.

  • Markov output policy: Monotonic V-learning lets each agent output a Markov policy for two-player zero-sum Markov games while retaining Theorem 5’s guarantees.Theorem 8 states that the modified method has the same theoretical guarantees as Theorem 5 with the same hyperparameter choices.
  • Markov output policy: O(HSA_j) space stores player j’s Markov policy, compared with O(HSA_jK) space for the nested-mixture output policy.The nested-mixture representation can be advantageous with many agents but undesirable when the number of agents is small.
  • Monotonic update: Monotonic V-learning changes one update so V_h(s_h) decreases monotonically, keeping V-values as high-probability upper bounds on the unique equilibrium value.The decreasing upper bounds move toward the equilibrium value and improve estimate accuracy.
  • Markov output policy: The Markov policies are formed by weighted averages of policies maintained during V-learning at each state-step pair.The resulting policies are Markov, but their computation uses the other player’s most recent update episode.
  • Markov output policy: Although execution is fully decentralized, policy computation requires players to communicate their latest V-value update indexes, so monotonic V-learning is not fully decentralized.The computation of one player’s policy depends on the other player’s update time.

7 Conclusion

The paper presents V-learning as a decentralized approach that breaks the multiagent action-space bottleneck. Its guarantees cover Nash, correlated, and coarse correlated equilibria using complexity governed by the largest individual action space.

  • 7 Conclusion: V-learning finds Nash, correlated, and coarse correlated equilibria by having all agents run the algorithm independently.The conclusion contrasts the resulting dependence on the largest individual action count with prior dependence on the joint action space.
  • 7 Conclusion: The algorithm’s parameterization uses V-values rather than Q-values, enabling its extension to multiple agents without jointly maintaining action-value functions.The supplied conclusion identifies this as the key algorithmic basis for the decentralized extension.
  • 7 Conclusion: The paper defines policy classes starting from a given step and uses them to construct joint and product policies for subsequent analysis.These policies can depend on later state-action histories while omitting history before the starting step.
  • 7 Conclusion: The operators P_h[V] and D^π[Q] represent one-step expected continuation values and policy-averaged action values, respectively.They are defined for arbitrary value functions, action-value functions, and one-step Markov policies.

A.2 Basic lemmas

This appendix establishes the hierarchy among equilibrium concepts and introduces notation for analyzing V-learning updates. It also expresses maintained value estimates through weighted earlier updates.

  • Equilibrium relations: In Markov games, every ε-approximate Nash equilibrium is an ε-approximate correlated equilibrium, and every ε-approximate correlated equilibrium is an ε-approximate coarse correlated equilibrium.The appendix states the inclusion chain Nash ⊂ CE ⊂ CCE.
  • Equilibrium relations: The Nash-to-CE implication uses product-policy independence, making strategy modification equivalent to choosing a new independent policy.The CE-to-CCE implication follows by restricting strategy modifications to those that ignore the recommended action.
  • Basic lemmas: For a fixed state, step, and episode, the appendix represents V-learning’s maintained values using weighted sums of earlier updates.The representation is indexed by the number and episodes of prior visits to the state at that step.

B Proofs for Computing CCE in General-sum MGs

The proof develops concentration-based optimism and pessimism bounds for V-learning under the adversarial-bandit assumption. These bounds control value-estimation gaps needed for the CCE guarantee.

  • CCE proof: The proof’s central ingredients are adversarial-bandit regret control, concentration, and backward induction over the episode horizon.The appendix explicitly attributes successive inequalities to martingale concentration, bonus definitions, induction, and the bandit assumption.
  • Concentration: The concentration parameter is set using ι = log(mHSAK/δ), linking the confidence level to players, horizon, states, and episodes.This parameter appears in the adversarial-bandit concentration lemma.
  • Optimism: V is shown to be an optimistic estimate of the best-response value against the output policy.The corresponding lemma provides a high-probability statement over states, steps, episodes, and players.
  • Pessimism: The proof also establishes pessimistic lower estimates for the relevant value quantities with high probability.These lower bounds are then used to control the gap required by the main theorem.
  • Gap bound: The analysis bounds the cumulative estimation gap by summing update-related terms across episodes and applying properties of the learning-rate sequence.The proof uses changes in summation order and concavity in the resulting bounds.

C Proofs for Computing CE in General-sum MGs

The proof establishes optimism and pessimism properties for V-learning estimates, then bounds their resulting gap using adversarial-bandit regret and concentration arguments.

  • C Proofs for Computing CE in General-sum MGs: The analysis applies a swap-regret lemma to control the adversarial bandit component at each state and time step.The bound uses the adversarial-bandit assumption and logarithmic confidence term ι = log(KHS/δ).
  • C Proofs for Computing CE in General-sum MGs: The proof first establishes optimism and pessimism bounds for V-learning value estimates with high probability.These properties are stated in Lemmas 16 and 17 and proved by backward induction.
  • C Proofs for Computing CE in General-sum MGs: The final proof bounds the cumulative value-estimation gap by combining update-rule properties, concentration, induction, and summation over episodes.The argument explicitly changes summation order and uses concavity in the resulting bounds.
  • C Proofs for Computing CE in General-sum MGs: The section proves the single-agent and two-player zero-sum cases through reductions and the relationship between their reward formulations.An MDP is treated as a two-player zero-sum Markov game with a singleton action set for the second player.

E Proofs for Monotonic V-learning

The monotonic V-learning proof uses minimax value functions, optimism of the estimates, and monotonic updates to establish the two-player zero-sum guarantee.

  • E Proofs for Monotonic V-learning: The proof defines the two-player zero-sum minimax value through Bellman equations and relates it to the V-learning estimates.The reward convention is r1,h = 1 − r2,h, which preserves the relevant Nash equilibria.
  • E Proofs for Monotonic V-learning: Lemma 18 establishes optimism of the V-estimates with high probability by backward induction.The proof combines the update rule, the minimax value definition, induction, concentration, and regret bounds.
  • E Proofs for Monotonic V-learning: Monotonicity and Lemma 18 are used to upper-bound the relevant value terms and complete the proof of Theorem 8.The argument invokes the Bellman equation, Lemma 12, martingale concentration, and the theorem’s precondition.
  • E Proofs for Monotonic V-learning: The implementation uses FTRL as the adversarial-bandit subroutine within the monotonic V-learning analysis.The proof references the FTRL procedure and its weighted-regret analysis.

F Adversarial Bandit with Weighted External Regret

This section develops an FTRL-style adversarial-bandit algorithm with changing step sizes and proves high-probability weighted external-regret guarantees.

  • F Adversarial Bandit with Weighted External Regret: FTRL is presented as a style of algorithm for achieving low weighted external regret in adversarial bandits.The section motivates the derivation because a suitable changing-step-size, weighted-regret, high-probability reference was unavailable.
  • F Adversarial Bandit with Weighted External Regret: Theorem 20 gives a high-probability weighted-regret bound under conditions on the step sizes η_i and γ_i.The theorem applies for t ≤ K and uses ι = log(B/δ).
  • F Adversarial Bandit with Weighted External Regret: The resulting regret upper bounds are simplified by considering cases and using concavity in the episode count.The derivation includes bounds involving H, B, t, and the confidence quantity ι.
  • F Adversarial Bandit with Weighted External Regret: The proof decomposes weighted regret into three terms and bounds them with concentration and FTRL lemmas.The analysis uses a martingale concentration result, changing-step-size FTRL analysis, and a union bound.

G Adversarial Bandit with Weighted Swap Regret

This section adapts FTRL to weighted swap regret by maintaining action-to-action modification weights and proves the resulting high-probability guarantee.

  • G Adversarial Bandit with Weighted Swap Regret: The section adapts FTRL to obtain low weighted swap regret for adversarial bandits.The construction follows a technique for converting external-regret algorithms to swap-regret algorithms in the unweighted case.
  • G Adversarial Bandit with Weighted Swap Regret: The swap algorithm maintains a B × B matrix and uses its eigenvector when selecting actions.Its loss estimator is modified by multiplying the FTRL loss estimator by the action probability term.
  • G Adversarial Bandit with Weighted Swap Regret: Theorem 26 proves a high-probability weighted swap-regret bound under non-increasing step-size conditions.The theorem applies for t ≤ K with ι = log(B^2/δ).
  • G Adversarial Bandit with Weighted Swap Regret: The proof decomposes swap regret into three terms and bounds them separately using concentration and FTRL-style lemmas.The resulting bounds are then combined to establish the theorem and its corollary.
Loading 2110.14555v1…