Paper deep dive
Fully Online Decentralized Learning in Stochastic Games with Unknown Independent Chains
S. Rasoul Etesami
Intelligence
Status: succeeded | Model: Gemma-4-26B-A4B | Prompt: intel-v1 | Confidence: 93%
Last extracted: 10/2/2026, 8:22:41 AM
Summary
This paper presents a fully online, decentralized, and uncoordinated mirror-descent algorithm for learning stationary Nash equilibrium policies in n-player stochastic games with independent controlled chains and unknown transition kernels. The algorithm operates in the dual space of occupancy measures, using only local state and payoff observations without requiring synchronized episodes or joint state space coverage. It achieves a time-averaged fixed-comparator regret decay rate of O~(T^{-1/2}) and provides an approximate coarse-correlated-equilibrium guarantee. Under a global variational-stability condition, the algorithm converges asymptotically to a stationary epsilon-Nash equilibrium.
Entities (7)
Relation Signals (5)
S. Rasoul Etesami → affiliatedwith → University of Illinois Urbana-Champaign
confidence 95% · Affiliation: Department of Industrial and Systems Engineering... University of Illinois Urbana-Champaign
Stochastic Games → hasproperty → Independent Controlled Chains
confidence 95% · stochastic games with independent controlled chains
Mirror-Descent Algorithm → solves → Stochastic Games
confidence 95% · We develop a fully online, decentralized, and uncoordinated mirror-descent algorithm... for stochastic games with independent controlled chains
Mirror-Descent Algorithm → convergesto → Nash Equilibrium
confidence 90% · converges asymptotically in the last iterate to a stationary epsilon-NE
Mirror-Descent Algorithm → uses → Occupancy Measures
confidence 90% · operates in the dual space of occupancy measures
Cypher Suggestions (0)
No Cypher suggestions yet.
Abstract
Abstract: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.
Tags
Links
- Source: https://arxiv.org/abs/2610.01181v1
- Canonical: https://arxiv.org/abs/2610.01181v1
Trouble viewing inline? Open PDF directly →
Full Text
181,582 characters extracted from source content.
Expand or collapse full text
Fully Online Decentralized Learning in Stochastic Games with Unknown Independent Chains S. Rasoul Etesami etesami1@illinois.edu Affiliation: Department of Industrial and Systems Engineering, Coordinated Science Laboratory Affiliation: University of Illinois Urbana-Champaign, Urbana, IL, USA 61801 Abstract We consider stochastic games with independent controlled chains and unknown transition kernels, in which players observe only their own 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, allows players to update using only local information, and requires neither coverage of the joint state space nor synchronized episodes. Under standard uniform-ergodicity and finite-coverage assumptions, we show that, with high probability, the time-averaged fixed-comparator regret decays at the canonical ~(T−1/2) 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 on that of the product state space, thereby avoiding exponential dependence on the number of players and the sizes of the joint state and action spaces. We further show that the resulting finite-time regret bound provides an approximate coarse-correlated-equilibrium guarantee. Such a guarantee is natural for arbitrary reward functions, since, in this setting, computing a stationary ϵε-Nash equilibrium (ϵε-NE) is known to be PPAD-hard. Under an additional global variational-stability condition, we show that the same fully online algorithm converges asymptotically in the last iterate to a stationary ϵε-NE. Our results thus provide the first fully online and scalable learning framework for stochastic games with unknown independent chains. Our algorithmic development can also be viewed as a primal-dual framework for Markov games that fully exploits the independence and local structure of the players’ controlled transition chains and may be of independent interest. †shortheadings: / †firstpage: 1 keywords Stochastic games; independent chains; stationary Nash equilibrium; online decentralized learning; occupancy measures; unknown transition kernels; coarse-correlated equilibrium. 1 Introduction Learning in multi-agent systems becomes particularly challenging when strategic interactions, dynamic stochastic state evolution, and limited information are present simultaneously (Zhang et al., 2021). Unlike in a single-agent Markov decision process (Altman, 2021), where the environment is typically viewed as exogenous, each agent in a stochastic game faces an environment that is partly shaped by the evolving decisions of other strategic agents (Shapley, 1953; Başar and Olsder, 1999). Consequently, even when the underlying transition dynamics are stationary, the effective optimization problem faced by each player changes as the other players adapt. This coupling raises a fundamental question in decentralized learning: under what structural conditions can self-interested agents, using only locally available observations, learn meaningful equilibrium behavior without coordination or knowledge of the underlying model? For general-sum games (Nash, 1950), one cannot expect an affirmative answer without additional structure. Computing a Nash equilibrium (NE) is PPAD-hard even for finite normal-form games (Daskalakis et al., 2009), and stochastic games contain such static games as special cases. Much of the algorithmic literature has therefore focused on structured settings in which equilibrium learning becomes tractable (Mertikopoulos and Zhou, 2019). Examples include two-player zero-sum stochastic games, where fictitious-play or independent-learning procedures can achieve asymptotic or finite-sample convergence guarantees (Daskalakis et al., 2020; Sayin et al., 2022; Zhao et al., 2022), and Markov potential games (MPGs), where the potential structure can be exploited to establish global convergence guarantees for policy-gradient-type methods (Fox et al., 2022; Etesami, 2026; Maheshwari et al., 2025; Zhang et al., 2024; Leonardos et al., 2021). These results demonstrate how suitable structure can fundamentally alter the computational and statistical difficulty of multi-agent learning. However, their structural assumptions may exclude systems in which agents have distinct objectives while their state processes evolve largely independently. This paper studies a different source of tractability: independence in the controlled state dynamics. We consider n-player stochastic games in which each player controls its own finite-state Markov chain. A player’s local transition kernel depends only on its own state and action, while strategic interactions occur through the reward functions, which may depend on the states and actions of all players. This model is natural in systems where individual agents have local physical dynamics but interact through a common environment, prices, congestion, or shared resources. Examples include wireless communication systems (Altman et al., 2007; Narayanan and Theagarajan, 2017), decentralized energy management (Etesami et al., 2018), and decentralized robotic navigation and coverage (Marden et al., 2009). Importantly, independence of the transition processes does not make the game strategically separable: a player’s payoff can still depend arbitrarily on the behavior of all other players. Our information model is deliberately restrictive. Each player observes only its own local state, chosen action, realized payoff, and subsequent local state; it neither observes the states or actions of the other players nor knows its own transition kernel. Thus, each player must simultaneously learn its local dynamics and adapt strategically to the other players from a single continuing trajectory. Moreover, we seek algorithms whose complexity is governed by the sizes and mixing properties of the local controlled chains rather than those of the product state–action space. This distinction is important because the joint state and action spaces grow exponentially with the number of players, even when each individual controlled chain is small. The independence structure permits a useful reformulation of the game in terms of stationary occupancy measures. Under stationary policies, independence of the local chains implies that the long-run joint state–action distribution factors into the product of local stationary occupancies (Etesami, 2024). Consequently, each player’s average reward is linear in its own occupancy measure when the occupancies of the other players are fixed. This converts the original dynamic interaction into a continuous-action static virtual game over local occupancy polytopes. When the transition kernels are unknown, however, these polytopes are themselves unknown and must be learned from data. This creates a coupled learning problem in which players must perform online optimization while simultaneously estimating the feasible regions over which the optimization is carried out. A further difficulty is that a genuinely online implementation cannot rely on the episodic simplifications commonly used to separate estimation from optimization. If policies are frozen for sufficiently long episodes, transition and payoff-gradient estimates can be formed from approximately stationary data before the next policy update. Along a continuing online trajectory, by contrast, policies change while data are being generated. The state distribution therefore tracks a moving stationary distribution, samples are temporally dependent, and confidence regions for the unknown kernels evolve asynchronously across players. Establishing regret guarantees in this setting requires controlling all of these effects without introducing synchronization among the players. The objective of this paper is to show that the local independence structure is strong enough to overcome these difficulties. We develop a fully online occupancy-based mirror-descent method in which each primitive interaction produces one transition/reward observation and one learning update. Each player maintains a confidence set for its unknown local transition kernel, which is updated only when a local state–action count reaches a dyadic threshold. Between such updates, the feasible occupancy region remains unchanged. This lazy confidence-update mechanism is useful both computationally and analytically: each player updates its model independently, its feasible region changes only logarithmically many times, and no global episode boundaries or synchronization signals are required. For arbitrary reward functions, unconditional convergence to a NE cannot in general be expected, given the computational hardness inherited from general-sum static games. We therefore first analyze the algorithm through fixed-comparator regret and establish a high-probability ~(T−1/2) O(T^-1/2) average regret bound against every fixed feasible stationary deviation. This directly yields an approximate coarse-correlated equilibrium guarantee for the empirical distribution of play (Cesa-Bianchi and Lugosi, 2006). Crucially, the resulting complexity depends only on local state and action dimensions, mixing parameters, and cover times, rather than on the cover time or cardinality of the exponentially larger joint state–action space. We then identify conditions under which the stronger conclusion of NE convergence can be recovered. Under an additional variational-stability condition (Mertikopoulos and Zhou, 2019) and diminishing step sizes, we show that the same decentralized fully online procedure converges in the last iterate to the unique stationary ϵε-NE with arbitrarily high probability. 1.1 Related Work Our work lies at the intersection of learning in stochastic games, online learning in MDPs, and decentralized primal-dual methods for stochastic games. For general stochastic games, much of the finite-sample literature has focused on settings with additional game-theoretic structure. Independent policy-gradient and Q-learning methods have been shown to converge in two-player zero-sum stochastic games under decentralized learning protocols (Daskalakis et al., 2020; Sayin et al., 2021). Another important line of work concerns MPGs, where policy-gradient and gradient-play methods exploit the potential structure to obtain global convergence guarantees for stationary NE policies (Zhang et al., 2022; Zhang et al., 2024; Jordan et al., 2024; Leonardos et al., 2021; Ding et al., 2022; Sun et al., 2023). These results leverage restrictions on payoff interactions to make equilibrium computation tractable, whereas our setting allows general reward coupling and derives scalability from the independence of the players’ controlled transition processes. More recently, several works have combined independent transition dynamics with the Markov potential structure. (Nakhleh et al., 2025) studied fictitious play in product Markov games with Kullback–Leibler (KL) control costs and established asymptotic convergence to a NE for the subclass of product MPGs. (Jordan and Kamgarpour, 2026) studied MPGs with independent chains under a more restrictive information structure in which players only partially observe their local states, and established communication-free learning of approximate NE with quasi-polynomial sample and computational complexity. A related recent line of work studies decentralized learning in Markov α-potential games (Guo et al., 2025; Das and Eksin, 2024; Etesami, 2026), which generalize MPGs by allowing violations of the Markov potential property up to an additive error α. (Guo et al., 2025) derived Nash-regret guarantees for projected gradient-ascent and sequential maximum-improvement schemes under exact Q-function oracle access. (Das and Eksin, 2024) introduced constrained α-Markov potential games, which further accommodate coupled constraints among players, and developed decentralized best-response-based algorithms with finite-time guarantees for approximate NE. A fully online decentralized learning framework with finite-time guarantees has only recently been developed for Markov α-potential games, where KL-projected natural policy-gradient algorithms achieve high-probability Nash-regret guarantees under both episodic and fully online learning (Etesami, 2026). Like the algorithm developed here, its fully online method operates along a continuing trajectory using one realized sample per interaction. The two frameworks, however, exploit different sources of tractability: the former relies on an approximate Markov-potential structure in discounted Markov games, whereas our work imposes no potential structure on the rewards and instead exploits independent controlled chains in an average-reward setting. Our analysis also builds on ideas from online learning in MDPs. Occupancy measures provide a convex representation of stationary policies and have been widely used to develop regret-minimization algorithms for adversarial MDPs (Cardoso et al., 2019). In particular, online mirror-descent methods over occupancy polytopes yield sublinear regret when losses vary across episodes, while confidence-set constructions extend such methods to unknown transition kernels (Rosenberg and Mansour, 2019). Related work has also considered bandit feedback with unknown dynamics in online MDPs (Jin et al., 2020). These single-agent techniques motivate our use of occupancy optimization and confidence regions, but do not directly apply to our setting: each player’s effective reward vector is generated endogenously by the evolving policies and state distributions of the other players, while all players learn simultaneously along their own continuing trajectories. More directly, stochastic games with independent state processes have been studied as a structured class of decentralized dynamic games. (Altman et al., 2007) established equilibrium existence for cost-coupled stochastic games with independent state processes, and subsequent work characterized stationary equilibria through mathematical programming formulations (Singh and Hemachandra, 2014). For learning problems, (Qiu et al., 2021) showed that, in two-player zero-sum stochastic games with independent chains, fictitious-play policy-optimization algorithms can achieve ~(T) O( T) regret, assuming that each player has knowledge of the opponent’s past strategies. (Etesami, 2024) introduced an occupancy-based dual formulation and developed decentralized dual-averaging procedures for n-player stochastic games with independent chains. That work demonstrated that independence can be leveraged as a source of computational tractability and established finite-time convergence guarantees in terms of the averaged Nikaido–Isoda gap (Nikaidô and Isoda, 1955). Its main algorithms, however, assume known local transition kernels and operate in an episodic fashion, thereby requiring synchronization among players. Unknown transition dynamics were subsequently addressed by (Qin and Etesami, 2024), who combined the occupancy formulation with confidence sets and decentralized online mirror descent. Their algorithm learns the local transition models from observed trajectories and, under a variational-stability assumption, converges asymptotically to a stationary ϵε-NE. The learning protocol, however, remains episodic: policies are held fixed while sufficiently many local observations are collected, and an episode-ending signaling mechanism coordinates policy updates across players. Extending this framework to a fully online setting presents significant additional challenges, as continuous policy updates eliminate the stationary sampling environment provided by episodic learning and synchronization. The present paper removes this episodic architecture through delayed conditioning, coupling with frozen-policy dynamics, sensitivity bounds for policy and kernel movement, tracking of time-varying stationary occupancies, and careful treatment of asynchronous confidence-set updates. Players learn from every primitive interaction, confidence sets evolve asynchronously using only local information, and no episode boundaries, dedicated covering phases, or synchronization signals are required. Beyond this algorithmic distinction, we establish a finite-time, high-probability fixed-comparator regret bound for arbitrary reward functions and distinguish the resulting coarse-correlated-equilibrium guarantee from the stronger last-iterate ϵε-NE convergence guarantee, which requires an additional variational-stability assumption. 1.2 Contributions We study stochastic games with independent controlled chains and unknown transition kernels and develop a fully decentralized online algorithm for learning stationary equilibrium policies. Our main contributions are as follows. • We develop a fully online, decentralized, and uncoordinated algorithm that uses one sample per time step. At each primitive time t, every player observes one local transition and realized payoff, updates its local transition counts, forms an importance-weighted payoff-gradient estimate, and takes one mirror-descent step. The algorithm requires no covering episodes, burn-in phases, or synchronization signals. Confidence sets are updated asynchronously only when a local state–action count reaches a dyadic threshold, so the feasible occupancy region remains fixed between updates and changes only logarithmically many times over a finite horizon. • For arbitrary reward functions, we establish a high-probability fixed-comparator regret bound of order ~(T−1/2) O(T^-1/2) after a local-cover transient period. The bound depends only on local state and action dimensions, mixing parameters, and cover times, rather than on those of the exponentially larger joint state–action space. Consequently, the empirical distribution of play satisfies an approximate coarse-correlated-equilibrium guarantee. • We further identify a regime in which the stronger NE conclusion can be recovered. Under an additional variational-stability assumption and diminishing step sizes, we prove that the same fully online decentralized algorithm converges asymptotically in the last iterate to the unique stationary ϵε-NE with arbitrarily high probability. Thus, the finite-time no-regret guarantee requires no structural assumptions on the reward functions, while last-iterate NE convergence follows under stability of the induced occupancy game. 1.3 Organization The rest of the paper is organized as follows. In Section 2, we formulate stochastic games with independent controlled chains and unknown transition kernels and introduce the stationary equilibrium concepts used throughout the paper. Section 3 develops the occupancy-measure representation, the associated virtual game, and the local coverage quantities needed for the analysis. In Section 4, we introduce the fully online decentralized mirror-descent algorithm together with its asynchronous confidence-set updates. Section 5 establishes the finite-time, high-probability fixed-comparator regret bound and derives the resulting coarse-correlated-equilibrium guarantee. Section 6 studies the diminishing-step-size regime and establishes last-iterate convergence to an ϵε-NE under variational stability. Section 7 discusses applications and implications of the framework. Finally, Section 8 concludes the paper and outlines directions for future research. Omitted proofs and additional technical details are provided in the appendices. Notation. For a positive integer n, we write [n]:=1,…,m[n]:=\1,…,m\. For a finite set X, |||X| denotes its cardinality. Vectors are indexed by their corresponding states, actions, or state–action tuples, and ⟨x,y⟩ x,y denotes the standard Euclidean inner product. We use ‖x‖1\|x\|_1, ‖x‖2\|x\|_2, and ‖x‖∞\|x\|_∞ for the ℓ1 _1, Euclidean, and supremum norms, respectively, and ⋅ 1\·\ for the indicator function. For a profile x=(x1,…,xn)x=(x_1,…,x_n), we write x−i:=(xj)j≠ix_-i:=(x_j)_j≠ i for the profile excluding player i. Lowercase letters such as sis_i and aia_i denote local states and actions, while s=(s1,…,sn)s=(s_1,…,s_n) and a=(a1,…,an)a=(a_1,…,a_n) denote joint profiles; uppercase letters denote the corresponding random variables. We use ℙP and E for probability and expectation, respectively, and ℱtF_t for the filtration in the probabilistic analysis. For occupancy measures, νi _i, ρi _i, and qiq_i denote state, state–action, and state–action–next-state occupancies, respectively. Throughout, unhatted quantities (qit,ρit,νit)(q_i^t, _i^t, _i^t) denote the occupancies induced by the current policy πit _i^t under the true kernel PiP_i, whereas hatted quantities (q^it,ρ^it,ν^it)( q_i^t, ρ_i^t, ν_i^t) denote the confidence-feasible quantities maintained by the algorithm. We write x≲yx y if x≤αyx≤α y for some universal constant α>0α>0. Throughout, we use c>0c>0 to denote an adjustable universal positive constant. Finally, (⋅)O(·) and ~(⋅) O(·) hide universal constants and, in the latter case, logarithmic factors. 2 Problem Formulation We consider an n-player infinite-horizon, time-average stochastic game with independent state transitions, described by the tuple :=([n],ii=1n,ii=1n,rii=1n,Pii=1n)G:= ([n],\S_i\_i=1^n,\A_i\_i=1^n,\r_i\_i=1^n,\P_i\_i=1^n ), as follows. • iS_i is the finite state space of player i, with elements si∈is_i _i. We denote the joint state space of all players by =1×⋯×nS=S_1×·s×S_n, with elements s∈s , where s=(s1,…,sn)s=(s_1,…,s_n). • iA_i is the finite action space of player i, with elements ai∈ia_i _i. We denote the joint action space of all players by =1×⋯×nA=A_1×·s×A_n, with elements a∈a , where a=(a1,…,an)a=(a_1,…,a_n). • ri:×→[0,1]r_i:S×A→[0,1] is the reward function of player i, where ri(s,a)r_i(s,a) is the immediate reward received by player i when the joint state is s=(s1,…,sn)s=(s_1,…,s_n) and the players take the joint action a=(a1,…,an)a=(a_1,…,a_n). • PiP_i is the transition probability kernel of player i, where Pi(si′∣si,ai)P_i(s_i s_i,a_i) is the probability that the state of player i transitions from sis_i to si′s_i when the player chooses action aia_i. Crucially, PiP_i is unknown to player i, and player i’s next-state distribution depends only on (si,ai)(s_i,a_i). The precise factorization of the joint transition kernel is stated in the following assumption. Assumption 1. We assume that the joint transition probability kernel P(s′∣s,a)P(s s,a) factors into independent components as P(s′∣s,a)=∏i=1nPi(si′∣si,ai)P(s s,a)= _i=1^nP_i(s_i s_i,a_i), where Pi(si′∣si,ai)P_i(s_i s_i,a_i) denotes the (unknown) transition probability of player i from state sis_i to state si′s_i under action aia_i. At any time t, the information available to player i is given by the history of its realized states, actions, and rewards, i.e., ℋit=siℓ,aiℓ,ri(sℓ,aℓ):ℓ=0,1,…,t−1∪sitH_i^t=\s _i,a _i,r_i(s ,a ): =0,1,…,t-1\∪\s^t_i\. Given the information set ℋitH_i^t, player i takes an action aita_i^t according to her current policy πit(⋅∣ℋit) _i^t(· _i^t), which is a probability measure over iA_i, and receives the reward ri(st,at)r_i(s^t,a^t), which may also depend on the states and actions of the other players. Subsequently, the state of player i transitions from sits_i^t to a new state sit+1s_i^t+1 according to the transition probability Pi(sit+1∣sit,ait)P_i(s_i^t+1 s_i^t,a_i^t). A general policy for player i is a sequence of decision rules πi=πit:t=0,1,… _i=\ _i^t:t=0,1,…\, where each πit(⋅∣ℋit) _i^t(· _i^t) is a probability measure over iA_i. However, the use of general policies is often computationally expensive, and in practical applications, players are typically interested in easily implementable stationary policies, as defined next, which are also the main focus of this paper. Definition 1. A policy πi _i for player i is called stationary if the probability πit(ai∣ℋt) _i^t(a_i ^t) of choosing action aia_i at time t depends only on the current local state sit=sis^t_i=s_i, and is independent of the time t. In the case of the stationary policy, we use πi(ai∣si) _i(a_i s_i) to denote this time-independent probability. Given an initial state s0s^0, the objective of each player i∈[n]i∈[n] is to choose a stationary policy πi _i that maximizes its long-term expected average reward (payoff), given by Vi(πi,π−i)=lim supT→∞1T[∑t=0Tri(st,at)], V_i( _i, _-i)= _T→∞ 1TE [ _t=0^Tr_i(s^t,a^t) ], (1) where π−i=(πj,j≠i) _-i=( _j,j≠ i), and the expectation is with respect to the randomness introduced by players’ internal kernels (P1,…,Pn)(P_1,…,P_n) and their stationary policies π=(π1,…,πn)π=( _1,…, _n). This fully characterizes the n-player stochastic game considered here, in which each player i seeks to choose a stationary policy πi _i to maximize its expected aggregate payoff Vi(πi,π−i)V_i( _i, _-i). In the remainder of the paper, we refer to the above reward-coupled stochastic game with independent chains and unknown transition kernels as the original game G. Next, to establish meaningful convergence and learning guarantees, we impose the following assumption throughout this work. Assumption 2. For any player i and any stationary policy πi _i chosen by that player, the induced Markov chain, with transition probabilities Pπi(si′∣si):=∑ai∈iPi(si′∣si,ai)πi(ai∣si),P _i(s_i s_i):= _a_i _iP_i(s_i s_i,a_i) _i(a_i s_i), is ergodic and satisfies a uniform contraction condition: there exists a constant κ∈(0,1]κ∈(0,1] such that11 1 Here, Δ(i) (S_i) denotes the probability simplex over the local state space iS_i. ‖(ν−ν′)Pπi‖1≤(1−κ)‖ν−ν′‖1,∀i,πi,ν,ν′∈Δ(i). \|(ν-ν )P _i\|_1≤(1-κ)\|ν-ν \|_1, ∀ i,\ _i,\ ν,ν ∈ (S_i). Assumption 2 is a uniform-ergodicity condition commonly used in finite-time analyses of average-reward online MDPs (see, e.g., Rivera Cardoso et al., 2019; Neu et al., 2010; Rosenberg and Mansour, 2019). Its role here is quantitative: the proof uses policy-uniform contraction to control the tracking error of the continuously changing local chains and the bias of the delayed one-sample gradient estimator. We do not claim that such a condition is necessary for learning in general MDPs; weaker communicating assumptions may suffice for other objectives and algorithms. Rather, Assumption 2 delineates the controlled-chain regime covered by our analysis. As shown in the next section, under Assumption 2, for any stationary policy profile π, the limit in (1) exists and admits the closed-form expression. Definition 2. For a stationary policy profile π∗=(π1∗,…,πn∗)π^*=( _1^*,…, _n^*), πi∗ _i^* is called a stationary best response to π−i∗ _-i^* if Vi(πi∗,π−i∗)≥Vi(πi,π−i∗)V_i( _i^*, _-i^*)≥ V_i( _i, _-i^*) for every stationary policy πi _i. Similarly, πi∗ _i^* is called a stationary ϵε-best response to π−i∗ _-i^* if Vi(πi∗,π−i∗)≥Vi(πi,π−i∗)−ϵV_i( _i^*, _-i^*)≥ V_i( _i, _-i^*)-ε for every stationary policy πi _i. The stationary policy profile π∗π^* is a stationary Nash equilibrium (NE) if πi∗ _i^* is a stationary best response to π−i∗ _-i^* for every player i, and it is a stationary ϵε-NE if πi∗ _i^* is a stationary ϵε-best response to π−i∗ _-i^* for every player i. All equilibrium statements in this paper concern stationary policies. Our main objective is to understand the equilibrium guarantees of a decentralized and fully online learning rule for this class of stochastic games. We establish two types of guarantees: a finite-time fixed-comparator regret bound for the time-averaged iterates and, under stronger conditions, last-iterate convergence to a stationary ϵε-NE. 3 Preliminaries on Occupancy Measures, Dual Formulation, and Local Cover Times In this section, we provide an alternative dual formulation of the original stochastic game G based on occupancy measures (Altman, 2021). Intuitively, from player i’s perspective, its long-term expected average payoff depends on the proportion of time it spends in each state sis_i and takes each action aia_i, as captured by its occupancy measure. Thus, the policy optimization problem for player i can be reformulated as an optimization problem over occupancy measures, where each player seeks to steer its chain toward high-reward states and actions. An advantage of optimizing over occupancy measures is that, due to the independence of the players’ internal chains, the payoff functions admit a simple closed-form that is easier to analyze than the original formulation in terms of policy variables. Moreover, this simplified payoff structure allows us to leverage the rich literature on online learning and primal-dual methods to address the learning problem. We use this dual formulation to develop learning algorithms for finding a stationary ϵε-NE. 3.1 Occupancy Measures For a given single-agent MDP with state space S, action space A, transition probability kernel P, and stationary policy π, one can associate with P and π three notions of occupancy measures: ν:→[0,1]ν:S→[0,1], ρ:×→[0,1]ρ:S×A→[0,1], and q:×→[0,1]q:S×A×S→[0,1], defined as follows.22 2 The first type of occupancy measure ν is often referred to as the stationary distribution in the past literature. ν(s)=limT→∞1T∑t=0T−1ℙπ(st=s), ν(s)= _T→∞ 1T _t=0^T-1P_π(s^t=s), (2) ρ(s,a)=limT→∞1T∑t=0T−1ℙπ(st=s,at=a), ρ(s,a)= _T→∞ 1T _t=0^T-1P_π(s^t=s,a^t=a), (3) q(s,a,s′)=limT→∞1T∑t=0T−1ℙπ(st=s,at=a,st+1=s′). q(s,a,s )= _T→∞ 1T _t=0^T-1P_π(s^t=s,a^t=a,s^t+1=s ). (4) Intuitively, ν(s),ρ(s,a)ν(s),ρ(s,a) and q(s,a,s′)q(s,a,s ) are the long-term average proportion of time of encountering the state s, state-action pair (s,a)(s,a), and state-action-next-state triple (s,a,s′)(s,a,s ), when executing policy π in an MDP with transition probability kernel P. It can be readily shown that under Assumption 2, the limits in (2), (3), and (4) indeed exist, and moreover, the following relations always hold: ρ(s,a)=ν(s)π(a∣s),q(s,a,s′)=ρ(s,a)P(s′∣s,a). ρ(s,a)=ν(s)π(a s), q(s,a,s )=ρ(s,a)P(s s,a). In this work, we are primarily concerned with the occupancy measure q(s,a,s′)q(s,a,s ) due to players not knowing their independent transition probability kernel PiP_i in the stochastic game G. In the following, we provide conditions that fully characterize the set of feasible occupancy measures q. Definition 3. We define the polytope of feasible occupancy measures, denoted by Δ , as Δ:=q∈[0,1]||||2:∑s,a,s′q(s,a,s′)=1,∑s′,aq(s′,a,s)=∑a,s′q(s,a,s′)∀s∈. := \q∈[0,1]^|A||S|^2:\ \ \ _s,a,s q(s,a,s )=1, _s ,aq(s ,a,s)= _a,s q(s,a,s )\ \ ∀ s \. (5) Moreover, for any q∈Δq∈ , we define its induced transition probability matrix PqP^q and its induced stationary policy πqπ^q by Pq(s′∣s,a):=q(s,a,s′)∑s′q(s,a,s′)∀s,a,s′,πq(a∣s):=∑s′q(s,a,s′)∑a′,s′q(s,a′,s′)∀s,a. P^q(s s,a):= q(s,a,s ) _s q(s,a,s )\ ∀ s,a,s ,\ \ \ \ \ \ π^q(a s):= _s q(s,a,s ) _a ,s q(s,a ,s )\ ∀ s,a. In addition, for a transition probability matrix P or a set of transition probability matrices P, we denote by Δ(P) (P) and Δ() (P) the sets of occupancy measures in Δ that are compatible with P and P, respectively; that is, their induced transition matrices equal P or belong to P: Δ(P):=q∈Δ:Pq=P,Δ():=q∈Δ:Pq∈. (P):=\q∈ :P^q=P\, (P):=\q∈ :P^q \. The reason why (5) provides the set of feasible occupancy measures is because any feasible occupancy measure q should be a valid probability distribution, i.e., ∑s,a,s′q(s,a,s′)=1 _s,a,s q(s,a,s )=1, and moreover, for any state s∈s , the probability of entering it should equal to the probability of leaving it, i.e., ∑s′,aq(s′,a,s)=∑a,s′q(s,a,s′)∀s∈. _s ,aq(s ,a,s)= _a,s q(s,a,s )\ ∀ s . Given the above definition, we have the following useful lemma from (Altman, 2021). Lemma 4 ((Altman, 2021)). If a function q:×→[0,1]q:S×A×S→[0,1] belongs to the feasible occupancy polytope Δ defined in (5), then it is exactly the occupancy measure associated with its induced transition probability matrix PqP^q and stationary policy πqπ^q. Specifically, (4) holds when policy πqπ^q is executed in an MDP with transition probability matrix PqP^q. 3.2 A Dual Formulation We now provide a dual formulation of the original stochastic game G based on occupancy measures. It is shown in (Etesami, 2024) that, under the ergodicity Assumption 2, the independence of the players’ internal chains allows the payoff functions to admit a simple decomposable form in terms of the occupancy measures ρ. However, since we are interested in stochastic games with unknown transition probabilities, we first extend this formulation to the occupancy measures q. Specifically, suppose that each player i follows a stationary policy πi _i, and let νi _i, ρi _i, and qiq_i denote the corresponding occupancy measures defined in (2), (3), and (4), respectively, induced by kernel PiP_i under policy πi _i. Then, the expected average payoff of player i, Vi(πi,π−i)V_i( _i, _-i), can be equivalently expressed as a function of ρi _i and ρ−i _-i. Proposition 5. Let Assumptions 1 and 2 hold, and assume that each player i follows a stationary policy πi _i. Let qi∈Δi(Pi)q_i∈ _i(P_i) denote the occupancy induced by πi _i under the true transition kernel PiP_i, with corresponding state–action marginal ρi _i. Then, each player’s payoff can be expressed as Vi(πi,π−i)=Vi(qi,q−i):=∑s,a∏j=1n∑sj′qj(sj,aj,sj′)ri(s,a)=⟨qi,gi(q−i)⟩, V_i( _i, _-i)=V_i(q_i,q_-i):= _s,a _j=1^n _s _jq_j(s_j,a_j,s _j)r_i(s,a)= q_i,g_i(q_-i) , (6) where gi(q−i)g_i(q_-i) is defined to be a vector of dimension |i||i|2|A_i||S_i|^2 whose (si,ai,si′)(s_i,a_i,s _i)-th component is gi(q−i)(si,ai,si′): g_i(q_-i)_(s_i,a_i,s _i): =∑s−i,a−i∏j≠i∑sj′qj(sj,aj,sj′)ri(s,a) = _s_-i,a_-i _j≠ i _s _jq_j(s_j,a_j,s _j)r_i(s,a) (7) =∑s−i,a−i∏j≠iρj(sj,aj)ri(s,a)∀si,ai,si′. = _s_-i,a_-i _j≠ i _j(s_j,a_j)r_i(s,a)\ \ ∀ s_i,a_i,s _i. (8) We note that gi(q−i)(si,ai,si′)g_i(q_-i)_(s_i,a_i,s _i) is independent of si′s _i, with the same value repeated across all si′∈is _i _i. Using Lemma 4 and Proposition 5, the problem of finding optimal stationary policies for the players reduces to that of finding their optimal feasible occupancy measures. In fact, using the dual formulation, we can define an equivalent virtual game associated with the original stochastic game G as follows: Definition 6. Define the feasible occupancy polytope for player i by Δi=qi∈[0,1]|i||i|2:∑si,ai,si′qi(si,ai,si′)=1,∑si′,aiqi(si′,ai,si)=∑si′,aiqi(si,ai,si′)∀si∈i. _i= \q_i∈[0,1]^|A_i||S_i|^2\!: _s_i,a_i,s _iq_i(s_i,a_i,s _i)=1,\ \ _s _i,a_i\!q_i(s _i,a_i,s_i)= _s _i,a_i\!q_i(s_i,a_i,s _i)\ ∀ s_i _i \. Moreover, let Δi(Pi)⊂Δi _i(P_i)⊂ _i be the set of feasible occupancy measures for player i whose induced transition probability matrix PqiP^q_i is exactly PiP_i. The virtual game =([n],q=(qi)i,Vi(q)i)V= ([n],q=(q_i)_i,\V_i(q)\_i ) associated with the original stochastic game G is an n-player continuous-action static game, where the action of player i is to choose an qiq_i from its action set Δi(Pi) _i(P_i), and its payoff is given by (6). Ideally, each player would optimize over the true-kernel feasible set Δi(Pi) _i(P_i), on which the virtual payoff is the linear functional ⟨qi,gi(q−i)⟩ q_i,g_i(q_-i) in its own occupancy variable qiq_i. Since PiP_i is unknown, our proposed algorithm (Algorithm 1) instead maintains an iterate q^i q_i that is feasible for some transition probability matrix in a confidence set. In particular, for any profile q=(qj)jq=(q_j)_j with qj∈Δj(Pj)q_j∈ _j(P_j) for all j, we have Vi(qi,q−i)=⟨qi,gi(q−i)⟩V_i(q_i,q_-i)= q_i,g_i(q_-i) . For an arbitrary relaxed iterate q^=(q^i)i q=( q_i)_i, its payoff is defined as the payoff of its induced policy under the true kernels Pjj∈[n]\P_j\_j∈[n], namely, Vi(q^):=Vi(πiq^i,π−iq^−i).V_i( q):=V_i( _i q_i, _-i q_-i). Thus, q^i q_i denotes an algorithmic occupancy variable, whereas qiq_i denotes the true occupancy measure induced by πiq^i _i q_i under the true kernel PiP_i. By Lemma 4, whenever q^i∈Δi(Pi) q_i∈ _i(P_i), its induced transition matrix satisfies Pq^i=PiP q_i=P_i, and q^i q_i is exactly the occupancy measure induced by πiq^i _i q_i under the true kernel PiP_i. Hence, in this case, q^i=qi q_i=q_i. This distinction will be used explicitly throughout the paper. Finally, for the sake of exploration and to obtain high probability regret bounds, we consider the following definition of shrunk feasible occupancy polytope. Definition 7. Given 0<δi<1/(|i||i|)0< _i<1/(|S_i||A_i|), define the shrunk feasible occupancy polytope Δi,δi:=qi∈Δi:ρi(si,ai)=∑si′qi(si,ai,si′)≥δi,∀si,ai. _i, _i:= \q_i∈ _i: _i(s_i,a_i)= _s_i q_i(s_i,a_i,s_i )≥ _i,\ ∀ s_i,a_i \. For a kernel PiP_i or a set iP_i of kernels, Δi,δi(Pi) _i, _i(P_i) and Δi,δi(i) _i, _i(P_i) denote the corresponding subsets of Δi,δi _i, _i whose induced kernel equals PiP_i or belongs to iP_i, respectively. One advantage of working with the shrunk feasible occupancy sets is that the shrinkage constraint in Definition 7 ensures persistent exploration while incurring only a small loss in the best-response value. In particular, for every ϵ>0ε>0, δi _i can be chosen sufficiently small so that optimization over the shrunk feasible occupancy polytope is within ϵε of optimization over the full occupancy polytope (see Corollary 18). Moreover, as we will see, the rectangular confidence sets maintained by Algorithm 1 over the shrunk occupancy polytope preserve the computational tractability of the occupancy formulation. In particular, for any rectangular confidence set iP_i, the shrunk feasible occupancy set Δi,δi(i) _i, _i(P_i) admits an efficient representation, as shown in the following lemma. Lemma 8. Suppose a confidence set iP_i contains the set of probability transition matrices PiP_i that satisfy box constraints Li(si,ai,si′)≤Pi(si′∣si,ai)≤Ui(si,ai,si′)L_i(s_i,a_i,s _i)≤ P_i(s_i s_i,a_i)≤ U_i(s_i,a_i,s _i). Then Δi,δi(i) _i, _i(P_i) is a closed convex polytope admitting an explicit linear description with O(|i||i|2)O(|A_i||S_i|^2) variables and constraints. 3.3 Local Cover Times To provide meaningful convergence-rate guarantees, we work with a local cover-time parameter. Formally, for a fixed stationary policy πi _i, let τcov,iπi:=maxsi0∈imint≥0:Si0,…,Sit=i,Si0=si0 _ cov,i _i:= _s_i^0 _i \t≥ 0:\S_i^0,…,S_i^t\=S_i,\ S^0_i=s^0_i \ be the cover time of the Markov chain with transition matrix PiπiP_i _i. Define the expected cover time Hi H_i :=supπi∈Πi[τcov,iπi], := _ _i∈ _iE[ _ cov,i _i], H H :=maxi∈[n]Hi, := _i∈[n]H_i, (9) where Πi _i is the compact set of stationary policies on iS_i. Thus, HiH_i represents the worst-case expected time needed for player i to visit all of its local states under any fixed stationary policy. We note that the local cover time is defined with respect to each player’s local state space, which can be exponentially smaller than the joint state space. In particular, under Assumption 2, it is easy to see that Hi<∞H_i<∞ for all i, and hence H<∞H<∞.33 3 For every stationary policy πi _i, Assumption 2 implies that PiπiP_i _i is a finite irreducible Markov chain and hence has finite expected cover time. Since Πi _i is compact, the mapping πi↦Piπi _i P_i _i is continuous, and expected hitting times are locally continuous over irreducible Markov chains, compactness yields a finite uniform bound over all πi _i. 4 A Fully Online Decentralized Learning Algorithm In this section, we describe our fully online algorithm for stochastic games with unknown independent chains. Each primitive interaction produces exactly one transition/reward observation and one mirror-descent update. Unlike the episodic setting, which has been a standard approach in the previous literature Etesami (2024); Qin and Etesami (2024), no player waits until all of its state–action pairs have been observed, there are no burn-in episodes, and no episode-end synchronization or coordination among the players is required. The transition kernels remain unknown and are estimated from the same single trajectory used for learning. 4.1 Anytime confidence sets and one-sample updates To describe our algorithm, we first introduce the following notation and definitions. Player i maintains cumulative counters that record, respectively, the numbers of visits to each state–action pair (si,ai)(s_i,a_i) and each state–action–next-state triple (si,ai,si′)(s_i,a_i,s_i ) up to time t along the single realized trajectory of the game: Nit(si,ai):=∑ℓ<t(Siℓ,Aiℓ)=(si,ai), N_i^t(s_i,a_i):= _ <t 1\(S_i ,A_i )=(s_i,a_i)\, Mit(si,ai,si′):=∑ℓ<t(Siℓ,Aiℓ,Siℓ+1)=(si,ai,si′). M_i^t(s_i,a_i,s_i ):= _ <t 1\(S_i ,A_i ,S_i +1)=(s_i,a_i,s_i )\. Let P¯it P_i^t denote the empirical transition kernel for player i given by P¯it(si′∣si,ai):=Mit(si,ai,si′)Nit(si,ai)∨1, P_i^t(s_i s_i,a_i):= M_i^t(s_i,a_i,s_i )N_i^t(s_i,a_i) 1, where ∨ denotes the maximum of the quantities, and define the confidence radius at time t by βit(si,ai)=2ΛtNit(si,ai)∨1, _i^t(s_i,a_i)= 2 _tN_i^t(s_i,a_i) 1, where Λt:=log(64nAmaxSmax2(t+2)2γ) _t:= \! ( 64nA_ S_ ^2(t+2)^2γ ), Smax:=maxj∈[n]|j|,andAmax:=maxj∈[n]|j|S_ := _j∈[n]|S_j|,andA_ := _j∈[n]|A_j|. For a finite horizon T we write ΛT:=maxt≤TΛt _T:= _t≤ T _t. Moreover, at time t, we write ρ^it(si,ai)=∑si′q^it(si,ai,si′), ρ_i^t(s_i,a_i)= _s_i q_i^t(s_i,a_i,s_i ), (10) ν^it(si)=∑aiρ^it(si,ai), ν_i^t(s_i)= _a_i ρ_i^t(s_i,a_i), (11) πit(ai∣si)=ρ^it(si,ai)ν^it(si), _i^t(a_i s_i)= ρ_i^t(s_i,a_i) ν_i^t(s_i), (12) where we note that if q^it∈Δi,δi(it) q^t_i∈ _i, _i(P^t_i), then ρ^it(si,ai)≥δi ρ_i^t(s_i,a_i)≥ _i and ν^it(si)≤1 ν_i^t(s_i)≤ 1, and hence πit(ai∣si)≥δi,∀si,ai. _i^t(a_i s_i)≥ _i, ∀ s_i,a_i. (13) After observing the single reward rit:=ri(St,At)r_i^t:=r_i(S^t,A^t), we define the importance-weighted vector R^it R^t_i as R^it(si,ai,si′)=rit 1(Sit,Ait)=(si,ai)ρ^it(si,ai)∀si,ai,si′, R_i^t(s_i,a_i,s_i )= r_i^t\, 1\(S_i^t,A_i^t)=(s_i,a_i)\ ρ_i^t(s_i,a_i) ∀ s_i,a_i,s_i , (14) where we note that ‖R^it‖∞≤1/δi\| R_i^t\|_∞≤ 1/ _i. The estimator R^it R_i^t converts the realized payoff ritr_i^t into an estimate of the occupancy-payoff gradient git:=gi(q−it)g_i^t:=g_i(q_-i^t), with the importance-weighted factor 1/ρ^it(si,ai)1/ ρ_i^t(s_i,a_i) correcting for the fact that the payoff is observed only at the realized state–action pair (Sit,Ait)(S_i^t,A_i^t). Remark 9. To see the intuition behind R^it R_i^t, suppose hypothetically that the joint state–action profile (St,At)(S^t,A^t) were drawn from the product stationary law ⨂jρjt _j _j^t. Then, for any fixed (si,ai,si′)(s_i,a_i,s _i), ⨂jρjt[R^it(si,ai,si′)]=1ρ^it(si,ai)[ri(St,At)(Sit,Ait)=(si,ai)]=ρit(si,ai)ρ^it(si,ai)git(si,ai,si′).E_ _j _j^t[ R_i^t(s_i,a_i,s_i )]= 1 ρ_i^t(s_i,a_i)E[r_i(S^t,A^t)1\(S_i^t,A_i^t)=(s_i,a_i)\]= _i^t(s_i,a_i) ρ_i^t(s_i,a_i)g_i^t(s_i,a_i,s_i ). Thus, if additionally ρ^it=ρit ρ_i^t= _i^t (which holds, in particular, when the transition kernel induced by q^it q_i^t coincides with the true transition kernel PiP_i), then [R^it]=gitE[ R_i^t]=g_i^t. Hence, R^it R_i^t can be viewed as using the single realized payoff ritr_i^t to construct a stochastic estimate of the occupancy-payoff gradient gitg_i^t. 4.2 Description of the Algorithm Algorithm 1 Fully Online One-Sample Occupancy Mirror Descent for Player i 1: Input: Shrinkage δi _i, stepsizes ηt\ _t\, regularizer hi(qi)=12‖qi‖22h_i(q_i)= 12\|q_i\|_2^2, and confidence level γ. 2: Player i initializes Ni0(si,ai)=0N_i^0(s_i,a_i)=0 and Mi0(si,ai,si′)=0M_i^0(s_i,a_i,s_i )=0 for all si,ai,si′s_i,a_i,s_i , sets i0P_i^0 to the set of all transition kernels on iS_i, and chooses q^i0∈Δi,δi(i0) q_i^0∈ _i, _i(P_i^0). 3: for t=0,1,2,…t=0,1,2,… do 4: Player i observes SitS_i^t and samples Ait∼πit(⋅∣Sit)A_i^t _i^t(· S_i^t), where 5: πit(ai∣si)=ρ^it(si,ai)ν^it(si). _i^t(a_i s_i)= ρ_i^t(s_i,a_i) ν_i^t(s_i). 6: Player i observes rit=ri(St,At)r_i^t=r_i(S^t,A^t) and forms 7: R^it(si,ai,si′)=rit(Sit,Ait)=(si,ai)ρ^it(si,ai),∀si,ai,si′. R_i^t(s_i,a_i,s_i )= r_i^t 1\(S_i^t,A_i^t)=(s_i,a_i)\ ρ_i^t(s_i,a_i), ∀ s_i,a_i,s_i . 8: Player i also observes its next state Sit+1S_i^t+1 and updates its local counters: 9: Nit+1(si,ai)=Nit(si,ai)+(Sit,Ait)=(si,ai), N_i^t+1(s_i,a_i)=N_i^t(s_i,a_i)+ 1\(S_i^t,A_i^t)=(s_i,a_i)\, 10: Mit+1(si,ai,si′)=Mit(si,ai,si′)+(Sit,Ait,Sit+1)=(si,ai,si′). M_i^t+1(s_i,a_i,s_i )=M_i^t(s_i,a_i,s_i )+ 1\(S_i^t,A_i^t,S_i^t+1)=(s_i,a_i,s_i )\. 11: if Nit+1(Sit,Ait)=2kN_i^t+1(S_i^t,A_i^t)=2^k for some integer k≥0k≥ 0, then 12: Player i computes its empirical transition kernel 13: P¯it+1(si′∣si,ai)=Mit+1(si,ai,si′)Nit+1(si,ai)∨1,∀si,ai,si′. P_i^t+1(s_i s_i,a_i)= M_i^t+1(s_i,a_i,s_i )N_i^t+1(s_i,a_i) 1, ∀ s_i,a_i,s_i . 14: Player i computes the confidence radii 15: βit+1(si,ai)=2Λt+1Nit+1(si,ai)∨1∀si,ai,Λt+1=log(64nAmaxSmax2(t+3)2γ). _i^t+1(s_i,a_i)= 2 _t+1N_i^t+1(s_i,a_i) 1\ \ ∀ s_i,a_i,\ _t+1= \! ( 64nA_ S_ ^2(t+3)^2γ ). 16: Player i updates its confidence set as 17: it+1=it∩Pi:|Pi(si′∣si,ai)−P¯it+1(si′∣si,ai)|≤βit+1(si,ai),∀si,ai,si′. _i^t+1=P_i^t∩ \P_i: |P_i(s_i s_i,a_i)- P_i^t+1(s_i s_i,a_i) |≤ _i^t+1(s_i,a_i),\ ∀ s_i,a_i,s_i \. 18: else 19: Player i sets it+1=itP_i^t+1=P_i^t. 20: Player i performs the proximal occupancy update 21: q^it+1=argmaxqi∈Δi,δi(it+1)ηt⟨qi,R^it⟩−Dhi(qi∥q^it). q_i^t+1= argmax_q_i∈ _i, _i(P_i^t+1) \ _t q_i, R_i^t -D_h_i(q_i\| q_i^t) \. Using the definitions in the preceding subsection, the proposed online algorithm is summarized in Algorithm 1. To describe the algorithm, it is useful to distinguish between the two learning tasks carried out simultaneously by each player. Player i does not know its local controlled transition kernel PiP_i and therefore must learn the rows Pi(⋅∣si,ai)P_i(· s_i,a_i) from its observed local transitions. At the same time, it must adapt its strategic policy based on its realized payoff samples. Algorithm 1 performs both tasks along the same uninterrupted trajectory. The variable q^it q_i^t is player i’s current confidence-feasible occupancy iterate, which induces both a transition kernel P^it:=Pq^it∈it P_i^t:=P q_i^t _i^t and a policy πit:=πq^it _i^t:=π q_i^t. In particular, its state–action marginal ρ^it ρ_i^t determines the policy through (10), so the occupancy update implicitly induces the policy used to generate the online trajectory. The shrinkage constraint ρ^it(si,ai)≥δi ρ_i^t(s_i,a_i)≥ _i guarantees persistent local exploration through (13) and, at the same time, keeps the importance weights uniformly bounded. At each time t, player i samples AitA_i^t from its current policy πit(⋅∣Sit) _i^t(· S^t_i) and observes only its realized payoff rit:=ri(St,At)r_i^t:=r_i(S^t,A^t) and next local state Sit+1S_i^t+1. These observations serve two distinct purposes. The transition triple (Sit,Ait,Sit+1)(S_i^t,A_i^t,S_i^t+1) is used to learn the unknown true kernel PiP_i and refine the confidence set itP_i^t. In contrast, (Sit,Ait,rit)(S_i^t,A_i^t,r_i^t) is used to construct the importance-weighted vector R^it R_i^t in (14). The vector R^it R_i^t, which serves as a stochastic proxy for the gradient git:=gi(q−it)g_i^t:=g_i(q_-i^t) of the occupancy payoff function, is then used to move the occupancy iterate q^it q_i^t in a payoff-improving direction. The updated iterate is projected onto the shrunk confidence-feasible occupancy polytope Δi,δi(it+1) _i, _i(P_i^t+1), ensuring that its induced transition kernel remains consistent with the information currently available to player i while preserving the exploration constraint. The new occupancy iterate q^it+1 q_i^t+1 in turn induces the next policy through its state–action marginal, closing the online learning loop. The transition-confidence set is deliberately refreshed on a slower, event-driven clock. For each local pair (si,ai)(s_i,a_i), player i continues to collect every transition sample but rebuilds the confidence set only when the corresponding visit count first reaches a new dyadic threshold 1,2,4,8,…1,2,4,8,…. Equivalently, at time t+1t+1, a refresh is triggered if, for some (si,ai)(s_i,a_i) and integer k≥0k≥ 0, we have Nit+1(si,ai)=2kN_i^t+1(s_i,a_i)=2^k. We call such a time a confidence update time; it does not reset the trajectory, the counters, or the optimization iterate. There are two reasons for this dyadic schedule. First, it incurs only a constant-factor statistical loss. Between two successive thresholds 2k2^k and 2k+12^k+1, a confidence radius based on the last threshold is at most a factor of 2 2 larger than the radius based on the current count. Thus, the usual Nit(si,ai)−1/2N^t_i(s_i,a_i)^-1/2 estimation rate is preserved. Second, and more importantly for the analysis, changing the confidence set changes the feasible occupancy polytope. On intervals where this polytope is fixed, the ordinary proximal step gives the small-movement bound (Lemma 14), which is used to couple the time-varying local chain to a frozen-policy chain. Dyadic refreshing ensures that each local counter causes only (logT)O( T) feasible-set changes by time T. Hence, the exceptional times at which the feasible polytope itself changes can be charged separately without affecting the ~(T−1/2) O(T^-1/2) order of our final bound. Crucially, these confidence updates are entirely local and asynchronous. Player i determines its confidence update times using only its own counters. Player j may refresh its confidence set at a completely different primitive time, and neither player needs to know when the other player’s refresh occurs. Thus, the algorithm operates on a fast clock, on which every player updates its occupancy iterate after every interaction, and a slower, local, event-driven clock, on which each player independently refines its transition kernel. At a confidence update time, player i constructs a new rectangular confidence region using all samples accumulated so far and intersects it with its previous confidence set. By Lemma 8, the resulting shrunk occupancy set admits an explicit polynomial-size linear representation. Thus, the online mirror-descent update, which amounts to a Euclidean projection onto Δi,δi(it) _i, _i(P_i^t), can be carried out efficiently in polynomial time. As shown in the following lemma, on the anytime confidence event used in the analysis, the true kernel PiP_i belongs to every such confidence set; hence, the nested confidence sets remain nonempty while progressively refining the uncertainty about PiP_i. Lemma 10. Define the anytime confidence event ℰconf:=Pi∈it,∀i∈[n],∀t≥0E_ conf:= \P_i _i^t, ∀ i∈[n],\ ∀ t≥ 0 \. Under Algorithm 1, we have ℙ(ℰconf)≥1−γ/4P(E_ conf)≥ 1-γ/4. Consequently, on ℰconfE_ conf, Δi,δi(Pi)⊆Δi,δi(it)∀i,t≥0 _i, _i(P_i) _i, _i(P_i^t)\ ∀ i,t≥ 0. Remark 11. Algorithm 1 is fully decentralized in terms of the information used by each player. In particular, player i maintains only its own local counters NitN_i^t and MitM_i^t and checks for a confidence update only when the count associated with its currently observed local state–action pair (Sit,Ait)(S_i^t,A_i^t) reaches a power of two. Player i neither observes nor keeps track of the counters, states, actions, transition samples, or confidence-update events of any other player. Consequently, confidence updates of different players may occur at different primitive times, and no common confidence-update clock, joint-state counter, synchronization signal, or coordination among the players is required. We conclude this section by outlining the main ideas behind the finite-time regret analysis in the next section. The regret is decomposed into a mirror-descent optimization error, an occupancy-tracking error, and a one-sample gradient-estimation error. These terms are controlled using the proximal inequality, local coverage and confidence-set concentration, and a delayed coupling argument relating the time-varying trajectory to frozen-policy stationary dynamics, respectively. Finally, confidence-update times are handled separately by exploiting their logarithmic frequency under the dyadic schedule. Together, these ingredients establish the no-regret guarantee in the online setting. 5 Finite-Time Regret Guarantee for the Fully Online Decentralized Algorithm We begin the analysis of Algorithm 1 by introducing the following terminology and filtration. 5.1 True and Confidence-Feasible Occupancies We distinguish throughout between true-kernel feasible and confidence-feasible occupancy measures. An occupancy measure qiq_i is called true-kernel feasible if qi∈Δi(Pi)q_i∈ _i(P_i), i.e., if its induced transition kernel PqiP^q_i equals the true transition kernel PiP_i. Its corresponding state–action and state marginal occupancies are denoted by ρi _i and νi _i, respectively. In contrast, an occupancy measure q^i q_i is called confidence-feasible if q^i∈Δi,δi(i) q_i∈ _i, _i(P_i), meaning that its induced transition kernel belongs to the confidence set iP_i, i.e., Pq^i∈iP q_i _i. Its corresponding marginals are denoted by ρ^i ρ_i and ν^i ν_i. Accordingly, for each time t, let qit,ρit,νitq_i^t, _i^t, _i^t denote the true-kernel feasible occupancies induced by the current stationary policy πit _i^t and the true kernel PiP_i. Thus, qitq_i^t is the true-kernel feasible occupancy induced by (πit,Pi)( _i^t,P_i), whereas q^it q_i^t is the confidence-feasible occupancy that induces (πit,P^it)( _i^t, P_i^t), where, for simplicity, we write P^it:=Pq^it∈it P_i^t:=P q_i^t _i^t. Hence, throughout the analysis, unhatted occupancy quantities refer to the true kernel PiP_i, while hatted occupancy quantities refer to the confidence-feasible iterates maintained by the algorithm. 5.2 Filtration and Regret Decomposition For the probabilistic arguments, let the filtration ℱtF_t contain all the information available strictly before time t, such as S0,A0,r0,S1,A1,r1,…,At−1,rt−1S^0,A^0,r^0,S^1,A^1,r^1,…,A^t-1,r^t-1, as well as the current state StS^t, but not the fresh randomization used to sample AtA^t. Note that this is a global filtration used only for the purpose of analysis and does not enlarge any player’s information set in Algorithm 1. Thus, ℱtF_t represents the information available immediately before the action AtA^t is sampled: the current state StS^t and all states, actions, rewards, transition observations, counters, confidence sets, and iterates constructed from primitive times strictly before t are ℱtF_t-measurable. After conditioning on ℱtF_t, the action AtA^t is sampled according to the current policy profile, the reward rtr^t is observed, and the next state St+1S^t+1 is generated; consequently, these variables are measurable with respect to ℱt+1F_t+1. Throughout the paper, expressions such as ℙ(Sit=⋅∣ℱt−D)P(S_i^t=· _t-D) denote the conditional probability distribution of SitS_i^t given the information available at the beginning of the delay time t−Dt-D. Definition 12. For player i and a fixed true-kernel comparator qi′∈Δi,δi(Pi)q_i ∈ _i, _i(P_i), define the fixed-comparator regret Regi(T;qi′):=∑t=0T−1[Vi(qi′,q−it)−Vi(qit,q−it)]Reg_i(T;q_i ):= _t=0^T-1 [V_i(q_i ,q_-i^t)-V_i(q_i^t,q_-i^t) ], where qit∈Δi(Pi)q_i^t∈ _i(P_i) is the true-kernel feasible occupancy induced by the current policy πit:=πiq^it _i^t:= _i q_i^t under the true kernel PiP_i. We note that since Vi(qi,q−i)=⟨qi,gi(q−i)⟩V_i(q_i,q_-i)= q_i,g_i(q_-i) whenever the displayed occupancies are true-kernel feasible, using Proposition 5, we have Regi(T;qi′)=∑t=0T−1[Vi(qi′,q−it)−Vi(qit,q−it)]=∑t=0T−1⟨qi′−qit,gi(q−it)⟩. _i(T;q_i )= _t=0^T-1 [V_i(q_i ,q_-i^t)-V_i(q_i^t,q_-i^t) ]= _t=0^T-1 q _i-q_i^t,g_i(q_-i^t) . (15) Writing git:=gi(q−it)g_i^t:=g_i(q_-i^t) and adding and subtracting q^it q_i^t and R^it R_i^t to (15) gives the basic decomposition Regi(T;qi′)= _i(T;q_i )= ∑t<T⟨qi′−q^it,R^it⟩⏟ℳi(T,qi′)+∑t<T⟨qi′−q^it,git−R^it⟩⏟ℰi(T,qi′)+∑t<T⟨q^it−qit,git⟩⏟i(T). _t<T q_i - q_i^t, R_i^t _M_i(T;q_i )+ _t<T q_i - q_i^t,g_i^t- R_i^t _E_i(T;q_i )+ _t<T q_i^t-q_i^t,g_i^t _Q_i(T). (16) The decomposition (16) provides the roadmap for the proof. The first term, ℳiM_i, is the optimization error that would remain even if the payoff-gradient samples were unbiased and the transition kernels were known. It is controlled directly by the Euclidean proximal inequality in Lemma 13. The third term, iQ_i, captures the error from optimizing over the confidence-feasible occupancy q^it q_i^t rather than the true-kernel occupancy qitq_i^t induced by the same policy. To control this term, in Lemma 14, we first show that mirror descent changes the policy slowly whenever the confidence set remains unchanged. We then freeze the policy over deterministic local-cover blocks and couple the actual local chain with the corresponding frozen chain. This yields linear growth of every local state–action counter, which in turn implies shrinking confidence radii for PiP_i. Uniform contraction then translates the kernel estimation error into the corresponding stationary occupancy error, which controls iQ_i. The second term, ℰiE_i, captures the main difficulty arising from the fully online setting: R^it R_i^t is formed from a single payoff sample generated by an adaptive, nonstationary Markov trajectory, whereas gitg_i^t is the stationary payoff gradient associated with the current true-kernel occupancies q−itq_-i^t induced by the current policy πtπ^t. We control this term using delayed analysis in Lemma 16. 5.3 Main Regret Bound Analysis Here, we provide the main analysis for the finite-time no-regret guarantee. We begin with the following lemma, which bounds the first term ℳi(T,qi′)M_i(T;q_i ) in the regret decomposition (16). Lemma 13. On the anytime confidence event ℰconfE_ conf, for every qi′∈Δi,δi(Pi)q_i ∈ _i, _i(P_i) and every constant stepsize η>0η>0, we have ∑t<T⟨qi′−q^it,R^it⟩≤‖qi′−q^i0‖222η+η2∑t<T‖R^it‖22≤1η+|i|ηT2δi2. _t<T q_i - q_i^t, R_i^t ≤ \|q_i - q_i^0\|_2^22η+ η2 _t<T\| R_i^t\|_2^2≤ 1η+ |S_i|η T2 _i^2. (17) The following lemma provides a high-probability bound on the policy and occupancy movements over the course of the algorithm, which allows us to bound the third term i(T)Q_i(T) in (16). Lemma 14. Fix T and use the constant stepsize η=T−1/2η=T^-1/2. Define Li:=|i|3|i|L_i:= |S_i|^3|A_i|. Suppose maxiLiHi2ηδi2≤116. _i L_iH_i^2η _i^2≤ 116. (18) Then, with probability at least 1−γ/21-γ/2, the following hold simultaneously for every player i: (i) On every step t at which player i does not update its confidence set, maxsi∈i∥πit+1(⋅∣si)−πit(⋅∣si)∥1≤2Liηδi2. _s_i _i\| _i^t+1(· s_i)- _i^t(· s_i)\|_1≤ 2L_iη _i^2. (19) (i) Let Ki(T):=cHiδi(ΛTδi+|i||i|log2T)K_i(T):=c H_i _i ( _T _i+|S_i||A_i| _2T ). Then, for every Ki(T)≤t<TK_i(T)≤ t<T, ‖ρ^it−ρit‖1≤c|i|κmaxsi,aiβt(si,ai)≤c|i|κHiΛtδit. \| ρ_i^t- _i^t\|_1≤ c |S_i|κ _s_i,a_iβ^t(s_i,a_i)≤ c |S_i|κ H_i _t _it. (20) (i) Consequently, |1T∑t<T⟨q^it−qit,git⟩|≤cKi(T)T+c|i|κHiΛTδiT. | 1T _t<T q_i^t-q_i^t,g_i^t |≤ c K_i(T)T+c |S_i|κ H_i _T _iT. (21) Next, we bound the second term ℰi(T,qi′)=∑t<T⟨qi′−q^it,git−R^it⟩E_i(T;q_i )= _t<T q_i - q_i^t,g_i^t- R_i^t in the regret decomposition. At time t, the estimator R^it R_i^t uses the actual observation (St,At,rit)(S^t,A^t,r_i^t),44 4 The actual trajectory is generated by the true kernel PiP_i with the interaction flow it→q^it→πit→Ait→PiSit+1P_i^t→ q_i^t→ _i^t→ A_i^t P_iS_i^t+1. Thus, P^it=Pq^it P_i^t=P q_i^t is used only for analysis to relate the confidence-feasible occupancy q^it q_i^t, induced by (πit,P^it)( _i^t, P_i^t), to the true-kernel occupancy qitq_i^t, induced by (πit,Pi)( _i^t,P_i), and does not play a role in generating the actual trajectory. whereas git=gi(q−it)g_i^t=g_i(q_-i^t) is defined in terms of the stationary occupancies qjtq_j^t. In general, there is no reason for the actual state StS^t, conditional on the immediately preceding history, to be distributed according to these stationary occupancies. We therefore look back DTD_T steps and condition on ℱt−DTF_t-D_T, where the delay DTD_T is introduced for one fundamental reason: to provide a sufficiently long window over which the actual time-varying process can be approximated by a time-homogeneous process that has enough time to mix, so that the conditional law of the actual online sample can be well approximated by the corresponding stationary-occupancy distribution. Since the policies continue to change during these DTD_T steps, the proof couples the actual trajectory with an auxiliary time-homogeneous trajectory whose policies are frozen at time t−DTt-D_T. This allows us to show that, over a time window [t−DT,t][t-D_T,t] during which no player performs a confidence update, the conditional law of the actual state–action profile at time t is close to the product stationary law corresponding to the policies at time t−DTt-D_T. Lemma 15. Let DT≥0D_T≥ 0 be a nonnegative integer delay, and fix t≥DTt≥ D_T. Assume that no player updates its confidence set during the time delay window [t−DT,t][t-D_T,t], and let Lj=|j||j|3L_j\!=\! |A_j||S_j|^3. Then ∥ℙ((St,At)∈⋅∣ℱt−DT)−⨂j=1nρjt−DT∥TV≤cDT2η∑j=1nLjδj2+n(1−κ)DT. \|P((S^t,A^t)∈· _t-D_T)- _j=1^n _j^t-D_T \|_ TV≤ cD_T^2η _j=1^n L_j _j^2+n(1-κ)^D_T. (22) To relate the payoff estimator R^it R_i^t, which is constructed from the actual nonstationary trajectory, to the occupancy-payoff gradient gitg_i^t, we use a delayed comparison over a mixing window of length DTD_T. In particular, by conditioning on ℱt−DTF_t-D_T, we leave (St,At)(S^t,A^t) random over the mixing window. We first use the slow movement of the occupancy iterates in Lemma 14 to replace the current denominator ρ^it ρ_i^t in R^it R_i^t with the delayed denominator ρ^it−DT ρ_i^t-D_T, which is ℱt−DTF_t-D_T-measurable. Lemma 15 then shows that the conditional law of (St,At)(S^t,A^t) given ℱt−DTF_t-D_T is close to the product stationary law ⨂jρjt−DT _j _j^t-D_T. Under this product stationary law, the mean of R^it R_i^t with denominator ρ^it−DT ρ_i^t-D_T is git−DT(si,ai,si′)ρit−DT(si,ai)/ρ^it−DT(si,ai)g_i^t-D_T(s_i,a_i,s_i ) _i^t-D_T(s_i,a_i)/ ρ_i^t-D_T(s_i,a_i). The occupancy-estimation bound controls the difference between this quantity and the delayed occupancy-payoff gradient git−DTg_i^t-D_T, while the slow movement of the policies controls the remaining drift from git−DTg_i^t-D_T to gitg_i^t. Using these observations, the following lemma bounds the second term ℰi(T,qi′)E_i(T;q_i ) in (16) as follows: Lemma 16. Let git:=gi(q−it)g_i^t:=g_i(q_-i^t) be the occupancy-payoff gradient (7) and DT:=1+⌈1κlog(8nT3γ)⌉D_T:=1+ 1κ ( 8nT^3γ) . Then, with probability at least 1−γ1-γ, uniformly over qi′∈Δi,δi(Pi)q_i ∈ _i, _i(P_i), we have 1T|∑t<T⟨qi′−q^it,R^it−git⟩|≲TDTΛT+DTΛTδi+DTηLiδi3+DT2ηδi∑j=1nLjδj2 \!\!\!\! 1T | _t<T q_i - q_i^t, R_i^t-g_i^t | TD_T _T+D_T _TT _i+ D_Tη L_i _i^3+ D_T^2η _i _j=1^n L_j _j^2 (23) +|i|κδiHiΛTδiT+DTη∑j≠iLjκδj2+DTTδi∑j=1nJj(T)+DT+Ki(T)Tδi, + |S_i|κ _i H_i _T _iT+D_Tη _j≠ i L_jκ _j^2+ D_TT _i _j=1^nJ_j(T)+ D_T+K_i(T)T _i, (24) where Lj=|j|3|j|L_j= |S_j|^3|A_j|, Ki(T)=cHiδi(ΛTδi+|i||i|log2T)K_i(T)=c H_i _i ( _T _i+|S_i||A_i| _2T ), and Ji(T)=|i||i|(log2T+1)J_i(T)=|S_i||A_i|( _2T+1). Finally, by combining the preceding lemmas we obtain the main result of this section. Theorem 17. Let Assumptions 1 and 2 hold. Fix T≥2T≥ 2 and γ∈(0,1)γ∈(0,1), and assume players follow Algorithm 1 with the quadratic regularizer and constant stepsize η=T−1/2η=T^-1/2. Let Smax:=maxi∈[n]|i|,Amax:=maxi∈[n]|i|,H:=maxi∈[n]Hi,δ:=mini∈[n]δi,S_ := _i∈[n]|S_i|, A_ := _i∈[n]|A_i|, H:= _i∈[n]H_i, δ:= _i∈[n] _i, and suppose T≥256Smax3AmaxH4δ4T\!≥\! 256S_ ^3A_ H^4δ^4, so that condition (18) holds.55 5 For smaller horizons the criterion is bounded by its trivial constant upper bound. Then, with probability at least 1−γ1-γ, maxi∈[n]maxqi′∈Δi,δi(Pi)1TRegi(T;qi′)≤ℭ1T+ℭ2T, _i∈[n]\; _q_i ∈ _i, _i(P_i) 1TReg_i(T;q_i )≤ C_1 T+ C_2T, (25) where, up to universal constants and logarithmic factors, ℭ1 C_1 =~(SmaxHκδ3/2log(nAmaxSmax2T2γ)+nSmax3/2Amax1/2κ2δ3log2(nT3γ)), = O ( S_ Hκδ^3/2 \! ( nA_ S_ ^2T^2γ )+ nS_ ^3/2A_ ^1/2κ^2δ^3 ^2\! ( nT^3γ ) ), (26) ℭ2 C_2 =~(Hδ3log(nAmaxSmax2T2γ)+HSmaxAmaxδ2+nSmaxAmaxκδlog(nT3γ)). = O ( Hδ^3 \! ( nA_ S_ ^2T^2γ )+ HS_ A_ δ^2+ nS_ A_ κδ \! ( nT^3γ ) ). (27) Proof. Fix a player i and an arbitrary comparator qi′∈Δi,δi(Pi)q_i ∈ _i, _i(P_i). By (16), 1TRegi(T;qi′)= 1TReg_i(T;q_i )= ℳi(T,qi′)T+ℰi(T,qi′)T+i(T)T. M_i(T;q_i )T+ E_i(T;q_i )T+ Q_i(T)T. We bound the three terms using the preceding lemmas. First, on the anytime confidence event ℰconfE_ conf, Lemma 13 with η=T−1/2η=T^-1/2 gives ℳi(T,qi′)T≤1T+|i|2δi2T. M_i(T;q_i )T≤ 1 T+ |S_i|2 _i^2 T. (28) Second, Lemma 16, uniformly over qi′∈Δi,δi(Pi)q_i ∈ _i, _i(P_i), gives |ℰi(T,qi′)|T≲ |E_i(T;q_i )|T TDTΛT+DTΛTδi+DTLiδi3T+DT2δiT∑j=1nLjδj2 TD_T _T+D_T _TT _i+ D_TL_i _i^3 T+ D_T^2 _i T _j=1^n L_j _j^2 (29) +|i|κδiHiΛTδiT+DTT∑j≠iLjκδj2+DTTδi∑j=1nJj(T)+DT+Ki(T)Tδi. + |S_i|κ _i H_i _T _iT+ D_T T _j≠ i L_jκ _j^2+ D_TT _i _j=1^nJ_j(T)+ D_T+K_i(T)T _i. (30) Finally, part (i) of Lemma 14 yields |i(T)|T≲Ki(T)T+|i|κHiΛTδiT. |Q_i(T)|T K_i(T)T+ |S_i|κ H_i _T _iT. (31) We now simplify these bounds in terms of the maximal individual-chain parameters appearing in the theorem. By definition, |i|≤Smax|S_i|≤ S_ , |i|≤Amax|A_i|≤ A_ , Hi≤H_i≤ H, δi≥δ _i≥δ, and therefore Li L_i ≤Smax3/2Amax1/2,∑j=1nLjδj2≤nSmax3/2Amax1/2δ2,ΛT≲log(nAmaxSmax2T2γ),DT≲1κlog(nT3γ). ≤ S_ ^3/2A_ ^1/2, _j=1^n L_j _j^2≤ nS_ ^3/2A_ ^1/2δ^2, \! _T \! ( nA_ S_ ^2T^2γ ), \!\!D_T 1κ \! ( nT^3γ ). Substituting these relations into (28)–(31), the dominant terms of order T−1/2T^-1/2 are 1T~(SmaxHκδ3/2log(nAmaxSmax2T2γ)+nSmax3/2Amax1/2κ2δ3log2(nT3γ)). 1 T\, O ( S_ Hκδ^3/2 \! ( nA_ S_ ^2T^2γ )+ nS_ ^3/2A_ ^1/2κ^2δ^3 ^2\! ( nT^3γ ) ). (32) Indeed, the first displayed term contains the occupancy-estimation contributions in (29) and (31), while the second contains the dominant DT2∑jLj/δj2D_T^2 _jL_j/ _j^2 contribution in (29); the remaining T−1/2T^-1/2 terms are of no larger order and are absorbed into these two terms. For the lower-order terms, using Jj(T) J_j(T) =|j||j|(log2T+1),Ki(T)=cHiδi(ΛTδi+|i||i|log2T), =|S_j||A_j|( _2T+1), K_i(T)=c H_i _i ( _T _i+|S_i||A_i| _2T ), we obtain 1T~(Hδ3log(nAmaxSmax2T2γ)+HSmaxAmaxδ2+nSmaxAmaxκδlog(nT3γ)). 1T\, O ( Hδ^3 \! ( nA_ S_ ^2T^2γ )+ HS_ A_ δ^2+ nS_ A_ κδ \! ( nT^3γ ) ). (33) Here, the logarithmic factors in T arising from Jj(T)J_j(T) and the second term in Ki(T)K_i(T) are absorbed into the ~ O notation, while the dependence on the confidence level γ is displayed explicitly. Combining (32) and (33), and then taking the maximum over qi′∈Δi,δi(Pi)q_i ∈ _i, _i(P_i) and i∈[n]i∈[n], gives (25) with ℭ1 C_1 and ℭ2 C_2 as defined in (26). Finally, Lemma 16 holds on an event of probability at least 1−γ1-γ that includes the event of Lemma 14, and the anytime confidence event required by Lemma 13 is also included in that event. Consequently, all the preceding bounds hold simultaneously with probability at least 1−γ1-γ, which completes the proof. ∎ Corollary 18. On the event of Theorem 17, for sufficiently small action floor δ=maxiδiδ= _i _i, the empirical distribution over the policy profiles πtt=0T−1\π^t\_t=0^T-1 is an (ϵT+ϵδ)( _T+ _δ)-coarse correlated equilibrium of the original stochastic game, where ϵT:=ℭ1T+ℭ2T _T:= C_1 T+ C_2T, and ϵδ>0 _δ>0 is the approximation error due to the action-floor constraints, which can be made arbitrarily small as δ→0δ→ 0. Proof. Let U be uniformly distributed over 0,…,T−1\0,…,T-1\. For every player i, the definition of Regi(T;qi′)Reg_i(T;q_i ) and Theorem 17 give maxqi′∈Δi,δi(Pi)[Vi(qi′,q−iU)−Vi(qiU,q−iU)]=maxqi′∈Δi,δi(Pi)1T∑t=0T−1[Vi(qi′,q−it)−Vi(qit,q−it)]≤ϵT. _q_i ∈ _i, _i(P_i)E\! [V_i(q_i ,q_-i^U)-V_i(q_i^U,q_-i^U) ]= _q_i ∈ _i, _i(P_i) 1T _t=0^T-1 [V_i(q_i ,q_-i^t)-V_i(q_i^t,q_-i^t) ]≤ _T. Moreover, for every ϵδ>0 _δ>0, the action floor δ can be chosen sufficiently small so that optimization over the shrunk feasible occupancy polytope is within ϵδ _δ of optimization over the full occupancy polytope (Etesami, 2024, Lemma 3.4). Hence, maxqi′∈Δi(Pi)1T∑t=0T−1Vi(qi′,q−it)≤maxqi′∈Δi,δi(Pi)1T∑t=0T−1Vi(qi′,q−it)+ϵδ. _q_i ∈ _i(P_i) 1T _t=0^T-1V_i(q_i ,q_-i^t)≤ _q_i ∈ _i, _i(P_i) 1T _t=0^T-1V_i(q_i ,q_-i^t)+ _δ. Combining the two bounds yields maxqi′∈Δi(Pi)[Vi(qi′,q−iU)−Vi(qiU,q−iU)]≤ϵT+ϵδ,∀i∈[n] _q_i ∈ _i(P_i)E\! [V_i(q_i ,q_-i^U)-V_i(q_i^U,q_-i^U) ]≤ _T+ _δ,\ ∀ i∈[n], which is precisely the (ϵT+ϵδ)( _T+ _δ)-coarse correlated equilibrium condition for the virtual occupancy game. By the equivalence between the virtual occupancy game and the original stochastic game, the empirical distribution uniformly supported on the corresponding stationary policy profiles πtt=0T−1\π^t\_t=0^T-1 is therefore an (ϵT+ϵδ)( _T+ _δ)-coarse correlated equilibrium of the original stochastic game. ∎ Remark 19. Theorem 17 uses a horizon-dependent constant stepsize only to make the finite-time regret bound transparent. This dependence on a known horizon can be removed by a standard doubling schedule: run the algorithm over epochs of lengths 1,2,4,…1,2,4,… and use ηm≍2−m/2 _m 2^-m/2 during epoch m, without resetting the trajectory or the confidence counters. Applying the preceding finite-time analysis epochwise after the local-cover threshold and summing the resulting regret bounds yields the same ~(T−1/2) O(T^-1/2) average-regret rate, since the sum of the Tm T_m contributions over geometrically increasing epoch lengths is of order T T, while the lower-order transient contributions remain logarithmic in T. Alternatively, one may use ηt=c/t+1 _t=c/ t+1; once the stepsize is small enough for (18) to hold, the same block comparison applies, while the finitely many preceding time steps contribute only an additive O(1/T)O(1/T) term to the average regret. 6 Asymptotic Last-Iterate Convergence to an ϵε-Nash Equilibrium It is known that, for general reward functions, computing a NE in stochastic games with independent chains is PPAD-hard even when the transition kernels are known (Etesami, 2024, Proposition 3.3). Therefore, under general reward functions, developing a scalable no-regret algorithm for obtaining a coarse correlated equilibrium, as established in the previous section, is perhaps the best one can hope for computationally. In this section, we show that if the reward functions possess additional structure, in the sense that the game admits a stable NE, then the same fully online algorithm converges with arbitrarily high probability to a stationary ϵε-NE of the original stochastic game. This complements the results of the previous section: not only does the algorithm provide a scalable no-regret guarantee for coarse correlated equilibria, but under the additional stability condition, the same algorithm converges to an ϵε-NE of the original stochastic game. To this end, we first introduce the following notion of equilibrium stability, which has been well studied and motivated for static games (Mertikopoulos and Zhou, 2019). Assumption 3. The virtual game V admits a unique NE q∗q^* satisfying ∑i=1n⟨gi(q−i),qi∗−qi⟩≥0,∀q∈():=(Δδ1(P1),…,Δδn(Pn)), _i=1^n g_i(q_-i),q_i^*-q_i ≥ 0, ∀ q∈ _ δ( P):=( _ _1(P_1),…, _ _n(P_n)), with equality only at q=q∗q=q^*. Assumption 3 requires that the joint payoff-gradient field always points toward the unique NE q∗q^*. Moreover, the inequality is strict away from q∗q^*, so q∗q^* is the unique stable point toward which the learning dynamics are driven. We now turn to the convergence analysis of the fully online algorithm under Assumption 3. A key difficulty is that the transition kernels are unknown and the confidence-feasible occupancy sets continue to evolve over time. We first show in Lemma 20 that persistent exploration guarantees a positive asymptotic visitation frequency for every local state–action pair. This implies that the confidence radii vanish and, consequently, that the confidence-feasible occupancies q^it q_i^t asymptotically approach their true-kernel counterparts qitq_i^t. We next show in Lemma 21 that the confidence-feasible occupancy sets converge to their corresponding true-kernel feasible sets and that the occupancy jumps caused by confidence-set updates are summable. Finally, in Theorem 22, we combine these properties with the diminishing stepsizes and the variational-stability condition in Assumption 3 to establish convergence of the occupancy iterates to the unique stable equilibrium q∗q^*, which in turn yields last-iterate convergence of the induced policies to a stationary ϵε-NE of the original game. Lemma 20. Suppose Assumptions 1 and 2 hold, and let ηt=η0(t+1)−a _t= _0(t+1)^-a with a∈(1/2,1]a∈(1/2,1]. On the anytime confidence event ℰconfE_ conf, almost surely, for every player i and every local pair (si,ai)(s_i,a_i), lim inft→∞Nit(si,ai)t≥δi32Hi>0. _t→∞ N_i^t(s_i,a_i)t≥ _i32H_i>0. (34) Consequently, almost surely, there exists a finite random time T0T_0 such that, for every t≥T0t≥ T_0 and i, maxsi,aiβit(si,ai)=O(log(t+2)t+1), _s_i,a_i _i^t(s_i,a_i)=O (\! (t+2)t+1 ), (35) ‖q^it−qit‖1=O(log(t+2)t+1)→0. \| q_i^t-q_i^t\|_1=O (\! (t+2)t+1 )→ 0. (36) Next, we use the vanishing confidence radii established in Lemma 20 to control the effect of confidence-set updates. In particular, the following lemma shows that the confidence-feasible occupancy sets approach the corresponding true-kernel feasible sets as t→∞t→∞. As a consequence, the jumps in the occupancy iterates caused by the asynchronous confidence updates decay sufficiently fast to be summable. Lemma 21. Let dist1(x,):=infy∈‖x−y‖1dist_1(x,C):= _y \|x-y\|_1. On the event of Lemma 20, supx∈Δi,δi(it)dist1(x,Δi,δi(Pi))≤O(|i|maxsi,aiβit(si,ai))=O(|i|log(t+2)t+1). _x∈ _i, _i(P_i^t)dist_1\! (x, _i, _i(P_i) )≤ O (|S_i| _s_i,a_i _i^t(s_i,a_i) )=O (|S_i| (t+2)t+1 ). (37) Consequently, if ℛiR_i denotes the confidence-update times for player i, then occupancy jumps satisfy ∑t∈ℛi‖q^it+1−q^it‖1<∞. _t _i\| q_i^t+1- q_i^t\|_1<∞. (38) Finally, by combining the above lemmas we can prove the main result of this section. Theorem 22. Let Assumptions 1, 2, and 3 hold. Assume players follow Algorithm 1 with ηt=η0(t+1)−a _t= _0(t+1)^-a, a∈(1/2,1]a∈(1/2,1]. Then, with probability at least 1−γ1-γ, q^t→q∗ q^t→ q^* and qt→q∗q^t→ q^*, where q∗q^* is the unique stable NE of the virtual game. Consequently, the induced stationary policies converge to the policy profile represented by q∗q^*. In particular, for sufficiently small action floors δ=maxiδiδ= _i _i, this policy profile is an ϵδ _δ-NE of the original game, where ϵδ→0 _δ→ 0 as the action floors δ tend to zero. Proof. Work on the anytime confidence event ℰconfE_ conf, which, by Lemma 10, has probability at least 1−γ/41-γ/4. On this event, the conclusions of Lemmas 20 and 21 hold almost surely. In the argument below, we additionally invoke the concentration events from Lemma 16 on the dyadic epochs, with failure probabilities γmm≥0\ _m\_m≥ 0 satisfying ∑m≥0γm≤γ/2 _m≥ 0 _m≤γ/2. Hence, by a union bound, all the events used in the proof hold simultaneously with probability at least 1−3γ/41-3γ/4, and therefore at least 1−γ1-γ. By Assumption 3, the unique stable equilibrium q∗∈()q^*∈ _ δ( P) satisfies G(q):=∑i=1n⟨gi(q−i),qi∗−qi⟩≥0,G(q)=0⟺q=q∗.G(q):= _i=1^n g_i(q_-i),q_i^*-q_i ≥ 0, G(q)=0 q=q^*. Define the Lyapunov function V(q^t):=12∑i=1n‖qi∗−q^it‖22.V( q^t):= 12 _i=1^n\|q_i^*- q_i^t\|_2^2. We first show that, for every m≥0m≥ 0, over the dyadic interval Im:=2m,…,2m+1−1I_m:=\2^m,…,2^m+1-1\, V(q^2m+1)≤V(q^2m)−∑t∈ImηtG(qt)+em,em≥0,∑m=0∞em<∞. V( q^2^m+1)≤ V( q^2^m)- _t∈ I_m _tG(q^t)+e_m, e_m≥ 0, _m=0^∞e_m<∞. (39) Since qi∗∈Δi,δi(it)q_i^*∈ _i, _i(P_i^t) on the anytime confidence event ℰconfE_ conf, the one-step proximal inequality derived from (48), with qi′=qi∗q_i =q_i^* and stepsize ηt _t, gives V(q^t+1) V( q^t+1) −V(q^t)≤−ηt∑i⟨qi∗−q^it,R^it⟩+ηt22∑i∥R^it∥22 -V( q^t)≤- _t _i q_i^*- q_i^t, R_i^t + _t^22 _i\| R_i^t\|_2^2 =−ηtG(qt)−ηt∑i⟨qi∗−q^it,R^it−git⟩−ηt∑i⟨qit−q^it,git⟩+ηt22∑i‖R^it‖22. =- _tG(q^t)- _t _i q_i^*- q_i^t, R_i^t-g_i^t - _t _i q_i^t- q_i^t,g_i^t + _t^22 _i\| R_i^t\|_2^2. (40) Thus, after summing over t∈Imt∈ I_m, it remains only to show that the last three terms in (40), summed over the dyadic epochs, are absolutely summable. For the last two terms in (40), using ‖git‖∞≤1\|g_i^t\|_∞≤ 1, ‖R^it‖2≤|i|/δi\| R_i^t\|_2≤ |S_i|/ _i, and (36), we obtain ∑t=0∞ηt|∑i⟨qit−q^it,git⟩| _t=0^∞ _t | _i q_i^t- q_i^t,g_i^t | ≤∑i∑t=0∞ηt‖q^it−qit‖1≲∑t=1∞t−alog(t+2)t<∞, ≤ _i _t=0^∞ _t\| q_i^t-q_i^t\|_1 _t=1^∞t^-a (t+2)t<∞, (41) ∑t=0∞ηt22∑i‖R^it‖22 _t=0^∞ _t^22 _i\| R_i^t\|_2^2 ≤12∑i|i|δi2∑t=0∞ηt2<∞. ≤ 12 _i |S_i| _i^2 _t=0^∞ _t^2<∞. (42) It remains to control the estimator error in (40). For each epoch ImI_m, set Dm=1+⌈1κlog(16n 23(m+1)γm)⌉D_m\!=\!1+ 1κ ( 16n\,2^3(m+1) _m) and γm:=3γπ2(m+1)2 _m:= 3γπ^2(m+1)^2. We apply Lemma 16 to each epoch ImI_m, with q′=q∗q =q^*, horizon |Im|=2m|I_m|=2^m, delay Dm=O(m)D_m=O(m), failure probability γm _m, and stepsize upper bound η¯m:=η2m≍2−am η_m:= _2^m 2^-am.66 6 Although Lemma 16 is stated for a constant stepsize and the interval 0,…,T−1\0,…,T-1\, its proof extends directly to any interval I=u,…,v−1I=\u,…,v-1\ and nonincreasing stepsizes ηt\ _t\. Indeed, with η¯I:=maxt∈Iηt=ηu η_I:= _t∈ I _t= _u, the weights ηt _t can be carried through the same martingale and bias estimates and bounded by η¯I η_I, while the policy-movement estimates are controlled by η¯I η_I. Thus, the same cumulative estimate holds with the constant stepsize replaced by η¯I η_I. Substituting these quantities into the bound of Lemma 16, yields, up to fixed problem-dependent constants and logarithmic factors, ∑m=0∞|∑t∈Imηt∑i⟨qi∗−q^it,R^it−git⟩| _m=0^∞ | _t∈ I_m _t _i q_i^*- q_i^t, R_i^t-g_i^t | (43) ≲∑m=0∞[m 2(1/2−a)m+m2 2(1−2a)m+m 2(1/2−a)m+m 2−am]<∞. _m=0^∞ [m\,2^(1/2-a)m+m^2\,2^(1-2a)m+ m\,2^(1/2-a)m+m\,2^-am ]<∞. (44) Here, the first three summands in (43) dominate the terms obtained from Lemma 16. The additional last term m2−am2^-am accounts for the first DmD_m times of each shifted epoch, whose delay windows extend before the epoch. Bounding these terms directly gives a total weighted contribution of order Dmη¯m=O(m2−am)D_m η_m=O(m2^-am). All the sums in (43) are finite because a>1/2a>1/2 and by the choice of DmD_m. Moreover, ∑mγm≤γ2 _m _m≤ γ2, so a union bound over the dyadic epochs makes these estimates simultaneous on the common event under consideration. Finally, summing (40) over t∈Imt∈ I_m and defining eme_m as the sum of the absolute values of the three error contributions in (41)–(43) gives (39). We now use (39) to prove convergence. Since G(q)≥0G(q)≥ 0, summing (39) over m and using the summability of its error terms gives ∑t=1∞ηtG(qt)<∞. _t=1^∞ _tG(q^t)<∞. (45) Suppose that q^t q^t has a limit point q¯≠q∗ q≠ q^*. By (36), ‖qt−q^t‖1→0\|q^t- q^t\|_1→ 0, so q¯ q is also a limit point of qt\q^t\. By continuity of G(⋅)G(·) and Assumption 3, there exist r>0r>0 and a constant cU>0c_U>0 such that G(q)≥cUG(q)≥ c_U for every q∈()q∈ _ δ( P) satisfying ‖q−q¯‖1≤2r\|q- q\|_1≤ 2r. Define the neighborhoods U0:=q:‖q−q¯‖1<r/2U_0:=\q:\|q- q\|_1<r/2\ and U:=q:‖q−q¯‖1<rU:=\q:\|q- q\|_1<r\. Since ‖qt−q^t‖1→0\|q^t- q^t\|_1→ 0, for all sufficiently large t, q^t∈U q^t∈ U implies ‖qt−q¯‖1≤2r\|q^t- q\|_1≤ 2r, and hence G(qt)≥cUG(q^t)≥ c_U. Away from confidence-update times, the occupancy-movement estimate (53) established in the proof of Lemma 14 implies that ‖q^it+1−q^it‖1=O(ηt)\| q_i^t+1- q_i^t\|_1=O( _t). At confidence-update times, (38) and the finiteness of the number of players imply that ∑i=1n∑t∈ℛi‖q^it+1−q^it‖1<∞ _i=1^n _t _i\| q_i^t+1- q_i^t\|_1<∞. In particular, the total magnitude of confidence-update jumps after time T converges to zero as T→∞T→∞. Since U0¯⊂U U_0⊂ U, moving from U0U_0 to outside U requires a fixed positive amount of total movement. Thus, for every sufficiently late excursion that starts in U0U_0 and ends upon its first exit from U, the confidence-update jumps can account for only an arbitrarily small part of this movement, while the remaining movement is bounded by a constant multiple of the sum of ηt _t over the excursion. Consequently, there exists a constant c>0c>0 such that every sufficiently late such excursion satisfies ∑tduringtheexcursionηt≥c. _t\ during\ the\ excursion _t≥ c. Since q¯ q is a limit point of q^t\ q^t\, the trajectory visits U0U_0 infinitely often. It must therefore either eventually remain in U, or make infinitely many excursions from U0U_0 to outside U. In the first case, G(qt)≥cUG(q^t)≥ c_U eventually; since ∑tηt=∞ _t _t=∞, this gives ∑tηtG(qt)=∞ _t _tG(q^t)=∞. In the second case, during every sufficiently late excursion, up to its first exit from U, we have q^t∈U q^t∈ U and hence G(qt)≥cUG(q^t)≥ c_U, while the excursion satisfies ∑tduringtheexcursionηt≥c _t\ during\ the\ excursion _t≥ c. Infinitely many disjoint excursions therefore again give ∑tηtG(qt)=∞ _t _tG(q^t)=∞. Both cases contradict (45). Thus q∗q^* is the only limit point of q^t\ q^t\, and compactness yields q^t→q∗ q^t→ q^*. Equation (36) then immediately gives qt→q∗q^t→ q^*. Finally, the policy map πi(ai∣si)=ρi(si,ai)∑biρi(si,bi) _i(a_i s_i)= _i(s_i,a_i) _b_i _i(s_i,b_i) is continuous on the shrunk occupancy set, since its state marginals are bounded away from zero. Hence the induced stationary policies converge to the policy profile represented by q∗q^*. Moreover, since q∗q^* is an NE of the shrunk virtual game, for every player i, Vi(qi∗,q−i∗)≥maxqi∈Δi,δi(Pi)Vi(qi,q−i∗)V_i(q_i^*,q_-i^*)≥ _q_i∈ _i, _i(P_i)V_i(q_i,q_-i^*). By the same shrinkage argument used in Corollary 18, for sufficiently small action floors, maxqi∈Δi(Pi)Vi(qi,q−i∗)≤maxqi∈Δi,δi(Pi)Vi(qi,q−i∗)+ϵδ _q_i∈ _i(P_i)V_i(q_i,q_-i^*)≤ _q_i∈ _i, _i(P_i)V_i(q_i,q_-i^*)+ _δ, where ϵδ→0 _δ→ 0 as δ=maxiδi→0δ= _i _i→ 0. Combining the last two displays shows that Vi(qi∗,q−i∗)≥maxqi∈Δi(Pi)Vi(qi,q−i∗)−ϵδ,∀i∈[n]V_i(q_i^*,q_-i^*)≥ _q_i∈ _i(P_i)V_i(q_i,q_-i^*)- _δ,\ ∀ i∈[n]. Thus, the stationary policy profile represented by q∗q^* is an ϵδ _δ-NE of the original game. ∎ 7 Real-World Applications The stochastic game model studied in this paper is relevant to multi-agent systems in which each player controls the evolution of a local stochastic state while interacting with other players through its payoff. This structure arises when the physical dynamics of individual agents are locally controlled, but their objectives are coupled through a shared resource, market, or environment. We illustrate this connection through three representative applications: energy management in smart grids, resource allocation in wireless networks, and decentralized robotic navigation and coverage. For these applications, the framework developed in this paper provides a fully decentralized way for agents to learn from a single continuing trajectory without knowing their local transition kernels or observing the states and actions of other players, thereby respecting users’ privacy and accommodating communication or information bottlenecks that hinder coordination. Our results provide finite-time no-regret and asymptotic convergence guarantees whose complexity is governed by local state spaces and cover times, making them scalable and practical for large-scale systems. 7.1 Energy Management in Smart Grids Consider a collection of n geographically distributed energy users, indexed by [n]=1,…,n[n]=\1,…,n\, interacting with a utility company. Each user acts as a prosumer: it can consume electricity from the grid while also producing energy locally through renewable sources such as solar panels or wind turbines. In addition, user i is equipped with a storage device of capacity C, allowing unused energy to be carried from one period to the next. Let sits_i^t denote the quantized energy stored by user i at the beginning of day t, and let hith_i^t denote the renewable energy harvested during that day. The random variable hith_i^t captures uncertainty in local renewable production due, for example, to weather conditions. If aita_i^t denotes the amount of energy consumed by user i during day t, its storage level evolves according to sit+1=minC,hit+(sit−ait)+s_i^t+1= \C,\;h_i^t+ (s_i^t-a_i^t )^+ \, where x+:=maxx,0x^+:= \x,0\. Thus, the current consumption decision directly influences the distribution of the user’s future storage state. When ait>sita_i^t>s_i^t, the user must obtain (ait−sit)+ (a_i^t-s_i^t )^+ units of electricity from the grid to meet its consumption requirement. Although the storage dynamics are local, the users interact strategically through the electricity market. In particular, suppose that the utility determines the unit price of grid energy based on the aggregate demand, and denote this price by p(at,st)p(a^t,s^t). If ui(ait)u_i(a_i^t) denotes the benefit that user i obtains from consuming aita_i^t units of energy, its instantaneous reward can be written as ri(at,st)=ui(ait)−p(at,st)(ait−sit)+r_i(a^t,s^t)=u_i(a_i^t)-p(a^t,s^t) (a_i^t-s_i^t )^+. Hence, while player i controls only its own storage dynamics, its reward depends on the states and consumption decisions of the entire population through the market price (see Figure 1–a). This model fits the independent-chain framework particularly well when the users are sufficiently geographically separated that their local renewable-generation processes can be modeled as independent. Conditional on (sit,ait)(s_i^t,a_i^t), the next storage state of player i is then governed by its own renewable-generation process and does not depend on the states or actions of other users. Nevertheless, the players remain strategically coupled because the price p(at,st)p(a^t,s^t) depends on their collective demand. Consequently, each user seeks to learn a long-run consumption and storage policy from its own observations without knowing the stochastic model governing its renewable generation or observing the states and actions of other users. This provides a decentralized energy-management application of the stochastic game studied in this paper (Etesami et al., 2018). Figure 1: Representative applications of stochastic games with independent controlled chains. (a) Energy management: prosumers with local renewable generation and storage interact through a utility company and an aggregate-demand-dependent price. (b) Wireless communication: users with independent local queues adjust transmission decisions while competing over a shared channel. (c) Robotic navigation and coverage: robots with local controlled dynamics navigate through a shared environment while balancing individual navigation objectives with collective criteria such as congestion avoidance and spatial coverage. 7.2 Power and Bandwidth Allocation in Wireless Networks A second example arises in decentralized wireless communication systems in which several transmitters compete for access to a common channel (Altman et al., 2007). Consider n users transmitting packets to one or more receivers over a shared wireless medium. For transmitter i, let sits_i^t represent its local queue state at time t, describing, for example, the number of packets waiting to be transmitted. New packets arrive according to a local stochastic arrival process that is independent of the packet-generation processes of the other users. At each time t, transmitter i observes its own queue and selects an action aita_i^t, which may specify a transmission-power level, bandwidth allocation, transmission rate, or channel-access decision. Its queue then evolves according to the packets that arrive locally and the packets served as a consequence of its transmission decision. Thus, the action of each transmitter controls the evolution of its own queue state, while the underlying packet-arrival uncertainty is local to that user. The strategic interaction occurs through the shared communication medium. For example, the probability that player i successfully transmits a packet may depend on the transmission powers of all users, since simultaneous transmissions generate interference. More generally, the reward ri(st,at)r_i(s^t,a^t) may account for successful throughput, transmission energy, queueing delay, packet loss, or congestion, and may therefore depend on the joint state–action profile. Channel conditions, such as background noise and available capacity, may further influence the realized payoff (see Figure 1–b). The resulting system separates local dynamics from strategic interaction in precisely the manner captured by the independent-chain model: each user’s queue evolves according to its own controlled local dynamics, whereas the performance resulting from a transmission decision depends on the simultaneous behavior of the other users. A transmitter can therefore seek to learn a stationary power- or bandwidth-allocation policy using only its local queue, selected transmission action, observed next queue state, and realized transmission payoff, without knowing its local transition law or observing the states and actions of the competing transmitters. 7.3 Decentralized Robotic Navigation and Coverage A third application arises in decentralized robotic navigation and coverage, where a collection of autonomous agents moves through a common environment while collectively monitoring, exploring, or covering a region of interest. Such cooperative-control problems have been studied using potential, state-based potential, and distributed welfare games (Marden et al., 2009; Marden, 2012; Marden and Wierman, 2013). To connect this setting to the independent-chain model, suppose that robot i has a quantized local state sits_i^t describing its position, heading, velocity, battery level, sensing status, or other locally available information relevant to its motion and operation. At time t, the robot observes its current local state and selects a local control action aita_i^t, such as a movement direction, velocity adjustment, or sensing decision. Its next state is then generated according to an unknown controlled transition kernel Pi(sit+1∣sit,ait)P_i(s_i^t+1 s_i^t,a_i^t), which may capture uncertainty in actuation, localization, terrain conditions, sensor measurements, or other robot-specific disturbances encountered during operation (see Figure 1–c). When these disturbances are independent across robots, each robot’s state evolves according to its own locally controlled stochastic dynamics, and the resulting system has the independent controlled-chain structure considered in this paper. The robots nevertheless interact strategically through their rewards, which may account for travel time, energy consumption, congestion, collision avoidance, or progress toward a destination. The reward may also incorporate a collective coverage objective. For example, the workspace can be partitioned into Voronoi cells, with each robot responsible for monitoring its associated region, and the collective reward can favor configurations that cover a larger fraction of the workspace, reduce the aggregate distance between points and their nearest robots, or place robots near the centroids of their Voronoi regions (Marden et al., 2009; Marden and Wierman, 2013). Accordingly, the reward ri(st,at)r_i(s^t,a^t) can combine individual navigation and energy costs with team-dependent criteria such as coverage, congestion, and collision avoidance. Thus, although each robot controls only its local dynamics, its reward can depend on the configuration and actions of the entire robot population. The resulting equilibrium policies can therefore represent decentralized motion strategies that balance local navigation costs with collective objectives such as efficient spatial coverage. 8 Conclusion We developed a fully online one-sample occupancy-measure learning algorithm for stochastic games with unknown independent controlled chains. The algorithm operates along a single continuing trajectory, using one local transition and realized payoff per time step, while players update their policies and learn their unknown transition kernels asynchronously using only local information. Under uniform ergodicity, each individual controlled chain has a finite worst-case expected cover time HiH_i, which enters the finite-time complexity as a local problem-dependent parameter. A frozen-policy block comparison, together with the slow movement of mirror descent, transfers fixed-policy coverage and mixing properties to the time-inhomogeneous online trajectory. The resulting high-probability fixed-comparator regret decreases at the rate ~(T−1/2) O(T^-1/2) after a local-cover transient period. For arbitrary reward functions, this regret guarantee further implies that the empirical distribution of play approaches a coarse-correlated equilibrium. Because transition estimation and delayed moving-chain comparisons are performed separately on each local state space iS_i, neither the cover time nor the cardinality of the product state space ∏i _iS_i enters the complexity. Under an additional variational-stability condition and diminishing stepsizes, the same fully online scheme further yields asymptotic last-iterate convergence to a stationary ϵε-NE. References Altman et al. (2007) E. Altman, K. Avratchenkov, N. Bonneau, M. Debbah, R. El-Azouzi, and D. S. Menasché Constrained stochastic games in wireless networks. In IEEE GLOBECOM 2007-IEEE Global Telecommunications Conference, p. 315–320. Cited by: §1.1, §1, §7.2. Altman (2021) E. Altman Constrained Markov Decision Processes. Routledge. Cited by: §1, §3.1, §3, Lemma 4. Başar and Olsder (1999) T. Başar and G. J. Olsder Dynamic Noncooperative Game Theory. 2nd Ed, SIAM. Cited by: §1. Cardoso et al. (2019) A. R. Cardoso, H. Wang, and H. Xu Large scale Markov decision processes with changing rewards. In 33rd Conference on Neural Information Processing Systems 32 (NIPS), p. 1–11. Cited by: §1.1. Cesa-Bianchi and Lugosi (2006) N. Cesa-Bianchi and G. Lugosi Prediction, Learning, and Games. Cambridge University Press. Cited by: §1. Das and Eksin (2024) S. Das and C. Eksin Learning Nash in constrained Markov games with an α-potential. IEEE Control Systems Letters 8, p. 808–813. Cited by: §1.1. Daskalakis et al. (2020) C. Daskalakis, D. J. Foster, and N. Golowich Independent policy gradient methods for competitive reinforcement learning. Advances in Neural Information Processing Systems 33, p. 5527–5540. Cited by: §1.1, §1. Daskalakis et al. (2009) C. Daskalakis, P. W. Goldberg, and C. H. Papadimitriou The complexity of computing a Nash equilibrium. SIAM Journal on Computing 39 (1), p. 195–259. Cited by: §1. Ding et al. (2022) D. Ding, C. Wei, K. Zhang, and M. R. Jovanovic Independent policy gradient for large-scale Markov potential games: Sharper rates, function approximation, and game-agnostic convergence. In International Conference on Machine Learning, p. 5166–5220. Cited by: §1.1. Etesami et al. (2018) S. R. Etesami, W. Saad, N. B. Mandayam, and H. V. Poor Stochastic games for the smart grid energy management with prospect prosumers. IEEE Transactions on Automatic Control 63 (8), p. 2327–2342. Cited by: §1, §7.1. Etesami (2024) S. R. Etesami Learning stationary Nash equilibrium policies in n-player stochastic games with independent chains. SIAM Journal on Control and Optimization 62 (2), p. 799–825. Cited by: §A.1, §1.1, §1, §3.2, §4, §5.3, §6. Etesami (2026) S. R. Etesami High-probability Nash regret for decentralized learning in Markov α-potential games: Episodic and fully online asynchronous algorithms with applications to Markov congestion games. External Links: 2609.14959 Cited by: §1.1, §1, Acknowledgment.. Fox et al. (2022) R. Fox, S. M. McAleer, W. Overman, and I. Panageas Independent natural policy gradient always converges in Markov potential games. In Proceedings of the 25th International Conference on Artificial Intelligence and Statistics, Proceedings of Machine Learning Research, Vol. 151, p. 4414–4425. Cited by: §1. Guo et al. (2025) X. Guo, X. Li, C. Maheshwari, S. S. Sastry, and M. Wu Markov α-potential games. IEEE Transactions on Automatic Control 71 (1), p. 275–290. Cited by: §1.1. Jin et al. (2020) C. Jin, T. Jin, H. Luo, S. Sra, and T. Yu Learning adversarial Markov decision processes with bandit feedback and unknown transition. In International Conference on Machine Learning, p. 4860–4869. Cited by: §1.1. Jordan et al. (2024) P. Jordan, A. Barakat, and N. He Independent learning in constrained Markov potential games. In Proceedings of the 27th International Conference on Artificial Intelligence and Statistics, Proceedings of Machine Learning Research, Vol. 238, p. 4024–4032. Cited by: §1.1. Jordan and Kamgarpour (2026) P. Jordan and M. Kamgarpour Independent learning of Nash equilibria in partially observable Markov potential games with decoupled dynamics. arXiv preprint arXiv:2605.06377. Cited by: §1.1. Leonardos et al. (2021) S. Leonardos, W. Overman, I. Panageas, and G. Piliouras Global convergence of multi-agent policy gradient in Markov potential games. arXiv preprint arXiv:2106.01969. Cited by: §1.1, §1. Maheshwari et al. (2025) C. Maheshwari, M. Wu, D. Pai, and S. Sastry Independent and decentralized learning in Markov potential games. IEEE Transactions on Automatic Control 70 (11), p. 7538–7553. Cited by: §1. Marden et al. (2009) J. R. Marden, G. Arslan, and J. S. Shamma Cooperative control and potential games. IEEE Transactions on Systems, Man, and Cybernetics, Part B: Cybernetics 39 (6), p. 1393–1407. External Links: Document Cited by: §1, §7.3, §7.3. Marden and Wierman (2013) J. R. Marden and A. Wierman Distributed welfare games. Operations Research 61 (1), p. 155–168. External Links: Document Cited by: §7.3, §7.3. Marden (2012) J. R. Marden State based potential games. Automatica 48 (12), p. 3075–3088. External Links: Document Cited by: §7.3. Mertikopoulos and Zhou (2019) P. Mertikopoulos and Z. Zhou Learning in games with continuous action sets and unknown payoff functions. Mathematical Programming 173, p. 465–507. Cited by: §1, §1, §6. Nakhleh et al. (2025) K. Nakhleh, S. Aydin, C. Eksin, and S. Ekin Fictitious play in product Markov games with Kullback–Leibler control cost. In Proceedings of the 59th Asilomar Conference on Signals, Systems, and Computers, p. 1682–1686. Cited by: §1.1. Narayanan and Theagarajan (2017) P. Narayanan and L. N. Theagarajan Large player games on wireless networks. arXiv preprint arXiv:1710.08800. Cited by: §1. Nash (1950) J. F. Nash Equilibrium points in n-person games. Proceedings of the National Academy of Sciences 36 (1), p. 48–49. Cited by: §1. Neu et al. (2010) G. Neu, A. György, C. Szepesvári, et al. The online loop-free stochastic shortest-path problem. In COLT, Vol. 2010, p. 231–243. Cited by: §2. Nikaidô and Isoda (1955) H. Nikaidô and K. Isoda Note on non-cooperative convex games. Pacific Journal of Mathematics 5, p. 807–815. External Links: Document Cited by: §1.1. Qin and Etesami (2024) T. Qin and S. R. Etesami Learning ϵε-Nash equilibrium stationary policies in stochastic games with unknown independent chains using online mirror descent. In Proceedings of the 6th Annual Learning for Dynamics & Control Conference, Proceedings of Machine Learning Research, Vol. 242, p. 784–795. Cited by: §1.1, §4, Acknowledgment.. Qiu et al. (2021) S. Qiu, X. Wei, J. Ye, Z. Wang, and Z. Yang Provably efficient fictitious play policy optimization for zero-sum Markov games with structured transitions. In International Conference on Machine Learning, p. 8715–8725. Cited by: §1.1. Rivera Cardoso et al. (2019) A. Rivera Cardoso, H. Wang, and H. Xu Large scale Markov decision processes with changing rewards. Advances in Neural Information Processing Systems 32. Cited by: §2. Rosenberg and Mansour (2019) A. Rosenberg and Y. Mansour Online stochastic shortest path with bandit feedback and unknown transition function. Advances in Neural Information Processing Systems 32. Cited by: §1.1, §2. Sayin et al. (2022) M. O. Sayin, F. Parise, and A. Ozdaglar Fictitious play in zero-sum stochastic games. SIAM Journal on Control and Optimization 60 (4), p. 2095–2114. Cited by: §1. Sayin et al. (2021) M. Sayin, K. Zhang, D. Leslie, T. Başar, and A. Ozdaglar Decentralized Q-learning in zero-sum Markov games. Advances in Neural Information Processing Systems 34, p. 18320–18334. Cited by: §1.1. Shapley (1953) L. S. Shapley Stochastic games. Proceedings of the National Academy of Sciences 39 (10), p. 1095–1100. Cited by: §1. Singh and Hemachandra (2014) V. V. Singh and N. Hemachandra A characterization of stationary Nash equilibria of constrained stochastic games with independent state processes. Operations Research Letters 42 (1), p. 48–52. Cited by: §1.1. Sun et al. (2023) Y. Sun, T. Liu, R. Zhou, P. R. Kumar, and S. Shahrampour Provably fast convergence of independent natural policy gradient for Markov potential games. In Advances in Neural Information Processing Systems, Vol. 36. Cited by: §1.1. Zhang et al. (2021) K. Zhang, Z. Yang, and T. Başar Multi-agent reinforcement learning: A selective overview of theories and algorithms. Handbook of Reinforcement Learning and Control, p. 321–384. Cited by: §1. Zhang et al. (2022) R. Zhang, J. Mei, B. Dai, D. Schuurmans, and N. Li On the global convergence rates of decentralized softmax gradient play in markov potential games. In Advances in Neural Information Processing Systems, Vol. 35. Cited by: §1.1. Zhang et al. (2024) R. Zhang, Z. Ren, and N. Li Gradient play in stochastic games: stationary points, convergence, and sample complexity. IEEE Transactions on Automatic Control 69 (10), p. 6499–6514. Cited by: §1.1, §1. Zhao et al. (2022) Y. Zhao, Y. Tian, J. Lee, and S. Du Provably efficient policy optimization for two-player zero-sum markov games. In International Conference on Artificial Intelligence and Statistics, p. 2736–2761. Cited by: §1. Acknowledgment. The core ideas and technical contributions of this work originated with the author and were inspired by his earlier collaborative work on episodic learning (Qin and Etesami, 2024), together with his recent work on developing the first fully online algorithm for Markov α-potential games (Etesami, 2026). The author acknowledges the use of generative AI (GPT-5.6 Sol) for brainstorming and for technical and writing assistance, including refining and checking proofs, filling in standard technical gaps, improving exposition and grammar, and preparing figures. All AI-assisted material was independently verified and revised by the author. Appendix A Omitted Proofs for Section 3 A.1 Proof of Lemma 5 Proof. It has been shown in (Etesami, 2024) that, under Assumptions 1 and 2, if each player i follows a stationary policy πi _i, then Vi(πi,π−i)=Vi(ρi,ρ−i)=∑s,a∏j=1nρj(sj,aj)ri(s,a)=⟨ρi,vi(ρ−i)⟩, V_i( _i, _-i)=V_i( _i, _-i)= _s,a _j=1^n _j(s_j,a_j)r_i(s,a)= _i,v_i( _-i) , (46) where vi(ρ−i)v_i( _-i) denotes player i’s payoff-gradient vector with respect to ρi _i; it is a vector of dimension |i||i||S_i||A_i| whose (si,ai)(s_i,a_i)-th coordinate is given by vi(ρ−i)(si,ai)=∑s−i,a−i∏j≠iρj(sj,aj)ri(s,a). v_i( _-i)_(s_i,a_i)= _s_-i,a_-i _j≠ i _j(s_j,a_j)r_i(s,a). (47) Since ρj(sj,aj)=∑sj′qj(sj,aj,sj′) _j(s_j,a_j)= _s _jq_j(s_j,a_j,s _j) for every player j, substituting this relation into (46) gives Vi(ρi,ρ−i) V_i( _i, _-i) =∑si,ai,si′qi(si,ai,si′)∑s−i,a−i∏j≠i∑sj′qj(sj,aj,sj′)ri(s,a)=⟨qi,gi(q−i)⟩, = _s_i,a_i,s _iq_i(s_i,a_i,s _i) _s_-i,a_-i _j≠ i _s _jq_j(s_j,a_j,s _j)r_i(s,a)= q_i,g_i(q_-i) , which establishes (6) and (7). Now, comparing (7) and (47), and using ρj(sj,aj)=∑sj′qj(sj,aj,sj′) _j(s_j,a_j)= _s _jq_j(s_j,a_j,s _j) shows that gi(q−i)(si,ai,si′)=vi(ρ−i)(si,ai),∀si,ai,si′.g_i(q_-i)_(s_i,a_i,s _i)=v_i( _-i)_(s_i,a_i), ∀\,s_i,a_i,s _i. In particular, gi(q−i)(si,ai,si′)g_i(q_-i)_(s_i,a_i,s _i) is independent of si′s _i, with the same value repeated across all si′∈is _i _i. ∎ A.2 Proof of Lemma 8 Proof. For qi∈Δi,δiq_i∈ _i, _i, since ρi(si,ai)≥δi>0 _i(s_i,a_i)≥ _i>0 where we note that ρi(si,ai)=∑yiqi(si,ai,yi) _i(s_i,a_i)= _y_iq_i(s_i,a_i,y_i), the transition kernel induced by qiq_i is well defined and satisfies Piqi(si′∣si,ai)=qi(si,ai,si′)ρi(si,ai).P_i^q_i(s_i s_i,a_i)= q_i(s_i,a_i,s_i ) _i(s_i,a_i). Therefore, the condition Pqi∈iP^q_i _i is equivalent to imposing the box constraints Li(si,ai,si′)≤Piqi(si′∣si,ai)≤Ui(si,ai,si′)L_i(s_i,a_i,s_i )≤ P_i^q_i(s_i s_i,a_i)≤ U_i(s_i,a_i,s_i ), which are equivalent to the linear inequalities Li(si,ai,si′)∑yiqi(si,ai,yi)≤qi(si,ai,si′)≤Ui(si,ai,si′)∑yiqi(si,ai,yi).L_i(s_i,a_i,s_i ) _y_iq_i(s_i,a_i,y_i)≤ q_i(s_i,a_i,s_i )≤ U_i(s_i,a_i,s_i ) _y_iq_i(s_i,a_i,y_i). Consequently, Δi,δi(i) _i, _i(P_i) admits the following explicit representation as the set of all occupancies qiq_i satisfying the following linear constraints: qi(si,ai,si′)≥0,∀si,ai,si′,∑si,ai,si′qi(si,ai,si′)=1,∑si′,aiqi(si′,ai,si)=∑si′,aiqi(si,ai,si′),∀si,∑si′qi(si,ai,si′)≥δi,∀si,ai,Li(si,ai,si′)∑yiqi(si,ai,yi)≤qi(si,ai,si′)≤Ui(si,ai,si′)∑yiqi(si,ai,yi),∀si,ai,si′. array[]lq_i(s_i,a_i,s_i )≥ 0,&∀ s_i,a_i,s_i ,\\[2.84526pt] _s_i,a_i,s_i q_i(s_i,a_i,s_i )=1,&\\[5.69054pt] _s_i ,a_iq_i(s_i ,a_i,s_i)= _s_i ,a_iq_i(s_i,a_i,s_i ),&∀ s_i,\\[5.69054pt] _s_i q_i(s_i,a_i,s_i )≥ _i,&∀ s_i,a_i,\\[5.69054pt] L_i(s_i,a_i,s_i ) _y_iq_i(s_i,a_i,y_i)\!≤\!q_i(s_i,a_i,s_i )\!≤\!U_i(s_i,a_i,s_i ) _y_iq_i(s_i,a_i,y_i),&∀ s_i,a_i,s_i . array All the displayed constraints in Δi,δi(i) _i, _i(P_i) are linear in qiq_i with |i|2|i||S_i|^2|A_i| variables and O(|i|2|i|)O(|S_i|^2|A_i|) constraints. Moreover, the set is closed and bounded by nonnegativity and normalization. Hence Δi,δi(i) _i, _i(P_i) is a closed convex polytope with an explicit polynomial-size linear description. ∎ Appendix B Omitted Proofs for Section 4 B.1 Proof of Lemma 10 Proof. Fix i∈[n]i∈[n], (si,ai)∈i×i(s_i,a_i) _i×A_i, and si′∈is_i _i. All random variables below are defined on the common probability space supporting the entire game trajectory. For each ℓ≥1 ≥ 1, let Si,ℓ+S_i, ^+ denote the next-state observation following the ℓ occurrence of the state–action pair (si,ai)(s_i,a_i). Let ℱi,0F_i,0 contain the entire game history immediately after the first occurrence of (si,ai)(s_i,a_i) and before observing Si,1+S_i,1^+. More generally, for ℓ≥1 ≥ 1, let ℱi,ℓF_i, contain the entire game history immediately after the (ℓ+1)( +1)st occurrence of (si,ai)(s_i,a_i) and before observing Si,ℓ+1+S_i, +1^+. Thus, ℱi,ℓ≥0\F_i, \_ ≥ 0 is the filtration obtained by indexing the entire game history by successive occurrences of (si,ai)(s_i,a_i). In particular, ℱi,ℓ−1F_i, -1 contains the entire history preceding Si,ℓ+S_i, ^+, including the fact that the ℓ occurrence of (si,ai)(s_i,a_i) has taken place, but does not contain Si,ℓ+S_i, ^+ itself. For m≥1m≥ 1, define P¯i,m(si′∣si,ai):=1m∑ℓ=1mSi,ℓ+=si′. P_i,m(s_i s_i,a_i):= 1m _ =1^m 1\S_i, ^+=s_i \. By the controlled Markov property, conditional on ℱi,ℓ−1F_i, -1, the next state following the ℓ occurrence of (si,ai)(s_i,a_i) is distributed according to Pi(⋅∣si,ai)P_i(· s_i,a_i). Therefore, [Si,ℓ+=si′|ℱi,ℓ−1]=Pi(si′∣si,ai).E [ 1\S_i, ^+=s_i \\, |\,F_i, -1 ]=P_i(s_i s_i,a_i). Consequently, Xi,ℓ:=Si,ℓ+=si′−Pi(si′∣si,ai),ℓ≥1,X_i, := 1\S_i, ^+=s_i \-P_i(s_i s_i,a_i), ≥ 1, is a martingale-difference sequence with respect to ℱi,ℓ≥0\F_i, \_ ≥ 0. Moreover, Xi,ℓX_i, takes values in an interval of length one. Hence, by Hoeffding–Azuma, for every m≥1m≥ 1 and x>0x>0, ℙ(|P¯i,m(si′∣si,ai)−Pi(si′∣si,ai)|>2xm)≤2e−x.P ( | P_i,m(s_i s_i,a_i)-P_i(s_i s_i,a_i) |> 2xm )≤ 2e^-x. Now consider any time t such that Nit(si,ai)=m≥1N_i^t(s_i,a_i)=m≥ 1. By the definitions of NitN_i^t, P¯it P_i^t, and P¯i,m P_i,m, P¯it(si′∣si,ai)=P¯i,m(si′∣si,ai). P_i^t(s_i s_i,a_i)= P_i,m(s_i s_i,a_i). Moreover, m≤tm≤ t, and Λt _t is nondecreasing, so Λt≥Λm=log(64nAmaxSmax2(m+2)2γ). _t≥ _m= ( 64nA_ S_ ^2(m+2)^2γ ). Therefore, if for some t with Nit(si,ai)=m≥1N_i^t(s_i,a_i)=m≥ 1, |P¯it(si′∣si,ai)−Pi(si′∣si,ai)|>βit(si,ai), | P_i^t(s_i s_i,a_i)-P_i(s_i s_i,a_i) |> _i^t(s_i,a_i), then necessarily |P¯i,m(si′∣si,ai)−Pi(si′∣si,ai)|>2Λm. | P_i,m(s_i s_i,a_i)-P_i(s_i s_i,a_i) |> 2 _mm. Thus, taking a union bound over all possible visit counts m≥1m≥ 1, 77 7 If Nit(si,ai)=0N_i^t(s_i,a_i)=0, then P¯it(si′∣si,ai)=0 P_i^t(s_i s_i,a_i)=0, while Pi(si′∣si,ai)≤1P_i(s_i s_i,a_i)≤ 1. Moreover, βit(si,ai)=2Λt≥1 _i^t(s_i,a_i)= 2 _t≥ 1. Hence, |P¯it(si′∣si,ai)−Pi(si′∣si,ai)|≤βit(si,ai) | P_i^t(s_i s_i,a_i)-P_i(s_i s_i,a_i) |≤ _i^t(s_i,a_i), so the confidence bound holds automatically. ℙ(∃t≥1:Nit(si,ai)≥1,|P¯it(si′∣si,ai)−Pi(si′∣si,ai)|>βit(si,ai)) (∃\,t≥ 1:N_i^t(s_i,a_i)≥ 1,\ | P_i^t(s_i s_i,a_i)-P_i(s_i s_i,a_i) |> _i^t(s_i,a_i) ) ≤∑m=1∞ℙ(|P¯i,m(si′∣si,ai)−Pi(si′∣si,ai)|>2Λm)≤2∑m=1∞e−Λm ≤ _m=1^∞P ( | P_i,m(s_i s_i,a_i)-P_i(s_i s_i,a_i) |> 2 _mm )≤ 2 _m=1^∞e^- _m =2∑m=1∞(γ64nAmaxSmax2(m+2)2). =2 _m=1^∞ ( γ64nA_ S_ ^2(m+2)^2 ). By taking a union bound over all i,si,ai,si′i,s_i,a_i,s_i and using ∑i=1n|i||i|2≤nAmaxSmax2 _i=1^n|A_i||S_i|^2≤ nA_ S_ ^2, we obtain ℙ(∃i,t,si,ai,si′:|P¯it(si′∣si,ai)−Pi(si′∣si,ai)|>βit(si,ai)) (∃\,i,t,s_i,a_i,s_i : | P_i^t(s_i s_i,a_i)-P_i(s_i s_i,a_i) |> _i^t(s_i,a_i) ) ≤2nAmaxSmax2∑m=1∞(γ64nAmaxSmax2(m+2)2)<γ4. ≤ 2nA_ S_ ^2 _m=1^∞ ( γ64nA_ S_ ^2(m+2)^2 )< γ4. Thus, with probability at least 1−γ/41-γ/4, every confidence region constructed by every player at every confidence-update time contains the corresponding true transition kernel PiP_i. Since i0P_i^0 contains all transition kernels and Algorithm 1 updates itP_i^t only by intersecting the previous confidence set with such confidence regions, it follows inductively that Pi∈it,∀i∈[n],∀t≥0.P_i _i^t, ∀ i∈[n],\ ∀ t≥ 0. Hence, ℙ(ℰconf)≥1−γ/4P(E_ conf)≥ 1-γ/4. Finally, on ℰconfE_ conf, if qi∈Δi,δi(Pi)q_i∈ _i, _i(P_i), then its induced transition kernel satisfies Pqi=Pi∈itP^q_i=P_i _i^t. Therefore, qi∈Δi,δi(it)q_i∈ _i, _i(P_i^t), and consequently Δi,δi(Pi)⊆Δi,δi(it),∀i∈[n],∀t≥0. _i, _i(P_i) _i, _i(P_i^t), ∀ i∈[n],\ ∀ t≥ 0. ∎ Appendix C Omitted Proofs for Section 5 C.1 Proof of Lemma 13 Proof. On the event ℰconfE_ conf, Pi∈itP_i _i^t for every t, hence the fixed comparator qi′q_i belongs to every feasible set Δi,δi(it) _i, _i(P_i^t). The first-order optimality condition for the proximal occupancy update in Algorithm 1 therefore gives ⟨q^it+1−q^it−ηR^it,qi′−q^it+1⟩≥0. q_i^t+1- q_i^t-η R_i^t,q_i - q_i^t+1 ≥ 0. (48) Now, we can write η⟨qi′−q^it,R^it⟩ η q_i - q_i^t, R_i^t =η⟨qi′−q^it+1,R^it⟩+η⟨q^it+1−q^it,R^it⟩ =η q_i - q_i^t+1, R_i^t +η q_i^t+1- q_i^t, R_i^t (49) ≤⟨q^it+1−q^it,qi′−q^it+1⟩+η⟨q^it+1−q^it,R^it⟩ ≤ q_i^t+1- q_i^t,q_i - q_i^t+1 +η q_i^t+1- q_i^t, R_i^t (50) =12‖qi′−q^it‖22−12‖qi′−q^it+1‖22−12‖q^it+1−q^it‖22+η⟨q^it+1−q^it,R^it⟩ = 12\|q_i - q_i^t\|_2^2- 12\|q_i - q_i^t+1\|_2^2- 12\| q_i^t+1- q_i^t\|_2^2+η q_i^t+1- q_i^t, R_i^t (51) ≤12‖qi′−q^it‖22−12‖qi′−q^it+1‖22+η22‖R^it‖22, ≤ 12\|q_i - q_i^t\|_2^2- 12\|q_i - q_i^t+1\|_2^2+ η^22\| R_i^t\|_2^2, (52) where the first inequality follows from the first-order optimality condition (48), the second equality uses the three-point identity 2⟨x−y,z−x⟩=‖z−y‖22−‖z−x‖22−‖x−y‖222 x-y,z-x =\|z-y\|_2^2-\|z-x\|_2^2-\|x-y\|_2^2, and the last inequality follows from Young’s inequality, which cancels the term −12‖q^it+1−q^it‖22- 12\| q_i^t+1- q_i^t\|_2^2. Summing the above relation over t telescopes globally. Importantly, a confidence update does not create a restart term in this telescope because the true-kernel comparator remains feasible after every confidence-set intersection. Since both occupancy vectors have unit mass, ‖qi′−q^i0‖22≤2\|q_i - q_i^0\|_2^2≤ 2. Moreover, by (14), R^it R_i^t has exactly |i||S_i| possibly nonzero next-state coordinates, all corresponding to the observed pair (Sit,Ait)(S_i^t,A_i^t), and every such coordinate is at most 1/δi1/ _i. Hence ‖R^it‖22≤|i|δi2\| R_i^t\|_2^2≤ |S_i| _i^2. Substitution proves (17). ∎ C.2 Proof of Lemma 14 Proof. We first establish the policy-movement bound. Suppose that player i does not update its confidence set at step t. Then the feasible set in the proximal step is the same set that contains q^it q_i^t. Hence the Euclidean update is the projection of q^it+ηR^it q_i^t+η R_i^t onto this fixed convex set, and nonexpansiveness of projection gives ‖q^it+1−q^it‖2≤η‖R^it‖2≤η|i|δi.\| q_i^t+1- q_i^t\|_2≤η\| R_i^t\|_2≤ η |S_i| _i. Since the occupancy vector has dimension |i||i|2|A_i||S_i|^2, ‖q^it+1−q^it‖1≤|i||i|‖q^it+1−q^it‖2≤Liηδi. \| q_i^t+1- q_i^t\|_1≤|S_i| |A_i|\,\| q_i^t+1- q_i^t\|_2≤ L_iη _i. (53) By triangle inequality, marginalization cannot increase the ℓ1 _1 norm, so ‖ρ^it+1−ρ^it‖1≤Liηδi.\| ρ_i^t+1- ρ_i^t\|_1≤ L_iη _i. For a fixed sis_i, since every state–action marginal is at least δi _i, ν^it(si)=∑aiρ^it(si,ai)≥|i|δi≥δi ν^t_i(s_i)= _a_i ρ_i^t(s_i,a_i)≥|A_i| _i≥ _i and similarly ν^it+1(si)≥δi ν^t+1_i(s_i)≥ _i. Therefore, ∥πit(⋅∣si)−πit+1(⋅∣si)∥1=‖ρ^it(si,⋅)ν^t(si)−ρ^it+1(si,⋅)ν^t+1(si)‖1≤2‖ρ^it+1−ρ^it‖1δi≤2Liηδi2. \| _i^t(· s_i)- _i^t+1(· s_i)\|_1= \| ρ_i^t(s_i,·) ν^t(s_i)- ρ_i^t+1(s_i,·) ν^t+1(s_i) \|_1≤ 2\| ρ_i^t+1- ρ_i^t\|_1 _i≤ 2L_iη _i^2. This proves (19). In particular, since the controlled kernel is affine in the policy, for every such step, ∥Piπit+1(⋅∣si)−Piπit(⋅∣si)∥1 \|P_i _i^t+1(· s_i)-P_i _i^t(· s_i)\|_1 =∥∑ai(πit+1(ai∣si)−πit(ai∣si))Pi(⋅∣si,ai)∥1 = \| _a_i ( _i^t+1(a_i s_i)- _i^t(a_i s_i) )P_i(· s_i,a_i) \|_1 (54) ≤∑ai|πit+1(ai∣si)−πit(ai∣si)| ≤ _a_i | _i^t+1(a_i s_i)- _i^t(a_i s_i) | (55) =∥πit+1(⋅∣si)−πit(⋅∣si)∥1≤2Liηδi2∀si∈i. =\| _i^t+1(· s_i)- _i^t(· s_i)\|_1≤ 2L_iη _i^2\ \ \ \ \ ∀ s_i _i. (56) We now prove the occupancy-estimation bound. The argument proceeds in three steps. First, we show that every local state–action pair is visited sufficiently often despite the slowly changing policy. This controls the confidence radii. Second, we use the confidence sets to bound the error between the represented and true transition kernels. Finally, the contraction assumption converts the kernel error into an occupancy error. Step 1: Sufficient visitation. We first show that the slowly varying policy does not destroy the local-cover property. Fix player i and an interval [u,v][u,v] containing no confidence update of player i. Conditional on ℱuF_u, consider two local state processes starting from the same state at time u: Siu=S¯iuS_i^u= S_i^u. The process (Sit)t=uv(S_i^t)_t=u^v is the actual local state trajectory and, at time t, uses the current controlled kernel PiπitP_i _i^t. In contrast, (S¯it)t=uv( S_i^t)_t=u^v is the frozen trajectory: throughout the entire interval it uses the single kernel PiπiuP_i _i^u. Thus, Sit+1∼Piπit(⋅∣Sit)S_i^t+1 P_i _i^t(· S_i^t) and S¯it+1∼Piπiu(⋅∣S¯it) S_i^t+1 P_i _i^u(· S_i^t). Couple the two chains maximally at each step as long as they have not separated. Conditional on Sit=S¯it=siS_i^t= S_i^t=s_i, by maximal coupling their probability of separating at the next transition is at most 12∥Piπit(⋅∣si)−Piπiu(⋅∣si)∥1. 12 \|P_i _i^t(· s_i)-P_i _i^u(· s_i) \|_1. Therefore, by a union bound over the transitions, we obtain ℙ(∃t∈[u,v] such that Sit≠S¯it|ℱu)≤12∑t=uv−1maxsi∥Piπit(⋅∣si)−Piπiu(⋅∣si)∥1. (∃\,t∈[u,v] such that S_i^t≠ S_i^t\, |\,F_u )≤ 12 _t=u^v-1 _s_i \|P_i _i^t(· s_i)-P_i _i^u(· s_i) \|_1. (57) As long as no confidence update occurs, (54) holds at every step. Hence, for t≥ut≥ u, maxsi∥Piπit(⋅∣si)−Piπiu(⋅∣si)∥1≤∑k=ut−1maxsi∥Piπik+1(⋅∣si)−Piπik(⋅∣si)∥1≤2Li(t−u)ηδi2. _s_i \|P_i _i^t(· s_i)-P_i _i^u(· s_i) \|_1≤ _k=u^t-1 _s_i \|P_i _i^k+1(· s_i)-P_i _i^k(· s_i) \|_1≤ 2L_i(t-u)η _i^2. Substituting into (57) gives ℙ(∃t∈[u,v] such that Sit≠S¯it|ℱu)≤Li(v−u)2ηδi2. (∃\,t∈[u,v] such that S_i^t≠ S_i^t\, |\,F_u )≤ L_i(v-u)^2η _i^2. (58) Next, we apply this comparison on blocks of length 2Hi+12H_i+1. Let ℓm:=m(2Hi+1),Bm:=ℓm,…,ℓm+2Hi, _m:=m(2H_i+1), B_m:=\ _m,…, _m+2H_i\, and let τm _m be the first confidence-update time of player i at or after ℓm _m. Thus, τm∈Bm _m∈ B_m if and only if a confidence update occurs in BmB_m. Couple the actual chain with the chain frozen at πiℓm _i _m until the first confidence update or the end of BmB_m, whichever comes first. On the event τm∉Bm\ _m∉ B_m\, this comparison therefore runs throughout the entire block. By the same maximal-coupling argument as in (58) and (18), we obtain ℙ(τm∉Bm∩∃t∈Bm such that Sit≠S¯it|ℱℓm)≤4LiHi2ηδi2≤14. (\ _m∉ B_m\∩\∃\,t∈ B_m such that S_i^t≠ S_i^t\\, |\,F_ _m )≤ 4L_iH_i^2η _i^2≤ 14. (59) Conditional on ℱℓmF_ _m, the frozen process starts from SiℓmS_i _m and evolves according to the homogeneous Markov chain PiπiℓmP_i _i _m induced by the fixed policy πiℓm _i _m. Let τcov,iπiℓm _ cov,i _i _m denote its cover time starting from SiℓmS_i _m. By the definition of HiH_i and Markov’s inequality, ℙ(τcov,iπiℓm≤2Hi|ℱℓm)=1−ℙ(τcov,iπiℓm>2Hi|ℱℓm)≥1−[τcov,iπiℓm∣ℱℓm]2Hi≥12.P\! ( _ cov,i _i _m≤ 2H_i\, |\,F_ _m )=1-P\! ( _ cov,i _i _m>2H_i\, |\,F_ _m )≥ 1- E[ _ cov,i _i _m _ _m]2H_i≥ 12. Thus, conditional on ℱℓmF_ _m, the frozen chain visits every local state, and hence any prescribed sis_i, during BmB_m with probability at least 1/21/2. Combining this with the coupling bound (59), the event that either a confidence update occurs in BmB_m or the actual chain visits sis_i has conditional probability at least 1/2−1/4=1/41/2-1/4=1/4. Therefore, for every si∈is_i _i, ℙ(∃t∈Bm:Sit=si∪τm∈Bm|ℱℓm)≥14. \! (\∃\,t∈ B_m:S_i^t=s_i\∪\ _m∈ B_m\\, |\,F_ _m )≥ 14. (60) We now lower bound the visit count Nit(si,ai)N_i^t(s_i,a_i). Fix a prescribed (si,ai)(s_i,a_i). For each block, we count it as successful if it either produces an observation of (si,ai)(s_i,a_i) or contains a confidence update; the latter blocks will later be charged to the total number of confidence updates. Accordingly, define Ymi(si,ai):=(si,ai) is observed in Bm, or τm∈Bm.Y_m^i(s_i,a_i):= 1 \$(s_i,a_i)$ is observed in $B_m$, or $ _m∈ B_m$ \. Thus, Ymi(si,ai)Y_m^i(s_i,a_i) is a “visit-or-update” indicator: every block with Ymi(si,ai)=1Y_m^i(s_i,a_i)=1 either contributes at least one visit to (si,ai)(s_i,a_i) or can be charged to a confidence update. More precisely, fix any t≤Tt≤ T and let Mt:=⌊t2Hi+1⌋M_t:= t2H_i+1 be the number of complete blocks before time t, and Ji(t)J_i(t) be the number of confidence updates before time t. Since the blocks are disjoint, for these MtM_t complete blocks, Nit(si,ai)≥∑m=0Mt−1Ymi(si,ai)−Ji(t)≥∑m=0Mt−1Ymi(si,ai)−|i||i|(1+⌊log2t⌋), N_i^t(s_i,a_i)≥ _m=0^M_t-1Y_m^i(s_i,a_i)-J_i(t)≥ _m=0^M_t-1Y_m^i(s_i,a_i)-|S_i||A_i| (1+ _2t ), (61) where the second inequality follows by the dyadic update rule for confidence updates. It remains to show that sufficiently many blocks have Ymi(si,ai)=1Y_m^i(s_i,a_i)=1. By (60) and the fact that the action floor (13) gives conditional probability at least δi _i of selecting aia_i, we have [Ymi(si,ai)|ℱℓm]≥δi4.E\! [Y_m^i(s_i,a_i)\, |\,F_ _m ]≥ _i4. Applying Freedman’s inequality88 8 We use the standard Freedman inequality for martingale differences XmX_m satisfying |Xm|≤1|X_m|≤ 1: if Mk=∑m<kXmM_k= _m<kX_m and Vk=∑m<k[Xm2∣ℱℓm]V_k= _m<kE[X_m^2 _ _m], then ℙ(Mk≤−2Vkx−2x3)≤e−xP\! (M_k≤-2 V_kx- 2x3 )≤ e^-x for every fixed k. to Xm:=Ymi(si,ai)−[Ymi(si,ai)∣ℱℓm],X_m:=Y_m^i(s_i,a_i)-E[Y_m^i(s_i,a_i) _ _m], and observing that ∑m<Mt[Xm2∣ℱℓm]≤Mt _m<M_tE[X_m^2 _ _m]≤ M_t, we obtain, for every fixed t≤Tt≤ T, ℙ(∑m=0Mt−1Ymi(si,ai)<δi4Mt−2Mtx−2x3)≤e−x.P\! ( _m=0^M_t-1Y_m^i(s_i,a_i)< _i4M_t-2 M_tx- 2x3 )≤ e^-x. Using 2Mtx≤δi16Mt+16xδi2 M_tx≤ _i16M_t+ 16x _i, choosing x=cΛTx=c _T with a sufficiently large universal constant c>0c>0, and taking a union bound over all players, state–action pairs, and t≤Tt≤ T gives ℙ(∃i,(si,ai),t≤T:∑m=0Mt−1Ymi(si,ai)<3δi16Mt−cΛTδi)≤γ4.P\! (∃\,i,\,(s_i,a_i),\,t≤ T: _m=0^M_t-1Y_m^i(s_i,a_i)< 3 _i16M_t-c _T _i )≤ γ4. Hence, with probability at least 1−γ/41-γ/4, simultaneously for all i, (si,ai)(s_i,a_i), and t≤Tt≤ T, combining this bound with (61) gives Nit(si,ai) N_i^t(s_i,a_i) ≥3δi16Mt−cΛTδi−|i||i|(1+⌊log2t⌋) ≥ 3 _i16M_t-c _T _i-|S_i||A_i| (1+ _2t ) (62) ≥δi32Hit−c(ΛTδi+|i||i|(1+⌊log2t⌋)+1), ≥ _i32H_it-c ( _T _i+|S_i||A_i| (1+ _2t )+1 ), (63) where the second inequality is obtained using Mt=⌊t2Hi+1⌋≥t3Hi−1M_t= t2H_i+1 ≥ t3H_i-1 and by adjusting the universal constant. Therefore, by the definition of Ki(T)K_i(T), for every t≥Ki(T)t≥ K_i(T), the number of visits to (si,ai)(s_i,a_i) grows linearly, Nit(si,ai)≥cδitHi, N_i^t(s_i,a_i)≥ c _itH_i, (64) and consequently maxsi,aiβit(si,ai)≤cHiΛtδit. _s_i,a_i _i^t(s_i,a_i)≤ c H_i _t _it. (65) Step 2: Kernel approximation error. On the anytime confidence event ℰconfE_ conf of Lemma 10, Pi∈itP_i _i^t for every i and t. Moreover, by construction, P^it:=Pq^it∈it. P_i^t:=P q_i^t _i^t. Fix t≥Ki(T)t≥ K_i(T) and (si,ai)(s_i,a_i), and let θit(si,ai)≤t _i^t(s_i,a_i)≤ t denote its most recent dyadic confidence-update time. Since no new constraint for (si,ai)(s_i,a_i) is imposed between θit(si,ai) _i^t(s_i,a_i) and t, Nit(si,ai)<2Niθit(si,ai)(si,ai)⇒βiθit(si,ai)(si,ai)≤2βit(si,ai).N_i^t(s_i,a_i)<2N_i _i^t(s_i,a_i)(s_i,a_i) _i _i^t(s_i,a_i)(s_i,a_i)≤ 2\, _i^t(s_i,a_i). On the anytime confidence event, both PiP_i and P^it P_i^t belong to the confidence set itP_i^t centered at the empirical kernel P¯it P_i^t with radius βθit(si,ai)(si,ai)β _i^t(s_i,a_i)(s_i,a_i). Thus, by the triangle inequality, |P^it(si′∣si,ai)−Pi(si′∣si,ai)| | P_i^t(s_i s_i,a_i)\!-\!P_i(s_i s_i,a_i)| ≤|P^it(si′∣si,ai)−P¯it(si′∣si,ai)|+|P¯it(si′∣si,ai)−Pi(si′∣si,ai)| \!≤\!| P_i^t(s_i s_i,a_i)\!-\! P^t_i(s_i s_i,a_i)|\!+\!| P_i^t(s_i s_i,a_i)\!-\!P_i(s_i s_i,a_i)| ≤2βiθit(si,ai)(si,ai)≤22βit(si,ai). \!≤\!2 _i _i^t(s_i,a_i)(s_i,a_i)≤ 2 2\, _i^t(s_i,a_i). Therefore, maxsi,ai∥P^it(⋅∣si,ai)−Pi(⋅∣si,ai)∥1≤3|i|maxsi,aiβit(si,ai). _s_i,a_i\| P_i^t(· s_i,a_i)-P_i(· s_i,a_i)\|_1≤ 3|S_i| _s_i,a_i _i^t(s_i,a_i). (66) Step 3: Kernel to occupancy error. For an arbitrary time Ki(T)≤t<TK_i(T)≤ t<T, denote the stationary distributions of PiπitP_i _i^t and (P^it)πit( P_i^t) _i^t by νit _i^t and ν^it ν_i^t, respectively. By stationarity and Assumption 2, ∥ν^it−νit∥1=∥ν^it(P^it)πit−νitPiπit∥1≤maxsi∥(P^it)πit(⋅∣si)−Piπit(⋅∣si)∥1+(1−κ)∥ν^it−νit∥1. \| ν_i^t- _i^t\|_1=\| ν_i^t( P_i^t) _i^t- _i^tP_i _i^t\|_1≤ _s_i\|( P_i^t) _i^t(· s_i)-P_i _i^t(· s_i)\|_1+(1-κ)\| ν_i^t- _i^t\|_1. Therefore, ∥ν^it−νit∥1≤1κmaxsi∥(P^it)πit(⋅∣si)−Piπit(⋅∣si)∥1≤1κmaxsi,ai∥P^it(⋅∣si,ai)−Pi(⋅∣si,ai)∥1, \| ν_i^t- _i^t\|_1≤ 1κ _s_i\|( P_i^t) _i^t(· s_i)-P_i _i^t(· s_i)\|_1≤ 1κ _s_i,a_i\| P_i^t(· s_i,a_i)-P_i(· s_i,a_i)\|_1, where the last inequality follows from the convexity of the ℓ1 _1-norm and because (P^it)πit( P_i^t) _i^t and PiπitP_i _i^t are formed using the same policy πit _i^t. Because the represented and true occupancies use the same policy πit _i^t, ‖ρ^it−ρit‖1=‖ν^it−νit‖1\| ρ_i^t- _i^t\|_1=\| ν_i^t- _i^t\|_1. Combining this identity with (66) and (65), for every Ki(T)≤t<TK_i(T)≤ t<T, ‖ρ^it−ρit‖1≤3|i|κmaxsi,aiβt(si,ai)≤c|i|κHiΛtδit,\| ρ_i^t- _i^t\|_1≤ 3|S_i|κ _s_i,a_iβ^t(s_i,a_i)≤ c |S_i|κ H_i _t _it, which proves (20). Finally, using ‖ρ^it−ρit‖1≤2\| ρ_i^t- _i^t\|_1≤ 2 for t<Ki(T)t<K_i(T) and ∑t=1Tt−1/2≤2T _t=1^Tt^-1/2≤ 2 T, 1T∑t<T‖ρ^it−ρit‖1≤cKi(T)T+c|i|κHiΛTδiT. 1T _t<T\| ρ_i^t- _i^t\|_1≤ c K_i(T)T+c |S_i|κ H_i _T _iT. (67) Since git=gi(q−it)g_i^t=g_i(q_-i^t) is independent of si′s_i and ‖git‖∞≤1\|g_i^t\|_∞≤ 1, |∑t<T⟨q^it−qit,git⟩| | _t<T q_i^t-q_i^t,g_i^t | =|∑t<T∑si,ai,si′(q^it(si,ai,si′)−qit(si,ai,si′))git(si,ai)| = | _t<T _s_i,a_i,s_i ( q_i^t(s_i,a_i,s_i )-q_i^t(s_i,a_i,s_i ) )g_i^t(s_i,a_i) | =|∑t<T∑si,ai(ρ^it(si,ai)−ρit(si,ai))git(si,ai)|≤∑t<T‖ρ^it−ρit‖1. = | _t<T _s_i,a_i ( ρ_i^t(s_i,a_i)- _i^t(s_i,a_i) )g_i^t(s_i,a_i) |≤ _t<T\| ρ_i^t- _i^t\|_1. Dividing by T and applying (67) proves (21). Finally, the visitation event above has probability at least 1−γ/41-γ/4, while the anytime transition-confidence event ℰconfE_ conf of Lemma 10 has probability at least 1−γ/41-γ/4. Hence, by a union bound, their intersection has probability at least 1−γ/21-γ/2, completing the proof. ∎ C.3 Proof of Lemma 15 Proof. Fix t≥DTt≥ D_T and suppose the delay window [t−DT,t][t-D_T,t] is clean, meaning that no player updates its confidence set during that window, and condition on ℱt−DTF_t-D_T. Freeze each player’s policy at πjt−DT _j^t-D_T and, as in Step 1 of the proof of Lemma 14, couple its actual local trajectory over the delay window with the corresponding frozen-policy trajectory, evolving under the true transition kernel PjP_j and starting from the same state at time t−DTt-D_T.99 9 As in the proof of Lemma 14, we denote the local state trajectories of the actual process and the frozen-policy process for player i by Siτ\S_i^τ\_τ and S¯iτ\ S_i^τ\_τ, respectively. Similarly, we denote the corresponding joint state trajectories by Sτ\S^τ\_τ and S¯τ\ S^τ\_τ, respectively. More precisely, whenever Sjτ=S¯jτS_j^τ= S_j^τ, we use a maximal coupling of the one-step transition laws of the actual and frozen processes. Thus, the conditional probability that the two next states differ is bounded by the total variation distance between these one-step transition laws. Iterating this coupling over the delay window gives the path-separation bound in (58). Using this frozen-policy coupling argument, ∥ℙ((St,At)∈⋅∣ℱt−DT)−ℙ((S¯t,A¯t)∈⋅∣ℱt−DT)∥TV \|P((S^t,A^t)∈· _t-D_T)-P(( S^t, A^t)∈· _t-D_T) \|_ TV ≤∑j=1nℙ(∃τ∈[t−DT,t]:Sjτ≠S¯jτ|ℱt−DT)+sups∥⨂j=1nπjt(⋅∣sj)−⨂j=1nπjt−DT(⋅∣sj)∥TV, ≤ _j=1^nP\! (∃\,τ∈[t-D_T,t]:S_j^τ≠ S_j^τ\, |\,F_t-D_T )+ _s \| _j=1^n _j^t(· s_j)- _j=1^n _j^t-D_T(· s_j) \|_ TV, (68) where in the above inequality the first term bounds the probability that the coupled state trajectories separate at some time during the delay window. On its complement, the two processes have the same terminal state St=S¯t=sS^t= S^t=s. Conditional on this common state, the players choose their actions independently according to πjt(⋅∣sj)j=1n\ _j^t(· s_j)\_j=1^n in the actual process and πjt−DT(⋅∣sj)j=1n\ _j^t-D_T(· s_j)\_j=1^n in the frozen process, which gives the second term. By bounding each summand in the above inequality using (58) with DT2ηLj/δj2D_T^2η L_j/ _j^2 while bounding the second term using the product-TV bound ‖⨂jμj−⨂jνj‖TV≤∑j‖μj−νj‖TV,\| _j _j- _j _j\|_ TV≤ _j\| _j- _j\|_ TV, we can write ∥ℙ((St,At)∈⋅∣ℱt−DT)−ℙ((S¯t,A¯t)∈⋅∣ℱt−DT)∥TV \|P((S^t,A^t)∈· _t-D_T)-P(( S^t, A^t)∈· _t-D_T) \|_ TV (69) ≤cDT2η∑j=1nLjδj2+sups∑j=1n∥πjt(⋅∣sj)−πjt−DT(⋅∣sj)∥TV ≤ cD_T^2η _j=1^n L_j _j^2+ _s _j=1^n\| _j^t(· s_j)- _j^t-D_T(· s_j)\|_ TV ≤cDT2η∑j=1nLjδj2+cDTη∑j=1nLjδj2≤cDT2η∑j=1nLjδj2, ≤ cD_T^2η _j=1^n L_j _j^2+cD_Tη _j=1^n L_j _j^2≤ cD_T^2η _j=1^n L_j _j^2, (70) where the second inequality follows from (19), and the last inequality is obtained by adjusting the constant c. Since, conditional on ℱt−DTF_t-D_T, the initial local states and the frozen policies πjt−DTj=1n\ _j^t-D_T\_j=1^n are fixed, and the local transition and action randomizations are independent across players, the frozen local processes evolve independently. Therefore, their conditional joint law factorizes and we have ∥ℙ((S¯t,A¯t)∈⋅∣ℱt−DT)−⨂j=1nρjt−DT∥TV \|P(( S^t, A^t)∈· _t-D_T)- _j=1^n _j^t-D_T \|_ TV =∥⨂j=1nℙ((S¯jt,A¯jt)∈⋅∣ℱt−DT)−⨂j=1nρjt−DT∥TV = \| _j=1^nP(( S_j^t, A_j^t)∈· _t-D_T)- _j=1^n _j^t-D_T \|_ TV (71) ≤∑j=1n∥ℙ((S¯jt,A¯jt)∈⋅∣ℱt−DT)−ρjt−DT∥TV ≤ _j=1^n \|P(( S_j^t, A_j^t)∈· _t-D_T)- _j^t-D_T \|_ TV ≤∑j=1n∥ℙ(S¯jt∈⋅∣ℱt−DT)−νjt−DT∥TV ≤ _j=1^n \|P( S_j^t∈· _t-D_T)- _j^t-D_T \|_ TV ≤n(1−κ)DT, ≤ n(1-κ)^D_T, (72) where the first inequality follows from the product-TV inequality, the second follows because applying the common frozen action kernel πjt−DT(⋅∣sj) _j^t-D_T(· s_j) cannot increase total variation distance, while the third follows from Assumption 2. Finally, combining (69) and (71) by the triangle inequality gives the desired bound (22). ∎ C.4 Proof of Lemma 16 Proof. We work throughout on the event of Lemma 14, which holds with probability at least 1−γ/21-γ/2. Moreover, throughout we assume t≥DTt≥ D_T as the first DTD_T primitive times can be bounded directly and contribute at most cDT/(Tδi)cD_T/(T _i) after normalization. Now, fix t≥DTt≥ D_T and call a window [t−DT,t][t-D_T,t] clean if no player updates its confidence set during that window, and contaminated otherwise. Since player j has at most Jj(T)J_j(T) confidence updates up to time T, and each such update can contaminate the delay windows associated with at most DT+1D_T+1 primitive times, the number of primitive times t∈DT,…,T−1t∈\D_T,…,T-1\ whose delay window [t−DT,t][t-D_T,t] is contaminated satisfies #primitive times t with contaminated delay windows≲DT∑j=1nJj(T). \#\primitive times $t$ with contaminated delay windows\ D_T _j=1^nJ_j(T). (73) For t≥DTt≥ D_T, we use the direct decomposition R^it−git= R_i^t-g_i^t= (R^it−[R^it∣ℱt−DT])+([R^it∣ℱt−DT]−git−DT)+(git−DT−git). ( R_i^t-E[ R_i^t _t-D_T] )+ (E[ R_i^t _t-D_T]-g_i^t-D_T )+ (g_i^t-D_T-g_i^t ). (74) The first term is a delayed sampling martingale fluctuation, the second is the delayed bias, and the last term captures the drift of the stationary payoff gradient over the delay window. Step 1: Sampling term. We now control the delayed martingale term R^it−[R^it∣ℱt−DT] R_i^t-E[ R_i^t _t-D_T]. By construction, ‖R^it‖∞≤1/δi\| R_i^t\|_∞≤ 1/ _i, and hence ‖R^it−[R^it∣ℱt−DT]‖∞≤2/δi \| R_i^t-E[ R_i^t _t-D_T] \|_∞≤ 2/ _i. Moreover, [R^it−[R^it∣ℱt−DT]|ℱt−DT]=0.E [ R_i^t-E[ R_i^t _t-D_T]\, |\,F_t-D_T ]=0. Because the centering is with respect to ℱt−DTF_t-D_T rather than ℱtF_t, partition DT≤t<TD_T≤ t<T into the DT+1D_T+1 residue classes modulo DT+1D_T+1. Let r=DT≤t<T:(tmodDT+1)=rN_r=\D_T≤ t<T:(t\ mod\ D_T+1)=r\ denote the rrth residue class. Within each residue class, successive times are separated by DT+1D_T+1, so for every coordinate (si,ai,si′)(s_i,a_i,s_i ) the corresponding centered terms form a martingale-difference sequence. Moreover, since q^it−DT q_i^t-D_T is ℱt−DTF_t-D_T-measurable and has unit mass, the inner product of R^it−[R^it∣ℱt−DT] R_i^t-E[ R_i^t _t-D_T] with q^it−DT q_i^t-D_T also forms a martingale-difference sequence on the same residue class. Thus, Freedman’s inequality gives, for every x>0x>0, ℙ(|∑t∈r(R^it−[R^it∣ℱt−DT])(si,ai,si′)|≳|r|x+xδi)≤2e−x, ( | _t _r ( R_i^t-E[ R_i^t _t-D_T] )(s_i,a_i,s_i ) | |N_r|x+x _i )≤ 2e^-x, ℙ(|∑t∈r⟨q^it−DT,R^it−[R^it∣ℱt−DT]⟩|≳|r|x+xδi)≤2e−x. ( | _t _r q_i^t-D_T, R_i^t-E[ R_i^t _t-D_T] | |N_r|x+x _i )≤ 2e^-x. Taking a union bound over all players, coordinates, and residue classes, with x=cΛTx=c _T for a sufficiently large universal constant c, gives an event ℰgradE_ grad satisfying ℙ(ℰgrad)≥1−γ4.P(E_ grad)≥ 1- γ4. Since there are DT+1D_T+1 residue classes and ∑r=0DT|r|≤T _r=0^D_T|N_r|≤ T, Cauchy–Schwarz gives ∑r=0DT|r|≤T(DT+1) _r=0^D_T |N_r|≤ T(D_T+1). Thus, summing the residue-class bounds, on ℰgradE_ grad, for any qi′∈Δi,δi(Pi)q_i ∈ _i, _i(P_i), we have |∑DT≤t<T⟨qi′−q^it−DT,R^it−[R^it∣ℱt−DT]⟩|≲TDTΛT+DTΛTδi. | _D_T≤ t<T q_i - q_i^t-D_T, R_i^t-E[ R_i^t _t-D_T] | TD_T _T+D_T _T _i. (75) It remains to replace q^it−DT q_i^t-D_T by q^it q_i^t in (75). Using the occupancy movement bound (53) established in the proof of Lemma 14, we have ‖q^iℓ+1−q^iℓ‖1≤Liηδi\| q_i +1- q_i \|_1≤ L_iη _i. Hence, on a clean delay window, ‖q^it−q^it−DT‖1≤DTLiηδi. \| q_i^t- q_i^t-D_T\|_1≤ D_TL_iη _i. (76) Using ‖R^it−[R^it∣ℱt−DT]‖∞≤2/δi\| R_i^t-E[ R_i^t _t-D_T]\|_∞≤ 2/ _i and the trivial bound ‖q^it−q^it−DT‖1≤2\| q_i^t- q_i^t-D_T\|_1≤ 2 at primitive times t with contaminated delay windows, whose total number is at most of order DT∑j=1nJj(T)D_T _j=1^nJ_j(T) by (73), |∑DT≤t<T⟨q^it−DT−q^it,R^it−[R^it∣ℱt−DT]⟩|≲DTLiηδi2T+DTδi∑j=1nJj(T). | _D_T≤ t<T q^t-D_T_i- q_i^t, R_i^t-E[ R_i^t _t-D_T] | D_TL_iη _i^2T+ D_T _i _j=1^nJ_j(T). (77) Finally, by summing (75) and (77), and normalizing by T, we obtain |1T∑DT≤t<T⟨qi′−q^it,R^it−[R^it∣ℱt−DT]⟩|≲TDTΛT+DTΛTδiT+DTLiηδi2+DTδiT∑j=1nJj(T). | 1T\!\!\! _D_T≤ t<T\!\!\! q_i - q_i^t, R_i^t-E[ R_i^t _t-D_T] \! | TD_T _T+D_T _T _iT+ D_TL_iη _i^2+ D_T _iT _j=1^nJ_j(T). (78) Step 2: Delayed bias. Fix an arbitrary (si,ai,si′)(s_i,a_i,s _i). Since ri(S,A)(Si,Ai)=(si,ai)r_i(S,A) 1\(S_i,A_i)=(s_i,a_i)\ is a deterministic function of (S,A)(S,A) bounded by one, Lemma 15 implies that, on every clean window, |[rit(Sit,Ait)=(si,ai)|ℱt−DT]−ρit−DT(si,ai)git−DT(si,ai,si′)|= |E [r_i^t 1\(S_i^t,A_i^t)\!=\!(s_i,a_i)\\, |\,F_t-D_T ]- _i^t-D_T(s_i,a_i)g_i^t-D_T(s_i,a_i,s_i ) |= (79) |[ri(St,At)(Sit,Ait)=(si,ai)|ℱt−DT]−(S,A)∼⨂ρjt−DT[ri(S,A)(Si,Ai)=(si,ai)]| |E [r_i(S^t,A^t) 1\(S_i^t,A_i^t)\!=\!(s_i,a_i)\\, |\,F_t-D_T ]-E_(S,A) _j^t-D_T [r_i(S,A) 1\(S_i,A_i)\!=\!(s_i,a_i)\ ] | (80) ≲DT2η∑j=1nLjδj2+n(1−κ)DT. D_T^2η _j=1^n L_j _j^2+n(1-κ)^D_T. (81) Since ρ^it−DT(si,ai) ρ_i^t-D_T(s_i,a_i) is ℱt−DTF_t-D_T-measurable, we may divide (79) by ρ^it−DT(si,ai) ρ_i^t-D_T(s_i,a_i) and bring this factor inside the conditional expectation. Using ρ^it−DT(si,ai)≥δi ρ_i^t-D_T(s_i,a_i)≥ _i, we obtain |[rit(Sit,Ait)=(si,ai)ρ^it−DT(si,ai)|ℱt−DT]−ρit−DT(si,ai)ρ^it−DT(si,ai)git−DT(si,ai,si′)| |E [ r_i^t 1\(S_i^t,A_i^t)=(s_i,a_i)\ ρ_i^t-D_T(s_i,a_i)\, |\,F_t-D_T ]- _i^t-D_T(s_i,a_i) ρ_i^t-D_T(s_i,a_i)g_i^t-D_T(s_i,a_i,s_i ) | (82) ≲DT2ηδi∑j=1nLjδj2+nδi(1−κ)DT. D_T^2η _i _j=1^n L_j _j^2+ n _i(1-κ)^D_T. (83) We now relate the delayed normalization in (82) to the current normalization used in R^it R_i^t. On a clean delay window, using (76) and the fact that marginalization does not increase the ℓ1 _1-norm, we have ‖ρ^it−ρ^it−DT‖1≤DTLiη/δi\| ρ_i^t- ρ_i^t-D_T\|_1≤ D_TL_iη/ _i. Since both ρ^it(si,ai) ρ_i^t(s_i,a_i) and ρ^it−DT(si,ai) ρ_i^t-D_T(s_i,a_i) are at least δi _i, |1ρ^it(si,ai)−1ρ^it−DT(si,ai)|≤DTLiηδi3. | 1 ρ_i^t(s_i,a_i)- 1 ρ_i^t-D_T(s_i,a_i) |≤ D_TL_iη _i^3. Consequently, for any (si,ai,si′)(s_i,a_i,s _i) we have |[R^it(si,ai,si′)∣ℱt−DT]−[rit(Sit,Ait)=(si,ai)ρ^it−DT(si,ai)|ℱt−DT]|≤DTLiηδi3. |E[ R_i^t(s_i,a_i,s_i ) _t-D_T]-E [ r_i^t 1\(S_i^t,A_i^t)=(s_i,a_i)\ ρ_i^t-D_T(s_i,a_i)\, |\,F_t-D_T ] |≤ D_TL_iη _i^3. (84) Finally, since ‖git−DT‖∞≤1\|g_i^t-D_T\|_∞≤ 1 and ρ^it−DT(si,ai)≥δi ρ_i^t-D_T(s_i,a_i)≥ _i, ‖ρit−DTρ^it−DTgit−DT−git−DT‖∞ \| _i^t-D_T ρ_i^t-D_Tg_i^t-D_T-g_i^t-D_T \|_∞ ≤‖ρit−DT−ρ^it−DT‖1δi≲|i|κδiHiΛTδi(t−DT). ≤ \| _i^t-D_T- ρ_i^t-D_T\|_1 _i |S_i|κ _i H_i _T _i(t-D_T). (85) where the second inequality follows by the pointwise occupancy bound (20) of Lemma 14. Combining (82), (84), and (85), for every t with a clean delay window and t−DT≥Ki(T)t-D_T≥ K_i(T), we obtain ‖[R^it∣ℱt−DT]−git−DT‖∞≲DTLiηδi3+DT2ηδi∑j=1nLjδj2+nδi(1−κ)DT+|i|κδiHiΛTδi(t−DT). \|E[ R_i^t _t-D_T]-g_i^t-D_T \|_∞ D_TL_iη _i^3+ D_T^2η _i _j=1^n L_j _j^2+ n _i(1-κ)^D_T+ |S_i|κ _i H_i _T _i(t-D_T). For the remaining times, we use the trivial c/δic/ _i bound. In particular, by (73), there are at most of order DT∑j=1nJj(T)D_T _j=1^nJ_j(T) times whose associated delay windows are contaminated, and there are at most Ki(T)K_i(T) times in the range DT≤t<TD_T≤ t<T for which t−DT<Ki(T)t-D_T<K_i(T). Therefore, using ∑u=1Tu−1/2≤2T _u=1^Tu^-1/2≤ 2 T, we obtain 1T∑DT≤t<T‖[R^it∣ℱt−DT]−git−DT‖∞ 1T _D_T≤ t<T \|E[ R_i^t _t-D_T]-g_i^t-D_T \|_∞ ≲DTLiηδi3+DT2ηδi∑j=1nLjδj2+nδi(1−κ)DT D_TL_iη _i^3+ D_T^2η _i _j=1^n L_j _j^2+ n _i(1-κ)^D_T +|i|κδiHiΛTδiT+DTTδi∑j=1nJj(T)+Ki(T)Tδi. + |S_i|κ _i H_i _T _iT+ D_TT _i _j=1^nJ_j(T)+ K_i(T)T _i. (86) Step 3: Target drift. We now establish a bound on the target drift ‖git−git−DT‖∞\|g_i^t-g_i^t-D_T\|_∞. Since no confidence update occurs during a clean delay window, (54) gives, for every ℓ∈[t−DT,t−1] ∈[t-D_T,t-1], maxsj∥Pjπjℓ+1(⋅∣sj)−Pjπjℓ(⋅∣sj)∥1≤2Ljηδj2. _s_j\|P_j _j +1(· s_j)-P_j _j (· s_j)\|_1≤ 2L_jη _j^2. By stationarity and Assumption 2, ∥νjℓ+1−νjℓ∥1=∥νjℓ+1Pjπjℓ+1−νjℓPjπjℓ∥1≤maxsj∥Pjπjℓ+1(⋅∣sj)−Pjπjℓ(⋅∣sj)∥1+(−κ)∥νjℓ+1−νjℓ∥1, \| _j +1- _j \|_1\!=\!\| _j +1P_j _j +1\!\!\!\!\!- _j P_j _j \|_1\!≤\! _s_j\|P_j _j +1\!\!\!\!(· s_j)-P_j _j (· s_j)\|_1\!+\!(1\!-\!κ)\| _j +1- _j \|_1, and hence ‖νjℓ+1−νjℓ‖1≤2Ljηκδj2.\| _j +1- _j \|_1≤ 2L_jηκ _j^2. Since ρjℓ(sj,aj)=νjℓ(sj)πjℓ(aj∣sj) _j (s_j,a_j)= _j (s_j) _j (a_j s_j), using (19) gives ‖ρjℓ+1−ρjℓ‖1 \| _j +1- _j \|_1 ≤∥νjℓ+1−νjℓ∥1+maxsj∥πjℓ+1(⋅∣sj)−πjℓ(⋅∣sj)∥1≲Ljηκδj2. ≤\| _j +1- _j \|_1+ _s_j\| _j +1(· s_j)- _j (· s_j)\|_1 L_jηκ _j^2. (87) Therefore, telescoping over the clean delay window and using the multilinearity of gig_i in the opponents’ state–action occupancies, together with the fact that rewards lie in [0,1][0,1], gives ‖git−git−DT‖∞ \|g_i^t-g_i^t-D_T\|_∞ ≤∑j≠i‖ρjt−ρjt−DT‖1≤∑j≠i∑ℓ=t−DTt−1‖ρjℓ+1−ρjℓ‖1≲DTη∑j≠iLjκδj2. ≤ _j≠ i\| _j^t- _j^t-D_T\|_1≤ _j≠ i _ =t-D_T^t-1\| _j +1- _j \|_1 D_Tη _j≠ i L_jκ _j^2. (88) Here, the first inequality follows from the multilinearity of gig_i in the opponents’ state–action occupancies and the fact that rewards lie in [0,1][0,1], the second inequality is obtained by telescoping over the clean delay window, while the last follows from (87). Now, using the bound (87) for clean windows and the trivial bound ‖git−DT−git‖∞≤1\|g_i^t-D_T-g_i^t\|_∞≤ 1 on contaminated windows, we obtain 1T∑DT≤t<T‖git−DT−git‖∞≲DTη∑j≠iLjκδj2+DTT∑j=1nJj(T). 1T _D_T≤ t<T\|g_i^t-D_T-g_i^t\|_∞ D_Tη _j≠ i L_jκ _j^2+ D_TT _j=1^nJ_j(T). (89) Putting all together: Since ‖qi′−q^it‖1≤2\|q_i - q_i^t\|_1≤ 2, combining (74), (78), (86), and (89), and absorbing the first DTD_T primitive times and the smaller contaminated-window terms, gives 1T|∑t<T⟨qi′−q^it,R^it−git⟩|≲ 1T | _t<T q_i - q_i^t, R_i^t-g_i^t | TDTΛT+DTΛTδi+DTηLiδi3+DT2ηδi∑j=1nLjδj2+|i|κδiHiΛTδiT TD_T _T+D_T _TT _i+ D_Tη L_i _i^3+ D_T^2η _i _j=1^n L_j _j^2+ |S_i|κ _i H_i _T _iT +DTη∑j≠iLjκδj2+DTTδi∑j=1nJj(T)+DT+Ki(T)Tδi, +D_Tη _j≠ i L_jκ _j^2+ D_TT _i _j=1^nJ_j(T)+ D_T+K_i(T)T _i, where since (1−κ)DT≤e−κDT≤γ8nT3(1-κ)^D_T≤ e^-κ D_T≤ γ8nT^3, the exponentially small mixing term in (86) is absorbed into the displayed bound. Since ℙ(ℰgrad)≥1−γ/4P(E_ grad)≥ 1-γ/4, the result holds on the event of Lemma 14 and an additional event of probability at least 1−γ/41-γ/4, uniformly over qi′∈Δi,δi(Pi)q_i ∈ _i, _i(P_i). This proves (23). ∎ Appendix D Omitted Proofs for Section 6 D.1 Proof of Lemma 20 Proof. Partition primitive time into deterministic blocks Bm=ℓm,…,ℓm+2HiB_m=\ _m,…, _m+2H_i\ with ℓm=m(2Hi+1) _m=m(2H_i+1), as in the proof of Lemma 14. Because ηt→0 _t→ 0, for every sufficiently late block the small-movement condition (18), with η replaced by the stepsize at the beginning of the block, is satisfied. Thus, conditional on the filtration at the deterministic left endpoint, the event that the prescribed pair (si,ai)(s_i,a_i) is observed in the block, or that a confidence update occurs in the block, has probability at least δi/4 _i/4. We may therefore apply the same Freedman and union-bound argument leading to (64). To extend this finite-horizon bound to all sufficiently large times, we apply it on the nested dyadic horizons [0,Tk][0,T_k], Tk=2kT_k=2^k, and use Borel–Cantelli to ensure that all sufficiently large such horizons are simultaneously good. More precisely, apply the argument on horizon TkT_k with failure probability γk=c0/(k+1)2 _k=c_0/(k+1)^2, where c0>0c_0>0 is fixed. Since ∑k≥0γk<∞ _k≥ 0 _k<∞, the Borel–Cantelli lemma implies that, almost surely, there exists a finite random k0k_0 such that the corresponding finite-horizon event holds for every k≥k0k≥ k_0, simultaneously over the finitely many players and local pairs. Consequently, almost surely, for all sufficiently large k, the bound (64) holds simultaneously for all Ki(Tk)≤t≤TkK_i(T_k)≤ t≤ T_k. For every sufficiently large t, let k=⌈log2t⌉k= _2t . Then t≤Tk<2t≤ T_k<2t and Ki(Tk)=O(log(t+2))≤tK_i(T_k)=O( (t+2))≤ t. Hence (64) holds for all sufficiently large t, which gives (34). Thus, almost surely, we may choose a single finite random time T0T_0 large enough that k=⌈log2t⌉≥k0k= _2t ≥ k_0 and Ki(Tk)≤tK_i(T_k)≤ t for every player i and every t≥T0t≥ T_0, as claimed. By substituting (34) into the definition of the confidence radius βit(si,ai) _i^t(s_i,a_i) we get (35). Moreover, qit(si,ai,si′)=ρit(si,ai)Pi(si′∣si,ai),q^it(si,ai,si′)=ρ^it(si,ai)P^it(si′∣si,ai).q_i^t(s_i,a_i,s_i )= _i^t(s_i,a_i)P_i(s_i s_i,a_i), q_i^t(s_i,a_i,s_i )= ρ_i^t(s_i,a_i) P_i^t(s_i s_i,a_i). Therefore, ‖q^it−qit‖1 \| q_i^t-q_i^t\|_1 ≤∑si,ai|ρ^it(si,ai)−ρit(si,ai)|∑si′P^it(si′∣si,ai) ≤ _s_i,a_i| ρ_i^t(s_i,a_i)- _i^t(s_i,a_i)| _s_i P_i^t(s_i s_i,a_i) +∑si,aiρit(si,ai)∑si′|P^it(si′∣si,ai)−Pi(si′∣si,ai)| + _s_i,a_i _i^t(s_i,a_i) _s_i | P_i^t(s_i s_i,a_i)-P_i(s_i s_i,a_i)| ≤∥ρ^it−ρit∥1+maxsi,ai∥P^it(⋅∣si,ai)−Pi(⋅∣si,ai)∥1 ≤\| ρ_i^t- _i^t\|_1+ _s_i,a_i\| P_i^t(· s_i,a_i)-P_i(· s_i,a_i)\|_1 (90) ≤c|i|κmaxsi,aiβit(si,ai)+3|i|maxsi,aiβit(si,ai)=O(log(t+2)t+1)→0, ≤ c |S_i|κ _s_i,a_i _i^t(s_i,a_i)+3|S_i| _s_i,a_i _i^t(s_i,a_i)=O (\! (t+2)t+1 )→ 0, (91) where the third inequality uses (20) and (66), and the last equality is obtained by (35). ∎ D.2 Proof of Lemma 21 Proof. Fix x∈Δi,δi(it)x∈ _i, _i(P_i^t) and let PxP^x denote its induced transition kernel. By definition, Px∈itP^x _i^t. On the anytime confidence event ℰconfE_ conf, Pi∈itP_i _i^t as well. Therefore, the same dyadic-confidence argument used to establish (66), with P^it P_i^t replaced by PxP^x, gives maxsi,ai∥Px(⋅∣si,ai)−Pi(⋅∣si,ai)∥1≤3|i|maxsi,aiβit(si,ai). _s_i,a_i\|P^x(· s_i,a_i)-P_i(· s_i,a_i)\|_1≤ 3|S_i| _s_i,a_i _i^t(s_i,a_i). (92) Now x satisfies the normalization, flow, nonnegativity, and shrinkage constraints defining Δi,δi(Pi) _i, _i(P_i). Its only possible violation of this polytope is therefore in the true-kernel constraints x(si,ai,si′)=ρx(si,ai)Pi(si′∣si,ai).x(s_i,a_i,s_i )= _x(s_i,a_i)P_i(s_i s_i,a_i). Since x(si,ai,si′)=ρx(si,ai)Px(si′∣si,ai)x(s_i,a_i,s_i )= _x(s_i,a_i)P^x(s_i s_i,a_i) and ρx(si,ai)≤1 _x(s_i,a_i)≤ 1, the kernel bound (92) controls the violation of these linear constraints. Hoffman’s error bound1010 10 Hoffman’s error bound states that, for a nonempty polyhedron defined by a fixed finite system of linear equalities and inequalities, the distance of any point to the polyhedron is bounded by a constant times the magnitude of its constraint violations. The constant depends only on the coefficients of the fixed constraint system. for the fixed nonempty polytope Δi,δi(Pi) _i, _i(P_i) consequently gives dist1(x,Δi,δi(Pi))≤O(|i|maxsi,aiβit(si,ai)).dist_1\! (x, _i, _i(P_i) )≤ O (|S_i| _s_i,a_i _i^t(s_i,a_i) ). Taking the supremum over x∈Δi,δi(it)x∈ _i, _i(P_i^t) and applying (35) proves (37). We next control the change of the iterate at a confidence update t∈ℛit _i. Since the confidence sets are nested and contain the true kernel PiP_i, Δi,δi(Pi)⊆Δi,δi(it+1)⊆Δi,δi(it) _i, _i(P_i) _i, _i(P_i^t+1) _i, _i(P_i^t). Thus, dist1(q^it,Δi,δi(it+1))≤dist1(q^it,Δi,δi(Pi))≤O(|i|maxsi,aiβit(si,ai)), _1\! ( q_i^t, _i, _i(P_i^t+1) ) _1\! ( q_i^t, _i, _i(P_i) )≤ O (|S_i| _s_i,a_i _i^t(s_i,a_i) ), (93) where the second inequality follows from (37) since q^it∈Δi,δi(it) q_i^t∈ _i, _i(P_i^t). At a confidence update time t, using the Euclidean proximal update rule in the algorithm, we can write ‖q^it+1−q^it‖2 \| q_i^t+1- q_i^t\|_2 =‖projΔi,δi(it+1)(q^it+ηtR^it)−q^it‖2 \!=\! \|proj_ _i, _i(P_i^t+1)\! ( q_i^t\!+\! _t R_i^t )- q_i^t \|_2 ≤‖projΔi,δi(it+1)(q^it+ηtR^it)−projΔi,δi(it+1)(q^it)‖2+‖projΔi,δi(it+1)(q^it)−q^it‖2 \!≤\! \|proj_ _i, _i(P_i^t+1)\! ( q_i^t\!+\! _t R_i^t )-proj_ _i, _i(P_i^t+1)\! ( q_i^t ) \|_2\!\!+ \|proj_ _i, _i(P_i^t+1)\! ( q_i^t )- q_i^t \|_2 (94) ≤ηt‖R^it‖2+dist2(q^it,Δi,δi(it+1)) \!≤ _t\| R_i^t\|_2+dist_2\! ( q_i^t, _i, _i(P_i^t+1) ) (95) ≤ηt|i|δi+dist1(q^it,Δi,δi(it+1)) \!≤\! _t |S_i| _i+dist_1\! ( q_i^t, _i, _i(P_i^t+1) ) (96) ≤ηt|i|δi+O(|i|maxsi,aiβit(si,ai)), \!≤\! _t |S_i| _i+O (|S_i| _s_i,a_i _i^t(s_i,a_i) ), (97) where the second inequality uses nonexpansiveness of projection, the third inequality holds because dist2≤dist1dist_2 _1 and ‖R^it‖2≤|i|/δi\| R_i^t\|_2≤ |S_i|/ _i, and the last inequality follows from (93). Therefore, using the equivalence of norms in the fixed finite-dimensional occupancy space, ‖q^it+1−q^it‖1≤θi(maxsi,aiβit(si,ai)+ηt),\| q_i^t+1- q_i^t\|_1≤ _i ( _s_i,a_i _i^t(s_i,a_i)+ _t ), where θi<∞ _i<∞ depends only on the fixed problem parameters such as δi _i and |i||S_i|. It remains to sum this bound over the confidence-update times t∈ℛit _i. Fix a local pair (si,ai)(s_i,a_i) and let tkt_k be the time at which its counter reaches the kkth dyadic threshold, i.e., Nitk(si,ai)=2kN^t_k_i(s_i,a_i)=2^k. Since the counter can increase by at most one at each primitive time, tk≥2kt_k≥ 2^k. Moreover, (34) implies that, for all sufficiently large k, tk≤ci2kt_k≤ c_i2^k for some constant ci<∞c_i<∞, and hence tk≍2kt_k 2^k. Thus, by (35) and ηt=η0(t+1)−a _t= _0(t+1)^-a, we obtain maxsi,aiβitk(si,ai)=O(k 2−k/2) _s_i,a_i _i^t_k(s_i,a_i)=O( k\,2^-k/2) and ηtk=O(2−ak) _t_k=O(2^-ak), where we note that both these sequences are summable. Since player i has only finitely many local state–action pairs (si,ai)(s_i,a_i), summing over their dyadic confidence updates gives ∑t∈ℛi∥q^it+1−q^it∥1≤θi|i||i|O(∑k(k 2−k/2+2−ak))<∞, _t _i\| q_i^t+1- q_i^t\|_1≤ _i|S_i||A_i|O ( _k ( k\,2^-k/2+2^-ak ) )<∞, which proves (38). ∎