PaperlayerView exact revision on arXiv

Source-linked AI summary

Decentralized Bandit Learning of Markov Perfect Equilibria

Felix Höfer, H. Mete Soner

arXiv:2610.14333v1cs.LGmath.OC

TL;DR

Decentralized learning of equilibria in continuous-action general-sum Markov games is challenging when agents have only private bandit feedback and must learn continuation values. The paper uses simultaneous perturbation to update policies and values from one trajectory. Under strong monotonicity and a small time-step condition, the updates converge almost surely to the unique stationary MPE.

  • Problem

    The paper addresses decentralized equilibrium learning in dynamic general-sum games when agents lack opponents’ actions and must learn unknown continuation values alongside policies.

    Source: §1 · pp. 1–2

  • Method

    Agents use simultaneous perturbation estimates from private observations to update policies and continuation values along one uninterrupted trajectory.

    Source: §1 · p. 1, §1.2 · p. 3

  • Results

    Under strong monotonicity and a small time-step condition, the coupled updates converge almost surely to the unique stationary MPE.

    Source: §1 · p. 2, §2.3 · pp. 6–7

  • Takeaways & Limitations

    The result establishes decentralized learning of ordinary MPE in continuous-action games from private bandit feedback alone.

    Source: §1 · p. 1

    The contraction condition κh < 1 is not required for episodic learning.

    Source: §2.1 · p. 5

Abstract

from arXiv · show

We study decentralized bandit learning in discounted infinite-horizon, general-sum Markov games with continuous actions. Agents observe the public state, but only their own realized rewards, and use simultaneous perturbation stochastic approximation to update their actions. Under strong monotonicity of the negative running-reward gradients and sufficiently small time steps, we prove that the fully decentralized procedure converges almost surely to the unique stationary Markov perfect equilibrium. We obtain an $O(n^{-1/2})$ convergence rate and present a natural extension to episodic finite-horizon learning.

1 Introduction

The paper studies continuous-action, discounted general-sum Markov games in which agents learn a Markov perfect equilibrium from private bandit feedback. It develops a decentralized learning procedure and analyzes the coupled challenges of estimating policies and continuation values from a single trajectory.

1 Introduction

  • Under strong monotonicity and a small time-step condition, the coupled policy and value updates converge almost surely to the unique stationary MPE.The result concerns the fully decentralized procedure.Source: §1 · pp. 1–2, §1.2 · p. 4
  • Unlike approaches requiring opponents’ actions or repeated terminating trials, this method learns ordinary MPE from private bandit feedback on a single trajectory.The policy and value updates do not require separate timescales.Source: §1 · pp. 1–2
  • The dynamic problem couples policy and value errors along one evolving trajectory, because actions affect future states and changing policies alter which states are visited.The analysis must control these errors together while preserving the needed monotone structure.Source: §1 · p. 2
  • Agents estimate their own Bellman-operator action gradients from private one-step observations using simultaneous perturbation, while continuation values are learned alongside policies.Unknown continuation values introduce a stochastic-approximation bias that the analysis controls through contraction of coupled policy and value errors.Source: §1 · pp. 1–2

1.1 Markov game and the Nash system

  • The game has a finite public state space, unknown rewards and transitions, and stationary feedback policies evaluated by discounted expected rewards.A stationary MPE is characterized through the stationary Nash system under differentiability and monotonicity conditions.Source: §1.1 · p. 3

1.2 Algorithm

  • Each agent maintains policy and value tables and updates visited entries during one uninterrupted trajectory, without communication or knowledge of opponents’ actions or tables.The procedure uses a perturbed action and private reward to form a one-point pseudo-gradient estimate.Source: §1.2 · pp. 3–4

2 Assumptions and results

The section lays out assumptions for the game and learning algorithm, then states equilibrium and convergence results for stationary and episodic settings.

2.1 Assumptions on the game

  • Game assumptions require differentiable reward and transition maps and strong monotonicity; the discounted contraction condition requires a sufficiently small time step.Source: §2.1 · p. 5

2.2 Assumptions on the algorithm

  • Algorithm assumptions include finite states with uniformly positive transition probabilities, conditionally independent perturbations across agents, and perturbation sizes that keep actions admissible.Source: §2.2 · p. 6

