PaperlayerView exact revision on arXiv

Source-linked AI summary

Online Reinforcement Learning in Stochastic Games

Chen-Yu Wei, Yi-Te Hong, Chi-Jen Lu

arXiv:1712.00579v1cs.LG

TL;DR

Online learning in average-reward stochastic games must contend with an opponent whose behavior can be arbitrary and non-stationary. UCSG uses an optimism-based approach and a stationary-policy replacement in its analysis. The paper reports improved regret bounds over prior work in the same setting and an offline average-reward sample-complexity result.

  • Problem

    In stochastic games, an online learner faces an uncontrollable, potentially non-stationary opponent, which makes MDP analyses based on stationary-distribution perturbations inapplicable.

    Source: §1 · p. 2

  • Method

    UCSG uses optimism-based reinforcement learning and replaces the opponent’s non-stationary policy with a stationary one in its regret analysis.

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

  • Results

    UCSG significantly improves R-MAX’s regret bounds in a similar average-reward stochastic-game setting and can output its current best stationary policy during learning.

    Source: §1 · p. 2

  • Takeaways & Limitations

    The paper also establishes an offline average-reward sample-complexity bound of order O~(poly(1/ε)) using an asymmetric approach that finds one player’s worst-case optimal policy at a time.

    Source: §1 · p. 2

    The guarantees rely on diameter assumptions; the stronger Assumption 1 requires every state to be visited within an average of D steps under any players’ policies.

    Source: §3 · p. 4

Abstract

from arXiv · show

We study online reinforcement learning in average-reward stochastic games (SGs). An SG models a two-player zero-sum game in a Markov environment, where state transitions and one-step payoffs are determined simultaneously by a learner and an adversary. We propose the UCSG algorithm that achieves a sublinear regret compared to the game value when competing with an arbitrary opponent. This result improves previous ones under the same setting. The regret bound has a dependency on the diameter, which is an intrinsic value related to the mixing property of SGs. If we let the opponent play an optimistic best response to the learner, UCSG finds an $\varepsilon$-maximin stationary policy with a sample complexity of $\tilde{\mathcal{O}}\left(\text{poly}(1/\varepsilon)\right)$, where $\varepsilon$ is the gap to the best policy.

1 Introduction

Stochastic games model simultaneous multi-agent interaction in Markov environments, and this paper studies online learning when a learner faces an arbitrary opponent. It presents improved regret results for average-reward games and a technique for analyzing the opponent’s non-stationary behavior.

1 Introduction

  • Stochastic games extend MDPs to simultaneous multi-agent interaction with jointly determined transitions and rewards, making them suitable for modeling MARL.The paper focuses on two-player zero-sum games, where one player maximizes reward and the other minimizes it.Source: §1 · p. 1
  • In online learning, the learner controls one player and faces an arbitrary opponent, whereas offline learning centrally controls both players to find the game equilibrium.Online work evaluates regret against a benchmark that may use optimal policies for both players or the learner’s best stationary response to the opponent.Source: §1 · pp. 1–2
  • The paper gives an offline average-reward sample-complexity bound of order O~(poly(1/ε)), addressing settings where discounted rewards may be unsuitable for long-term planning.Its asymmetric approach finds one player’s worst-case optimal policy at a time and extends a two-stage-game method.Source: §1 · p. 2
  • For online average-reward stochastic games, UCSG significantly improves the regret bounds of R-MAX under a similar scenario and regret definition.UCSG can output its currently best stationary policy during learning, unlike R-MAX’s Tε-step fixed-horizon policy.Source: §1 · p. 2
  • UCSG adapts optimism-based MDP reinforcement learning by replacing the opponent’s non-stationary policy with a stationary one in its analysis, enabling perturbation analysis.The authors say the replacement costs some constant regret and facilitates regret bounding.Source: §1 · p. 2
  • Unlike the robust-MDP setting of, the learner here must learn worst-case transitions and rewards while arbitrary opponent actions may hinder that learning.The authors describe their contribution and ’s as orthogonal.Source: §1 · p. 2

2 Preliminaries

