Finite-Time Concentration and Convergence Rates for Projected Two-Time-Scale Stochastic Approximation with Markov Noise

1.1 Contributions

• Under uniform one-block Lyapunov contraction, polynomial step sizes give joint fast-tracking and slow-error exponents arbitrarily close to 1/3; at the harmonic endpoint, fast tracking is Oa.s.((N0+n)^-1/3 sqrt(log(N0+n))).The harmonic-endpoint slow Lyapunov-error exponent is min{λT, 1/3}.Source: §1 · p. 3
• A strictly attracting box face with constant fast equilibrium yields joint rate Oa.s.(n^-1/2 log n), while the actor–critic value gap is Oa.s.(n^-1 log n).The actor–critic application also has critic error Oa.s.(n^-1/2 log n).Source: §1 · p. 3, §1.1 · p. 4
• The analysis gives high-probability fast-equilibrium tracking bounds that separate martingale noise, Markov sampling, equilibrium movement, and time-scale-separation effects.Only the averaged fast map is assumed contractive; the slow recursion need not be contractive.Source: §1.1 · p. 3
• The Skorokhod map handles possible boundary discontinuity and yields finite-horizon supremum-norm concentration of slow iterates around the projected-ODE trajectory.The slow iterate is projected onto a compact convex polyhedron.Source: §1 · p. 2, §1.1 · p. 3
• A Lipschitz Lyapunov function with uniform decrease over a fixed time horizon gives almost-sure convergence without requiring contraction or nonexpansiveness of the reduced slow map.A power lower bound on the decrease yields explicit optimized rates; uniform one-block contraction is the linear-decrease case.Source: §1.1 · p. 4
• The framework also covers projected TD(0), projected SGD, and fast-recursion projection, which ensures bounded fast iterates while retaining Euclidean contraction of the averaged fast map.The fast-projection extension removes Assumption 3.7.Source: §1 · p. 3, §1.1 · p. 4

Two-time-scale stochastic approximation

• Earlier TTSA rate analyses commonly require contraction or strong monotonicity of both the frozen-slow fast operator and equilibrium-reduced slow operator.Reported results include mean-square and concentration bounds, asymptotic normality, and almost-sure convergence.Source: §2 · p. 4
• Linear two-time-scale work includes asymptotic covariance and normality under i.i.d. noise, and concentration bounds with reinforcement-learning applications.Konda and Tsitsiklis [17] study asymptotic covariance; Dalal et al. [12] derive concentration bounds; Doan give an O(k^-2/3) mean-square bound under strong-monotonicity assumptions.Source: §2 · p. 4
• Chandak allows a nonexpansive slow map and projected fast recursion, with residual mean-square rate O(k^-1/4+ε).Chandak [6] obtains O(k^-a) for α_k ≍ k^-a, β_k ≍ k^-1, a ∈ (1/2, 1), using contraction on both reduced operators.Source: §2 · p. 5

Projected stochastic approximation

• Classical projected stochastic approximation studies asymptotic convergence, weak convergence, and large-deviation principles rather than finite-time rates.For single-time-scale projection onto a hyperrectangle, Borowski and Miasojedow [4] prove almost-sure convergence to the projected ODE's stationary set.Source: §2 · p. 5

Model

• The model couples a fast iterate x_n with a slow iterate θ_n projected onto a compact convex polyhedron, while the Markov transition law depends on θ_n.The fast update functions and noise processes are introduced in the model; the chain has a unique stationary distribution for each parameter.Source: §3 · pp. 5–6

Regularity and stability

• The assumptions require martingale-difference noise, bounded-set Lipschitz updates, and a uniform hitting-time bound for the controlled chain.The hitting-time condition controls Poisson-equation solutions used to decompose Markov noise; boundedness of the fast iterate keeps proof quantities uniformly bounded.Source: §3 · pp. 6–8

Averaged fast dynamics

• For each frozen θ, the stationary-averaged fast map is a contraction with a unique fixed point x*(θ), and no contractivity of a discrete slow map is required.The contraction factor may depend on θ if it is uniformly bounded below one; the fixed-point map is Lipschitz under the stated assumptions.Source: §3 · pp. 6–7

Step sizes and boundedness

