PaperlayerView exact revision on arXiv

Source-linked AI summary

Decentralized Q-Learning for Stochastic Teams and Games

Gürdal Arslan, Serdar Yüksel

arXiv:1506.07924v2math.OCcs.GTcs.LG

TL;DR

Learning equilibrium policies in stochastic games is difficult because simultaneous learners create a non-stationary environment, and decisions also change states and future costs. The paper develops decentralized Q-learning algorithms for weakly acyclic games, using extended exploration phases and policy comparisons. It reports almost-sure convergence to equilibrium policies for large classes of stochastic games.

  • Problem

    Learning equilibrium policies in stochastic games remains difficult because concurrent learners make the environment non-stationary, while decisions alter states and future costs.

    Source: §I · p. 1, A. Learning Paradigm for Stochastic… · p. 5

  • Method

    The paper modifies decentralized Q-learning with extended fixed-policy exploration phases and compares learned Q-factors for baseline and experimental policies before updating with inertia.

    Source: B. Q-Learning in Stochastic Dynamic… · p. 5, A. Learning in Weakly Acyclic Games… · p. 7, §VI · p. 9

  • Results

    The decentralized algorithms converge almost surely to equilibrium policies in large classes of stochastic games, including weakly acyclic cases.

    Source: §VI · p. 9

  • Takeaways & Limitations

    The approach covers team problems within a broader weakly acyclic game class and requires only local information, state information, and local cost realizations.

    Source: §I · p. 1, §VI · p. 9

    The convergence results are scoped to weakly acyclic stochastic games, with team problems as an important special case.

    Source: §VI · p. 9

Abstract

from arXiv · show

There are only a few learning algorithms applicable to stochastic dynamic teams and games which generalize Markov decision processes to decentralized stochastic control problems involving possibly self-interested decision makers. Learning in games is generally difficult because of the non-stationary environment in which each decision maker aims to learn its optimal decisions with minimal information in the presence of the other decision makers who are also learning. In stochastic dynamic games, learning is more challenging because, while learning, the decision makers alter the state of the system and hence the future cost. In this paper, we present decentralized Q-learning algorithms for stochastic games, and study their convergence for the weakly acyclic case which includes team problems as an important special case. The algorithm is decentralized in that each decision maker has access to only its local information, the state information, and the local cost realizations; furthermore, it is completely oblivious to the presence of other decision makers. We show that these algorithms converge to equilibrium policies almost surely in large classes of stochastic games.

I. INTRODUCTION

The paper develops learning algorithms for weakly acyclic stochastic games, where decisions affect both immediate costs and future stages through state dynamics. It frames the goal around bounded-rational decision makers and cooperative settings, while treating games more broadly than repeated single-stage interactions.

I. INTRODUCTION

  • Existing stochastic-game learning work is limited; many methods require agents to exchange actions and objectives and compute equilibria, while standard Q-learning lacks analytical guarantees in this setting.The introduction also notes computational, convergence, or scope limitations in several fictitious-play and policy-iteration approaches.Source: §I · p. 1
  • The paper targets bounded-rational agents pursuing their own objectives, with strategies that can converge to an agreeable solution in cooperative settings without requiring a prescribed strategy.The motivating setting includes stochastic dynamic games, where policies affect immediate costs and alter future stage games through state dynamics.Source: §I · pp. 1–2

II. STOCHASTIC DYNAMIC GAMES

  • Controllers choose their own inputs and minimize individual long-term costs, but costs and state transitions can depend on all controllers’ decisions, creating dynamic coupling.This coupling motivates modeling the system as a stochastic game rather than as independent control problems.Source: §II · p. 2

A. Discounted Stochastic Dynamic Games

  • A discounted stochastic game combines finite states and control sets with decision-maker-specific costs and a joint-action state-transition kernel.Together these define a controlled Markov process whose state evolves under the controllers’ decisions.Source: A. Discounted Stochastic Dynamic Games · p. 2
  • Stationary policies depend only on the state, and an equilibrium is a joint policy that is person-by-person optimal for every decision maker and initial state.Deterministic equilibrium policies exist in many cooperative games, including team problems with a common cost.Source: A. Discounted Stochastic Dynamic Games · p. 3

B. Weakly Acyclic Games