The preliminaries define the game and policy notation, then introduce average reward and the bias vector. The bias captures relative state advantage and its span relates to the difficulty of learning.

2 Preliminaries

  • A stochastic game is represented as a model M=(S,A,r,p), with joint action space A=A1×A2; policies may depend on the full history or only the current state.Joint policies are denoted by π.Source: §2 · pp. 2–3
  • The average reward is the limiting expected total reward per step when the limit exists, and the game value exists.When the value is independent of the initial state, the notation omits that state.Source: §2 · p. 3
  • The bias vector measures accumulated reward relative to average reward, and differences between its state coordinates represent relative state advantage under a policy.The span sp(h) is the maximum coordinate minus the minimum; large span means visiting a bad state is costly during learning and regret can depend on it.Source: §2 · p. 3
  • In stochastic games, the sup and inf defining the game value need not be attained, and players may lack stationary optimal policies.This contrasts with the one-player MDP case.Source: §2 · p. 3

3 Problem Settings and Results Overview

The section defines diameter assumptions that support online regret guarantees and considers both competing against an arbitrary opponent and finding a maximin policy offline. Under a regret bound, running UCSG long enough ensures some policy is ε-optimal.

3 Problem Settings and Results Overview

  • Assumption 2 ensures the learner can reach any state within bounded time regardless of the opponent's policy, preventing a lock-in scenario from causing linear regret.The motivation is that the learner may otherwise enter a bad state before learning to avoid it.Source: §3 · p. 4
  • Assumption 1 is stronger: under any player policies, every state is visited within an average of D steps, and this condition improves asymptotic regret.The passage compares its visitation property to the infinite-visitation requirement used in Q-learning-type algorithms [18].Source: §3 · p. 4

3.1 Two Settings and Results Overview

  • In the online setting, Player 1 competes against an arbitrary Player 2; offline, the learner controls both players to find Player 1's maximin policy.The section focuses mainly on the more challenging online setting and defers offline discussion.Source: §3.1 · p. 4
  • When T exceeds the bound on Lε, some policy played at a time t is ε-optimal.Lε counts rounds when the policy's worst-case reward is more than ε below the game value.Source: §3.1 · p. 4
  • Theorem 3.1 states that, under Assumption 1, UCSG achieves Reg(on); Theorem 3.2 states that, under Assumption 2, UCSG achieves Reg(on).Source: §3.1 · p. 4

4 Upper Confidence Stochastic Game Algorithm (UCSG)

UCSG extends UCRL2 by using optimism to balance exploration and exploitation, updating the learner’s policy in data-dependent phases. It plans over confidence-supported game models, and its Extended SG construction enables MAXIMIN-EVI.

4 Upper Confidence Stochastic Game Algorithm (UCSG)

  • UCSG extends UCRL2, using optimism to balance exploitation and exploration while changing the learner’s policy in phases.Phase lengths depend on past observations.Source: §4 · p. 5
  • At each phase’s start, empirical transition frequencies define confidence regions and plausible models; the learner then optimistically selects a model and policy against the most adversarial opponent.The confidence regions are built from observations in previous phases.Source: §4 · p. 5
  • The learner executes its phase policy until some state-action pair’s occurrence count doubles, with phase counts reset at the start of each phase.This observation-dependent stopping rule makes phase lengths variable.Source: §4 · p. 5

4.1 Extended SG and Maximin-EVI

  • The Extended SG represents each admissible transition choice as a learner action while preserving its reward, enabling value iteration with a Schweitzer transform in MAXIMIN-EVI.The construction embeds the true model when it belongs to the confidence-model set.Source: §4.1 · pp. 5–6
  • With high probability, the true model belongs to the confidence-model set in every phase.The analysis uses this inclusion in most of its arguments.Source: §4.1 · p. 6

5 Analysis under Assumption 1

The analysis combines techniques from one-player MDPs with tools for handling non-stationary opponents. Under Assumption 1, it bounds the number of non-benign phases and uses perturbation analysis to address a bias-span bound that does not carry over directly from one-player MDPs.