2.3 Main results

  • The section establishes a unique stationary MPE under Assumptions 2.1–2.3 and states an almost-sure convergence theorem under additional learning assumptions.Source: §2.3 · pp. 6–7

2.4 Episodic learning

  • The episodic extension allows time-varying rewards, transitions, and feedbacks plus a terminal reward, and replaces the stationary continuation table with the next-time table.The paper states an analogous convergence result for episodic learning.Source: §2.4 · pp. 7–8

3 Illustrative example

The illustrative service game models providers choosing processing rates in a shared finite-capacity queue, with actions affecting future job assignments. Under the stated assumptions, its unique stationary MPE is learned almost surely by a modified decentralized algorithm.

3 Illustrative example

  • Providers choose service rates when busy; the public state records waiting jobs and busy servers, while idle providers use zero service rates.The state-dependent action space is [−ϱ, ϱ] for busy providers and {0} for idle providers.Source: §3 · pp. 8–9
  • Arrivals are assigned uniformly to idle servers or join the queue when all servers are busy; service completions free servers or reduce the queue.At full capacity, arrivals are rejected and leave the state unchanged.Source: §3 · p. 8
  • Busy providers receive capacity-based payments and incur quadratic operating costs, while idle providers receive standby payments.Net payment is p_i a_i − c_E(a_i)^2 when busy and v_i when idle.Source: §3 · p. 9
  • The modified algorithm perturbs and updates policies only for busy providers, but updates values for every provider.Actions are centered before applying the algorithm; idle providers retain the prescribed zero service rate.Source: §3 · pp. 9–10
  • Under (3.3) and (3.2), the service game has a unique stationary MPE, and the modified service-rate and value tables converge to it almost surely.The result also bounds each equilibrium value by hCr/(1 − βi).Source: §3 · p. 9
  • On active coordinates, ⟨F(x,a)−F(x,b),a−b⟩=−2cE‖a−b‖²; therefore the negative field −F is strongly monotone with parameter µ=LF=2cE.Source: §3 · p. 10

4 Preliminaries

The preliminaries establish tools for estimating agents’ pseudo-gradients from one-point observations and proving convergence of projected stochastic approximation. Strong monotonicity and controlled bias are central to the convergence argument.

4 Preliminaries

  • The negative pseudo-gradient is strongly monotone because the paper’s strong monotonicity assumption on −F is inherited by the pseudo-gradient.This property supplies the drift condition used in the projected stochastic approximation argument.Source: §4 · p. 10
  • The one-point gradient estimate uses a perturbed action and private observation to represent the pseudo-gradient as its conditional mean plus bias and mean-zero noise.The estimate scales the observed reward by the perturbation sign and inverse perturbation size; its bias and variance are bounded under the lemma’s conditions.Source: §4 · pp. 10–11
  • The Robbins–Siegmund lemma supplies an almost-sure convergence tool for nonnegative adapted processes under summability conditions.The paper introduces it as a classical result for the subsequent stochastic approximation analysis.Source: §4 · p. 11
  • The projected stochastic approximation result gives convergence to the target when the drift is strongly monotone, the bias is eventually bounded, and the step sizes have an infinite sum.Its proof controls excursions outside a neighborhood using a stopping time and a squared-distance estimate.Source: §4 · pp. 11–12

5 Existence and uniqueness of the MPE

For each value function, the paper defines the equilibrium policy through a variational inequality. Strong monotonicity yields a unique policy, and contraction of the Bellman operator yields a unique MPE.

5 Existence and uniqueness of the MPE

  • The policy at each state solves a variational inequality, equivalently characterized by a projection fixed-point condition on the action set.The equivalence follows from the projection characterization for convex sets.Source: §5 · p. 13
  • Strong monotonicity of −Φ[W] makes the variational-inequality solution unique for each W.The paper obtains this property from Lemma 4.1.Source: §5 · p. 13
  • The Bellman operator is a contraction with factor κh < 1, so it has a unique fixed point whose associated policy yields the unique MPE.The policy is defined by α⋆ = Sh(V⋆).Source: §5 · p. 13

6 Convergence proof

The convergence proof controls policy and value estimation errors along the learning trajectory. It establishes that both errors vanish, yielding almost-sure convergence to the unique MPE.

