PaperlayerView exact revision on arXiv

Source-linked AI summary

Fully Online Decentralized Learning in Stochastic Games with Unknown Independent Chains

S. Rasoul Etesami

arXiv:2610.01181v1cs.LGcs.GTcs.MAcs.SYeess.SYmath.OC

TL;DR

In stochastic games with unknown independent chains, decentralized players must learn equilibrium behavior from local observations while rewards remain coupled. The paper develops a fully online occupancy-measure mirror-descent algorithm, establishing high-probability regret guarantees and stability-conditioned last-iterate Nash convergence.

  • Problem

    Decentralized players with unknown local dynamics face coupled rewards, while computing a Nash equilibrium for general rewards is PPAD-hard.

    Source: §1 · p. 1

  • Method

    A fully online occupancy-based mirror-descent method learns local kernels and updates policies from one sample per interaction using local information.

    Source: §1 · p. 3, §3.2 · p. 9, §8 · p. 26

  • Results

    The method achieves high-probability O(T^-1/2) average fixed-comparator regret, while variational stability yields asymptotic last-iterate convergence to a stationary ϵ-NE.

    Source: §1 · p. 3, §8 · p. 26

  • Takeaways & Limitations

    Finite-time complexity depends on local chain dimensions and cover times rather than the exponentially larger joint state–action space.

    Source: §1 · p. 3, §8 · p. 26

    Uniform ergodicity underlies the analysis; for arbitrary rewards, unconditional Nash convergence cannot generally be expected.

    Source: §1 · p. 3, §2 · p. 7

Abstract

from arXiv · show

We consider stochastic games with independent controlled chains and unknown transition kernels, where players observe only their local states and realized payoffs. We develop a fully online, decentralized, and uncoordinated mirror-descent algorithm that operates in the dual space of occupancy measures for approximating stationary Nash equilibrium (NE) policies. The algorithm uses a single transition/reward sample at every primitive time step, relies only on local information, and requires neither coverage of the joint state space nor synchronized episodes. Under uniform-ergodicity and finite-coverage assumptions, we show that, with high probability, the time-averaged fixed-comparator regret decays at the canonical $O(T^{-1/2})$ rate, up to logarithmic factors and polynomial dependence on the game parameters. In particular, the complexity depends on the cover times of the individual local state spaces rather than the product state space, avoiding exponential dependence on the number of players and the sizes of the joint state and action spaces. The resulting finite-time regret bound further yields an approximate coarse-correlated-equilibrium guarantee, which is natural for arbitrary reward functions since computing a stationary $\epsilon$-NE is PPAD-hard in this setting. Under an additional global variational-stability condition, we show that the same fully online algorithm converges asymptotically in the last iterate to a stationary $\epsilon$-NE. Our results provide a fully online and scalable learning framework for stochastic games with unknown independent chains. The algorithm can also be viewed as a primal-dual framework for Markov games that exploits the independence and local structure of the players' controlled transition chains.

1 Introduction

The paper studies decentralized equilibrium learning when players’ unknown local dynamics evolve independently but rewards couple their strategic choices. It develops a fully online occupancy-based method, establishing finite-time regret and, under additional stability conditions, last-iterate Nash convergence.

1 Introduction

  • Players’ independent controlled chains enable tractability even though each player’s payoff may depend on every player’s states and actions.The paper targets complexity governed by local chain dimensions and mixing properties rather than the exponentially growing joint state–action space.Source: §1 · p. 2

1.1 Related Work

  • Earlier approaches exploit zero-sum or potential-game structure, while this paper derives scalability from independent controlled chains and allows general reward coupling.Prior work on independent chains includes episodic methods requiring known kernels or synchronization, motivating the fully online setting addressed here.Source: §1.1 · pp. 3–4

1.2 Contributions

  • The algorithm uses one local transition and payoff sample per time step, with asynchronous confidence-set updates and no covering episodes or synchronization signals.Each local feasible occupancy region changes only logarithmically many times over a finite horizon.Source: §1.2 · p. 5
  • Under variational stability and diminishing step sizes, the algorithm converges asymptotically in the last iterate to the unique stationary ϵ-NE with arbitrarily high probability.Without reward-structure assumptions, the paper instead establishes a high-probability fixed-comparator regret bound and an approximate coarse-correlated-equilibrium guarantee.Source: §1.2 · p. 5

