PaperlayerView exact revision on arXiv

Source-linked AI summary

Decentralized Learning for Optimality in Stochastic Dynamic Teams and Games with Local Control and Global State Information

Bora Yongacoglu, Gürdal Arslan, Serdar Yüksel

arXiv:1903.05812v4math.OC

TL;DR

In dynamic multi-agent learning, nonstationarity and slow, noisy policy evaluation make formal guarantees difficult to transfer from single-agent and repeated-game settings. The paper presents a decentralized algorithm using local information and adaptive cost estimates; it guarantees probabilistic convergence to team-optimal policies without control sharing. Its scope includes stochastic teams as a special case of stochastic common-interest games, but assumes agents observe the full state.

  • Problem

    In multi-agent learning, nonstationarity prevents single-agent theoretical guarantees from carrying over, while dynamic games make policy evaluation slow and noisy.

    Source: §I · p. 1, §II · p. 3

  • Method

    The algorithm uses local costs, local action histories, and common state, with a finite window of noisy aggregate-cost scores to estimate each decision maker’s lowest possible cost.

    Source: A. Contributions · p. 2

  • Results

    The algorithm has probabilistic convergence guarantees for team-optimal policies in stochastic common-interest games, without control sharing.

    Source: A. Contributions · p. 2

  • Takeaways & Limitations

    Because stochastic teams are a special case of stochastic common-interest games, the convergence result also covers stochastic teams.

    Source: A. Contributions · p. 2

    The analysis assumes full state observations; learning with only local state information is left for future research.

    Source: §VIII · p. 12

Abstract

from arXiv · show

Stochastic dynamic teams and games are rich models for decentralized systems and challenging testing grounds for multi-agent learning. Previous work that guaranteed team optimality assumed stateless dynamics, or an explicit coordination mechanism, or joint-control sharing. In this paper, we present an algorithm with guarantees of convergence to team optimal policies in teams and common interest games. The algorithm is a two-timescale method that uses a variant of Q-learning on the finer timescale to perform policy evaluation while exploring the policy space on the coarser timescale. Agents following this algorithm are "independent learners": they use only local controls, local cost realizations, and global state information, without access to controls of other agents. The results presented here are the first, to our knowledge, to give formal guarantees of convergence to team optimality using independent learners in stochastic dynamic teams and common interest games.

I. INTRODUCTION

The paper addresses the difficulty of guaranteeing team-optimal behavior when agents learn independently in stochastic, stateful settings. It presents algorithms for stochastic common-interest games with formal team-optimality guarantees and no action sharing.

I. INTRODUCTION

  • MARL has relatively few formal results because interacting learners make the environment non-stationary, so single-agent theoretical guarantees do not carry over.With random state dynamics, policy evaluation is slow, noisy, and algorithm-dependent, complicating extensions of repeated-game methods.Source: §I · p. 1, §II · p. 3

A. Contributions

  • Theorem 1’s algorithm uses local cost and local action history plus the common state, and converges to a team-optimal policy in a probabilistic sense.Theorem 2 treats weakly acyclic games, while Theorem 3 uses constant, preset aspiration levels and requires those levels to separate team-optimal policies from other policies.Source: A. Contributions · p. 2

II. LITERATURE REVIEW

  • Prior independent-learning guarantees include deterministic state dynamics and costs, while most cited Q-learning variants offer empirical rather than formal team-optimality guarantees.The literature review distinguishes these results from methods for repeated games, where state dynamics are absent and scalar costs can directly set aspiration or baseline levels.Source: §II · pp. 2–3
  • The studied information structure gives every agent full state information but no access to other agents’ actions.The paper notes applications where a global sensor broadcasts state to separate controllers, including microair-jet control and robotics.Source: §II · p. 3

A. Contributions

  • The paper modifies an independent learner to guarantee convergence to team optimality when possible, without control sharing among agents.The algorithm uses local cost and local action history with the common state; the paper presents separate guarantees for common-interest games, weakly acyclic games, and constant-aspiration variants.Source: A. Contributions · p. 2, §II · p. 4

A. Stationary Markov Decision Problems and Q-learning

The section introduces the stationary MDP setting behind Q-learning, then extends the setup to stochastic games in which agents’ costs depend on joint actions. It motivates decentralized learning of team-optimal policies without control sharing.