Weak acyclicity requires a strict best-reply route from every deterministic joint policy to an equilibrium. This condition allows cycles, provided a route to an equilibrium remains available.

B. Weakly Acyclic Games

  • A decision maker’s best replies against the other policies can be characterized by its optimal Q-factors, which represent expected discounted cost-to-go after an initial action.The other decision makers’ policies are held fixed in this cost-to-go characterization.Source: B. Weakly Acyclic Games · p. 3
  • A game is weakly acyclic under strict best replies when every deterministic joint policy has a strict best-reply path ending at a deterministic equilibrium.The path changes one decision maker’s policy at a time through strict best replies.Source: B. Weakly Acyclic Games · p. 3
  • In the strict best-reply graph, nodes are deterministic joint policies, edges are single-decision-maker strict best replies, and equilibria are sinks.Weakly acyclic games may contain cycles, but every node has a path to a sink; the illustrated game has paths to π7 or π10 and also a cycle.Source: B. Weakly Acyclic Games · pp. 3–4, Figure 2 · p. 4
  • Weakly acyclic games include team problems with identical costs and discount factors, as well as single-stage potential and dominance-solvable games.Appropriate multi-stage generalizations restricted to stationary Markov policies are also included.Source: B. Weakly Acyclic Games · p. 4

C. A Best Reply Process for Weakly Acyclic Games

The section describes a best-reply process with inertia and a decentralized learning paradigm for weakly acyclic stochastic games. The paper states that its Q-learning variation converges to equilibrium policies in this class.

C. A Best Reply Process for Weakly Acyclic Games

  • In weakly acyclic games, every cycle in the strict best-reply graph has an exit, allowing a path to equilibrium even when cycles occur.Having all decision makers update with inertia avoids requiring prior agreement on which decision maker updates.Source: C. A Best Reply Process for Weakly… · p. 4
  • The best-reply process with inertia reaches an equilibrium policy in a finite number of steps with probability one.From any policy, an equilibrium is reachable within L steps with positive probability, and an equilibrium policy remains unchanged.Source: C. A Best Reply Process for Weakly… · p. 4
  • Direct best-reply computation requires transition probabilities and other decision makers’ policies, information agents may not have.The proposed learning paradigm instead lets agents learn near-best replies with minimal information.Source: C. A Best Reply Process for Weakly… · p. 4

A. Learning Paradigm for Stochastic Dynamic Games

B. Q-Learning in Stochastic Dynamic Games

Algorithm 1 creates exploration phases with fixed baseline policies so decision makers can learn in a temporarily stationary environment, then adjust toward near-best replies. The theorem’s stated scope is discounted games weakly acyclic under strict best replies, subject to Assumptions 1 and 2.

B. Q-Learning in Stochastic Dynamic Games

  • During each exploration phase, constant baseline policies create a stationary learning environment, with occasional experimentation.Each phase runs from t=tk through tk+1−1.Source: B. Q-Learning in Stochastic Dynamic… · pp. 5–6
  • Theorem 1 analyzes Algorithm 1 for discounted games weakly acyclic under strict best replies, subject to Assumptions 1 and 2.The supplied theorem passage gives its scope and assumptions but not its conclusion.Source: B. Q-Learning in Stochastic Dynamic… · p. 6
  • Long phases and small, nonzero experimentation probabilities let each decision maker learn its Q-factors accurately and compute near-best replies with high probability.Policy updates with inertia approximate the best-reply process with inertia.Source: B. Q-Learning in Stochastic Dynamic… · p. 6
  • The paper notes that explicit lower bounds on exploration-phase lengths for almost-sure convergence remain a desired result, and points to standard Q-learning convergence rates.The remark frames such bounds as something one may wish to obtain.Source: B. Q-Learning in Stochastic Dynamic… · p. 7

IV. GENERALIZATIONS

A second algorithm targets convergence in discounted stochastic games weakly acyclic under strict better replies. It learns baseline and experimental policies and permits transitions along strict better-reply paths.