• Polynomial step sizes use α_n=(N0+n)^-a and β_n=(N0+n)^-b with 1/2<a<b≤1, so the slow scale decays faster.The fast iterate is assumed bounded; projecting it onto a compact convex polyhedron can ensure boundedness by construction and removes that assumption in the extension.Source: §3 · p. 8

4 Continuous-time step embeddings and projected dynamical systems

• The slow iterate is embedded as a right-continuous, piecewise-constant path on the cumulative grid t(n+1)-t(n)=β_n, with discrete blocks corresponding to fixed slow-time intervals.Each block K_m has slow-time interval [T_m,T_{m+1}], and the block path is indexed from its entrance.Source: §4 · p. 9

4.1 Projected dynamical systems

• A projected dynamical-system solution is absolutely continuous and follows the projected vector field almost everywhere; the slow recursion uses this definition with C=Θ.The block comparison uses the normal-reflection Skorokhod map, whose finite Lipschitz constant controls differences between projected paths.Source: §4.1 · p. 10, §4 · p. 10

Concentration proof sketch and overview

• A high-probability fast-tracking bound is used to compare the slow step embedding with the projected ODE over each finite slow-time block.The maximum deviation is controlled blockwise after establishing the bound on ||x_n-x*(θ_n)||.Source: §5 · p. 11
• A Lipschitz Lyapunov function with uniform one-block decrease yields almost-sure convergence; a power lower bound on the decrease supplies explicit rates.One-block Lyapunov contraction is the linear-decrease special case.Source: §5 · p. 11
• The projected vector field may be discontinuous at the constraint boundary, so standard concentration arguments for Lipschitz ODE fields do not apply directly.Each projected step path is the Skorokhod-map image of its unconstrained driver; the map's finite-horizon Lipschitz property bounds projected-path differences through driver differences.Source: §5 · p. 11

6.1 Block-restarted averaged recursion

• The original fast recursion is compared with a block-restarted averaged recursion initialized at the same fast iterate and driven by the same slow-parameter sequence.The comparison isolates within-block martingale increments and Markov noise; the auxiliary recursion itself uses the averaged map without sampled states or explicit noise increments.Source: §6 · p. 12, §6.1 · p. 12

6.2 Poisson decomposition and local fast fluctuations

• The fast Markov sampling error is decomposed into a martingale term and a successive-state Poisson residual, controlled by concentration and summation by parts.The Poisson residual is bounded using the slow variation of the fast and slow iterates.Source: §6.2 · p. 13

6.3 Comparison with the block-restarted averaged recursion

• Contraction transfers the martingale and residual bounds into a local comparison between the original and block-restarted averaged recursions.The successive-state residual is stepsize-weighted and bounded by summation by parts.Source: §6.3 · p. 14

6.4 Tracking the moving fixed point

• The moving-equilibrium comparison combines contracted block-entry error with deterministic tracking lag of order β_nm/α_nm.The contraction accumulated since block entry and the equilibrium’s movement jointly determine the local bound.Source: §6.4 · pp. 14–15

6.5 Blockwise fast tracking

• The fast tracking error is formed by combining the averaged-recursion comparison with the moving-equilibrium comparison.The resulting block-endpoint estimate supports iteration across successive blocks.Source: §6.5 · p. 15
• Blockwise fast tracking combines martingale and Markov-noise fluctuations with the lag from movement of the fast equilibrium.The bounds include both pointwise and block-endpoint tracking estimates, which can be iterated across blocks.Source: §6.5 · p. 15

7.1 Auxiliary projected recursion

• The original slow recursion is compared with an auxiliary projected recursion to isolate fast-tracking error, slow martingale noise, and Markov noise.The auxiliary update separates the fast-tracking error, centered Markov sampling error, auxiliary-state mismatch, and explicit slow martingale noise.Source: §7 · p. 16, §7.1 · pp. 16–18
• The auxiliary projected recursion is distinct from the block-restarted averaged fast recursion used in the fast-iterate analysis.It is the slow-coordinate recursion used in the first stage of the projected-ODE comparison.Source: §7 · p. 16

7.2 Comparison of the auxiliary recursion with the projected ODE

• The auxiliary recursion and projected ODE are compared through their unconstrained driving paths, whose differences the Lipschitz Skorokhod map transfers to projected paths.The comparison also accounts for time-grid discretization and the mismatch between off-diagonal auxiliary drift evaluations and the ODE’s diagonal field.Source: §7 · p. 16, §7.2 · p. 20