5 Analysis under Assumption 1

  • The analysis imports one-player MDP techniques and develops methods for non-stationary opponents.The opponent may use a history-dependent randomized policy.Source: §5 · p. 6

5.1 Bounding P

  • A stationary opponent policy replaces the non-stationary policy in the analysis, at a constant regret cost, to enable perturbation analysis.The replacement policy is imaginary and used only in the analysis.Source: §5 · p. 6, §5.1 · p. 7
  • Unlike the one-player case, the two-player bias span need not be bounded by D, so the analysis uses mean-first-passage-time perturbation analysis.The section identifies bounding the bias-vector span as a main ingredient of regret analysis.Source: §5.1 · p. 7
  • Under Assumption 1, each stationary policy pair induces an irreducible Markov chain with a unique stationary distribution.Source: §5 · p. 6, §5.1 · p. 7
  • With high probability, the number of non-benign phases is at most ˜O(D^3S^5A).Source: §5.1 · p. 7

6 Analysis under Assumption 2

Under Assumption 2, the analysis approximates the average-reward game with repeated finite-horizon stochastic games. It then draws on episodic-MDP analysis to bound the resulting regret terms.

6 Analysis under Assumption 2

  • The proof approximates the average-reward game value over T steps by the sum of H-step episodic game values, then uses episodic-game sample-complexity results to bound regret.The horizon H is used in the analysis, not by UCSG itself.Source: §6 · p. 8
  • Approximating the infinite-horizon game with repeated H-step games introduces an error term, and phase boundaries can leave up to two incomplete episodes.Source: §6 · p. 8
  • The analysis reuses [9]’s episodic-MDP results, whose PAC bounds hold for arbitrarily selected ε.The passage says the input ε can be removed without affecting those bounds.Source: §6 · pp. 8–9

7 Sample Complexity of Offline Training

The offline UCSG analysis gives a sample-complexity guarantee and an ε-optimal stationary policy output guarantee. Its phase-wise procedure selects optimistic policies and uses extended value iteration.

7 Sample Complexity of Offline Training

  • In each phase, both players select optimistic policies, and Player 2’s policy is obtained by extended value iteration under fixed Player 1 policy.The value iteration is performed on an extended MDP.Source: §7 · p. 9
  • Under Assumption 1, UCSG achieves Lε = ˜O(D^3S^5A + D^2S^2A/ε^2) with high probability.Source: §7 · p. 9
  • If offline UCSG runs for T > Lε steps, it can output a single ε-optimal stationary policy for Player 1.Source: §7 · p. 9

8 Open Problems

The section covers unresolved questions about regret bounds and learnability under weaker diameter assumptions, as well as an iterative construction for a discounted stochastic game and its limiting behavior as the discount factor approaches one.

8 Open Problems

  • The authors leave improving both the asymptotic and constant terms of their regret bounds as an open problem, with lower bounds inheritable from one-player MDPs.The supplied passage truncates the lower-bound expression, so no rate is reported here.Source: §8 · p. 9
  • With only the weaker diameter assumption, sublinear online regret is generally impossible, but cooperative exploration may permit polynomial-time offline sample complexity.The weaker condition is max over state pairs of the minimum, over both players’ policies, of the expected hitting time being at most D.Source: §8 · p. 9

A Previous Bounds for MDPs and SGs

  • R-MAX learns stochastic games against arbitrary opponents but requires ε and the ε-return mixing time Tε in advance; unlike R-MAX, this paper’s algorithm outputs a stationary policy.The passage characterizes Tε as resembling the paper’s diameter assumption.Source: A Previous Bounds for MDPs and SGs · pp. 12–13

C Perturbation Bounds for Markov Chains

  • The analysis uses perturbation bounds for mean first passage times, in addition to stationary-distribution perturbation bounds, to obtain a tighter regret bound.The passage says perturbation analysis studies how small transition-probability changes affect stationary distributions or mean first passage times.Source: C Perturbation Bounds for Markov Chains · p. 13