A. Learning in Weakly Acyclic Games under Strict Better Replies

  • Weak acyclicity under strict better replies means every deterministic joint policy has a strict better-reply path to a deterministic equilibrium policy.The path changes one decision maker’s policy at each step.Source: A. Learning in Weakly Acyclic Games… · p. 7
  • Every strict best-reply path is also a strict better-reply path, so weak acyclicity under strict better replies covers a strictly larger set of games.The passage compares these two classes directly.Source: A. Learning in Weakly Acyclic Games… · p. 7
  • Algorithm 2 learns Q-factors for a baseline and a randomly selected experimental policy, updating the baseline toward the experimental policy when it is better within a tolerance, with inertia.This is intended to approximate strict better-reply paths while using limited information.Source: A. Learning in Weakly Acyclic Games… · p. 7
  • Unlike Algorithm 1, Algorithm 2 can switch to any strict better reply with positive probability, enabling escape from strict best-reply cycles when a better reply exists.This flexibility requires two Q-learning recursions instead of one and yields convergence in a strictly larger set of games.Source: A. Learning in Weakly Acyclic Games… · p. 7
  • Theorem 2 establishes the stated convergence result for Algorithm 2 in discounted games weakly acyclic under strict better replies, under Assumptions 1 and 3.The theorem passage specifies these conditions; the supplied excerpt does not include its full conclusion.Source: A. Learning in Weakly Acyclic Games… · p. 7

B. Learning in Weakly Acyclic Games under multi-DM Strict Best or Better Replies

The paper extends weak acyclicity to paths where multiple decision makers update simultaneously. Its convergence results apply to games weakly acyclic under these multi-DM strict best- or better-reply paths.

B. Learning in Weakly Acyclic Games under multi-DM Strict Best or Better Replies

  • A multi-DM strict best- or better-reply path allows at least one decision maker to change policy at each step, with every deviator choosing a strict reply.The path must start at each deterministic joint policy and end at a deterministic equilibrium policy for the game to be weakly acyclic under this definition.Source: B. Learning in Weakly Acyclic Games… · p. 8
  • In the illustrated three-DM game, simultaneous reply updates make equilibrium (2, 3, 2) reachable from every joint decision, unlike single-DM-at-a-time updates.The example states that several starting decisions have no single-DM reply path to equilibrium.Source: B. Learning in Weakly Acyclic Games… · p. 8, Figure 4 · p. 8
  • Theorem 1 and Theorem 2 also hold for games weakly acyclic under multi-DM strict best or better replies, since the algorithms allow simultaneous policy updates with positive probability.The result extends both main convergence theorems to the generalized path condition.Source: B. Learning in Weakly Acyclic Games… · p. 8

V. A SIMULATION STUDY: PRISONER’S DILEMMA WITH A STATE

The simulation uses a state-dependent prisoner’s dilemma to examine learning under conditions where cooperation can be an equilibrium. The concluding remarks describe decentralized Q-learning for weakly acyclic stochastic games and its convergence analysis.

V. A SIMULATION STUDY: PRISONER’S DILEMMA WITH A STATE

  • The simulated single-stage game is a prisoner’s dilemma: mutual defection is its unique equilibrium, although both decision makers receive better rewards from mutual cooperation.The setup uses b = 2, c = 1, a = −1, and γ = 0.3.Source: §V · p. 8
  • With sufficiently patient decision makers and sufficiently small state-error probability γ, the game has cooperation and defection Markov perfect equilibria.From any joint policy, a strict best-reply path leads to one of these equilibria, making the game weakly acyclic under strict best replies.Source: §V · p. 8
  • As exploration length T increases, learned policies visit equilibrium and agree with the inertia best-reply process more often.For sufficiently large T, they are nearly always at equilibrium and agree regardless of initial policy; typical runs reach and remain at equilibrium within a few steps.Source: §V · p. 9, Table I · p. 9

VI. CONCLUDING REMARKS

  • The decision makers observe only their own decisions and cost realizations, plus state transitions, and need not know other decision makers are present.The paper develops decentralized Q-learning algorithms with convergence properties for stochastic games under weak acyclicity.Source: §VI · p. 9
  • The approach has a two-time-scale flavor without relying on stochastic approximation theory, and yields simpler analysis for weakly acyclic stochastic games.The paper contrasts this with existing multi-time-scale work requiring analysis of nonlinear ordinary differential equations.Source: §VI · p. 9

Q-LEARNING ALGORITHM WITH A SINGLE DM