1.3 Organization

  • The paper proceeds from game formulation and occupancy measures to the algorithm, regret and equilibrium guarantees, stability-based convergence, and applications.Section 8 concludes the paper and outlines future research directions.Source: §1.3 · p. 5

2 Problem Formulation

The paper formulates an infinite-horizon average-reward stochastic game in which each player controls an independent local chain and chooses a stationary policy. Its analysis assumes uniform ergodicity to control tracking error and delayed gradient-estimator bias.

2 Problem Formulation

  • Each player has a finite local state and action space, receives rewards that may depend on joint states and actions, and transitions according to an unknown local kernel.The joint transition kernel factors into independent player-specific components.Source: §2 · p. 6
  • Players choose stationary policies to maximize their long-term expected average rewards, and equilibrium claims concern stationary policies.A stationary policy depends only on the player’s current local state and is time-independent.Source: §2 · p. 7
  • The analysis assumes every policy-induced local chain is ergodic and satisfies a uniform contraction condition.Policy-uniform contraction controls tracking error from changing chains and bias in the delayed one-sample gradient estimator.Source: §2 · p. 7
  • The paper targets finite-time fixed-comparator regret for time-averaged iterates and, under stronger conditions, last-iterate convergence to a stationary ϵ-NE.Source: §2 · p. 7

3 Preliminaries on Occupancy Measures, Dual Formulation, and Local Cover Times

The section reformulates stationary policy optimization using occupancy measures, which capture long-run state and action frequencies. Independence of the players’ chains supports a decomposable payoff formulation, while local cover times characterize the relevant coverage scale.

3.1 Occupancy Measures

  • Occupancy measures represent long-run proportions of time spent in states, state–action pairs, and state–action–next-state triples.The measures satisfy ρ(s, a) = ν(s)π(a | s) and q(s, a, s′) = ρ(s, a)P(s′ | s, a).Source: §3.1 · p. 8
  • Feasible occupancy measures form a polytope constrained to be a probability distribution with equal probability flow into and out of each state.A feasible q corresponds to the occupancy measure of its induced transition matrix and stationary policy.Source: §3.1 · pp. 8–9

3.2 A Dual Formulation

  • Under independent chains, each player’s expected average payoff can be expressed using occupancy measures, yielding a continuous-action static virtual game.The virtual action for each player is a feasible occupancy measure, with payoff given by the occupancy-based formulation.Source: §3.2 · pp. 9–10
  • The algorithmic occupancy iterate may differ from the true occupancy induced by its policy when it is not feasible for the true transition kernel.When the iterate is feasible for the true kernel, the two occupancies coincide.Source: §3.2 · p. 10
  • The shrunk feasible occupancy set enforces persistent exploration while allowing its best-response value to approach that of the full set as shrinkage decreases.For rectangular confidence sets, it also admits an explicit linear representation with O(|Ai||Si|^2) variables and constraints.Source: §3.2 · p. 10

3.3 Local Cover Times

  • The local cover-time parameter is the worst-case expected time for a player’s chain to visit all its local states under a fixed stationary policy.The local state space can be exponentially smaller than the joint state space.Source: §3.3 · p. 11

4 A Fully Online Decentralized Learning Algorithm

The algorithm learns unknown local transition kernels and adapts strategic policies on a single uninterrupted trajectory. Each player updates occupancy after every interaction, while confidence sets are refreshed asynchronously using only local information.

4 A Fully Online Decentralized Learning Algorithm

  • Each primitive interaction supplies one transition/reward observation and one mirror-descent update, without burn-in episodes or episode-end synchronization.The same single trajectory is used to estimate the unknown transition kernels.Source: §4 · p. 11

4.2 Description of the Algorithm

  • Each player simultaneously learns its local transition rows and adapts its strategic policy from realized payoff samples along the same uninterrupted trajectory.The two learning tasks use local transitions and payoffs, respectively.Source: §4.2 · p. 12
  • Occupancy updates use a payoff-gradient proxy and project onto a confidence-feasible set; a shrinkage constraint ensures persistent local exploration and bounded importance weights.The updated occupancy induces the policy used to generate the next online interaction.Source: §4.2 · p. 13
  • Confidence sets refresh only when a local state–action count reaches a dyadic threshold, limiting feasible-set changes while preserving the usual count-based estimation rate.The dyadic schedule yields O(log T) feasible-set changes per local counter by time T.Source: §4.2 · p. 14
  • Confidence updates are local and asynchronous: players use their own counters and need no shared update clock, joint-state counter, or coordination.One player may refresh at a different primitive time from another.Source: §4.2 · p. 14