A. Stationary Markov Decision Problems and Q-learning

  • In a stationary MDP, the decision maker observes state, action, cost, and next-state feedback and seeks a policy minimizing discounted cost from every initial state.The paper restricts attention to stationary deterministic policies without loss of optimality.Source: A. Stationary Markov Decision Problems… · p. 4
  • Standard Q-learning can recover optimal policies under suitable visitation and step-size conditions, but its guarantee depends on system stationarity.When feedback is not generated by the same Markovian source, convergence to optimal Q-factors is not guaranteed.Source: A. Stationary Markov Decision Problems… · p. 4

B. Stochastic Games and Decentralized Q-learning

  • The objective is a decentralized algorithm that provably leads agents in common-interest games to team-optimal policies without control sharing.The proposed algorithm adapts exploration phases and baseline-policy updates to exploit Q-factor structure in teams and common-interest games.Source: B. Stochastic Games and Decentralized… · pp. 5–6

IV. LEARNING TEAM OPTIMALITY

The section introduces an idealized policy-update procedure as a proof device for learning team optimality. Agents mix random exploration with condition-dependent updates, including inertial best-responding when the joint policy is team optimal.

IV. LEARNING TEAM OPTIMALITY

  • The Idealized Update Procedure defines a Markov chain over joint stationary deterministic policies, but is not implementable under the decentralized information structure.The chain is used in approximation arguments for the main results.Source: §IV · p. 6
  • Inertia can prevent perpetual cycling between joint policies when agents switch to best replies simultaneously.The example identifies cycling between (1, 2) and (2, 1) when both players switch at each step.Source: §IV · p. 6
  • Under the procedure, agents combine uniform random experimentation with inertial best-responding at team-optimal policies and a selected stochastic-kernel update otherwise.The policy-update rule is condition-dependent on whether the current joint policy is team optimal.Source: §IV · p. 6

1 Set Parameters

The section motivates independent learning through an idealized update procedure and specifies how agents explore and update policies. Its guarantee depends on experimentation being sufficiently rare relative to exploration when policies are not team optimal.

10 end

  • The procedure favors moving away from non-team-optimal joint policies by requiring more exploration there than at team-optimal policies.The specified condition is κ_i ≫ γ_i when the joint policy is not team optimal.Source: §10 · p. 6
  • Under the idealized procedure, sufficiently small positive experimentation probabilities relative to nonoptimal-policy exploration yield arbitrarily high long-run probability of choosing a team-optimal policy.The claim applies to common-interest games and permits arbitrary update kernels in the stated lemma.Source: §10 · pp. 6–7
  • Each decision maker can run its own algorithm using its control, cost realization, and next state, without observing other agents’ controls or policies.The paper calls this implementation independent learning.Source: §10 · p. 7

32 end

The discussion explains the algorithm’s two-timescale structure and why aspiration levels and continued policy-space experimentation matter. It also relates fixed baseline policies within each exploration phase to policy evaluation as a stationary MDP.

Discussion

  • Q-factors are updated at the faster stage-game timescale, while best-reply estimation, cost-score comparisons, and baseline-policy updates occur at exploration-phase boundaries.The policy updates are discrete rather than incremental; Q-learning step sizes are reset between exploration phases.Source: Discussion · p. 8
  • Fixed baseline policies make each exploration phase stationary from an agent’s perspective, equivalent to an MDP determined by the other agents’ policies.Under the stated assumptions, Q-learning within a phase can yield informative Q-factors for recovering best replies.Source: Discussion · p. 8
  • Policy evaluation in dynamic stochastic games is slow and noisy, making aspiration levels harder to set than in repeated games without state dynamics.In repeated games, scalar cost realizations can directly inform aspiration levels or baseline costs.Source: Discussion · p. 8
  • A finite window of recent cost scores helps discard unattainable aspiration levels caused by noisy Q-factor estimates.The method uses the minimum recent score within a tolerance rather than the minimum over the entire past.Source: Discussion · p. 8
  • Continued experimentation is needed both when agents meet their aspiration levels and when they do not, to avoid settling on nonoptimal policies and to search for team-optimal ones.The risk of settling follows from finite-window aspiration updates and potentially suboptimal aspiration levels.Source: Discussion · p. 8
  • The approximate best-reply sets computed during each exploration phase contain only stationary deterministic policies.Their size is bounded by the number of stationary deterministic policies available to the decision maker.Source: Discussion · p. 8

V. BEYOND TEAM OPTIMALITY: APPLICATION TO WEAKLY ACYCLIC GAMES

The section extends the algorithm’s guarantees to weakly acyclic games: a special-case update rule leads to equilibrium policies, and common-interest games allow equilibrium policies to be replaced by team-optimal policies.