7.3 Putting the estimates together

• The localized blockwise tracking theorem bounds the slow iterate’s deviation from the projected ODE using fast- and slow-martingale thresholds.The thresholds may be chosen separately for each block.Source: §7.3 · p. 21

8 Almost-sure convergence and last-iterate rates

• A Lipschitz Lyapunov function with uniform one-block decrease yields almost-sure convergence of both the Lyapunov error and distance to the projected-ODE equilibrium set.The decrease is required over a fixed block horizon, uniformly over initial states.Source: §8 · pp. 23–24
• A power-law lower bound on Lyapunov decrease supplies explicit last-iterate rates, while uniform one-block contraction permits a sharper slow-error estimate.The rate results apply under the hypotheses of the one-block decrease theorem.Source: §8 · p. 24

T Jmax + LJCB,T

• Under uniform Lyapunov contraction, polynomial step sizes give joint fast-tracking and slow Lyapunov-error exponents arbitrarily close to 1/3.The fast exponent is maximized at b = 1 and a = 2/3, where it equals 1/3.Source: §8 · p. 23, T Jmax + LJCB,T · p. 25
• For harmonic slow step sizes, b = 1 and a = 2/3 yield fast tracking at O_a.s.((N0 + n)^-1/3 sqrt(log(N0 + n)).Under the power-decrease result, the slow rate depends on the Lyapunov decrease exponent.Source: §8 · p. 24, T Jmax + LJCB,T · p. 25

8.1 Faster rates at an attracting equilibrium face

• A strictly attracting equilibrium face of a box and a fast equilibrium constant on that face yield a joint rate of O_a.s.(n^-1/2 log n) with the second step-size schedule.The face condition reduces the contribution from movement of the fast equilibrium.Source: §8.1 · p. 26

8.2 Improved rates under contraction of the reduced slow map

• A Euclidean contraction of the reduced slow update map gives O_a.s.(n^-1/2 log n) joint rates with logarithmically separated step sizes, including boundary equilibria.Unlike the attracting-face result, this condition allows an arbitrary compact convex polyhedron and does not require a common fast target along a face.Source: §8.2 · p. 27

Actor–critic setup

• The actor–critic result concerns a global-clock recursion that updates observed state and state–action coordinates using step sizes indexed by environment transitions.The recursion uses one observed state–action transition per iteration.Source: §9 · p. 28
• Uniformly positive stationary state–action frequencies support Lyapunov decrease and identify a restricted-optimal equilibrium face where the critic equilibrium is the restricted optimum.The actor’s endpoint coordinates have strictly outward drift, so the attracting-face rate result applies.Source: §9 · p. 29

Actor–critic rate

• For αn = A log(N0+n)/(N0+n) and βn = B/(N0+n), with the shift specified in that proposition, the actor value gap is Oa.s.(n^-1 log n).Source: §9 · p. 29
• For any prescribed policy-class tolerance, the logit bound can be chosen so the restriction bias is at most that tolerance.The unrestricted aggregate value gap is then bounded by that tolerance plus the vanishing term in (9.3).Source: §9 · p. 29

10 Conclusion

• Skorokhod-map comparisons handle boundary discontinuities and separate martingale, Markovian, and time-scale contributions in the tracking bounds.The bounds compare the fast iterate with its moving equilibrium and the projected slow path with its ODE trajectory on each slow-time block.Source: §10 · pp. 29–30
• Uniform one-block Lyapunov decrease gives almost-sure convergence, while power decrease and contraction yield explicit last-iterate rates.With polynomial step sizes, the joint exponent approaches 1/3; under a strictly attracting equilibrium face and common fast target, logarithmically separated steps give a joint O(n^-1/2 log n) rate.Source: §10 · p. 30
• Euclidean contraction of the reduced slow map gives the same joint O(n^-1/2 log n) rate on compact convex polyhedra, including boundary equilibria.The attracting-face result also gives an O(n^-1 log n) constrained-policy value gap in actor–critic; companion applications include projected TD(0), projected SGD, and fast-coordinate projection.Source: §10 · p. 30

A Selected Proofs of the Main Results

• The paper gives path comparisons for the fast and slow recursions and carries Lyapunov control from block endpoints to every iteration.Supporting Skorokhod representations, Poisson-equation and martingale estimates, and remaining proofs are collected in the Online Companion.Source: A Selected Proofs of the Main Results · p. 30

A.1 Proof of Proposition 6.1

• The proof of Proposition 6.1 combines the fast- and slow-tracking lemmas to establish its block bounds, then sums pointwise bounds for the cumulative estimate.Monotonicity of the step-size ratio and the block-weight recursion support the summation.Source: §A.1 · p. 30

A.2 Proof of Lemma 6.3

• Lemma 6.3 controls the discrepancy between the original and block-restarted averaged fast iterates using fast-state contraction, without comparing parameter paths or Skorokhod maps.The decomposition separates a martingale transform, a Poisson residual, and contractive propagation.Source: §A.2 · pp. 30–31

A.3 Proof of Lemma 6.4

• Lemma 6.4 uses projection nonexpansiveness and the stated assumptions to obtain a scalar recursion, which is then iterated.The supplied proof excerpts do not state the resulting bound explicitly.Source: §A.3 · p. 32

A.4 Proof of Proposition 7.1; A.5 Proof of Proposition 7.2

• Proposition 7.2 bounds the auxiliary driver’s discrepancy by the contribution of one grid interval and uses Gronwall and a finite-horizon Skorokhod estimate.The proof of Proposition 7.1 also applies a Skorokhod comparison and discrete Gronwall to obtain its bound.Source: §A.5 · p. 33, §A.4 · p. 33

A.6 Proof of Theorem 7.1

• Theorem 7.1’s proof combines the finite-horizon slow-dynamics comparison with fast tracking to establish its stated tracking bound.The proof also uses the step-size relation and a bound on the block time horizon.Source: §A.6 · p. 34

S.1 Projected On-Policy Linear TD(0)

• Projected linear TD(0) yields an eventual almost-sure envelope for the raw iterate, with the usual on-policy projected-Bellman solution as target when it lies in the constraint set.The proof verifies that the TD matrix is nonsingular and its contraction parameter is positive.Source: §S.1 · pp. 38–40

S.2 Optimization: Projected Stochastic Gradient Descent

• Projected SGD has almost-sure rates for distance to its constrained minimizer and objective gap; when the minimizer is interior, the gap is controlled by squared distance.The rate result assumes strong convexity; the interior conclusion follows from the descent lemma.Source: §S.2 · pp. 40–41

S.3 One-time-scale specialization

• The one-time-scale specialization provides almost-sure bounds under one-block contraction and separately treats a Lipschitz Lyapunov function with power-type decrease.The hypotheses include bounded martingale differences and a controlled Markov chain; recursions without a fast variable are embedded by setting that coordinate and its noise to zero.Source: §S.3 · pp. 41–42
• J(θ_n) → 0 almost surely under the stated uniform decrease condition.The result is the one-time-scale specialization of the Lyapunov argument.Source: §S.3 · p. 42

S.5.3 Fast Poisson residual

• The fast Poisson-residual proof uses summation by parts and step-size monotonicity, with bounds controlled by fast and slow iterate changes and the fast Poisson solution.The proof also bounds interior and boundary terms using the Poisson-solution bound and step sizes.Source: §S.5.3 · pp. 45–46

S.5.5 Arbitrary fast-coordinate norms

• The fast-scale arguments allow any fixed fast-coordinate norm when the relevant assumptions use that norm, while slow projection and Skorokhod-map arguments remain Euclidean.Norm-equivalence constants convert between coordinatewise martingale bounds and the chosen fast norm.Source: §S.5.5 · p. 47

S.7.1 Proof of Theorem 8.3

• At b = 1, the power-decrease condition alone cannot guarantee a polynomial iteration-wise rate; when p_J = 2, the rate is O_a.s.(1/log n).A deterministic scalar recursion demonstrates that the logarithmic rate is intrinsic to this condition.Source: §S.7.1 · pp. 48–49

S.7.4 Proof of Corollary 8.1

• For fixed b > 3/4, the rate-exponent maximum is b/3 at a = 2b/3; for 1/2 < b ≤ 3/4, its supremum is b − 1/2.These values follow by optimizing r_x(a, b).Source: §S.7.4 · p. 51
• For Corollary 8.1, the proof establishes the stated optimized rates for b<1 and shows that rx(a,1) is maximized at a=2/3, with maximum 1/3.The harmonic-endpoint claims follow from Theorems 8.4 and 8.1.Source: §S.7.4 · p. 52
• Corollary 8.1’s almost-sure envelope does not imply a mean-square bound without an additional integrability argument, and comparison with Chandak et al. is limited by differing assumptions and convergence modes.The remark says the squared trajectory-wise scale agrees at the exponent level, up to logarithmic and arbitrarily small polynomial losses, with their O(n^-2/3) mean-square rate.Source: §S.7.4 · p. 52

S.7.5 Proof of Corollary 8.2

• For Corollary 8.2 with b<1, choosing a=2pJ/(4pJ−1) and b=3pJ/(4pJ−1) gives rx(a,b)=pJ/(4pJ−1).The proof derives the slow bound from Theorem 8.3 and the fast bound from Theorem 8.1.Source: §S.7.5 · p. 53
• For Corollary 8.2 at the harmonic endpoint b=1, the proof takes a=2/3 and invokes the harmonic branch of Theorem 8.3.The supplied passage does not state the resulting rate.Source: §S.7.5 · p. 53

S.7.6 Proof of Proposition 8.1

• The proof establishes consistency by showing the Lyapunov error tends to zero and the slow iterate approaches the equilibrium set almost surely.It uses blockwise projected-ODE tracking, Lyapunov decrease, and a distance bound derived from the endpoint recursion.Source: §S.7.6 · pp. 55, 57
• For the common-target case, the fast recursion contracts toward the shared fast target, with forcing controlled by distance to the equilibrium set.The argument uses a fixed fast-time interval and a previously established face-distance bound; the stated polynomial exponents follow by substituting the schedules.Source: §S.7.6 · pp. 57–58

S.7.7 Proof of Proposition S.3.1

• For the recursion without a fast component, the proof reuses the projected-ODE comparison argument with fast terms omitted.The cited proof passage identifies the substitutions and invokes the resulting comparison theorem, but does not state the full rate formula.Source: §S.7.7 · pp. 58, 60

S.7.8 Proof of Proposition S.3.2

• Under the power-decrease condition, the block-endpoint Lyapunov error follows an eventual perturbed recursion, whose optimized polynomial exponent is 1/(3p_J − 1).The proof balances the two rate terms to obtain the common exponent.Source: §S.7.8 · pp. 60–61

S.8 Proofs from Main-Paper Section 9 (Actor-Critic)

• The projected actor ODE’s equilibria are exactly the zero set of JBac, and every trajectory reaches that set within a uniform finite time, yielding one-block Lyapunov contraction.The proof first shows that JBac is nonincreasing and bounds the time to enter a small sublevel; nonzero restricted gaps then drive logits to their required endpoints.Source: §S.8 · pp. 66–67
• The actor-critic proof verifies the theorem’s conditions and establishes the component bounds and joint rate in (9.5), together with a bound on bounded-logit restriction bias.The proof uses the common fast target V⋆_Bac and establishes the restriction-bias bound by comparing restricted and unrestricted optimal values.Source: §S.8 · p. 68

S.9 Extension: Projection of the Fast-Scale Iterate

• The optional extension projects the fast iterate at every step onto a fixed compact feasible set, removing the need for the fast-stability assumption and enforcing boundedness.Under the stated Euclidean contraction and bounded-preprojection-noise conditions, it provides the corresponding high-probability path-tracking and almost-sure last-iterate guarantees.Source: §S.9 · p. 68

S.9.1 Euclidean projection and contraction

• On a compact convex polyhedron with averaged contraction in the Euclidean norm, the Euclidean projection is nonexpansive.The extension restricts the contraction requirement and fast-state Lipschitz assumptions to the feasible set X.Source: §S.9.1 · pp. 68–69
• Fast projection bounds the state but does not by itself bound preprojection noise, so the pathwise bounded-noise assumption remains necessary.Source: §S.9.1 · p. 69

S.9.2 Constrained equilibrium and projected fast ODE

• For each slow parameter, Euclidean contraction gives a unique constrained fast equilibrium with exponential stability; it may differ from the unprojected target and change the reduced slow dynamics.Source: §S.9.2 · pp. 70–71

S.9.3 Fixed fast-time blocks and the moving-parameter comparison

• Because a slow-time block has diverging fast-time duration, the proof partitions it into fixed fast-time subblocks and compares the projected recursion with a moving-parameter averaged recursion.The comparison uses the Skorokhod map and yields bounds on each fast-time block, with contraction on full blocks.Source: §S.9.3 · pp. 71, 74, 75

S.9.4 Slow-block interface and high-probability event

• A high-probability slow-block event transfers the projected-fast tracking bounds to localized tracking of the slow projected ODE, and a Borel–Cantelli argument gives an eventual pathwise block event.The transfer accounts for both projections and combines the fast- and slow-block failure probabilities.Source: §S.9.4 · pp. 77–78

S.9.5 Almost-sure rates, including the harmonic slow step

• A global fast-clock partition is introduced to obtain an iteration-wise fast rate, under either the shifted-step condition or a finite-prefix alternative.Source: §S.9.5 · p. 78
• Theorem S.9.1 establishes the fast bound and slow conclusions for a compact convex polyhedron under the stated standing assumptions, without requiring Assumption 3.7.It applies with either the shifted-step condition or the finite-prefix alternative.Source: §S.9.5 · pp. 78–79
• Oa.s.(1/log n) is the harmonic rate when pJ = 2 under the general one-block decrease condition and b < 1.The theorem also gives a conclusion under a power lower bound with pJ > 1.Source: §S.9.5 · p. 79
• Under the linear one-block contraction condition with b < 1, the slow-rate expression uses rx(2/3, 1) = 1/3.The stated parameter constraint is 0 < λX T < rx(a, 1).Source: §S.9.5 · p. 79

• The lemma records bounds for the fast Poisson-equation solution and the martingale difference sequence under the stated bounded-state conditions.Source: §S.10 · p. 80
• A return-time representation and a uniform bound on the centered fast drift are used to bound the Poisson-equation solution.Source: §S.10 · pp. 80–81
• The vector-valued supremum norm is defined by taking the maximum over states, and scalar-matrix bounds incur no dimension-dependent factor.Source: §S.10 · p. 81
• The proof controls changes in the Poisson solution across states and parameters using a resolvent identity, with both solutions vanishing at y⋆.Source: §S.10 · p. 81

S.11 Auxiliary Results Used for Main-Paper Section 7

• S.11 establishes bounds for the Poisson equation and its martingale differences, and controls the residual term in the Poisson decomposition over a block.The residual result applies for 1 ≤ n ≤ Km.Source: §S.11 · pp. 82–83

S.12 Strong monotonicity and exponential stability of projected ODEs

• Strong monotonicity at an equilibrium makes the projected ODE well posed and globally exponentially stable, with a unique equilibrium and a contracting Lipschitz Lyapunov function.The one-block contraction factor is ρT = e^(−µsmT) for every T > 0; a contraction update map yields the strong-monotonicity condition.Source: §S.12 · p. 85

S.13 Skorokhod problem

• For convex polyhedra, the Skorokhod problem has a unique solution and its map is Lipschitz, enabling comparisons between projected paths through their driving paths.A blockwise result identifies the step-path embeddings with Skorokhod-map projections and applies the map’s Lipschitz bound.Source: §S.13 · pp. 87–88

S.14 Step-size-related results

• S.14 provides auxiliary step-size estimates for polynomial step sizes αn = (n + N0)^−a with 0 < a < 1.The supplied passages show estimates involving the step-size weights but do not expose their full bounds.Source: §S.14 · p. 89

S.15 Miscellaneous results

• S.15 supplies lemmas for well-posedness of the projected ODE, perturbed power-drift recursions, and geometric convolution of a blockwise rate envelope.The ODE solution is unique and remains in Θ; the recursion results provide comparison bounds under their stated conditions.Source: §S.15 · pp. 90–91
• For 1/2 < b < 1, block indices grow polynomially in m; for harmonic steps, block locations grow exponentially and m = O(log X_m).These block-geometry estimates support the later blockwise bounds.Source: §S.15 · pp. 92–94
• For harmonic slow steps, geometric-convolution bounds depend on whether λρ,T is greater than, equal to, or less than r.The equality case sums a polynomial-logarithmic factor, while the other cases use convergent geometric-series comparisons.Source: §S.15 · p. 94
• For a finite-state chain with finite expected return time to y⋆, the expected cycle occupation measure is µ/µ(y⋆).The proof identifies the occupation measure as invariant, then normalizes it using its value at y⋆.Source: §S.15 · p. 95

S.16.1 Choosing N0 to begin the analysis at n = 1

• A sufficiently large N0 lets the analysis begin at n = 1, with the named domination inequality following from the stated step-size conditions.The small-step condition supports local martingale and Poisson-residual estimates; block-dependent thresholds avoid an additional fixed-threshold infinite-horizon condition.Source: §S.16.1 · pp. 95–96

S.16.2 Beginning the analysis at n = n0 when N0 = 1

• With N0 = 1, the analysis can begin at n0 using prior algorithm iterates, and the resulting almost-sure rates hold at sufficiently large original indices with unchanged exponents.Suffix step-size estimates support the blockwise arguments, and retaining the original slow-time grid changes only constants in the block-geometry and convolution bounds.Source: §S.16.2 · pp. 96–97

Coupled contraction estimates

• Oa.s.(log(N0 + n)/√(N0 + n)) is obtained by induction and transferred from the auxiliary sequences to the original iterates.The bound applies under logarithmically separated step sizes and the coupled contraction estimates.Source: §S.17 · p. 100

Projected equilibrium and initial convergence

• At a boundary equilibrium, the averaged slow drift may be nonzero and point outward even though projection leaves the equilibrium fixed.The proof retains this equilibrium normal in its slow-error comparison rather than assuming the averaged drift vanishes.Source: §S.17 · pp. 101, 104
• Distance to the unique projected equilibrium is a global Lipschitz Lyapunov function with uniform one-block contraction.The proof identifies the unique fixed point of the projected contractive map and uses the corresponding Lyapunov control.Source: §S.17 · p. 101

Noise averaging within the feasible set

• The fast-noise weighted average is Oa.s.(√(αn log tn)), with the martingale contribution controlled by Azuma–Hoeffding and Borel–Cantelli.The proof uses a Poisson-equation decomposition to separate martingale differences, bounded correctors, and a small remainder.Source: §S.17 · pp. 98, 101, 102

The face reached by the auxiliary

• The auxiliary sequence eventually enters and remains on the face maximizing the inner product with the equilibrium drift.On that face, the drift term is constant in the projection objective, sharpening the auxiliary increment bound.Source: §S.17 · pp. 100, 103
• The auxiliary-face argument requires only that the auxiliary sequence eventually remain on the selected face; the noisy iterates need not do so.No strict complementarity is required, and the fast equilibrium need not be constant along the face.Source: §S.17 · p. 103

Motivation and assumptions

• Convexity–concavity alone does not guarantee convergence of the descent–ascent ODE, which can cycle even in bilinear games.The stated power-curvature condition permits curvature to vanish at the saddle and does not require strong convexity–concavity.Source: §S.18 · p. 105

Saddle-point learning under power curvature

• The projected saddle-point ODE has a unique equilibrium and a distance Lyapunov function satisfying the required power decrease with pJ = q − 1.The fast variable estimates the saddle field while both primal and dual variables evolve on the slow time scale.Source: §S.18 · p. 105

A family with vanishing curvature

• For q = 4, the slow-iterate rate is Oa.s.((N0 + n)^−1/11{log(N0 + n)}^1/6), with no optimality claim.This example allows the saddle to lie on the boundary and does not have strong convexity or strong concavity near zero.Source: §S.18 · p. 107

Comparison with existing frameworks

• For the bilinear family with A ≠ 0, the reduced forward map is not locally nonexpansive in any fixed norm, so the cited reduced-map assumptions do not cover it.Its Jacobian has eigenvalues 1 ± ihσ with moduli greater than one for every h > 0 when σ is a nonzero singular value of A.Source: §S.18 · p. 107

Application scope

• The actor–critic rate claim applies to the stated global-clock recursion, not the original visit-count or delayed implementation.The paper identifies the global-clock recursion as the scope of that application’s rate claim.Source: §S.18 · p. 108