5 Finite-Time Regret Guarantee for the Fully Online Decentralized Algorithm

The analysis separates true-kernel occupancies from confidence-feasible iterates and decomposes regret into optimization, sampling, and occupancy-estimation errors. A delayed mixing comparison supports the finite-time regret bound and an empirical-play coarse correlated equilibrium guarantee.

5.1 True and Confidence-Feasible Occupancies

  • True-kernel occupancies induce the true transition kernel, whereas confidence-feasible iterates induce a kernel within the current confidence set.Unhatted quantities refer to the true kernel; hatted quantities refer to the algorithm's confidence-feasible iterates.Source: §5.1 · p. 15

5.2 Filtration and Regret Decomposition

  • The proof uses a global pre-action filtration for analysis, without enlarging any player's information set in the algorithm.It includes past observations and the current state, but not the fresh randomization for the current action.Source: §5.2 · p. 15
  • The regret decomposition separates optimization error, error from confidence-feasible rather than true-kernel occupancies, and error from adaptive payoff-gradient samples.These are the M_i, Q_i, and E_i terms, respectively.Source: §5.2 · p. 16

5.3 Main Regret Bound Analysis

  • A delayed comparison conditions on F_{t−D_T} and freezes policies over a mixing window to relate the online sample to stationary occupancy-payoff gradients.The comparison addresses the nonstationary trajectory and policy drift.Source: §5.3 · p. 17
  • T^-1/2 is the dominant order in the high-probability finite-time regret bound with quadratic regularization and stepsize η=T^-1/2, up to logarithmic factors.The theorem gives probability at least 1−γ.Source: §5.3 · pp. 18–19
  • The empirical distribution over policy profiles is an (ϵT+ϵδ)-coarse correlated equilibrium, with ϵδ from action-floor constraints and arbitrarily small as δ→0.The guarantee holds on the event of the finite-time regret theorem.Source: §5.3 · p. 19

6 Asymptotic Last-Iterate Convergence to an ϵ-Nash Equilibrium

Under variational stability, the fully online algorithm converges in the last iterate to the unique stable equilibrium of the virtual game. With sufficiently small action floors, the induced stationary policies are an approximate Nash equilibrium of the original game.

6 Asymptotic Last-Iterate Convergence to an ϵ-Nash Equilibrium

  • The convergence theorem assumes variational stability: the payoff-gradient field points toward a unique NE and is strictly directed away from it elsewhere.The theorem also uses Assumptions 1 and 2 and stepsizes ηt = η0(t + 1)^−a for a ∈ (1/2, 1].Source: §6 · pp. 20–21
  • Persistent exploration gives positive visitation of every local state–action pair, so confidence radii vanish and confidence-feasible occupancies approach their true-kernel counterparts.The resulting confidence-set occupancy jumps are summable.Source: §6 · pp. 20–21
  • Diminishing stepsizes, vanishing estimation errors, and summable confidence-update jumps combine with stability to establish occupancy and policy convergence.The proof controls estimation error over dyadic epochs and shows the Lyapunov gap can only have the stable equilibrium as a limit point.Source: §6 · pp. 20–23
  • With probability at least 1 −γ, occupancy iterates converge to the unique stable virtual-game NE, inducing stationary policies that are an ϵδ-NE when action floors are sufficiently small.The approximation error ϵδ tends to zero as the action floors tend to zero.Source: §6 · pp. 21, 23

7 Real-World Applications

The applications share a structure: agents control local stochastic dynamics but interact through coupled rewards. The paper illustrates this structure in energy management, wireless communication, and robotic navigation and coverage.

7 Real-World Applications

  • These applications let agents learn from one continuing trajectory using local information, without known transition kernels or observation of other players’ states and actions.The framework’s guarantees depend on local state spaces and cover times.Source: §7 · p. 24