V. BEYOND TEAM OPTIMALITY: APPLICATION TO WEAKLY ACYCLIC GAMES

  • Weak acyclicity requires a multi-DM strict best-reply path from every deterministic joint policy to a deterministic equilibrium policy.The paper’s notion is defined for stationary deterministic policies in stochastic games.Source: §V · p. 8
  • The IUP is a perturbed inertial best-reply dynamic when agents use the specified policy-update kernels.In weakly acyclic games, inertial best-reply dynamics lead to equilibrium policies.Source: §V · p. 9
  • With small experimentation probabilities, the IUP leads to equilibrium policies in the long run, and this behavior supports the Algorithm 2 result.The section uses this IUP property to establish the same long-run behavior for Algorithm 2 under Assumptions 1–3.Source: §V · p. 9
  • Earlier weakly acyclic-game algorithms assigned high long-run probability to equilibria but did not guarantee team optimality in teams or common-interest games.The section presents its result as strengthening that earlier guarantee.Source: §V · p. 9
  • In weakly acyclic common-interest games, Theorem 2 allows the equilibrium-policy set to be replaced by the team-optimal-policy set.The theorem’s guarantee is subject to its stated assumptions and parameter conditions.Source: §V · p. 9

VI. LEARNING WITH CONSTANT ASPIRATIONS

Algorithm 3 uses constant, preset aspiration levels rather than Algorithm 2’s adaptive levels. Its stated behavior depends on whether aspiration-achieving policies exist and on how they relate to strict best replies.

VI. LEARNING WITH CONSTANT ASPIRATIONS

  • Algorithm 3 keeps each decision-maker’s aspiration level Λi constant across exploration phases.The preset levels are motivated by prior knowledge of a conservative estimate of achievable cost, potentially from experience or initial experimentation.Source: §VI · p. 9
  • If some joint policies meet every decision-maker’s aspiration while all other policies fail at least one, Algorithm 3 almost surely outperforms the aspiration levels in the long run.The paper gives a common-interest game with aspirations between dominant and other costs as an example.Source: §VI · p. 9
  • Unlike Algorithm 3’s preset levels, Algorithm 2 adapts aspirations and achieves optimal performance only in common-interest games, in the weaker sense of eventually assigning arbitrarily high probability to optimal policies.Source: §VI · p. 9
  • Algorithm 3 also characterizes long-run behavior in general games, where likely policy sets are closed under multi-agent strict best replies and reduce to equilibrium policies in weakly acyclic games.The section describes this characterization as analogous to, and more general than, Algorithm 2’s weakly acyclic result.Source: §VI · pp. 9–10

1 Set Parameters

  • The parameter-setting instructions use common phase lengths, initialize each decision-maker’s policy and learning variables, advance exploration phases, and receive local cost feedback.Source: §1 · p. 10

33 end

The section defines cumber sets to characterize Algorithm 3’s long-run behavior under constant aspirations. Depending on the aspiration set and the game’s strict-best-reply structure, play may approach aspiration-achieving policies or minimal cumber sets.

33 end

  • A cumber set is closed under multi-DM strict best replies, and it is minimal when it contains no smaller cumber set.The section also defines the corresponding Λ-cumber set using aspiration levels.Source: §33 · p. 10
  • If all policies either meet every decision-maker’s aspiration or fail at least one, Algorithm 3 converges almost surely to an aspiration-achieving joint policy.This stated case also assumes agents stay with their policy when they assess that their aspiration is achieved.Source: §33 · p. 11
  • When aspiration-achieving policies form a cumber set, Algorithm 3 converges almost surely to a minimal cumber set within those policies.The stated result assumes sufficiently long exploration phases; the discussion notes that oscillations within such a set are not ruled out.Source: §33 · p. 11
  • In a weakly acyclic game, convergence to an aspiration-achieving equilibrium is guaranteed; in teams, this implies convergence to an optimal policy when aspiration levels lie between suboptimal and optimal equilibrium costs.Source: §33 · p. 11
  • If aspiration-achieving policies are not a cumber set, agents can leave that set through multi-DM strict best replies, and the convergence result may fail.Source: §33 · p. 11
  • In general games, small experimentation probabilities make policies in minimal Λ-cumber or minimal cumber sets likely in the long run, but aspirations need not be consistently achieved.The Λ-cumber result uses stay-on-achievement and inertial best replies otherwise; the cumber-set result uses inertial best replies throughout.Source: §33 · p. 11