D Lemmas for Failing Events

  • Confidence-set updates are bounded by SA log2 T, and a union bound yields that all confidence events hold with probability at least 1 − δ.The update count and confidence-event bounds are combined using Lemmas D.1–D.3.Source: D Lemmas for Failing Events · p. 16

E Lemmas for Stationary Optimal Policies

  • Under the stated continuity and Assumption 2 conditions, the stochastic game has maximin stationary policies attaining an initial-state-independent game value and a bounded function satisfying the Bellman equation.The passage states this result for countable state spaces and compact metric joint action spaces.Source: E Lemmas for Stationary Optimal Policies · p. 16
  • The construction initializes v0 ≡ 0 and iteratively updates values for a game with 0 < γ < 1 and 0 < α < 1.The update expression is truncated in the passage.Source: E Lemmas for Stationary Optimal Policies · p. 18
  • As α_k approaches 1, diagonalization and Lebesgue convergence yield a bounded function h and a constant ρ* with v_αk(·) converging to h(·).The passage also begins a limit involving (1 − α_k)V*, but its conclusion is truncated.Source: E Lemmas for Stationary Optimal Policies · p. 18

F MAXIMIN-EVI and Its Convergence

Under Assumption 2, MAXIMIN-EVI’s value iteration converges and yields a γ-optimal policy with value-vector span bounded by D. The proof of Lemma 5.2 uses action partitions based on importance and knownness to control transition-estimation error.

F MAXIMIN-EVI and Its Convergence

G Proof of Lemma 5.2

  • The Lemma 5.2 proof borrows techniques from and to bound steps with inaccurate transition estimates, including for history-dependent policies.The policy history is represented by Ht inside the time index.Source: G Proof of Lemma 5.2 · p. 19
  • Importance and knownness partition actions by selection probability and estimate accuracy; when each partition is small enough, plausible models’ transition probabilities differ from the true probabilities by at most ε.Larger knownness indicates a lower likelihood that an action contributes to inaccurate transition estimation.Source: G Proof of Lemma 5.2 · pp. 19–20

G.1 Proof of Lemma G.1

The proof of Lemma G.1 bounds how often state-action pairs can be sampled within importance-knownness partitions, then sums those bounds across actions. The following proof uses the confidence-set definition and Cauchy’s inequality.

G.1 Proof of Lemma G.1

  • For κ > 0, a state-action pair’s samples within a (κ, ι) partition are bounded conservatively by 6mκιwmin as knownness increases.The count bound follows because sampling increments the count, while UCSG updates it at phase changes.Source: §G.1 · p. 20
  • For κ = 0, samples in a (κ, ι) partition are bounded by 4mιwmin.The proof combines this case with the κ > 0 count bound.Source: §G.1 · p. 20
  • Summing the partition-count bound over actions yields the statement of Lemma G.1.The proof sketch links partition sampling frequency to a bound on how long partition sizes can remain large.Source: §G.1 · p. 20

G.2 Proof of Lemma G.2

  • The Lemma G.2 proof invokes the confidence-set definition and Cauchy’s inequality to obtain its desired bound.The proof identifies the effective κ and ι partitions in the summation.Source: §G.2 · p. 21

H Proofs of Lemma 5.1 and 5.3

This section proves Lemmas 5.1 and 5.3 using state-visit concentration, Markov-chain perturbation, discretized concentration bounds, and Bellman and dynamic-programming inequalities. It also includes a proof passage that sets i = H and states a lower-bound relation for ρ*(M+).

H Proofs of Lemma 5.1 and 5.3

  • A state is visited with probability at least 1/2 in each 2D interval, enabling concentration and a union bound over time frames and phases.The proof applies the interval bound to phases and sums the resulting estimates to establish the lemma’s bound.Source: H Proofs of Lemma 5.1 and 5.3 · p. 22

H.1 Proof of Lemma H.2

  • The stationary distribution of the empirical transition model is compared with the true chain’s distribution through transition-probability perturbation bounds.The proof uses an irreducible modified empirical model whose stationary distribution equals the empirical state distribution, and bounds the steps where transition estimates are insufficiently close.Source: §H.1 · pp. 22–23