7.1 Energy Management in Smart Grids

  • Energy users control their own storage dynamics, while aggregate demand affects the shared electricity price and strategically couples their rewards.The local renewable-generation processes are modeled as independent when users are sufficiently geographically separated.Source: §7.1 · p. 24

7.2 Power and Bandwidth Allocation in Wireless Networks

  • Wireless transmitters control their local queues, but compete through a shared channel where simultaneous transmissions can create interference.Users can learn power- or bandwidth-allocation policies from local queues, actions, next states, and realized payoffs.Source: §7.2 · p. 25

7.3 Decentralized Robotic Navigation and Coverage

  • Robots control local motion dynamics while rewards can couple navigation and energy costs with collective coverage, congestion, or collision-avoidance objectives.The model assumes robot-specific disturbances are independent across robots.Source: §7.3 · p. 26

8 Conclusion

The conclusion emphasizes a fully online occupancy-measure algorithm whose regret and equilibrium guarantees scale with local, rather than joint, state spaces. The appendix proof passage derives occupancy identities and a payoff-gradient representation.

8 Conclusion

  • The one-sample algorithm achieves high-probability fixed-comparator regret at an approximately O(T^−1/2) rate and yields an empirical coarse-correlated equilibrium.Its complexity depends on local cover times, not the cover time or cardinality of the product state–action space.Source: §8 · p. 26
  • Under variational stability and diminishing stepsizes, the same scheme converges in the last iterate to a stationary ϵ-NE.The conclusion states that the product state space does not enter the complexity.Source: §8 · p. 26

A.1 Proof of Lemma 5

  • The Lemma 5 proof uses stationary policies to derive occupancy relations and represents each player’s payoff gradient as a vector over local state–action pairs.The passage identifies the vector dimension as |Si||Ai| and says the derivation establishes equations (6) and (7).Source: §A.1 · p. 30

A.2 Proof of Lemma 8

The proof gives an explicit linear description of the shrunk feasible occupancy set. It shows that this set is a closed, bounded convex polytope of polynomial size.

A.2 Proof of Lemma 8

  • A positive action floor ensures that the transition kernel induced by an occupancy is well defined.The proof uses the floor constraint ρi(si, ai) ≥ δi > 0.Source: §A.2 · p. 30
  • Membership in the feasible transition-kernel set is converted into box constraints and then linear inequalities on occupancies.These constraints give an explicit representation of the shrunk feasible occupancy set.Source: §A.2 · pp. 30–31
  • The resulting occupancy set has |Si|^2|Ai| variables and O(|Si|^2|Ai|) constraints, and is a closed, bounded convex polytope.The passage characterizes its linear description as polynomial-size.Source: §A.2 · p. 31

B.1 Proof of Lemma 10

The proof establishes simultaneous high-probability coverage of the true transition kernels by the players’ confidence sets. It also shows that the occupancy-update comparison telescopes globally without a restart term when the true-kernel comparator remains feasible.

B.1 Proof of Lemma 10

  • With probability at least 1−γ/4, every confidence region at every player’s confidence-update time contains the corresponding true transition kernel.The proof indexes observations by successive visits to each state–action pair and applies a martingale concentration bound.Source: §B.1 · pp. 31–32
  • The confidence event has probability at least 1−γ/4 and ensures that true-kernel occupancies remain feasible in the players’ confidence sets.This follows because the initial sets contain all transition kernels and later sets are formed by intersection.Source: §B.1 · p. 32

C.1 Proof of Lemma 13

  • The proximal-update comparison telescopes globally without a restart term because the true-kernel comparator remains feasible after each confidence-set intersection.Both occupancy vectors have unit mass.Source: §C.1 · p. 33

C.2 Proof of Lemma 14

The proof bounds occupancy-estimation error in three stages: ensure sufficient local visits, control transition-kernel error, then translate it into occupancy error. Under the stated events, the local state–action visit counts grow linearly after a threshold.