VII. A SIMULATION STUDY

The simulation finds that lower experimentation probability increases the frequency of team-optimal joint policies, exceeding 90% at γ = 0.001. The paper concludes that its algorithms achieve team optimality without action sharing, while its analysis assumes full state observations.

VII. A SIMULATION STUDY

  • The simulation uses two DMs with binary state and control spaces and common discount factor β = 0.8.The stage costs are specified in Figure 3; the supplied passages describe row and column choices and assign each DM the corresponding entry in a cell.Source: §VII · p. 11, Figure 3 · p. 11
  • For sufficiently large discount factors, including β = 0.8, matching both DMs’ controls to the state is uniquely team optimal, although three suboptimal equilibrium policies also exist.At state 2, the simulation frames a choice between cost 10 with likely continued high cost and cost 13 with hopes of reaching the low-cost state.Source: §VII · pp. 11–12
  • At γ = 0.001, joint policies are team optimal for more than 90% of the time, and optimal-policy frequency increases as γ decreases.The authors say these numerical results confirm the theoretical results.Source: §VII · p. 12

VIII. CONCLUDING REMARKS

  • The conclusion presents algorithms for stochastic teams and common-interest games that achieve team optimality without players sharing actions during play and with limited prior game information.The proof approach approximates the joint policy-valued stochastic process with time-homogeneous Markov chains using Dobrushin-coefficient analysis.Source: §VIII · p. 12
  • The results assume full state observations for every agent; partial observations of local state remain a future research direction.The authors say they chose full observation because formal multi-agent learning results are scarce even under that simplifying assumption.Source: §VIII · p. 12

APPENDIX A: PROOF OF THEOREM 1

The proof establishes convergence by relating the policy process to a Markov chain with a unique invariant distribution. It controls deviations from that chain using exploration, reliable Q-factor estimates, and sufficiently long exploration phases.

APPENDIX A: PROOF OF THEOREM 1

  • A stochastic matrix with positive Dobrushin coefficient has a unique invariant probability vector, and repeated application converges to it from any initial probability vector.The proof then bounds the effect of using matrices that differ from the fixed matrix.Source: Appendix A · p. 12
  • Uniform randomization with strictly positive probability gives every policy transition positive probability, yielding a positive Dobrushin coefficient for the induced policy-update matrix.The proof uses this property to establish convergence of the policy process.Source: Appendix A · pp. 12–13
  • The proof controls deviations from the target policy-transition matrix by requiring high-probability events for reliable Q-factors, accurate cost estimates, and recent visits to an optimal baseline policy.These conditions jointly define the event R_k used to bound transition-matrix deviations.Source: Appendix A · p. 13
  • Within each exploration phase, the other agents’ baseline policies make each learner’s environment a stationary finite MDP, and sufficiently long phases bring Q-factors near their limits with arbitrarily high probability.The proof uses this Q-learning behavior to establish the required high-probability events.Source: Appendix A · p. 13

APPENDIX B: PROOF OF THEOREM 2

The proof of Theorem 2 applies Theorem 1’s convergence result under parameter choices that meet its hypotheses. It concludes the desired result for weakly acyclic games.

APPENDIX B: PROOF OF THEOREM 2

  • By [2, Lemma 4], there exists T_ε ∈ N+ such that the condition uses T_k ≥ T_ε, so equality is included rather than requiring strict exceedance.Source: Appendix B · p. 14
  • The proof concludes that the desired result for weakly acyclic games follows from its stated bounds and that the chosen parameters satisfy Theorem 1’s hypotheses.It therefore also invokes Theorem 1’s results for those parameter choices.Source: Appendix B · p. 14

APPENDIX C: PROOF OF THEOREM 3

The proof uses randomized policy updates and sufficiently long exploration phases to establish almost-sure eventual membership in the stated policy set. It also bounds repeated visits outside designated subsets.

APPENDIX C: PROOF OF THEOREM 3

  • The proof assumes randomized policy updates with probability ρ_i and exploration phases at least as long as the specified finite thresholds.It uses these parameter and phase-length conditions in the subsequent probability bounds.Source: Appendix C · p. 14
  • The proof states that the sum of probabilities of visiting Π_Λ ∩ Π_cumber after the specified interval is finite.The passage gives this bound for every starting index k.Source: Appendix C · p. 15
  • With probability one, the policy sequence is outside Π_Λ ∩ Π_cumber only finitely often.This is the stated result in the proof passage.Source: Appendix C · p. 15

Related papers

Loading 1903.05812v4…