6 Convergence proof

  • Uniform bounds keep value estimates and one-step value observations within [−M, M] throughout learning.The value update is a convex combination of bounded quantities, and unvisited table entries remain unchanged.Source: §6 · p. 13
  • Every state is visited with conditional probability at least ζ, ensuring that the cumulative policy and value step sizes for each state diverge.This supports applying the stochastic approximation result state by state.Source: §6 · pp. 14–15
  • Conditional estimates bound the policy-gradient bias by value-estimation error plus terms that vanish with the perturbation and smoothing parameters.The bound is L⋆∥bVn − V⋆∥∞ + K(δn + λn).Source: §6 · p. 14
  • The proof separates each policy update into a strongly monotone drift, a controlled bias, and mean-zero noise before applying projected stochastic approximation.When the current state is x, the update targets the policy table entry for x; otherwise that entry is unchanged.Source: §6 · p. 15
  • The maximum policy error over states and agents vanishes almost surely, and the value error also vanishes by contraction of the Bellman operator.The proof concludes that EV = 0 and Eα = 0, then applies the preceding error bounds.Source: §6 · pp. 15–16

7 Proof of complexity

The proof establishes the target polynomial error bound by controlling iteration and total errors, then applying a recursion lemma.

Step 3: Total error

  • A recursion lemma converts the bound on the expected total error into polynomial decay of the total error sequence.The proof first derives a reverse inequality relating consecutive expected total errors.Source: §7 · pp. 16, 18, 19

Step 1: Error measurement

  • The error measure balances policy and value errors using a constant chosen under the contraction condition.The proof chooses s⋆ so that both terms in f(s⋆) are below 1.Source: §7 · p. 16

Step 2: Iteration error

  • The iteration-error estimate controls the change in total error because each update changes only the currently visited state.The proof bounds policy and value increments separately and combines the bounds to obtain (7.2).Source: §7 · pp. 17–18

Step 4: Conclusion

  • The proof concludes that the expected total error is O(n^-p/4), establishing claim (2.14).The rate follows after choosing ε so that the recursion lemma applies with θ = p/4.Source: §7 · pp. 16, 19

8 Episodic learning

The episodic extension establishes a unique finite-horizon Markov perfect equilibrium and almost-sure convergence of the episodic algorithm under its stated assumptions.

Assumptions

  • The episodic setting retains analogous assumptions to the discounted problem, but does not require the contraction condition κh < 1.It assumes the time-dependent versions of Assumptions 2.1 and 2.2 hold uniformly in t, along with µT > 0.Source: §8 · p. 20

Theorem 8.1

  • The episodic algorithm converges almost surely to the unique finite-horizon MPE characterized by (2.16).The theorem also gives a bound on its values.Source: §8 · p. 20

Proof

  • The episodic proof uses backward induction and estimates from the proofs of Theorem 2.10 and Proposition 4.4.The proof is omitted.Source: §8 · p. 20

A Proof of the estimates

The estimates bound how policy and value changes affect the gradient terms, combining continuation and running-reward contributions.

Lemma 4.1

  • The proof bounds the change in the continuation gradient by taking the Euclidean norm across agents after scaling each component by βi.The component bound uses (2.3).Source: A Proof of the estimates · pp. 20–21
  • The continuation contribution to the gradient bound is at most β⋆Nh²c²m∥e∥, while the running-reward contribution is at most hLF∥e∥.Together these establish estimate (4.1).Source: A Proof of the estimates · p. 21

B Proof of the gradient-estimate

The proof expands the perturbed action value around the unperturbed action and controls the resulting gradient estimate using conditional independence and covariance assumptions.

Proof of Lemma 4.2

  • Taylor expansion expresses the perturbed action value as its unperturbed value plus a gradient inner product and a remainder.The expansion is in agent i’s action.Source: B Proof of the gradient-estimate · p. 21
  • Conditional independence and covariance assumptions are used to bound the gradient-estimation terms.The proof also uses measurability of the gradient and the stated conditional second-moment identity for Δi.Source: B Proof of the gradient-estimate · p. 21
  • A componentwise Lipschitz estimate is applied to the gradient to obtain the final bound.The proof increases K if necessary.Source: B Proof of the gradient-estimate · p. 22
Loading 2610.14333v1…