C.2 Proof of Lemma 14

  • The occupancy-estimation argument first establishes sufficient local visits despite slowly changing policies, then bounds kernel error and converts it to occupancy error.The conversion uses the contraction assumption.Source: §C.2 · p. 34
  • Conditional on the block’s starting history, either a confidence update occurs or the actual chain visits any prescribed local state with probability at least 1/4.The proof couples the actual chain to a frozen-policy chain over blocks of length 2H_i + 1.Source: §C.2 · p. 35
  • A successful block either contributes a visit to the prescribed state–action pair or can be charged to a confidence update.The disjoint-block count is bounded using the dyadic update rule.Source: §C.2 · p. 35
  • With probability at least 1−γ/4, every local state–action pair has a visit count that grows linearly for all times after K_i(T).The bound combines block successes with the action floor and a Freedman inequality.Source: §C.2 · pp. 35–36
  • On the visitation and transition-confidence events, kernel approximation error is converted into occupancy error, completing the occupancy-estimation bound with probability at least 1−γ/2.The transition-confidence event itself has probability at least 1−γ/4.Source: §C.2 · p. 37

C.3 Proof of Lemma 15

The proof of Lemma 15 compares the actual process with one using policies frozen over a clean delay window. Lemma 16 then controls delayed gradient error by separating sampling fluctuation, delayed bias, and target drift.

C.3 Proof of Lemma 15

  • On a clean delay window, the proof freezes each player’s policy and couples actual and frozen local trajectories to bound their terminal state–action distributions.The conditional joint law of the frozen local processes factorizes because their transitions and action randomizations are independent across players.Source: §C.3 · pp. 38–39
  • The comparison bounds distributional differences using path separation and a product-total-variation bound, yielding the stated bound under Assumption 2.Applying the common frozen action kernel cannot increase total variation distance.Source: §C.3 · pp. 38–39

C.4 Proof of Lemma 16

  • The delayed gradient error decomposes into a sampling martingale fluctuation, delayed bias, and drift of the stationary payoff gradient over the delay window.The proof treats clean windows separately from contaminated windows and accounts for the latter through confidence-update counts.Source: §C.4 · pp. 39, 41
  • The sampling terms are controlled by partitioning times into residue classes modulo D_T + 1, so centered terms form martingale differences within each class.Freedman’s inequality and a union bound yield the event Egrad.Source: §C.4 · pp. 39–40
  • Combining the sampling, bias, and drift bounds gives the delayed-gradient result on the event of Lemma 14 and an additional event of probability at least 1−γ/4.The proof absorbs the exponentially small mixing term into the displayed bound.Source: §C.4 · p. 42

D.1 Proof of Lemma 20

The proof extends a finite-horizon visitation bound to all sufficiently large times almost surely. It then uses that bound in subsequent confidence-radius and occupancy estimates.

D.1 Proof of Lemma 20

  • For sufficiently late blocks, the probability of observing a prescribed state–action pair or a confidence update is at least δ_i/4.The argument uses the vanishing stepsize and the small-movement condition.Source: §D.1 · p. 43
  • A dyadic-horizon argument with summable failure probabilities and Borel–Cantelli yields the visitation bound simultaneously for all sufficiently large times, almost surely.The proof chooses one finite random time after which the bound holds for every player and local pair.Source: §D.1 · p. 43
  • The proof substitutes the eventual visitation bound into the confidence-radius expression and uses the resulting estimates in the subsequent occupancy bound.The final inequality invokes the pointwise occupancy bound and the confidence estimate.Source: §D.1 · p. 43

D.2 Proof of Lemma 21

The proof controls how far an occupancy iterate can lie from the true-kernel feasible polytope, then bounds changes at confidence updates. It uses dyadic sampling thresholds to make the update-related bounds summable.

D.2 Proof of Lemma 21

  • Hoffman’s error bound converts violations of the true-kernel constraints into a bound on the iterate’s distance from the feasible occupancy polytope.The iterate already satisfies normalization, flow, nonnegativity, and shrinkage constraints; the kernel bound controls its remaining possible violations.Source: §D.2 · pp. 43–44
  • At confidence updates, the iterate-change bound uses projection nonexpansiveness and the fact that the true-kernel feasible polytope lies inside the updated confidence-set polytope.The proof also invokes the previously established distance bound for the iterate.Source: §D.2 · p. 44
  • Dyadic confidence-update times grow on the order of 2^k, making the stated confidence-radius and step-size sequences summable.The proof sums these contributions over the finitely many local state–action pairs.Source: §D.2 · p. 44
Loading 2610.01181v1…