The appendix studies standard Q-learning for a single decision maker and establishes a uniform convergence result under recurrent state-action visits. It also gives a recursion for learning Q-factors under a fixed deterministic policy.

  • At each step, the Q-factor for every state-action pair other than the visited pair remains unchanged; the selected action ut is chosen according to policy π(xt).Source: Q-LEARNING ALGORITHM WITH A SINGLE DM · p. 9
  • If every state-action pair is visited infinitely often almost surely, the Q-learning recursion has a uniform convergence result over compact sets of initial Q-values.The appendix assumes one-stage costs are exogenous random variables with finite variance.Source: Q-LEARNING ALGORITHM WITH A SINGLE DM · pp. 9–10
  • For a fixed deterministic policy, Q-factors can be learned by updating only the visited pair while selecting actions according to that policy.The appendix states that the uniform convergence result also holds for this modified recursion.Source: Q-LEARNING ALGORITHM WITH A SINGLE DM · p. 10

APPENDIX B PROOF OF THEOREM 1

The appendix proof uses convergence of Q-factor estimates during exploration phases to support the theorem’s learning argument. Its stated conditions include sufficiently long phases and bounds on tolerances and experimentation rates.

  • The argument uses contraction of the relevant mapping and bounds on quantities associated with a finite set of policies.The supplied proof passages identify the mapping as a contraction and refer to a finite subset of policies.Source: Appendix B · p. 10
  • When exploration phases are sufficiently long, the probability of the stated Q-factor estimation event can be made arbitrarily close to one.The proof invokes uniform convergence for the stationary random policies used during each phase.Source: Appendix B · p. 10
  • The proof imposes a positive upper bound on tolerance levels and an upper bound on experimentation rates to obtain its stated lemma.The upper bound on experimentation rates is supported by Lemma 3.Source: Appendix B · p. 10

A. Proof of part (i)

The proof of Theorem 1 builds from equilibrium stability and strict best-reply paths to probability bounds on reaching equilibrium. It then treats eventual lower bounds on exploration lengths and a varying-threshold argument.

A. Proof of part (i)

  • At an equilibrium policy, the next policy remains unchanged with probability one.Source: A. Proof of part (i) · p. 11
  • Weak acyclicity supplies a finite strict best-reply path from every joint policy to an equilibrium, with a positive lower bound on following such paths.The path-length bound is maximized over the finite policy set.Source: A. Proof of part (i) · p. 11
  • When minℓTℓ≥˜T, block-event probability is at least 1−˜ǫ; conditional on πk∈Πeq, equilibrium persists through L steps with probability at least 1−˜ǫ, while pnL rises by pmin˜ǫ per block below (1−˜ǫ)pmin.Source: A. Proof of part (i) · p. 11

B. Proof of part (ii)

  • If exploration lengths eventually stay above the part (i) threshold, then the probability of an equilibrium policy is eventually at least 1 − ǫ.Source: B. Proof of part (ii) · p. 11

C. Proof of part (iii)

  • The varying-threshold argument uses a sequence of positive error bounds and invokes the Borel-Cantelli lemma to obtain the desired result.Source: C. Proof of part (iii) · p. 11

APPENDIX C PROOF OF THEOREM 2

The proof uses contraction and finite-policy arguments to establish intermediate conditions for the convergence analysis.

APPENDIX C PROOF OF THEOREM 2

  • F_i^π is a contraction in the maximum norm with Lipschitz constant β_i and has a unique fixed point.Source: Appendix C · p. 12
  • Lemma 5's proof invokes Lemma 1 using finite states, compact Q-factor sets, and finitely many stationary random policies during exploration.Source: Appendix C · p. 12
  • Lemma 6 states an ε-dependent condition on experimentation rates, but the supplied passage does not include its conclusion.Source: Appendix C · p. 12

Appendix B). Because (πi

This proof fragment sets bounds on better-reply paths and experimentation, then uses recursive inequalities in its convergence argument.

Appendix B). Because (πi

  • For tolerances below ˇδ, an upper bound ˇρ on experimentation rates exists, as guaranteed by Lemma 6.Source: Appendix B · p. 12
  • Every policy has a finite strict better-reply path to equilibrium; the maximum path length is bounded by ˇL.Source: Appendix B · p. 12
  • The proof derives recursive inequalities for equilibrium-policy probabilities and states that the remaining theorem parts follow analogously to Theorem 1.Source: Appendix B · p. 13
Loading 1506.07924v2…