H.2 Proof of Lemma H.3

  • Markov-chain perturbation bounds show that sufficiently accurate transition estimates preserve a bounded span, while phases with larger errors are controlled by counting their steps.The proof uses a transition-error threshold of 1/(8DS^2) and derives a span bound of 2D.Source: §H.2 · pp. 24–25

J Proofs of Lemma 6.1 and 6.2

  • Under Assumption 2, the dynamic-programming iterate satisfies ui(s) ≥ i(rho*(M+) − gamma) − D for every state s.The argument fixes the learner’s policy and lets the opponent run an H-step stochastic game after value iteration halts.Source: J Proofs of Lemma 6.1 and 6.2 · p. 28
  • The proof sets i = H and states that ρ*(M+) is at least a minimum-response value for M1.The supplied formula is truncated after ρ(M1, so the full right-hand side is unavailable.Source: J Proofs of Lemma 6.1 and 6.2 · p. 28

K Proof of Theorem K.1 and Lemma 6.3

The proof partitions state-joint-action pairs by importance and knownness, adapting the indices to episodes in the non-episodic setting. It establishes episode-level approximation bounds and explains how UCSG obtains PAC guarantees without requiring ε as an input.

K Proof of Theorem K.1 and Lemma 6.3

  • The analysis partitions state-joint-action pairs by importance, their relative occurrence frequency, and knownness, the ratio of observations to occurrence frequency.The partitions are defined for each episode in the state-joint-action space.Source: K Proof of Theorem K.1 and Lemma 6.3 · p. 29
  • Unlike the episodic setting, initial states in the non-episodic setting may be sampled from different distributions across episodes.Here those distributions matter for computing expected state-joint-action frequencies.Source: K Proof of Theorem K.1 and Lemma 6.3 · p. 29
  • Importance and knownness are indexed by episode because the opponent may use different policies across episodes.Source: K Proof of Theorem K.1 and Lemma 6.3 · p. 29
  • UCSG needs only δ as an input and has (ε, δ)-PAC bounds for arbitrarily selected ε, though ε cannot tend to zero too quickly in the analysis.The proof gives a lower limit on ε through its bound on the number of κ values.Source: K Proof of Theorem K.1 and Lemma 6.3 · p. 30
  • At scale j, at most ˜O(4^j S^2 A) episodes are not (2^-j H)-optimal with probability at least 1 − δ0.The proof invokes the bound logarithmically many times and applies a union bound to obtain regret.Source: K Proof of Theorem K.1 and Lemma 6.3 · p. 30

L Proofs for Offline Training Complexity

The offline-training proof derives a ˜O(DS^2A/ε^3) sample-complexity bound and an observable rule for selecting a stationary policy. The accompanying technical lemmas and regularization discussion add structural bounds while noting practical and asymptotic limits of the latter approach.

L Proofs for Offline Training Complexity

  • The algorithm can select the phase with the smallest observable regret upper bound, and the proof guarantees a phase whose bound is below ε.The per-phase bound is available to the algorithm and is used to select a stationary policy.Source: L Proofs for Offline Training Complexity · p. 32
  • Setting H = D/(2ε) gives the dominating sample-complexity bound ˜O(DS^2A/ε^3).The proof obtains the bound by substituting this H into the preceding sample-complexity estimate.Source: L Proofs for Offline Training Complexity · p. 32

M Other Technical Lemmas

  • Under Assumption 1, stationary-policy bias span is at most Tπ(M); an absorbing-state MDP represents maximum first-passage time as maximum reward achievable by stationary joint policies.The MDP construction leaves transitions from states other than the absorbing state unchanged, assigns them reward 1, and assigns reward 0 to the absorbing state.Source: M Other Technical Lemmas · p. 33

N Regularization/Constraint-based Approach for Assumption 1

  • When D is known, constrained or regularized model selection can improve the ˜O(D^3S^5A) additive term, but no practical solver is known and asymptotic performance is unchanged.The true model remains in the feasible set of the constrained optimization problem.Source: N Regularization/Constraint-based… · p. 33
Loading 1712.00579v1…