Achieving ϵ−2 Sample Complexity for Single-Loop Actor-Critic under Minimal Assumptions Ishaq Hamza∗ and Zaiwei Chen†
arXiv:2605.13639v1 [cs.LG] 13 May 2026
∗
IISc, [email protected] ,
†
Purdue IE, [email protected]
Abstract In this paper, we establish last-iterate convergence rates for off-policy actor– critic methods in reinforcement learning. In particular, under a single-loop, single-timescale implementation and a broad class of policy updates, including approximate policy iteration and natural policy gradient methods, we prove the first Õ(ϵ−2 ) sample complexity guarantee for finding an ϵ-optimal policy under minimal assumptions, namely, the existence of a policy that induces an irreducible Markov chain. This stands in stark contrast to the existing literature, where an Õ(ϵ−2 ) sample complexity is achieved only through nestedloop updates and/or under strong, algorithm-dependent assumptions on the policies, such as uniform mixing and uniform exploration. Technically, to address the challenges posed by the coupled update equations arising from the single-loop implementation, as well as the potentially unbounded iterates induced by off-policy learning, our analysis is based on a coupled Lyapunov drift framework. Specifically, we establish a geometric convergence rate for the actor and an Õ(1/T ) convergence rate for the critic, and combine the two Lyapunov drift inequalities through a cross-domination property. We believe this analytical framework is of independent interest and may be applicable to other coupled iterative algorithms with unbounded iterates.
1
Introduction
Reinforcement learning (RL) has become increasingly impactful in solving sequential decisionmaking problems [56], ranging from game-playing AI [53] to large language models [43]. Mathematically, RL can be viewed as a data-driven framework for solving Markov decision processes (MDPs) [46]. Two classical approaches to solving MDPs are value iteration and policy iteration, which, in model-free RL, correspond to value-space methods such as Q-learning [63] and policyspace methods such as actor–critic [29], respectively. For Q-learning, it has long been established that an Õ(ϵ−2 ) sample complexity is achievable as long as the stationary behavior policy induces an irreducible and aperiodic Markov chain; see [14, 35, 48], among many others. The aperiodicity assumption has recently been relaxed in [9, 22, 41]. Irreducibility is essentially minimal for exploration in the sense that, if this assumption is violated, then there exists at least one state that is visited only finitely many times during the learning process. ∗
Much of this work was carried out while the author was a research intern at the Edwardson School of Industrial Engineering, Purdue University.
1
For actor–critic methods, existing results achieving an Õ(ϵ−2 ) sample complexity mostly rely on a nested-loop implementation [24, 30, 36, 65], where the actor is updated in an outer loop while being held fixed in an inner loop for critic updates. In contrast, practical actor–critic algorithms are typically implemented using a more natural single-loop structure, in which both the actor and the critic are updated simultaneously at each iteration [21, 37, 38]. Moreover, even under a nested-loop implementation, existing results often impose strong, algorithm-dependent assumptions, such as requiring all policies encountered along the algorithm trajectory, or simply all policies, to induce irreducible and aperiodic Markov chains, with mixing factors uniformly bounded above and stationary distributions uniformly bounded away from zero [2, 10, 42, 47], with only a few exceptions [12, 24, 36]. A more detailed literature review is presented in Section 1.2. Since value-space and policy-space methods are two fundamental pillars of RL, there is little reason to believe that the latter are inherently less sample efficient or require stronger assumptions than the former. This motivates the following question: Can actor–critic methods achieve Õ(ϵ−2 ) sample complexity with a single-loop implementation under minimal assumptions, in particular, the existence of a policy that induces an irreducible Markov chain on the state space? In this paper, we answer this question in the affirmative.
1.1
Main Contributions
We consider a single-loop, single-timescale actor–critic algorithm in which the actor employs either incremental approximate policy iteration or incremental natural policy gradient updates, while the critic employs off-policy temporal-difference (TD) learning. • Last-Iterate Convergence Rates under Minimal Assumptions: We assume the existence of a policy that induces an irreducible Markov chain over the state trajectory. This policy need not be visited by the algorithm’s trajectory and thus constitutes a purely existential assumption on the underlying MDP. Under this assumption, we show that our single-loop, single-timescale actor–critic algorithm achieves an Õ(ϵ−2 ) sample complexity. To the best of our knowledge, this is the first result attaining near-minimax sample complexity (with respect to ϵ) without relying on a nested-loop implementation, timescale separation, or strong, potentially algorithm-dependent assumptions. • Technical Contributions: The main challenges in the analysis arise from the coupling between the actor and critic updates, due to the single-loop structure of the algorithm, and from the potentially unbounded iterates induced by off-policy learning in the critic. To overcome these challenges, we employ a coupled Lyapunov approach. Specifically, we construct one Lyapunov function for the actor and another for the critic, and establish a negative drift inequality for each while ensuring a cross-domination property. This structure allows the two drift inequalities to be combined to obtain the desired convergence rates. More details are provided in Section 2.3. While this approach is inspired by small-gain theory in the analysis of dynamical systems [26], to the best of our knowledge, the analytical framework we develop is the first to handle Markovian noise, time-varying targets, unbounded iterates, and coupled systems in a unified manner.
2
1.2
Related Literature
Actor–critic methods [29] are policy-space RL algorithms that iteratively perform policy evaluation and policy improvement. Policy evaluation is typically carried out using Monte Carlo methods or TD-learning [55], while policy improvement is performed via variants of policy gradient methods [25, 58] or approximate policy iteration [4]. Asymptotic convergence guarantees for actor–critic methods have been established for decades [7, 29]. Motivated by the need for sample efficiency in modern large-scale applications, recent work has increasingly focused on finite-time and sample-complexity guarantees. Existing non-asymptotic analyses can be broadly divided into two categories: nestedloop implementations, where the actor remains fixed while the critic performs multiple updates, and single-loop implementations, where the actor and critic are updated simultaneously at each iteration. Finite-Time Analysis of Nested-Loop Actor–Critic. For nested-loop actor–critic methods, Õ(ϵ−2 ) sample complexity has been achieved in both tabular and function approximation settings [2, 12, 19, 30, 33, 65, 67]. However, most existing results rely on strong uniform ergodicity assumptions on the policies generated by the algorithm, or simply on all policies [2, 19, 30, 60, 67], with only a few exceptions [12, 24, 36]. Such algorithm-dependent assumptions introduce a form of circularity: verifying them typically depends on properties of the policy sequence itself, which is generated by the algorithm whose convergence analysis relies on these conditions. We do not make such assumptions. Finite-Time Analysis of Single-Loop Actor–Critic. Motivated by empirical successes, we study actor–critic methods with a single-loop implementation. Depending on whether the actor and critic stepsizes are of different orders, such methods may have either a two-timescale structure [28, 62, 64] or a single-timescale structure [10, 15, 42]. Regardless of timescale separation, existing results either lack global convergence guarantees [42, 64], rely on strong assumptions [31, 32], or yield suboptimal sample complexity bounds [28, 31]. Our work establishes near-optimal sample complexity guarantees with respect to ϵ without timescale separation and under substantially weaker assumptions. A detailed comparison is provided in Table 1. Due to the computational limitations of large state-action spaces, popular RL algorithms typically rely on function approximation [56]. While the tabular setting is a special case of function approximation, we emphasize that existing results on actor–critic with function approximation [19, 42, 64, 66] are not applicable in our setting, as they require spectral assumptions on the feature map that do not hold in the tabular case; see, e.g., [64, Assumption 4.1], [42, Assumption 6], and [19, Assumption 4]. These assumptions and their incompatibility with the tabular setting are detailed in Appendix C.1. Off-Policy Learning. Off-policy TD-learning refers to TD-learning where the target policy, whose value function we aim to estimate, differs from the behavior policy used to collect samples [16]. Importance sampling is typically used to correct this discrepancy [17, 40, 45]. Off-policy actor–critic methods have been studied in the literature [11, 12, 27], achieving Õ(ϵ−2 ) sample complexity under nested-loop implementations. In contrast, in our single-loop actor–critic method, the off-policy TD-learning component must track a time-varying target, introducing challenges not addressed in existing off-policy actor–critic analyses. In summary, the existing literature can be broadly divided into two categories: (i) analyses that achieve strong finite-time guarantees but rely on nested-loop implementations, and (ii) single-
3
Table 1: Sample complexity results for single-loop actor–critic algorithms. Õ(ϵ−6 ) Õ(ϵ−2.5 )
Global Convergence ✓ ✗
Last Iterate ✓ ✓
Markovian Sampling ✓ ✓
[42]
O(ϵ−2 )
✗
✗
✗
[18] [31] [32] This work
Õ(ϵ−4 ) O(ϵ−3 ) O(ϵ−2 ) Õ(ϵ−2 )
✓ ✓ ✓ ✓
✗ ✓ ✓ ✓
✗ ✗ ✗ ✓
Work
Complexity
[28] [68]
Single Timescale Ergodicity ✗ Unif. mix. rates ✗ Unif. mix. rates ✗ Exploration Unif. mix. rates ✓ Exploration ✓ Exploration ✓ Irreducibility ✓ Assumptions
Some works in the table study the function approximation setting. Although the tabular setting is a special case of function approximation, their results do not directly transfer to the tabular setting because they impose assumptions (labeled “Exploration” in the table) that are not satisfied in this regime. “Unif. mix. rates” refers to a strong ergodicity assumption requiring the same mixing rate across a class of policies. See Appendix C.1 for details on these assumptions.
loop analyses that typically yield weaker guarantees, such as convergence to stationary points or global convergence with suboptimal rates. Moreover, most existing results rely on restrictive sampling or approximation assumptions. In contrast, we establish near order-optimal last-iterate finite-time guarantees for a single-loop algorithm under substantially weaker assumptions.
1.3
Preliminaries
An infinite-horizon discounted MDP [46] is defined by a tuple (S, A, p, R, γ), where S is the state space of size n, A is the action space of size m, p is the transition probability kernel, R : S × A → [0, 1] is the reward function, and γ ∈ (0, 1) is the discount factor. Given a policy π, its Q-function P∞ t Qπ : S ×A → R is defined as Qπ (s, a) = E t=0 γ R(St , At ) | S0 = s, A0 = a for all (s, a) ∈ S ×A. Note that Qπ can be alternatively viewed as a vector in Rmn . The goal is to learn an optimal policy π ∗ such that its associated Q-function, denoted by Q∗ , is maximized. To solve an MDP, existing methods can be broadly divided into two categories: value-space methods, such as value iteration, and policy-space methods, such as policy iteration, policy gradient [58], and natural policy gradient [25]. When the model parameters, e.g., the transition kernel and the reward function, are unknown, one must develop data-driven methods to learn an optimal policy, which corresponds to model-free RL. In this case, value-space methods translate to Qlearning [63], and policy-space methods translate to the popular actor–critic framework, in which an agent iteratively performs policy evaluation and policy improvement [29].
2
Main Results
This section presents our main results. Specifically, our single-loop actor–critic algorithm and its finite-time analysis are presented in Sections 2.1 and 2.2. The proof of the main theorem is presented in Section 2.3, with the proofs of technical lemmas deferred to the appendix.
4
2.1
Algorithm
Our single-loop, single-timescale off-policy actor–critic method is presented in Algorithm 1, where the actor and critic are updated simultaneously based on a single trajectory of Markovian samples. The actor incrementally updates the policy toward π̃t , which is computed from the current policy πt , the current Q-function estimate Qt , and a temperature parameter τt through a generic update map G(·). This update map can correspond to either approximate policy iteration or natural policy gradient, as discussed shortly. The critic performs off-policy TD-learning. To correct the distribution mismatch between the behavior and target policies, we propose two approaches. The first uses importance sampling (IS), where ρt+1 denotes the importance-sampling ratio. The second directly computes the expected Q-function at the next state St+1 ; we refer to this variant as expected temporal difference (ETD). In both cases, ∆t denotes the temporal-difference error, which is then used in the TD-learning update. We next describe the actor and critic in more detail. Algorithm 1 Single-Loop Off-Policy Actor–Critic 1: Input: Initialization: π0 and Q0 = 0, a single trajectory {(St , At )}t≥0 generated by a behavior policy πb , a sequence {(τt , ωt , αt )} of update parameters, and a choice of critic ∈ {IS, ETD}. 2: for t = 0, 1, 2, . . . do 3: πt+1 = (1 − ωt )πt + ωt π̃t , where π̃t = G(πt , Qt , τt ) ▷ Actor 4: if critic = IS then 5: ρt+1 = πt+1 (At+1 | St+1 )/πb (At+1 | St+1 ) 6: ∆t = R(St , At ) + γρt+1 Qt (St+1 , At+1 ) − Qt (St , At ) 7: else if critic = ETD then P 8: ∆t = R(St , At ) + γ a∈A πt+1 (a | St+1 )Qt (St+1 , a) − Qt (St , At ) 9: end if 10: Update Qt according to (
Qt+1 (s, a) =
Qt (s, a) + αt ∆t ,
if (s, a) = (St , At ),
Qt (s, a),
otherwise.
▷ Critic
11: end for
The Actor for Policy Improvement. In each iteration of Algorithm 1, the agent computes π̃t via the update map G(·) and then updates its policy by taking an incremental step toward π̃t with stepsize ωt . As for the function G, popular choices include natural policy gradient and approximate policy iteration with ϵ-greedy or softmax updates, as presented below. Natural Policy Gradient: Define the function G as π(a|s) exp(Q(s, a)/τ ) , ′ ′ a′ π(a |s) exp(Q(s, a )/τ )
[G(π, Q, τ )](s, a) = P
∀ (s, a).
Note that if the critic estimate is accurate, i.e., Qt = Qπt , the update π̃t = G(πt , Qt , τt ) coincides with the natural policy gradient update [1]. Approximate Policy Iteration with Softmax Update: Define the function G as exp(Q(s, a)/τ ) , ′ a′ exp(Q(s, a )/τ )
[G(π, Q, τ )](s, a) = P
5
∀ (s, a),
which corresponds to a “soft” version of policy iteration. Approximate Policy Iteration with ϵ-Greedy Update: Define the function G as [G(π, Q, τ )](s, a) =
τ /m + 1 − τ,
τ /m,
a = arg max Q(s, a′ ), ′ a ∈A
otherwise,
where the tie-breaking rule can be arbitrary. This is the usual ϵ-greedy update with exploration level ϵ = τ . We use the notation τ only to keep the temperature parameter consistent across the three actor updates. Although ϵ does not appear in the definition, the name ϵ-greedy is retained for consistency with the literature [39]. Note that as the tunable parameter τ approaches zero, all three updates reduce to policy iteration [25], thereby enabling a unified analysis. For ease of terminology, we will uniformly refer to τt in Algorithm 1 as the temperature parameter. The Critic for Policy Evaluation. Our critic update is an off-policy variant of TD-learning [55], motivated by both practical and theoretical considerations. From a practical perspective, in safety-critical applications such as autonomous driving, healthcare, and clinical trials, data collection can be costly and/or high-risk [40, 57]. In such settings, one must rely on historical data collected under a different policy. From a theoretical perspective, off-policy learning facilitates exploration by avoiding algorithm-dependent assumptions, such as requiring all policies encountered along the algorithm trajectory to satisfy uniform exploration properties [10, 28, 64]. While offpolicy learning is both practically and theoretically justified, it introduces a mismatch between the behavior policy πb and the target policy πt+1 . Recall that the goal of the critic is to estimate the Q-function Qπt+1 associated with πt+1 , while samples are generated from πb . To correct this mismatch, we consider two approaches: one based on importance sampling and the other based on directly computing the expectation. Given the current state-action pair (St , At ), the temporal difference ∆t is constructed as a conditionally unbiased estimator of the Bellman error R(St , At ) + γ
X s′ ∈S
|
p(s′ | St , At )
X
πt+1 (a′ | s′ )Qt (s′ , a′ ) −Qt (St , At ).
a′ ∈A
{z
:=E1
}
The key quantity to estimate is E1 . Since St+1 ∼ p(· | St , At ), one can construct an unbiased estimator of E1 using At+1 ∼ πb (· | St+1 ) via importance sampling, which corrects the mismatch between πt+1 and πb [17, 40]. This yields the IS-based approach in Lines 5–6 of Algorithm 1. Alternatively, since πt+1 is known, one can directly compute an unbiased estimator of E1 given St+1 P as a′ ∈A πt+1 (a′ | St+1 )Qt (St+1 , a′ ), resulting in the ETD-based approach in Line 8 of Algorithm 1. Comparing the two approaches, the IS-based method is computationally more efficient, as it avoids explicitly computing expectations over the action space, which can be costly when the action space is large. However, its analysis is more challenging due to nonlinear updates induced by the product of the importance sampling ratio and the Q-function, as well as the possibility of unbounded iterates. In contrast, the ETD-based approach is easier to analyze, as directly computing the expectation avoids the complications introduced by importance sampling. The trade-off is a higher computational cost.
6
2.2
Convergence Rates
We now state the only exploration assumption used in our analysis. Assumption 2.1. There exists a policy π such that the Markov chain {St } induced by π is irreducible. Remark. By choosing the behavior policy to have full support, i.e., πb,min := mins,a πb (a | s) > 0, Assumption 2.1 implies that the Markov chain {St } induced by πb is irreducible. Hence, it admits a unique stationary distribution µb ∈ ∆n (where ∆d denotes the d-dimensional probability simplex) satisfying µb,min := mins∈S µb (s) > 0. A proof of this claim is provided in Appendix C. Moreover, by applying an aperiodicity transformation, also known as the Schweitzer transformation [52], we may assume without loss of generality that the Markov chain {St } induced by πb is aperiodic. Consequently, the chain {St } mixes at a geometric rate [34, Theorem 4.9]: there exists a constant σb ∈ (0, 1) such that maxs∈S dTV Pπtb (s, ·), µb (·) ≤ 2σbt , where Pπb denotes the state transition matrix.1 Assumption 2.1 is purely existential: the policy π need not be known, computed, or visited by the algorithm. Thus, the assumption is independent of the algorithmic trajectory and instead captures an intrinsic explorability property of the underlying MDP. In Appendix C, we show that this condition is also necessary for exploration in the following sense: if it fails, then no algorithm can generate a single sample trajectory that visits every state infinitely often. Therefore, Assumption 2.1 is minimal for state-space exploration. This contrasts sharply with the assumptions commonly imposed in the actor–critic literature, for both nested-loop and single-loop implementations. Existing works often require all policies generated along the algorithm trajectory, or even all policies in the policy class, to induce irreducible and aperiodic Markov chains with uniformly bounded mixing constants, together with some form of uniform exploration [10, 42, 64]. Such conditions are not only stronger than Assumption 2.1, but also algorithm dependent: verifying them requires controlling the very policy sequence whose convergence is being analyzed. By imposing only the existential condition above, we decouple exploration from the algorithm trajectory and avoid this circularity. A detailed comparison with common assumptions is provided in Appendix C.1. For our main result, we consider stepsize sequences {αt , ωt } of the form αt = α/(t + h)η and ωt = ω/(t + h)η , where α, ω, h > 0 and η ∈ [0, 1] are constants. Let Cr = ω/α ∈ (0, 1) denote the ratio between the actor and critic stepsizes. Note that the actor and critic stepsizes are of the same order, reflecting the single-timescale nature of our method. This feature offers numerical stability and simplicity in implementation, making single-timescale actor–critic methods widely popular in practice [21, 38, 44, 50, 51]. Next, we state a condition on the choice of the temperature parameter τt in Algorithm 1. Condition 2.1. Let τ ≥ 0. Depending on the specific actor update rules and the stepsizes {αt , ωt }, the sequence {τt } is chosen such that the following conditions are satisfied. (1) Natural Policy Gradient: τt ≤ τ (t + h)−η/2 / log(1/ mins maxa πt (a|s)). 1
The total variation distance between two probability distributions p1 , p2 on a finite sample space Ω is defined as P dTV (p1 , p2 ) = 12 ω∈Ω |p1 (ω) − p2 (ω)|.
7
(2) Exponential Softmax: τt ≤ τ (t + h)−η/2 / log(m). (3) ϵ-Greedy: τt ≤ τ (t + h)−η/2 /(2γ ∥Qt ∥∞ ). Let zt nbe the mixing time of the Markov chain {Sot } under πb with precision ωt , defined as (s, ·), µb (·) ≤ ωt /2 . When using a constant stepsize ωt ≡ ω, zt := min k ≥ 1 | maxs∈S dTV Pπk−1 b we simply write zω . We also define a related quantity K = Kω,h,η := min{t ∈ N | t ≥ zt }. Due to geometric mixing, this quantity is well defined and finite for our choice of stepsizes. Theorem 2.1. Consider {πt } generated by Algorithm 1. Under Assumption 2.1, define Mcritic :=
mn(1 − γ)−3 π −3 µ−1 , b,min b,min
critic = IS,
(1 − γ)−2 ,
critic = ETD.
(1)
Then there exists a constant threshold C̃r = C̃r (n, m, p, γ, πb ) > 0 such that when using small enough stepsizes, for any Cr ≤ C̃r , and any temperature sequence {τt } satisfying Condition 2.1, the following bounds hold for all T ≥ K, where MSET := E∥Q∗ − QπT ∥2∞ . (1) Under constant stepsizes, i.e., η = 0, we have ω(1 − γ) 3 1− (1 − γ)2 2
MSET ≤
|
T −K
12τ 2 (1 − γ)4
+
{z
}
optimization bias
|
{z
+
}
432Mcritic ωzω . (1 − γ)Cr2 |
temperature error
{z
stochastic error
}
(2) Under harmonic stepsizes, i.e., η = 1, we have
3 MSET ≤ (1 − γ)2
K +h T +h
ω(1−γ) 2
+
′ 8Mcritic,T ω , ω(1−γ) 2 [2 − ω(1 − γ)](T + h) ′
Mcritic,T ω log(T + h)
T +h ′ 8eMcritic,T ω
,
[ω(1 − γ) − 2](T + h)
,
ω<
2 , 1−γ
ω=
2 , 1−γ
ω>
2 , 1−γ
′ where Mcritic,T := 6τ 2 /(1 − γ)3 + 216Mcritic zT ω/Cr2 . (3) Under polynomial stepsizes, i.e., η ∈ (0, 1), we have
h
MSET ≤
1−η − (K + h)1−η 3 exp − ω(1−γ) 2(1−η) (T + h)
(1 − γ)2
i
+
′ 4Mcritic,T
(1 − γ)(T + h)η
.
Recall that Q∗ is the Q-function of an optimal policy, whereas QπT is the Q-function of the last policy iterate πT . Thus, the left-hand side measures the mean-square optimality gap of πT . On the right-hand side, the bounds decompose into three terms (for the diminishing-stepsize cases, ′ after expanding Mcritic,T ): the optimization bias, the error induced by a nonzero temperature, and the stochastic error. For approximate policy iteration with either exponential softmax or ϵ-greedy updates, setting τ = 0 yields the strongest form of the bound. This is possible because exploration is handled by off-policy TD-learning. At the same time, our analysis allows for nonzero τ , which
8
is important in practice, as smoother regularized or trust-region updates, such as NPG and its variants TRPO and PPO, are often preferred for stabilizing policy updates [25, 50, 51]. To obtain the optimal convergence rate in Theorem 2.1, we use harmonic stepsizes with ω > 2/(1 − γ). Other stepsize choices offer different trade-offs. Constant stepsizes yield geometric decay of the bias but leave a nonvanishing stochastic error, while polynomial stepsizes guarantee convergence for any ω, making the choice more robust at the cost of a slower rate. The bounds have the same structure and rates for the IS and ETD updates, but ETD has milder dependence on the problem parameters m, n, (1 − γ)−1 , πb,min , and µb,min (cf. Eq. (1)). This is expected: by directly computing the conditional expectation, ETD avoids the additional stochasticity introduced by importance sampling, although at a higher computational cost. The proof of Theorem 2.1 is presented in Section 2.3. As a direct consequence, we obtain the following sample complexity bound. Corollary 2.2. Given ϵ > 0, to achieve E∥Q∗ − QπT ∥∞ < ϵ, the number of samples required by Algorithm 1 is !
O
m3 n3 log(1/ϵ) 7 5 15 ϵ2 (1 − γ) πb,min µb,min log(1/σb )
!
O
m2 n2 log(1/ϵ) 4 4 14 ϵ2 (1 − γ) πb,min µb,min log(1/σb )
with the IS-based critic, with the ETD-based critic.
To the best of our knowledge, this is the first last-iterate convergence result for a single-loop actor–critic algorithm achieving Õ(ϵ−2 ) sample complexity, which is minimax optimal with respect to ϵ up to logarithmic factors [20]. Notably, we do not impose strong, algorithm-dependent assumptions on the policies generated along the algorithm trajectory. While the dependence on ϵ is near optimal, the dependence on problem-specific constants such as n, m, and (1 − γ)−1 is likely suboptimal. Recall that even for value-based methods such as Q-learning [63], attaining minimax sample complexity with respect to all constants requires more refined techniques, such as variance reduction [61]. Developing analogous algorithmic or technical improvements for single-loop actor–critic methods is an interesting direction for future work.
2.3
Proof of Theorem 2.1
The main challenge in analyzing Algorithm 1 is that, due to its single-loop structure, the actor and critic iterates are coupled, and therefore the analysis cannot be decoupled as in nested-loop actor– critic schemes. Moreover, under off-policy learning with importance sampling, the critic iterates are not uniformly bounded. To address these challenges, we adopt a Lyapunov drift analysis, a standard approach in the study of dynamical systems [8, 26, 54]. Specifically, we construct one Lyapunov function for the actor and another for the critic, establish a drift inequality for each, and then solve the resulting recursions to derive convergence rates. Crucially, because the update equations are coupled, the drift inequalities contain additional error terms that capture this interaction. As a result, establishing an appropriate cross-domination structure is essential for obtaining the desired guarantees. We next outline this approach in more detail. For the actor, we denote the Lyapunov function by Vt , which depends on Q∗ − Qπt and captures the suboptimality gap of the policy πt . For the critic, we denote the Lyapunov function by Wt , 9
which depends on Qt − Qπt and captures the critic estimation error. The explicit forms of these Lyapunov functions will be presented in the next two sections, where we provide the detailed analysis. Our goal is to derive Lyapunov drift inequalities of the form EVt+1 ≤ (1 − κ1 ωt )EVt + D1,t EWt + o(ωt ),
EWt+1 ≤ (1 − κ2 αt )EWt + D2,t EVt + o(αt ),
(2)
where κ1 , κ2 are positive constants, and D1,t , D2,t depend on the stepsizes. These drift inequalities are coupled: Wt appears as an additive error term in the drift inequality for Vt , and vice versa. To solve the recursions, it is essential to ensure, while deriving the separate drift inequalities, that D2,t < κ1 ωt and D1,t < κ2 αt , a condition we call cross-domination. Once this condition holds, we can sum the two Lyapunov drift inequalities to obtain a clean recursion for Vt + Wt , which, upon iteration, yields the convergence of Algorithm 1. This idea is inspired by the small-gain analysis of continuous-time dynamical systems [23]. Related approaches have been used in actor–critic analysis, but only to establish stationary-point convergence [42]. We next follow the above plan and present the details of the analysis. Throughout the rest of this subsection, we assume that the assumptions in Theorem 2.1 hold. 2.3.1
Analysis of the Actor
To present our analysis of the actor, we begin by introducing the Bellman operators. Given a policy π, let Hπ : Rmn → Rmn be the Bellman operator associated with π, defined as [Hπ (Q)](s, a) = R(s, a) + γ
X
p(s′ | s, a)
X
s′
π(a′ |s′ )Q(s′ , a′ ),
∀ (s, a).
a′
Let H : Rmn → Rmn be the Bellman optimality operator defined as [H(Q)](s, a) = R(s, a) + γ
X s′
p(s′ | s, a) max Q(s′ , a′ ), ′ a
∀ (s, a).
We use ∥Q∗ − Qπt ∥∞ as our Lyapunov function for the actor. The following proposition presents its Lyapunov drift inequality. See Appendix A.1 for its proof. Proposition 2.1. The following inequality holds for all t: ∥Q∗ − Qπt+1 ∥∞ ≤ 1 − ωt (1 − γ) ∥Q∗ − Qπt ∥∞ +
|
{z
}
actor drift
2ωt ∥Qt − Qπt ∥∞ + 1−γ |
{z
critic coupling error
}
ωt χt 1−γ
,
(3)
| {z }
temperature error
where χt := ∥HQt − Hπ̃t Qt ∥∞ . In Proposition 2.1, the first term on the right-hand side represents the actor drift and exhibits a contraction structure. To see this, consider the special case where (i) there is no critic evaluation error, i.e., Qt = Qπt , and (ii) we perform a greedy update, i.e., χt = 0 and ωt ≡ 1. In this case, Algorithm 1 reduces to policy iteration, and Proposition 2.1 simplifies to ∥Q∗ − Qπt+1 ∥∞ ≤ γ ∥Q∗ − Qπt ∥∞ , which is consistent with the geometric convergence of policy iteration [46]. The critic evaluation error ∥Qt − Qπt ∥∞ will be analyzed in the next subsection. As for the last term χt , it captures the deviation from a greedy update and vanishes as τt → 0 for all three update 10
rules presented in Section 2.1. For this reason, we refer to the last term as the temperature error. The complete proof of Proposition 2.1 is provided in Appendix A.1. Here, we present a proof sketch highlighting the main ideas. Proof Sketch of Proposition 2.1. We adopt an approximate policy iteration viewpoint of Algorithm 1. Recall that the two key steps in establishing the geometric convergence of policy iteration are: (i) using the monotonicity of the Bellman operators to show monotonic improvement, namely Qπt ≤ Qπt+1 , where the inequalities are interpreted entry-wise, and (ii) using the contraction property of the Bellman operators to show that ∥Q∗ − Qπt+1 ∥∞ ≤ γ ∥Q∗ − Qπt ∥∞ [46]. In our setting, two deviations from exact policy iteration must be accounted for: (i) policy improvement is performed using an estimate Qt rather than the true Qπt , which introduces dependence on the evaluation error ∥Qt − Qπt ∥∞ , and (ii) the policy update is conservative, and the target π̃t is only approximately greedy with respect to Qt , which introduces dependence on the temperature error χt . In this case, we show that monotonic improvement holds up to additive error terms corresponding to these deviations. In particular, let δt := maxs,a Qπt (s, a) − Qπt+1 (s, a) . We show that δt ≤
ωt 2ωt ∥Qt − Qπt ∥∞ + χt . 1−γ 1−γ
Notably, when Qt = Qπt and χt = 0, we recover monotonic improvement, i.e., δt ≤ 0. Using the above bound together with the contraction property of the Bellman operators, we obtain the inequality (3). 2.3.2
Analysis of the Critic
We present the analysis of the critic only for the IS-based critic, as the analysis for the ETD-based critic is similar. The critic update can be viewed as a stochastic approximation scheme that tracks a moving target Qπt [49]. Stochastic approximation with fixed targets has been extensively studied using Lyapunov methods [6, 54]. In particular, off-policy TD-learning with a fixed target policy has been analyzed via weighted ℓ2 -norm Lyapunov functions [13]. Our setting is substantially more challenging due to the coupling with the actor and the resulting time-varying policies. We begin by reformulating the critic update as a stochastic approximation algorithm. For any t ≥ 0, let {Yt } be a stochastic process defined as Yt = (St , At , St+1 , At+1 ). It is clear that {Yt } is a Markov chain with a finite state space, denoted by Y. Moreover, under Assumption 2.1, the Markov chain {Yt } admits a unique stationary distribution, denoted by µY , which satisfies µY (s1 , a1 , s2 , a2 ) = µb (s1 )πb (a1 |s1 )p(s2 |s1 , a1 )πb (a2 |s2 ). Let FIS : Rmn × Y × (∆m )n → Rmn be an operator such that given inputs Q ∈ Rmn , y = (s1 , a1 , s2 , a2 ) ∈ Y and π ∈ (∆m )n , the (s, a)-th component of the output is defined as
π(a2 |s2 ) Q(s2 , a2 ) + 1{(s,a)̸=(s1 ,a1 )} Q(s, a). πb (a2 |s2 )
[FIS (Q, y, π)](s, a) = 1{(s,a)=(s1 ,a1 )} R(s1 , a1 ) + γ
The critic update in Algorithm 1, Line 10, can now be written compactly as
Qt+1 = Qt + αt FIS (Qt , Yt , πt+1 ) − Qt .
11
We further define the operator F̄ : Rmn × (∆m )n → Rmn as F̄ (Q, π) = EY ∼µY [FIS (Q, Y, π)]. It is now clear that the critic update is a Markovian stochastic approximation scheme for tracking the solution to the (time-varying) fixed-point equation F̄ (Q, πt ) = Q. While both F and F̄ depend on πb , since πb is fixed throughout the learning process, we omit this dependence from our notation. Next, we present several key properties of these operators that facilitate the convergence analysis. In particular, we show that the equation F̄ (Q, πt ) = Q admits Qπt as its unique solution, and that F̄ (·, π) is a contractive operator with respect to a weighted ℓ2 norm. For ease of presentation, P P for any nonnegative integers i ≤ j, we use the shorthand αi,j := ju=i αu and ωi,j := ju=i ωu . The proof of the following result is provided in Appendix A.4.2. Lemma 2.1. There exists ν ∈ (∆m )n with νmin := mins,a ν(s, a) ≥ (1 − γ)µb,min πb,min /(nm) such that the following properties hold. (1) F̄ (·, π) is a contraction mapping with respect to ∥ · ∥ν for all π ∈ (∆m )n , with contraction ratio γc := (1 − (1 − γ)µb,min πb,min )1/2 . Moreover, the fixed-point equation F̄ (Q, π) = Q admits a unique solution Qπ . (2) For all y ∈ Y and π ∈ (∆m )n , the operator FIS (·, y, π) satisfies ∥FIS (Q1 , y, π) − FIS (Q2 , y, π)∥ν ≤
1 √
∥Q1 − Q2 ∥ν , πb,min νmin 1 ∥Q1 − Q2 ∥∞ , ∥FIS (Q1 , y, π) − FIS (Q2 , y, π)∥∞ ≤ πb,min for all Q1 , Q2 ∈ Rmn , where ∥ · ∥ν denotes the weighted ℓ2 norm with weights {ν(s, a)}(s,a)∈S×A . (3) For all non-negative integers t1 < t2 , ∥F̄ (Q, πt1 ) − F̄ (Q, πt2 )∥∞ ≤ 2ωt1 ,t2 −1 ∥Q∥∞ for all Q ∈ Rmn . (4) For all non-negative integers t1 < t2 , ∥FIS (Q, y, πt1 ) − FIS (Q, y, πt2 )∥∞ ≤ 2ωt1 ,t2 −1 ∥Q∥∞ /πb,min for all y ∈ Y and Q ∈ Rmn . These properties play distinct roles in the analysis: the contraction of F̄ ensures a negative drift; the Lipschitz continuity of FIS is essential for controlling the stochastic noise; and properties (3) and (4) quantify the errors induced by the time-varying evaluation operators. In light of Lemma 2.1, we define the Lyapunov function for the critic as Wt := ∥Qt − Qπt ∥2ν /2. The following result establishes a one-step drift inequality for the critic; the proof is provided in Appendix A.2. Proposition 2.2. For sufficiently small, non-increasing stepsizes {αt , ωt } satisfying ωt ≤ C̃r αt (where C̃r is introduced in Theorem 2.1 and will be explicitly defined in Appendix A.2), the following holds for all t ≥ K:
EWt+1 ≤ 1 − αt (1 − γc ) EWt + |
{z
critic drift
}
108αt αt−zt ,t−1 ωt (1 − γ) ∗ πt 2 2 + E ∥Q − Q ∥ + Eχ t . ∞ 2 νmin | 2 (1 − γ)2 πb,min {z }
|
{z
stochastic error
}
actor-associated errors
The first two terms on the right-hand side of the previous inequality are standard in the study of TD-learning for policy evaluation [5, 54]; in particular, one provides a negative drift and the other captures the error due to stochasticity. The third term is unique, as it captures the convergence 12
error of the actor, which arises from the coupled nature of our single-loop algorithm. Importantly, the actor-associated error is dominated by the negative drift in the actor Lyapunov inequality (3), which is crucial for establishing the cross-domination property in the next step of the proof. Proof Sketch of Proposition 2.2. Let ⟨·, ·⟩ν denote the inner product defined as ⟨Q1 , Q2 ⟩ν = P s,a Q1 (s, a)Q2 (s, a)ν(s, a). Since the weighted ℓ2 -norm ∥ · ∥ν is induced by this inner product, by the binomial formula, we have Wt+1 = Wt + αt ⟨Qt − Qπt , F̄ (Qt , πt ) − Qt ⟩ν + αt ⟨Qt − Qπt , FIS (Qt , Yt , πt+1 ) − F̄ (Qt , πt )⟩ν |
{z
T1 : expected update term
}
|
{z
T2 : Markovian noise term
}
1 + ⟨Qt − Qπt , Qπt − Qπt+1 ⟩ν + ∥(Qt+1 − Qt ) − (Qπt+1 − Qπt )∥2ν . | {z } |2 {z } T3 : time-varying target term
T4 : residuals
To proceed, we summarize the key steps involved in bounding each term on the right-hand side. Terms T1 and T4 . Using the contraction property of F̄ (·, πt ) established in Lemma 2.1, we show in Appendix A.2 that T1 ≤ −2αt (1 − γc )Wt , making this expected update term the main contributor to the negative drift inequality. The residual term T4 is controlled using the Lipschitz properties of FIS together with standard stepsize arguments. In particular, we have the following lemma. Lemma 2.2. There exist constants C1 , C2 , C3 , C4 such that for all t ≥ 0, we have T4 ≤ C1 αt2 Wt + C2 ωt2 ∥Q∗ − Qπt ∥2∞ + C3 ωt2 χ2t + C4 αt2 . The proof of Lemma 2.2, along with the explicit expressions of the constants, is presented in Appendix A.4.5. Term T2 (Markovian noise). This term captures stochastic fluctuations arising from sampling along a Markovian trajectory. Its control relies on geometric mixing of the state process {St }, which ensures that FIS (Q, Yt , π) concentrates around F̄ (Q, π) after zt steps. Unlike the fixed-policy setting, the arguments of F̄ itself evolve over time due to the changing policy, making this term inherently time-dependent. The conservative actor update plays a key role here in controlling the effect of this time-sensitivity. Following this roadmap, we have the following lemma. Lemma 2.3. There exist constants C5 , C6 such that for all t ≥ K, we have ET2 ≤ C5 αt αt−zt ,t−1 EWt + C6 αt αt−zt ,t−1 . The proof of Lemma 2.3, along with the explicit expressions of the constants, is presented in Appendix A.4.3. Term T3 (Time-varying target). This term arises because, in the single-loop implementation, the critic tracks Qπt rather than a fixed target. We show in Appendix A.4 that ∥Qπt − Qπt+1 ∥∞ ≤
ωt ωt 2 ∥Qt − Qπt ∥∞ + χt + ∥Q∗ − Qπt ∥∞ , 1−γ 1−γ
which states that the impact of the time-varying target, i.e., ∥Qπt − Qπt+1 ∥∞ , can be controlled by
13
terms related to the actor Lyapunov function, the critic Lyapunov function, and the temperature error. In the end, we have the following lemma. Lemma 2.4. There exist constants C7 , C8 such that for all t ≥ 0, we have T3 ≤ C7 ωt Wt +
ωt (1 − γ) ∥Q∗ − Qπt ∥2∞ + C8 ωt χ2t . 4
The proof of Lemma 2.4, along with the explicit expressions of the constants, is presented in Appendix A.4.4. 2.3.3
Cross Domination
Propositions 2.1 and 2.2 establish Lyapunov drift inequalities for the actor and critic, respectively, both of the form in (2). It therefore remains to combine these inequalities and solve the resulting recursion to obtain the convergence rate of Algorithm 1. In particular, combining Propositions 2.1 and 2.2 yields the following lemma, where we denote Vt = ∥Q∗ − Qπt ∥2∞ for simplicity. Lemma 2.5. For sufficiently small, non-increasing stepsizes {αt , ωt } satisfying ωt ≤ C̃r αt , we have for all t ≥ K that
E [Vt+1 + Wt+1 ] ≤ 1 −
108αt αt−zt ,t−1 ωt (1 − γ) 6ωt E [Vt + Wt ] + Eχ2t + . 2 3 2 (1 − γ) (1 − γ)2 πb,min νmin
The proof of Lemma 2.5 follows by squaring both sides of (3), taking expectations, and adding the resulting bound to the critic drift inequality in Proposition 2.2. See Appendix A.3.1 for more details. Proof of Theorem 2.1. Applying Lemma 2.5 recursively, and using the fact that χt ≤ τ /(t+h)η/2 for all t under Condition 2.1 [12, Lemma 5.1], yields the desired convergence rates in Theorem 2.1 for the IS-based critic after substituting the specified stepsizes. The details are provided in Appendix A.3.2. The ETD-based critic satisfies an analogous coupled drift inequality with a smaller stochastic error term; the full proof is provided in Appendix B. The unified statement in Theorem 2.1 uses constants that upper bound those in both the IS and ETD cases.
3
Conclusion
In this work, we establish the first Õ(ϵ−2 ) sample complexity bounds, measured by the optimality gap of the last iterate, for a single-loop actor–critic method under minimal assumptions, without relying on timescale separation between the actor and critic updates. We conclude by outlining several directions for future work. While the dependence on problem parameters such as n, m, and (1 − γ) is not fully optimized, prior work on value-based methods suggests that these dependencies can often be improved via advanced variance-reduction techniques. It would be interesting to investigate whether similar ideas can be extended to policy-space methods. Another natural direction is to extend our analysis to the function approximation setting. However, the interplay of off-policy learning, bootstrapping methods such as TD learning, and
14
function approximation, commonly referred to as the deadly triad, can lead to instability [56]. While this deadly triad challenge can be addressed using gradient TD or TD with gradient correction [59], these TD-learning methods are already two-timescale. After combining them with the actor update, one obtains an iterative algorithm with three sets of coupled iterates. Understanding whether the Lyapunov-based approach developed in this work can address this challenge under minimal assumptions remains an interesting question.
References [1] Agarwal, A., Kakade, S. M., Lee, J. D., and Mahajan, G. (2021). On the theory of policy gradient methods: Optimality, approximation, and distribution shift. Journal of Machine Learning Research, 22(98):1–76. [2] Alacaoglu, A., Viano, L., He, N., and Cevher, V. (2022). A natural actor-critic framework for zero-sum Markov games. In International Conference on Machine Learning, pages 307–366. PMLR. [3] Banach, S. (1922). Sur les opérations dans les ensembles abstraits et leur application aux équations intégrales. Fund. Math, 3(1):133–181. [4] Bertsekas, D. P. (2011). Approximate policy iteration: A survey and some new methods. Journal of Control Theory and Applications, 9(3):310–335. [5] Bhandari, J., Russo, D., and Singal, R. (2018). A finite-time analysis of temporal difference learning with linear function approximation. In Conference On Learning Theory, pages 1691– 1692. [6] Borkar, V. S. (2009). Stochastic Approximation: A Dynamical Systems Viewpoint, volume 48. Springer. [7] Borkar, V. S. and Konda, V. R. (1997). The actor-critic algorithm as multi-time-scale stochastic approximation. Sadhana, 22(4):525–543. [8] Borkar, V. S. and Meyn, S. P. (2000). The ODE method for convergence of stochastic approximation and reinforcement learning. SIAM Journal on Control and Optimization, 38(2):447–469. [9] Chandak, S., Borkar, V. S., and Dodhia, P. (2022). Concentration of contractive stochastic approximation and reinforcement learning. Stochastic Systems, 12(4):411–430. [10] Chen, X. and Zhao, L. (2023). Finite-time analysis of single-timescale actor-critic. Advances in Neural Information Processing Systems, 36:7017–7049. [11] Chen, Z., Khodadadian, S., and Maguluri, S. T. (2022). Finite-sample analysis of off-policy natural actor–critic with linear function approximation. IEEE Control Systems Letters, 6:2611– 2616. [12] Chen, Z. and Maguluri, S. T. (2025). An approximate policy iteration viewpoint of actor–critic algorithms. Automatica, 179:112395. 15
[13] Chen, Z., Maguluri, S. T., Shakkottai, S., and Shanmugam, K. (2021). Finite-sample analysis of off-policy TD-learning via generalized Bellman operators. Advances in Neural Information Processing Systems, 34:21440–21452. [14] Chen, Z., Maguluri, S. T., Shakkottai, S., and Shanmugam, K. (2024). A Lyapunov theory for finite-sample guarantees of Markovian stochastic approximation. Operations Research, 72(4):1352–1367. [15] Chen, Z., Zhang, K., Mazumdar, E., Ozdaglar, A., and Wierman, A. (2023). A finite-sample analysis of payoff-based independent learning in zero-sum stochastic games. In Oh, A., Naumann, T., Globerson, A., Saenko, K., Hardt, M., and Levine, S., editors, Advances in Neural Information Processing Systems, volume 36, pages 75826–75883. Curran Associates, Inc. [16] Degris, T., White, M., and Sutton, R. (2012). Off-policy actor-critic. In International Conference on Machine Learning. [17] Espeholt, L., Soyer, H., Munos, R., Simonyan, K., Mnih, V., Ward, T., Doron, Y., Firoiu, V., Harley, T., Dunning, I. R., Legg, S., and Kavukcuoglu, K. (2018). IMPALA: Scalable distributed deep-RL with importance weighted actor-learner architectures. In International Conference on Machine Learning, pages 1407–1416. [18] Fu, Z., Yang, Z., and Wang, Z. (2021). Single-timescale actor-critic provably finds globally optimal policy. In International Conference on Learning Representations. [19] Ganesh, S., Chen, J., Mondal, W. U., and Aggarwal, V. (2025). Order-optimal global convergence for actor-critic with general policy and neural critic parametrization. In Chiappa, S. and Magliacane, S., editors, Proceedings of the Forty-first Conference on Uncertainty in Artificial Intelligence, volume 286 of Proceedings of Machine Learning Research, pages 1358–1380. PMLR. [20] Gheshlaghi Azar, M., Munos, R., and Kappen, H. J. (2013). Minimax PAC bounds on the sample complexity of reinforcement learning with a generative model. Machine learning, 91(3):325– 349. [21] Haarnoja, T., Zhou, A., Abbeel, P., and Levine, S. (2018). Soft actor-critic: Off-policy maximum entropy deep reinforcement learning with a stochastic actor. In Dy, J. and Krause, A., editors, Proceedings of the 35th International Conference on Machine Learning, volume 80 of Proceedings of Machine Learning Research, pages 1861–1870. PMLR. [22] Haque, S. U. and Maguluri, S. T. (2025). Stochastic approximation with unbounded Markovian noise: A general-purpose theorem. In International Conference on Artificial Intelligence and Statistics, pages 3718–3726. PMLR. [23] Jiang, Z.-P., Teel, A. R., and Praly, L. (1994). Small-gain theorem for ISS systems and applications. Mathematics of Control, Signals and Systems, 7(2):95–120. [24] Ju, C. and Lan, G. (2025). Auto-exploration for online reinforcement learning. Preprint Arxiv:2512.06244.
16
[25] Kakade, S. M. (2001). A natural policy gradient. Advances in Neural Information Processing Systems, 14. [26] Khalil, H. K. and Grizzle, J. W. (2002). Nonlinear Systems, volume 3. Prentice hall Upper Saddle River, NJ. [27] Khodadadian, S., Chen, Z., and Maguluri, S. T. (2021). Finite-sample analysis of off-policy natural actor-critic algorithm. In International Conference on Machine Learning, pages 5420– 5431. PMLR. [28] Khodadadian, S., Doan, T. T., Romberg, J., and Maguluri, S. T. (2022). Finite sample analysis of two-time-scale natural actor-critic algorithm. IEEE Transactions on Automatic Control. [29] Konda, V. and Tsitsiklis, J. (1999). Actor-critic algorithms. Advances in Neural Information Processing Systems, 12. [30] Kumar, H., Koppel, A., and Ribeiro, A. (2023). On the sample complexity of actor-critic method for reinforcement learning with function approximation. Machine Learning, pages 1–35. [31] Kumar, N., Agrawal, P., Ramponi, G., Levy, K. Y., and Mannor, S. (2026a). On the convergence of single-timescale actor-critic. In The Thirty-ninth Annual Conference on Neural Information Processing Systems. [32] Kumar, N., Dahan, T., Cohen, L., Barua, A., Ramponi, G., Levy, K. Y., and Mannor, S. (2026b). Optimal sample complexity for single time-scale actor-critic with momentum. arXiv preprint: 2602.01505. [33] Lan, G. (2022). Policy mirror descent for reinforcement learning: Linear convergence, new sampling complexity, and generalized problem classes. Mathematical Programming, pages 1–48. [34] Levin, D. A. and Peres, Y. (2017). Markov Chains and Mixing Times, volume 107. American Mathematical Soc. [35] Li, G., Wei, Y., Chi, Y., Gu, Y., and Chen, Y. (2020). Sample complexity of asynchronous Qlearning: sharper analysis and variance reduction. In Advances in Neural Information Processing Systems, volume 33, pages 7031–7043. Curran Associates, Inc. [36] Li, Y. and Lan, G. (2025). Policy mirror descent inherently explores action space. SIAM Journal on Optimization, 35(1):116–156. [37] Lillicrap, T., Hunt, J., Pritzel, A., Heess, N., Erez, T., Tassa, Y., Silver, D., and Wierstra, D. (2015). Continuous control with deep reinforcement learning. CoRR. [38] Mnih, V., Badia, A. P., Mirza, M., Graves, A., Lillicrap, T., Harley, T., Silver, D., and Kavukcuoglu, K. (2016). Asynchronous methods for deep reinforcement learning. In International Conference on Machine Learning, pages 1928–1937. [39] Mnih, V., Kavukcuoglu, K., Silver, D., Rusu, A. A., Veness, J., Bellemare, M. G., Graves, A., Riedmiller, M., Fidjeland, A. K., Ostrovski, G., Petersen, S., Beattie, C., Sadik, A., Antonoglou,
17
I., King, H., Kumaran, D., Wierstra, D., Legg, S., and Hassabis, D. (2015). Human-level control through deep reinforcement learning. Nature, 518(7540):529–533. [40] Munos, R., Stepleton, T., Harutyunyan, A., and Bellemare, M. G. (2016). Safe and efficient off-policy reinforcement learning. In Proceedings of the 30th International Conference on Neural Information Processing Systems, pages 1054–1062. [41] Nanda, P. and Chen, Z. (2025). A minimal-assumption analysis of Q-learning with time-varying policies. Preprint Arxiv:2510.16132. [42] Olshevsky, A. and Gharesifard, B. (2023). A small gain analysis of single timescale actor critic. SIAM Journal on Control and Optimization, 61(2):980–1007. [43] Ouyang, L., Wu, J., Jiang, X., Almeida, D., Wainwright, C. L., Mishkin, P., Zhang, C., Agarwal, S., Slama, K., Ray, A., Schulman, J., Hilton, J., Kelton, F., Miller, L., Simens, M., Askell, A., Welinder, P., Christiano, P., Leike, J., and Lowe, R. (2022). Training language models to follow instructions with human feedback. In Proceedings of the 36th International Conference on Neural Information Processing Systems, NIPS ’22, Red Hook, NY, USA. Curran Associates Inc. [44] Peters, J. and Schaal, S. (2008). Natural actor-critic. Neurocomputing, 71(7-9):1180–1190. [45] Precup, D., Sutton, R. S., and Dasgupta, S. (2001). Off-policy temporal difference learning with function approximation. In Proceedings of the Eighteenth International Conference on Machine Learning, ICML ’01, page 417–424, San Francisco, CA, USA. Morgan Kaufmann Publishers Inc. [46] Puterman, M. L. (2014). Markov Decision Processes: Discrete Stochastic Dynamic Programming. John Wiley & Sons. [47] Qiu, S., Yang, Z., Ye, J., and Wang, Z. (2021). On finite-time convergence of actor-critic algorithm. IEEE Journal on Selected Areas in Information Theory, 2(2):652–664. [48] Qu, G. and Wierman, A. (2020). Finite-time analysis of asynchronous stochastic approximation and Q-learning. In Conference on Learning Theory, pages 3185–3205. PMLR. [49] Robbins, H. and Monro, S. (1951). A stochastic approximation method. The Annals of Mathematical Statistics, pages 400–407. [50] Schulman, J., Levine, S., Abbeel, P., Jordan, M., and Moritz, P. (2015). Trust region policy optimization. In International Conference on Machine Learning, pages 1889–1897. PMLR. [51] Schulman, J., Wolski, F., Dhariwal, P., Radford, A., and Klimov, O. (2017). Proximal policy optimization algorithms. [52] Schweitzer, P. J. (1971). Iterative solution of the functional equations of undiscounted Markov renewal programming. Journal of Mathematical Analysis and Applications, 34(3):495–501. [53] Silver, D., Schrittwieser, J., Simonyan, K., Antonoglou, I., Huang, A., Guez, A., Hubert, T., Baker, L., Lai, M., Bolton, A., Chen, Y., Lillicrap, T., Hui, F., Sifre, L., van den Driessche, G.,
18
Graepel, T., and Hassabis, D. (2017). Mastering the game of Go without human knowledge. Nature, 550(7676):354. [54] Srikant, R. and Ying, L. (2019). Finite-time error bounds for linear stochastic approximation and TD-learning. In Conference on Learning Theory, pages 2803–2830. [55] Sutton, R. S. (1988). Learning to predict by the methods of temporal differences. Machine Learning, 3(1):9–44. [56] Sutton, R. S. and Barto, A. G. (2018). Reinforcement Learning: An Introduction. MIT press. [57] Sutton, R. S., Mahmood, A. R., and White, M. (2016). An emphatic approach to the problem of off-policy temporal-difference learning. The Journal of Machine Learning Research, 17(1):2603– 2631. [58] Sutton, R. S., McAllester, D., Singh, S., and Mansour, Y. (1999). Policy gradient methods for reinforcement learning with function approximation. In Proceedings of the 12th International Conference on Neural Information Processing Systems, pages 1057–1063. [59] Sutton, R. S., Szepesvári, C., and Maei, H. R. (2008). A convergent O(n) algorithm for off-policy temporal-difference learning with linear function approximation. Advances in Neural Information Processing Systems, 21(21):1609–1616. [60] Tian, H., Olshevsky, A., and Paschalidis, Y. (2023). Convergence of actor-critic with multilayer neural networks. In Oh, A., Naumann, T., Globerson, A., Saenko, K., Hardt, M., and Levine, S., editors, Advances in Neural Information Processing Systems, volume 36, pages 9279– 9321. Curran Associates, Inc. [61] Wainwright, M. J. (2019). Variance-reduced Q-learning is minimax optimal. arXiv e-prints, page arXiv:1906.04697. [62] Wang, Y., Wang, Y., Zhou, Y., and Zou, S. (2024). Non-asymptotic analysis for single-loop (Natural) actor-critic with compatible function approximation. In Salakhutdinov, R., Kolter, Z., Heller, K., Weller, A., Oliver, N., Scarlett, J., and Berkenkamp, F., editors, Proceedings of the 41st International Conference on Machine Learning, volume 235 of Proceedings of Machine Learning Research, pages 51771–51824. PMLR. [63] Watkins, C. J. and Dayan, P. (1992). Q-learning. Machine learning, 8(3-4):279–292. [64] Wu, Y. F., Zhang, W., Xu, P., and Gu, Q. (2020). A finite-time analysis of two time-scale actor-critic methods. Advances in Neural Information Processing Systems, 33:17617–17628. [65] Xiao, L. (2022). On the convergence rates of policy gradient methods. Journal of Machine Learning Research, 23(282):1–36. [66] Xu, T. and Liang, Y. (2021). Sample complexity bounds for two timescale value-based reinforcement learning algorithms. In International Conference on Artificial Intelligence and Statistics, pages 811–819. PMLR.
19
[67] Xu, T., Wang, Z., and Liang, Y. (2020a). Improving sample complexity bounds for (natural) actor-critic algorithms. Advances in Neural Information Processing Systems, 33. [68] Xu, T., Wang, Z., and Liang, Y. (2020b). Non-asymptotic convergence analysis of two timescale (natural) actor-critic algorithms. arXiv eprint: 2005.03557.
20
A
Proof of Theorem 2.1 with the IS-Based Critic
A.1
Analysis of the Actor
A.1.1
Proof of Proposition 2.1
The following lemma is needed, whose proof is presented in Appendix A.4.1. Lemma A.1. For any π1 , π2 and α ∈ R, let π = (1 − α)π1 + απ2 . Then, for any Q ∈ Rmn , we have Hπ Q = (1 − α)Hπ1 Q + αHπ2 Q. As illustrated in Section 2.3.1, our proof of Proposition 2.1 consists of two main steps. We first show that the policies generated by Algorithm 1 are approximately monotonic. Then, we leverage the approximate monotonicity property together with the contraction property of the Bellman operator to establish the one-step recursive inequality of ∥Q∗ − Qπt ∥∞ . We recall the following notation: δt = maxs,a Qπt (s, a) − Qπt+1 (s, a) and χt = ∥HQt − Hπ̃t Qt ∥∞ , and additionally define ξt := ∥Qt − Qπt ∥∞ . Throughout this proof and all upcoming appendices, inequalities between vectors are interpreted entry-wise. Step 1: Approximate monotonic improvement. Observe that by the definition of δt , we have Qπt+1 ≥ Qπt − δt 1. Using the Bellman equation, together with the monotonicity and translation invariance of the Bellman operator, we have Qπt+1 = Hπt+1 Qπt+1 ≥ Hπt+1 (Qπt − δt 1) = Hπt+1 Qπt − γδt 1 = (1 − ωt )Hπt Qπt + ωt Hπ̃t Qπt − γδt 1
(Lemma A.1)
= (1 − ωt )Qπt + ωt Hπ̃t Qπt − γδt 1.
(4)
Rearranging terms, we obtain Qπt − Qπt+1 ≤ ωt Qπt − Hπ̃t Qπt + γδt 1 ≤ ωt (HQπt − Hπ̃t Qπt ) + γδt 1,
where the last inequality follows from HQπt ≥ Hπt Qπt = Qπt . To proceed, observe that HQπt − Hπ̃t Qπt = HQπt − HQt + HQt − Hπ̃t Qt + Hπ̃t Qt − Hπ̃t Qπt ≤ ∥HQπt − HQt ∥∞ 1 + ∥HQt − Hπ̃t Qt ∥∞ 1 + ∥Hπ̃t Qt − Hπ̃t Qπt ∥∞ 1 ≤ 2γξt 1 + χt 1, where the last inequality follows from the contraction property of the operators H and Hπ̃t and the definitions of ξt and χt . Combining the previous two inequalities, we have Qπt − Qπt+1 ≤ ωt (2γξt 1 + χt 1) + γδt 1.
21
Since the right-hand side is a constant vector, we must have δt = max(Qπt (s, a) − Qπt+1 (s, a)) ≤ ωt (2γξt + χt ) + γδt . s,a
Rearranging terms, we obtain δt ≤ Step 2: A contractive recursion.
ωt (2γξt + χt ) . 1−γ
(5)
For any t ≥ 0, we have by Inequality (4) that
Q∗ − Qπt+1 ≤ (1 − ωt )(Q∗ − Qπt ) + ωt (Q∗ − Hπ̃t Qπt ) + γδt 1. To control the term Q∗ − Hπ̃t Qπt , note that Q∗ − Hπ̃t Qπt = HQ∗ − HQπt + HQπt − Hπ̃t Qπt ≤ γ ∥Q∗ − Qπt ∥∞ 1 + (2γξt + χt )1, where the last inequality follows from the contraction property of H and the previous bound on HQπt − Hπ̃t Qπt . Therefore, we have Q∗ − Qπt+1 ≤ (1 − ωt )(Q∗ − Qπt ) + ωt γ ∥Q∗ − Qπt ∥∞ + 2γξt + χt 1 + γδt 1
≤ (1 − ωt )∥Q∗ − Qπt ∥∞ 1 + ωt γ ∥Q∗ − Qπt ∥∞ + 2γξt + χt 1 + γδt 1
= (1 − (1 − γ)ωt )∥Q∗ − Qπt ∥∞ 1 + ωt 2γξt + χt 1 + γδt 1.
Since Q∗ − Qπt+1 ≥ 0 and the right-hand side of the previous inequality is a constant vector, we have ∥Q∗ − Qπt+1 ∥∞ ≤ 1 − ωt (1 − γ) ∥Q∗ − Qπt ∥∞ + ωt (2γξt + χt ) + γδt 2ωt ωt ≤ 1 − ωt (1 − γ) ∥Q∗ − Qπt ∥∞ + ξt + χt , 1−γ 1−γ
where the last inequality follows from the upper bound of δt in Inequality (5). A.1.2
Establishing the Drift Inequality for the Squared Norm Error
The following corollary follows from Proposition 2.1, which is needed to combine the actor drift with the critic drift. Corollary A.1. The following inequality holds for any t ≥ 0: ∥Q∗ − Qπt+1 ∥2∞ ≤ 1 − ωt (1 − γ) ∥Q∗ − Qπt ∥2∞ +
6ωt 5ωt ∥Qt − Qπt ∥2∞ + χ2 . 3 (1 − γ) (1 − γ)3 t
Proof of Corollary A.1. Recall the notation Vt = ∥Q∗ − Qπt ∥2∞ . Then, Proposition 2.1 implies
Vt+1 ≤
1 − ωt (1 − γ) ∥Q∗ − Qπt ∥∞ +
2 2ωt ωt ξt + χt 1−γ 1−γ
22
4ωt2 ωt2 2 ξ + χ2 t (1 − γ)2 (1 − γ)2 t 2ωt 1 − ωt (1 − γ) 4ωt 1 − ωt (1 − γ) ∗ πt ∥Q − Q ∥∞ ξt + ∥Q∗ − Qπt ∥∞ χt + 1−γ 1−γ 4ωt2 + ξ t χt . (1 − γ)2 2
= 1 − ωt (1 − γ) Vt +
(6)
We now control the cross terms using the AM–GM inequality: (1 − γ)2 3 ξ2, Vt + 6 2(1 − γ)2 t (1 − γ)2 3 ∥Q∗ − Qπt ∥∞ χt ≤ Vt + χ2 , 6 2(1 − γ)2 t 1 ξt χt ≤ ξt2 + χ2t . 4 ∥Q∗ − Qπt ∥∞ ξt ≤
Substituting these bounds into (6) yields 2
Vt+1 ≤ 1 − ωt (1 − γ) Vt +
=
h
ωt2 4ωt2 2 ξ + χ2 t (1 − γ)2 (1 − γ)2 t !
4ωt 1 − ωt (1 − γ) + 1−γ
(1 − γ)2 3 Vt + ξ2 6 2(1 − γ)2 t
2ωt 1 − ωt (1 − γ) + 1−γ
(1 − γ)2 3 4ωt2 2 Vt + χ + 6 2(1 − γ)2 t (1 − γ)2
1 − ωt (1 − γ)
2
!
1 2 ξ + χ2t 4 t
i
+ 1 − ωt (1 − γ) ωt (1 − γ) Vt
"
#
"
#
6ωt 1 − ωt (1 − γ) ωt2 4ωt2 ξ2 + + + (1 − γ)2 (1 − γ)3 (1 − γ)2 t 3ωt 1 − ωt (1 − γ) 4ωt2 ωt2 + + χ2 . + (1 − γ)2 (1 − γ)3 (1 − γ)2 t By straightforward algebraic manipulations, the coefficients of Vt , ξt2 , and χ2t can be simplified as 1 − ωt (1 − γ)
2
+ 1 − ωt (1 − γ) ωt (1 − γ) = 1 − ωt (1 − γ),
6ωt 1 − ωt (1 − γ) 4ωt2 ωt2 6ωt − ωt2 (1 − γ) 6ωt + + = ≤ , (1 − γ)2 (1 − γ)3 (1 − γ)2 (1 − γ)3 (1 − γ)3 3ωt 1 − ωt (1 − γ) ωt2 4ωt2 3ωt + 2ωt2 (1 − γ) 5ωt + + = ≤ . 2 3 2 (1 − γ) (1 − γ) (1 − γ) (1 − γ)3 (1 − γ)3 Therefore, we have
Vt+1 ≤ 1 − ωt (1 − γ) Vt +
23
6ωt 5ωt ξ2 + χ2 . (1 − γ)3 t (1 − γ)3 t
A.2
Analysis of the Critic
We first state the complete version of Proposition 2.2, with explicit expressions for all constants. Recall that zt = min{k ≥ 1 | maxs∈S dTV Pπk−1 (s, ·), µb (·) ≤ ωt /2} and K = min{t ∈ N | t ≥ zt }. b Proposition A.1. Under Assumption 2.1, suppose that the stepsizes are non-increasing and satisfy (1 − γ)3 (1 − γc )νmin ωt ≤ αt , 20
αt−zt ,t−1 ≤
2 πb,min νmin (1 − γc )
200
.
Then, the following inequality holds for any t ≥ K:
EWt+1 ≤ 1 − αt (1 − γc ) EWt +
108αt αt−zt ,t−1 1−γ 1−γ ωt E ∥Q∗ − Qπt ∥2∞ + ωt Eχ2t + . 2 2 2 (1 − γ)2 πb,min νmin
Proof of Proposition A.1. We have, by the binomial decomposition, that Wt+1 =Wt + ⟨Qt − Qπt , Qt+1 − Qt ⟩ν + ⟨Qt − Qπt , Qπt − Qπt+1 ⟩ν 1 + ∥(Qt+1 − Qt ) + (Qπt − Qπt+1 )∥2ν 2 =Wt + αt ⟨Qt − Qπt , FIS (Qt , Yt , πt+1 ) − Qt ⟩ν + ⟨Qt − Qπt , Qπt − Qπt+1 ⟩ν 1 + ∥(Qt+1 − Qt ) + (Qπt − Qπt+1 )∥2ν 2 =Wt + αt ⟨Qt − Qπt , F̄ (Qt , πt ) − Qt ⟩ν + αt ⟨Qt − Qπt , FIS (Qt , Yt , πt+1 ) − F̄ (Qt , πt )⟩ν |
{z
T1 : expected update term
}
|
{z
T2 : Markovian noise term
1 + ⟨Qt − Qπt , Qπt − Qπt+1 ⟩ν + ∥(Qt+1 − Qt ) + (Qπt − Qπt+1 )∥2ν . {z } |2 | {z } T3 : time-varying Target Term
}
(7)
T4 : residuals
We now bound the terms T1 , T2 , T3 and T4 . For the term T1 , we have, by the fact that Qπt is the fixed point of F̄ (·, πt ), that T1 = αt ⟨Qt − Qπt , F̄ (Qt , πt ) − Qt ⟩ν = αt ⟨Qt − Qπt , F̄ (Qt , πt ) − F̄ (Qπt , πt )⟩ν − αt ∥Qπt − Qt ∥2ν ≤ αt ∥Qt − Qπt ∥ν ∥F̄ (Qt , πt ) − F̄ (Qπt , πt )∥ν − αt ∥Qπt − Qt ∥2ν ≤ − αt (1 − γc )∥Qπt − Qt ∥2ν = − 2αt (1 − γc )Wt .
(8)
For the terms T2 , T3 , and T4 , they are bounded in the following sequence of lemmas, whose proofs are presented in Appendix A.4.3, Appendix A.4.4, and Appendix A.4.5 respectively. Lemma A.2. The following inequality holds for all t ≥ K: ET2 ≤
100αt αt−zt ,t−1 90αt αt−zt ,t−1 Wt + . 2 2 πb,min νmin (1 − γ)2 πb,min νmin
24
Lemma A.3. The following inequality holds for all t ≥ 0: T3 ≤
1−γ 8ωt 1−γ Wt + ωt ∥Q∗ − Qπt ∥2∞ + ωt χ2t . √ (1 − γ)3 νmin 4 4
Lemma A.4. The following inequality holds for all t ≥ 0: 24ωt2 9αt2 + T4 ≤ 2 πb,min νmin (1 − γ)2 νmin
!
Wt +
3ωt2 χ2t 8αt2 3ωt2 ∗ πt 2 ∥Q − Q ∥ + + . ∞ 2 (1 − γ)2 (1 − γ)2 (1 − γ)2 πb,min
Taking the expectation of both sides in (7) and substituting the bounds on T1 , ET2 , T3 , and T4 , we have 90αt αt−zt ,t−1 100αt αt−zt ,t−1 EWt + 2 2 πb,min (1 − γ)2 πb,min νmin νmin 1−γ 1−γ 8ωt EWt + ωt E ∥Q∗ − Qπt ∥2∞ + ωt Eχ2t + √ 3 (1 − γ) νmin 4 4
EWt+1 ≤EWt − 2αt (1 − γc )EWt +
9αt2 24ωt2 + 2 πb,min νmin (1 − γ)2 νmin
+ +
!
EWt +
3ωt2 3ωt2 E ∥Q∗ − Qπt ∥2∞ + Eχ2 2 (1 − γ) (1 − γ)2 t
8αt2 2 (1 − γ)2 πb,min
90αt αt−zt ,t−1 9αt2 24ωt2 8ωt = 1 − 2αt (1 − γc ) + + + + √ 2 2 πb,min νmin πb,min νmin (1 − γ)2 νmin (1 − γ)3 νmin + +
1−γ 3ωt2 ωt + 4 (1 − γ)2
! ∗
E ∥Q
− Qπt ∥2∞ +
1−γ 3ωt2 ωt + 4 (1 − γ)2
!
EWt
!
Eχ2t
100αt αt−zt ,t−1 8αt2 + . 2 2 (1 − γ)2 πb,min νmin (1 − γ)2 πb,min
The αt2 terms can be absorbed into the αt αt−zt ,t−1 contribution since αt ≤ αt−zt ,t−1 . Similarly the √ ωt2 terms can be absorbed into the ωt contribution as ωt ≤ (1 − γ)3 (1 − γc )νmin αt /20 ≤ νmin /12. Thus, we have !
100αt αt−zt ,t−1 10ωt 1 − 2αt (1 − γc ) + + EWt √ 2 (1 − γ)3 νmin πb,min νmin
EWt+1 ≤ +
108αt αt−zt ,t−1 ωt (1 − γ) ωt (1 − γ) 2 E∥Q∗ − Qπt ∥2∞ + Eχt + . 2 2 2 (1 − γ)2 πb,min νmin
Bounding the perturbation terms in the contraction factor (coefficient of EWt ) using the stepsize 2 conditions αt−zt ,t−1 ≤ πb,min νmin (1 − γc )/200 and ωt ≤ (1 − γ)3 (1 − γc )νmin αt /20, we obtain the result.
25
A.3
Combining the Actor and Critic
A.3.1
Proof of Lemma 2.5
We begin by stating the complete result with the exact stepsizes and constants. Lemma A.5. Under the same conditions as Proposition A.1, the following inequality holds for all t ≥ K: ωt (1 − γ) 6ωt E[∥Q∗ − Qπt ∥2∞ + Wt ] + Eχ2 2 (1 − γ)3 t 108αt αt−zt ,t−1 + . 2 (1 − γ)2 πb,min νmin
E[∥Q∗ − Qπt+1 ∥2∞ + Wt+1 ] ≤ 1 −
Proof of Lemma A.5. We add the critic drift (Proposition A.1) to the squared actor drift inequality from Corollary A.1 (after taking expectation) to obtain: E[∥Q∗ − Qπt+1 ∥2∞ + Wt+1 ] 6ωt 5ωt E∥Qt − Qπt ∥2∞ + Eχ2 3 (1 − γ) (1 − γ)3 t 108αt αt−zt ,t−1 ωt (1 − γ) 2 ωt (1 − γ) E∥Q∗ − Qπt ∥2∞ + Eχt + + 1 − αt (1 − γc ) EWt + 2 2 2 (1 − γ)2 πb,min νmin
≤ 1 − ωt (1 − γ) E∥Q∗ − Qπt ∥2∞ +
ωt (1 − γ) 6ωt ≤ 1− E ∥Q∗ − Qπt ∥2∞ + Eχ2 2 (1 − γ)3 t 108αt αt−zt ,t−1 12ωt EWt + + 1 − αt (1 − γc ) + 2 3 (1 − γ) νmin (1 − γ)2 πb,min νmin
2αt (1 − γc ) ωt (1 − γ) E ∥Q∗ − Qπt ∥2∞ + 1 − EWt (ωt ≤ (1 − γ)3 (1 − γc )νmin αt /20) 2 5 108αt αt−zt ,t−1 6ωt + Eχ2t + . 2 3 (1 − γ) (1 − γ)2 πb,min νmin
≤ 1−
Due to the stepsize condition ωt ≤ (1 − γ)3 (1 − γc )νmin αt /20, the coefficient of E ∥Q∗ − Qπt ∥2∞ in the above is larger than that of EWt . Using the same (1 − ωt (1 − γ)/2) as the common coefficient for both EWt and E ∥Q∗ − Qπt ∥2∞ gives the result. A.3.2
Solving the Recursion
The following lemma will be useful. Recall that K = min{k ∈ N | k ≥ zk }. √ Lemma A.6. For any stepsize sequence satisfying α0,K−1 ≤ πb,min νmin /4, the following inequality holds almost surely: ∥Q∗ − QπK ∥2∞ + WK ≤
3 . (1 − γ)2
√ Remark. The condition α0,K−1 ≤ πb,min νmin /4 holds when the stepsize condition αt−zt ,t−1 ≤ 2 πb,min νmin (1 − γc )/200 appearing in Theorem 2.1 for the IS-based critic, holds; by substituting t = K, for large enough h. 26
√ Proof of Lemma A.6. Under the condition α0,K−1 ≤ πb,min νmin /4, it is a direct consequence of [14, Lemma A.2], that the following holds almost surely: ∥QK − Q0 ∥∞ ≤
2α0,K−1 ∥Q0 ∥∞ + 2α0,K−1 = 2α0,K−1 ≤ 1. πb,min
(Q0 = 0)
It hence follows that 1 1 + ∥QK − QπK ∥2ν 2 (1 − γ) 2 1 ≤ + ∥QK ∥2ν + ∥QπK ∥2ν (1 − γ)2 2 + ∥QK − Q0 ∥2ν ≤ (1 − γ)2 3 ≤ . (1 − γ)2
∥Q∗ − QπK ∥2∞ + WK ≤
(Q0 = 0)
To prove Theorem 2.1 for the IS-based critic, we first verify the conditions of Lemma A.5. We begin by noting that, due to geometric mixing, zt ≤ log(4/ωt )/ log(1/σb ) + 1 is at most logarithmic in t for any of the stepsize sequences considered. It follows that αt−zt ,t−1 ≤ αzt /(t + h − zt )η is 2 uniformly bounded over all t ∈ N. Therefore, the condition αt−zt ,t−1 ≤ πb,min νmin (1 − γc )/200 can be ensured by choosing α small enough for constant stepsizes, and by choosing h large enough for diminishing stepsizes with η ∈ (0, 1]. We now prove the existence of the constant threshold C̃r . By choosing α and ω such that Cr ≤ C̃r :=
(1 − γ)3 (1 − γc )νmin , 20
the stepsize condition ωt ≤ (1 − γ)3 (1 − γc )νmin αt /20 is satisfied for any of the stepsize sequences considered in Theorem 2.1. Thus, the stepsize conditions of Lemma A.5, the coupled drift lemma, hold for all t. Moreover, since νmin ≥ (1 − γ)πb,min µb,min /(mn) (cf. Lemma 2.1), the threshold C̃r is a constant depending only on (n, m, p, γ, πb ), as claimed in Theorem 2.1. We now simplify the coupled drift from Lemma B.5. It follows directly from [12, Lemma 5.1] p that under Condition 2.1 with parameter τ ≥ 0, we have that χt ≤ τ /(t + h)η/2 = τ ωt /ω for all t. Now note that for constant stepsizes, αt−zt ,t−1 = αzt ≤ 2αt zt . For diminishing stepsizes, let h be large enough so that zt ≤ (t + h)/2 for all t ≥ K (possible since zt is logarithmic in t). This implies that αt−zt ,t−1 ≤
αzt αzt ≤ η ≤ 2αt zt . η (t − zt + h) (t + h)/2
The coupled drift from Lemma A.5 hence reduces to h
i
E ∥Q∗ − Qπt+1 ∥2∞ + Wt+1 ≤ 1 −
i h ωt (1 − γ) E ∥Q∗ − Qπt ∥2∞ + Wt 2
27
+
6τ 2 ωt2 216mnαt2 zt + , 3 (1 − γ)3 ω (1 − γ)3 πb,min µb,min
for all t ≥ K. Applying the above recursively yields the following for all T ≥ K: h
∗
E ∥Q
− QπT ∥2∞ + WT
i
h
∗
≤ E ∥Q
− QπK ∥2∞ + WK
−1 i TY t=K
+
6τ 2
TX −1
(1 − γ)3 ω t=K
ωt2
TY −1 u=t+1
ωt (1 − γ) 1− 2
ωu (1 − γ) 1− 2
TX −1 TY −1 ωu (1 − γ) 216mn 2 α z 1− . + t t 3 3 2 (1 − γ) πb,min µb,min t=K u=t+1
Define Πi,j := follows that
Qj
u=i
1 − ωu (1 − γ)/2 . From Lemma A.6 and the fact that zt ≤ zT for all t ≤ T , it
i
h
E ∥Q∗ − QπT ∥2∞ + WT ≤
TX −1 3ΠK,T −1 216mnzT α2 Πt+1,T −1 + 3 (1 − γ)2 (1 − γ)3 πb,min µb,min t=K t
+
TX −1 6τ 2 ω 2 Πt+1,T −1 . (1 − γ)3 ω t=K t
−3 µ−1 Note that ωt = Cr αt and recall the notation MIS = mn(1 − γ)−3 πb,min b,min . Substituting this into the above gives
h
∗
E ∥Q
− QπT ∥2∞ + WT
i
6τ 2 216MIS zT + (1 − γ)3 ω Cr2
3ΠK,T −1 ≤ ET := + (1 − γ)2
! T −1 X
ωt2 Πt+1,T −1 .
(9)
t=K
The remainder of the proof follows by bounding the term ET for the specific stepsize sequences. (1) Constant stepsizes.
When αt = α and ωt = ω for all t, we have
3 ω(1 − γ) ET ≤ 1− 2 (1 − γ) 2
T −K
ω(1 − γ) 3 1− 2 (1 − γ) 2
T −K
≤
+ +
6τ 2 216MIS zω + 3 (1 − γ) ω Cr2 12τ 2 (1 − γ)4
+
where the last step follows from the geometric sum stituting the above into (9) proves Theorem 2.1 (1). (2) Harmonic stepsizes. have ET ≤
3 (1 − γ)2
! T −1 X
ω2 1 −
t=K
ω(1 − γ) 2
T −1−t
432MIS ωzω , (1 − γ)Cr2 P∞
t=0
1 − ω(1 − γ)/2
t
= 2/ ω(1 − γ) . Sub-
When αt = α/(t + h) and ωt = ω/(t + h), by [14, Lemma A.7], we
K +h T +h
ω(1−γ)/2
28
+
6τ 2 216MIS zT + (1 − γ)3 ω Cr2
!
×
8ω 2 , 2 − ω(1 − γ) (T + h)ω(1−γ)/2 2
ω<
ω log(T + h) , T +h 8eω 2 , ω(1 − γ) − 2 (T + h)
2 , 1−γ
2 , 1−γ 2 ω> . 1−γ ω=
Substituting the above into (9) proves Theorem 2.1 (2). (3) Polynomial stepsizes. Lemma A.8], we have
When αt = α/(t + h)η and ωt = ω/(t + h)η for η ∈ (0, 1), by [14,
ω(1 − γ) 3 1−η 1−η exp − (T + h) − (K + h) ET ≤ (1 − γ)2 2(1 − η)
+
6τ 2 216MIS zT + 3 (1 − γ) ω Cr2
!
8ω . (T + h)η
Substituting the above into (9) proves Theorem 2.1 (3). A.3.3
Proof of Corollary 2.2
Let ϵ > 0 be sufficiently small. In order to ensure E ∥Q∗ − Qπt ∥∞ < ϵ, it suffices to ensure E ∥Q∗ − Qπt ∥2∞ < ϵ2 due to Jensen’s inequality. To that end, we consider harmonic stepsizes with ω = 3/(1 − γ) > 2/(1 − γ) and α=
20ω (1 − γ)3 (1 − γc )νmin
=
60 (1 − γ)4 (1 − γc )νmin
,
which ensures Cr ≤ C̃r . Further, for sufficiently large h, the condition αt−zt ,t−1 ≤ (1 − 2 γc )πb,min νmin /200 is also satisfied. Therefore, by Theorem 2.1, for all T ≥ K, ∗
E ∥Q
− QπT ∥2∞ ≤
K + h 3/2 48eτ 2 ω 3 + (1 − γ)2 T + h (1 − γ)3 (T + h) 9 × 602 × 216 × 8e × mn zT + . 3 2 11 2 (1 − γ) (1 − γc ) πb,min µb,min νmin T + h
|
{z
DT
}
Observe that DT , the third term above, is asymptotically larger than the other two terms since zT is logarithmic in T . To ensure E ∥Q∗ − QπT ∥2∞ = O(ϵ2 ), it therefore suffices to have DT = O(ϵ2 ). We now simplify DT . From the definition of γc in Lemma 2.1, it follows that 1 − γc ≥ (1 − γ)πb,min µb,min /2. Lemma 2.1 also gives νmin ≥ (1 − γ)πb,min µb,min /(mn). Further, by geometric mixing, we have that zT ≤
log(4/ωT ) +1 log(1/σb )
29
log 4(1 − γ)(T + h)/3 = +1 log(1/σb ) log T =O . log(1/σb ) Substituting these bounds into the expression for DT , we obtain DT = O
m 3 n3 log T 7 5 15 (1 − γ) πb,min µb,min log(1/σb ) T
!
.
Denoting the coefficient of (log T )/T in the above by Λ, it suffices to have (log T )/T = O ϵ2 /Λ . This is ensured by
Λ Λ log 2 2 ϵ ϵ log(1/ϵ) =O Λ ϵ2
T =O
!
m 3 n3 log(1/ϵ) . 7 5 15 ϵ2 (1 − γ) πb,min µb,min log(1/σb )
=O
A.4
Proofs of All Technical Lemmas
A.4.1
Proof of Lemma A.1
By definition of the Bellman operator, for any (s, a), we have [Hπ Q](s, a) = R(s, a) + γ
X
p(s′ | s, a)
s′ ∈S
(1 − α)π1 (a′ | s′ ) + απ2 (a′ | s′ ) Q(s′ , a′ )
X
a′ ∈A
= (1 − α) R(s, a) + γ
X
p(s′ | s, a)
X
π1 (a′ | s′ )Q(s′ , a′ )
a′ ∈A
s′ ∈S
+ α R(s, a) + γ
X
p(s′ | s, a)
s′ ∈S
X
π2 (a′ | s′ )Q(s′ , a′ )
a′ ∈A
= (1 − α)[Hπ1 Q](s, a) + α[Hπ2 Q](s, a). A.4.2
Proof of Lemma 2.1
The following lemma will be useful in proving Lemma 2.1; its proof is presented in Appendix A.4.6. Lemma A.7. The following inequalities hold. (1) For any Q ∈ Rmn , y ∈ Y, u ∈ U , and π ∈ (∆m )n , we have ∥FIS (Q, y, π)∥∞ ≤ 1 +
∥Q∥∞ , πb,min
∥FIS (Q, y, π)∥ν ≤ 1 +
30
∥Q∥ν . √ πb,min νmin
(2) For any Q ∈ Rmn and π ∈ (∆m )n , we have ∥F̄ (Q, π)∥ν ≤ 1 + ∥Q∥ν . √ (3) For any t1 , t2 > 0 (assuming t1 < t2 ) satisfying αt1 ,t2 −1 ≤ πb,min νmin /4, we have 4αt1 ,t2 −1 ∥Qt2 ∥ν , √ πb,min νmin 4αt1 ,t2 −1 ∥Qt2 ∥∞ ∥Qt1 − Qt2 ∥∞ ≤ 4αt1 ,t2 −1 + , πb,min 4αt1 ,t2 −1 6αt1 ,t2 −1 ∥Qt1 − Qt2 ∥ν ≤ ∥Qt2 − Qπt2 ∥ν + , √ √ πb,min νmin (1 − γ)πb,min νmin 4αt1 ,t2 −1 6αt1 ,t2 −1 ∥Qt1 − Qt2 ∥∞ ≤ ∥Qt2 − Qπt2 ∥∞ + , πb,min (1 − γ)πb,min 3 ∥Qt1 ∥ν ≤ + 2∥Qt2 − Qπt2 ∥ν , 1−γ 3 ∥Qt1 ∥∞ ≤ + 2∥Qt2 − Qπt2 ∥∞ , 1−γ ∥Qt1 − Qt2 ∥ν ≤ 4αt1 ,t2 −1 +
(4) maxs∈S dTV πt1 (s), πt2 (s) ≤ ωt1 ,t2 −1 . 2ωt1 ,t2 −1 (5) For any t1 , t2 > 0 (assuming t1 < t2 ), we have ∥Qπt1 − Qπt2 ∥∞ ≤ (1−γ) 2 . We now return to the proof of Lemma 2.1. (1) By the tower property of conditional expectations and the Markov property, we have F̄ (Q, π) = (I − D)Q + DHπ (Q),
(10)
where D ∈ Rmn×mn is the diagonal matrix with diagonal entries {µb (s)πb (a | s)}(s,a)∈S×A . The existence of the weighted ℓ2 norm ∥ · ∥ν and the contraction property then follow from [13, Theorem 2.1]. In view of (10), Qπ is clearly a fixed point of F̄ (·, π). The fact that it is the unique fixed point follows from F̄ (·, π) being a contraction mapping and the Banach fixed-point theorem [3]. (2) For any Q, Q′ ∈ Rmn , y = (s1 , a1 , s2 , a2 ) ∈ Y, and π, we have for any (s, a) that |[FIS (Q, y, π)](s, a) − [FIS (Q′ , y, π)](s, a)| ≤ (1 − 1{(s,a)=(s1 ,a1 )} )|Q(s, a) − Q′ (s, a)| 1{(s,a)=(s1 ,a1 )} + |Q(s2 , a2 ) − Q′ (s2 , a2 )| πb,min 1 ≤ ∥Q − Q′ ∥∞ . πb,min Therefore, we have ∥FIS (Q, y, π) − FIS (Q′ , y, π)∥ν ≤ ∥FIS (Q, y, π) − FIS (Q′ , y, π)∥∞ ≤
31
∥Q − Q′ ∥∞ πb,min
≤
∥Q − Q′ ∥ν . √ πb,min νmin
(3) For any two policies π and π ′ , we have the following where Pbπ and Pbπ′ denote their state-action transition probability matrices. ∥F̄ (Q, π) − F̄ (Q, π ′ )∥∞ = ∥D(Hπ (Q) − Hπ′ (Q))∥∞ = γ∥D(Pbπ − Pbπ′ )Q∥∞ ≤ γ∥D∥∞ ∥Pbπ − Pbπ′ ∥∞ ∥Q∥∞ ≤ ∥Pbπ − Pbπ′ ∥∞ ∥Q∥∞ . Since ∥Pbπ − Pbπ′ ∥∞ ≤ max s,a
X s′
p(s′ | s, a)∥π(s′ ) − π ′ (s′ )∥1 ≤ 2 max dTV (π(s′ ), π ′ (s′ )), ′ s
we further obtain ∥F̄ (Q, π) − F̄ (Q, π ′ )∥∞ ≤ 2∥Q∥∞ max dTV (π(s′ ), π ′ (s′ )). ′ s
The result then follows by combining the above inequality with Lemma A.7 (4). (4) For any Q ∈ Rmn and y = (s1 , a1 , s2 , a2 ) ∈ Y, we have [FIS (Q, y, πt1 ) − FIS (Q, y, πt2 )](s, a) 1{(s,a)=(s1 ,a1 )} γ = πt1 (a2 | s2 ) − πt2 (a2 | s2 ) Q(s2 , a2 ). πb (a2 | s2 ) Therefore, we have ∥FIS (Q, y, πt1 ) − FIS (Q, y, πt2 )∥ν ≤ ∥FIS (Q, y, πt1 ) − FIS (Q, y, πt2 )∥∞ γ ∥πt1 − πt2 ∥∞ ∥Q∥∞ ≤ πb,min 2 maxs dTV (πt1 (s), πt2 (s)) ∥Q∥∞ ≤ πb,min 2 maxs dTV (πt1 (s), πt2 (s)) ≤ ∥Q∥ν . √ πb,min νmin The result then follows by combining the above with Lemma A.7 (4). A.4.3
Proof of Lemma A.2
For any t ≥ K, we have D
Qt − Qπt , FIS (Qt , Yt , πt+1 ) − F̄ (Qt , πt )
D
= Qt−zt − Q |
πt−zt
E ν
E
, FIS (Qt−zt , Yt , πt−zt ) − F̄ (Qt−zt , πt−zt ) {z
ν
}
T21
32
+ ⟨Qt − Qπt , FIS (Qt , Yt , πt+1 ) − FIS (Qt−zt , Yt , πt+1 )⟩ν |
{z
}
T22
D
+ Qt − Qπt , F̄ (Qt−zt , πt−zt ) − F̄ (Qt , πt−zt ) |
{z
E ν
}
T23
+ ⟨Qt − Qπt , FIS (Qt−zt , Yt , πt+1 ) − FIS (Qt−zt , Yt , πt−zt )⟩ν |
{z
}
T24
D
+ Qt − Qπt , F̄ (Qt , πt−zt ) − F̄ (Qt , πt ) |
E
{z
ν
}
T25
E
D
+ (Qt − Qπt ) − (Qt−zt − Qπt−zt ), FIS (Qt−zt , Yt , πt+1 ) − F̄ (Qt−zt , πt−zt ) |
ν
{z
.
(11)
}
T26
We next bound each term on the right-hand side of the previous inequality. The term T21 . Let Ft be the sigma-algebra generated by {(Si , Ai )}0≤i≤t . Since Qt−zt and πt−zt are Ft−zt -measurable, we apply the tower property to obtain h
ET21 = E ⟨Qt−zt − Qπt−zt , FIS (Qt−zt , Yt , πt−zt ) − F̄IS (Qt−zt , πt−zt )⟩ν h
i
= E ⟨Qt−zt − Qπt−zt , E[FIS (Qt−zt , Yt , πt−zt )|Ft−zt ] − F̄IS (Qt−zt , πt−zt )⟩ν h
i
≤ E ∥Qt−zt − Qπt−zt ∥ν ∥E[FIS (Qt−zt , Yt , πt−zt )|Ft−zt ] − F̄IS (Qt−zt , πt−zt )∥ν
i
(12)
To bound ∥Qt−zt − Qπt−zt ∥ν , using Lemma A.7 Items (3) and (5), we have ∥Qt−zt − Qπt−zt ∥ν ≤ ∥Qt − Qπt ∥ν + ∥Qt − Qt−zt ∥ν + ∥Qπt − Qπt−zt ∥ν 6αt−zt ,t−1 2ωt−zt ,t−1 4αt−zt ,t−1 ∥Qt − Qπt ∥ν + + ≤ ∥Qt − Qπt ∥ν + √ √ πb,min νmin (1 − γ)πb,min νmin (1 − γ)2 2 , (13) ≤ 2∥Qt − Qπt ∥ν + 1−γ √ 2 where the last inequality follows from αt−zt ,t−1 ≤ πb,min νmin (1 − γc )/200 ≤ πb,min νmin /4, and ωt−zt ,t−1 ≤ αt−zt ,t−1 ≤ (1 − γ)/2. As for the term ∥E[FIS (Qt−zt , Yt , πt−zt )|Ft−zt ] − F̄IS (Qt−zt , πt−zt )∥ν on the right-hand side of (12), we have ∥E[FIS (Qt−zt , Yt , πt−zt )|Ft−zt ] − F̄IS (Qt−zt , πt−zt )∥ν ≤ max s∈S
≤ ≤
P zt −1 (s, s1 ) − µb (s1 ) πb (a1 |s1 )p(s2 | s1 , a1 )πb (a2 |s2 )∥FIS (Qt−zt , y, πt−zt )∥ν
X y=(s1 ,a1 ,s2 ,a2 )∈Y
∥Qt−zt ∥ν 1+ √ πb,min νmin
!
∥Qt−zt ∥ν 1+ √ πb,min νmin
!
max s∈S
X
P zt −1 (s, s1 ) − µb (s1 )
s1 ∈S
ωt .
33
(Lemma A.7 (1))
Here, the last inequality follows from the definition of zt , where we recall that zt = min{k ≥ 1 | maxs∈S dTV Pπk−1 (s, ·), µb (·) ≤ ωt /2}, which exists and is finite due to geometric mixing. b To proceed, observe that ∥Qt−zt ∥ν ≤ ∥Qt−zt − Qt ∥ν + ∥Qt − Qπt ∥ν + ∥Qπt ∥ν 4αt−zt ,t−1 6αt−zt ,t−1 1 ≤ ∥Qt − Qπt ∥ν + + ∥Qt − Qπt ∥ν + √ √ πb,min νmin (1 − γ)πb,min νmin 1−γ (Lemma A.7 (3)) 5 ≤ 2∥Qt − Qπt ∥ν + , 2(1 − γ) √ where the last inequality follows from αt−zt ,t−1 ≤ πb,min νmin /4. Therefore, we have ∥E[FIS (Qt−zt , Yt , πt−zt )|Ft−zt ] − F̄IS (Qt−zt , πt−zt )∥ν ≤
ωt √
πb,min νmin
2∥Qt − Qπt ∥ν +
3 1−γ
. (14)
Finally, substituting (13) and (14) in (12), we obtain "
#
2 3 E 2∥Qt − Q ∥ν + ET21 ≤ πb,min νmin 1−γ 2ωt 9 ≤ E 4∥Qt − Qπt ∥2ν + √ πb,min νmin (1 − γ)2 16ωt 18ωt . = EWt + √ √ πb,min νmin πb,min νmin (1 − γ)2
ωt √
The term T22 + T23 .
πt
((a + b)2 ≤ 2(a2 + b2 ) for any a, b ∈ R) (15)
By the Cauchy-Schwarz inequality, we have
T22 + T23 ≤ ∥Qt − Qπt ∥ν ∥F̄ (Qt−zt , πt−zt ) − F̄ (Qt , πt−zt )∥ν + ∥Qt − Qπt ∥ν ∥FIS (Qt , Yt , πt+1 ) − FIS (Qt−zt , Yt , πt+1 )∥ν
(16)
Since F̄ (·, πt−zt ) is a contraction mapping with respect to ∥ · ∥ν (cf. Lemma 2.1 (1)), we have ∥F̄ (Qt−zt , πt−zt ) − F̄ (Qt , πt−zt )∥ν ≤ ∥Qt − Qt−zt ∥ν . Since FIS (·, y, π) is Lipschitz continuous with respect to ∥ · ∥ν (cf. Lemma 2.1 (2)), we have ∥FIS (Qt , Yt , πt+1 ) − FIS (Qt−zt , Yt , πt+1 )∥ν ≤
1 √
πb,min νmin
∥Qt − Qt−zt ∥ν .
Substituting the previous two inequalities in (16), we obtain 2 ∥Qt − Qπt ∥ν ∥Qt − Qt−zt ∥ν √ πb,min νmin 4αt−zt ,t−1 3 πt πt ≤ 2 ∥Qt − Q ∥ν 2∥Qt − Q ∥ν + 1−γ πb,min νmin
T22 + T23 ≤
34
(Lemma A.7 (3))
4αt−zt ,t−1 3 ∥Qt − Qπt ∥ν 2∥Qt − Qπt ∥2ν + 2 1−γ πb,min νmin
=
4αt−zt ,t−1 9 2∥Qt − Qπt ∥2ν + ∥Qt − Qπt ∥2ν + 2 4(1 − γ)2 πb,min νmin 9αt−zt ,t−1 24αt−zt ,t−1 Wt + 2 . = 2 πb,min νmin πb,min νmin (1 − γ)2
≤
The term T24 + T25 .
(The AM-GM inequality) (17)
By the Cauchy-Schwarz inequality, we have
T24 + T25 ≤ ∥Qt − Qπt ∥ν ∥F̄ (Qt , πt−zt ) − F̄ (Qt , πt )∥ν + ∥Qt − Qπt ∥ν ∥F (Qt−zt , Yt , πt+1 ) − F (Qt−zt , Yt , πt−zt )∥ν
(18)
For the term ∥F̄ (Qt , πt−zt ) − F̄ (Qt , πt )∥ν on the right-hand side of (18), we have by Lemma 2.1 (3) that ∥F̄ (Qt , πt−zt ) − F̄ (Qt , πt )∥ν ≤ ∥F̄ (Qt , πt−zt ) − F̄ (Qt , πt )∥∞ ≤ 2ωt−zt ,t−1 ∥Qt ∥∞ ≤ 2ωt−zt ,t−1 (∥Qt − Qπt ∥∞ + ∥Qπt ∥∞ ) ≤ 2ωt−zt ,t−1
1 1 ∥Qt − Qπt ∥ν + √ νmin 1−γ
!
For the term ∥F (Qt−zt , Yt , πt+1 ) − F (Qt−zt , Yt , πt−zt )∥ν on the right-hand side of (18), we have by Lemma 2.1 (4) and Lemma A.7 (3) that ∥F (Qt−zt , Yt , πt+1 ) − F (Qt−zt , Yt , πt−zt )∥ν ≤ ∥F (Qt−zt , Yt , πt+1 ) − F (Qt−zt , Yt , πt−zt )∥∞ 2ωt−zt ,t ≤ ∥Qt−zt ∥∞ πb,min 2ωt−zt ,t 3 2∥Qt − Qπt ∥∞ + ≤ πb,min 1−γ 2ωt−zt ,t ≤ πb,min
3 2∥Qt − Qπt ∥ν + √ νmin 1−γ
!
.
Substituting the previous two inequalities in (18), we obtain "
2ωt−zt ,t 3 4 T24 + T25 ≤ ∥Qt − Qπt ∥ν √ ∥Qt − Qπt ∥ν + πb,min νmin 1−γ "
2ωt−zt ,t 3 4 = ∥Qt − Qπt ∥2ν + ∥Qt − Qπt ∥ν √ πb,min νmin 1−γ
#
#
" # √ 4 νmin 2ωt−zt ,t 3 1 πt 2 πt 2 ≤ ∥Qt − Q ∥ν + √ ∥Qt − Q ∥ν + √ πb,min νmin νmin (1 − γ)2 (The AM-GM inequality) 16ωt−zt ,t 8ωt−zt ,t ≤ Wt + . (19) √ πb,min νmin πb,min (1 − γ)2
35
The term T26 .
By the Cauchy–Schwarz inequality, we have
T26 ≤ ∥(Qt − Qπt ) − (Qt−zt − Qπt−zt )∥ν ≤ ∥Qt − Qt−zt ∥ν + ∥Q
πt
−Q
πt−zt
)∥ν
FIS (Qt−zt , Yt , πt+1 ) − F̄IS (Qt−zt , πt−zt )
ν
FIS (Qt−zt , Yt , πt+1 ) − F̄IS (Qt−zt , πt−zt )
ν
(20)
For the first term on the right-hand side of (20), we have by Lemma A.7 (3) and (5) that 4αt−zt ,t−1 6αt−zt ,t−1 2ωt−zt ,t−1 ∥Qt − Qπt ∥ν + + . √ √ πb,min νmin (1 − γ)πb,min νmin (1 − γ)2 (21)
∥Qt − Qt−zt ∥ν + ∥Qπt − Qπt−zt ∥ν ≤
For the second term on the right-hand side of (20), we have by Lemma A.7 (1) and (2) that ∥FIS (Qt−zt , Yt , πt+1 ) − F̄IS (Qt−zt , πt−zt )∥ν ≤ ∥FIS (Qt−zt , Yt , πt+1 )∥ν + ∥F̄ (Qt−zt , πt−zt )∥ν ∥Qt−zt ∥ν + ∥Qt−zt ∥ν √ πb,min νmin 3∥Qt−zt ∥ν ≤2+ (πb,min ≤ 1/2) √ 2πb,min νmin 3 3 πt ≤2+ + 2∥Qt − Q ∥ν √ 2πb,min νmin 1 − γ 5 3∥Qt − Qπt ∥ν + . (22) ≤ √ √ πb,min νmin (1 − γ)πb,min νmin
≤2+
Substituting the bounds (21) and (22) in (20), since ωt ≤ αt (1 − γ) and πb,min ≤ 1/2, we have T26 ≤
6αt−zt ,t−1 2ωt−zt ,t−1 4αt−zt ,t−1 ∥Qt − Qπt ∥ν + + √ √ πb,min νmin (1 − γ)πb,min νmin (1 − γ)2 ×
3∥Qt − Qπt ∥ν 5 + √ √ πb,min νmin (1 − γ)πb,min νmin
≤ αt−zt ,t−1
4 √
πt
!
!
7
!2
∥Qt − Q ∥ν + √ πb,min νmin (1 − γ)πb,min νmin 64αt−zt ,t−1 98αt−zt ,t−1 ≤ 2 Wt + , 2 πb,min νmin (1 − γ)2 πb,min νmin
(23)
where the last line follows from (a + b)2 ≤ 2(a2 + b2 ). Combining everything together. D
Substituting (15), (17), (19) and (23) in (11), we obtain E
E Qt − Qπt , FIS (Qt , Yt , πt+1 ) − F̄ (Qt , πt ) ≤
36
18ωt 16ωt EWt + √ √ πb,min νmin πb,min νmin (1 − γ)2 24αt−zt ,t−1 9αt−zt ,t−1 + 2 EWt + 2 πb,min νmin πb,min νmin (1 − γ)2 16ωt−zt ,t 8ωt−zt ,t + EWt + √ πb,min νmin πb,min (1 − γ)2
64αt−zt ,t−1 98αt−zt ,t−1 EWt + 2 2 πb,min νmin (1 − γ)2 πb,min νmin 90αt−zt ,t−1 100αt−zt ,t−1 ≤ 2 EWt + , 2 πb,min νmin (1 − γ)2 πb,min νmin +
where the last inequality follows from ωt ≤
αt−1,t−zt , √ 16πb,min νmin
which itself is a consequence of the stepsize condition ωt ≤ (1 − γ)3 (1 − γc )νmin αt /20. It now follows that 90αt αt−zt ,t−1 100αt αt−zt ,t−1 EWt + . 2 2 πb,min νmin (1 − γ)2 πb,min νmin
ET2 ≤
A.4.4
Proof of Lemma A.3
The following lemma will be useful in proving Lemma A.3; its proof is presented in Appendix A.4.7. Lemma A.8. For the policy iterates {πt } generated by Algorithm 1, we have ∥Qπt − Qπt+1 ∥∞ ≤
ωt ∥Q∗ − Qπt ∥∞ + 2∥Qt − Qπt ∥∞ + χt , 1−γ
∀ t ≥ 0.
Returning to the proof of Lemma A.3, observe that T3 = ⟨Qt − Qπt , Qπt − Qπt+1 ⟩ν ≤ ∥Qt − Qπt ∥ν ∥Qπt − Qπt+1 ∥ν ≤ ∥Qt − Qπt ∥ν ∥Qπt − Qπt+1 ∥∞ ωt ∥Qt − Qπt ∥ν (2∥Qt − Qπt ∥∞ + ∥Q∗ − Qπt ∥∞ + χt ) ≤ 1−γ
(Lemma A.8) !
ωt 2 ≤ ∥Qt − Qπt ∥ν √ ∥Qt − Qπt ∥ν + ∥Q∗ − Qπt ∥∞ + χt 1−γ νmin 4ωt ωt ωt = Wt + ∥Qt − Qπt ∥ν ∥Q∗ − Qπt ∥∞ + ∥Qt − Qπt ∥ν χt . √ (1 − γ) νmin 1−γ 1−γ To proceed, note that by the AM-GM inequality, we have for any C1 , C2 > 0 that C1 1 ∥Qt − Qπt ∥2ν + ∥Q∗ − Qπt ∥2∞ , 2 2C1 C2 1 2 ∥Qt − Qπt ∥ν χt ≤ ∥Qt − Qπt ∥2ν + χ . 2 2C2 t
∥Qt − Qπt ∥ν ∥Q∗ − Qπt ∥∞ ≤
Substituting the above in (24) yields ωt T3 ≤ 1−γ
2 C1 C2 + + √ νmin 2 2
!
∥Qt − Qπt ∥2ν +
37
1 1 2 ∥Q∗ − Qπt ∥2∞ + χ 2C1 2C2 t
!
(24)
ωt = 1−γ =
!
1 4 1 2 + C 1 + C 2 Wt + ∥Q∗ − Qπt ∥2∞ + χ √ νmin 2C1 2C2 t
!
1−γ 8ωt 1−γ Wt + ωt ∥Q∗ − Qπt ∥2∞ + ωt χ2t , √ 3 (1 − γ) νmin 4 4
where the last inequality follows by choosing C1 = C2 = 2/(1 − γ)2 . A.4.5
Proof of Lemma A.4
Observe that 1 T4 = ∥(Qt+1 − Qt ) + (Qπt − Qπt+1 )∥2ν ≤ ∥Qt+1 − Qt ∥2ν + ∥Qπt − Qπt+1 ∥2ν . 2
(25)
For the first term on the right-hand side of (25), the IS-based critic update, that ∥Qt+1 − Qt ∥2ν = αt2 ν(St ,At ) R(St , At ) + γρt+1 Qt (St+1 , At+1 ) − Qt (St , At ) ≤ αt2 ≤ αt2
1+ 1+
1 πb,min
!2
∥Qt ∥∞ + ∥Qt ∥∞
3 2πb,min 3
!2
∥Qt ∥∞
(πb,min ≤ 1/2) πt
3
!2 πt
≤ αt2
1+
≤ αt2
3 3 1+ ∥Qt − Qπt ∥ν + √ 2πb,min νmin 2πb,min (1 − γ)
≤ αt2
2 3 ∥Qt − Qπt ∥ν + √ 2πb,min νmin πb,min (1 − γ)
≤
2
2πb,min
∥Qt − Q ∥∞ +
2πb,min
∥Q ∥∞ !2
!2
(πb,min ≤ 1/2)
9αt2 8αt2 Wt + 2 . 2 πb,min νmin πb,min (1 − γ)2
(26)
For the second term on the right-hand side of (25), we have by Lemma A.8 that ∥Qπt − Qπt+1 ∥2ν ≤ ∥Qπt − Qπt+1 ∥2∞ ≤
ωt2 (∥Q∗ − Qπt ∥∞ + 2∥Qt − Qπt ∥∞ + χt )2 (1 − γ)2
ωt2 ≤ (1 − γ)2 =
2 ∥Q − Q ∥∞ + √ ∥Qt − Qπt ∥ν + χt νmin ∗
!2
πt
24ωt2 3ωt2 3ωt2 χ2t ∗ πt 2 W + ∥Q − Q , ∥ + t ∞ νmin (1 − γ)2 (1 − γ)2 (1 − γ)2
where the last inequality follows from (a + b + c)2 ≤ 3(a2 + b2 + c2 ) for any a, b, c ∈ R. Substituting the two bounds (26) and (27) in (25) yields the desired result.
38
(27)
A.4.6
Proof of Lemma A.7
(1) By definition of the operator FIS , for any Q ∈ Rmn , y = (s1 , a1 , s2 , a2 ) ∈ Y, and policy π ∈ (∆m )n , we have for any (s, a) that |[FIS (Q, y, π)](s, a)| ≤ (1 − 1{(s,a)=(s1 ,a1 )} )|Q(s, a)| + 1{(s,a)=(s1 ,a1 )} R(s1 , a1 ) + γ
π(a2 | s2 ) Q(s2 , a2 ) πb (a2 | s2 )
≤ (1 − 1{(s,a)=(s1 ,a1 )} )∥Q∥∞ + 1{(s,a)=(s1 ,a1 )} 1 + ≤1 +
1 πb,min
1 πb,min
!
∥Q∥∞
∥Q∥∞ .
It follows that ∥FIS (Q, y, π)∥∞ ≤ 1 +
1 ∥Q∥∞ . πb,min
√ Since ∥ · ∥ν ≤ ∥ · ∥∞ ≤ ∥ · ∥ν / νmin , we have ∥FIS (Q, y, π)∥ν ≤ 1 +
1 √
πb,min νmin
∥Q∥ν .
(2) For any policy π, since F̄ (·, π) is a contraction mapping with respect to ∥ · ∥ν (cf. Lemma 2.1), we have ∥F̄ (Q, π)∥ν ≤ ∥F̄ (0, π)∥ν + ∥F̄ (Q, πt+1 ) − F̄ (0, π)∥ν ≤ ∥F̄ (0, π)∥ν + ∥Q∥ν ≤ 1 + ∥Q∥ν , where the last inequality follows from ∥F̄ (0, π)∥ν ≤ 1. (3) The first two inequalities are direct consequences of [14, Lemma 4]. Since 4αt1 ,t2 −1 ∥Qt2 ∥ν √ πb,min νmin 4αt1 ,t2 −1 4αt1 ,t2 −1 ≤ 4αt1 ,t2 −1 + ∥Qt2 − Qπt2 ∥ν + ∥Qπt2 ∥ν √ √ πb,min νmin πb,min νmin 4αt1 ,t2 −1 6αt1 ,t2 −1 ≤ ∥Qt2 − Qπt2 ∥ν + , (πb,min ≤ 1/2) √ √ πb,min νmin πb,min νmin (1 − γ)
∥Qt1 − Qt2 ∥ν ≤ 4αt1 ,t2 −1 +
we obtain the third inequality. The fourth inequality follows by an identical argument. Using the triangle inequality, we have ∥Qt1 ∥ν ≤ ∥Qt1 − Qt2 ∥ν + ∥Qt2 − Qπt2 ∥ν + ∥Qπt2 ∥ν 4αt1 ,t2 −1 6αt1 ,t2 −1 1 ≤ ∥Qt2 − Qπt2 ∥ν + + ∥Qt2 − Qπt2 ∥ν + √ √ πb,min νmin πb,min νmin (1 − γ) 1−γ
39
≤ 2∥Qt2 − Qπt2 ∥ν +
3 , 1−γ
√ where the last inequality follows from αt1 ,t2 −1 ≤ πb,min νmin /4. This proves the fifth inequality. The last inequality follows by an identical argument. (4) By the definition of the total variation distance, we have for any s ∈ S that t −1
dTV πt1 (s), πt2 (s) =
2 X 1 1 ∥πt+1 (s) − πt (s)∥1 . max ∥πt1 (s) − πt2 (s)∥1 ≤ max 2 s 2 s t=t1
Since ∥πt+1 (s) − πt (s)∥1 = ωt ∥π̃t (s) − πt (s)∥1 ≤ 2ωt , we have max dTV (πt1 (s), πt2 (s)) ≤ ωt1 ,t2 −1 . s∈S
(5) Using the Bellman equations for Qπt1 and Qπt2 , we have ∥Qπt1 − Qπt2 ∥∞ = ∥Hπt1 Qπt1 − Hπt2 Qπt2 ∥∞ ≤ ∥Hπt1 Qπt1 − Hπt1 Qπt2 ∥∞ + ∥Hπt1 Qπt2 − Hπt2 Qπt2 ∥∞ ≤ γ∥Qπt1 − Qπt2 ∥∞ + ∥Hπt1 Qπt2 − Hπt2 Qπt2 ∥∞ . Rearranging terms, we obtain the following where Pbπ denotes the state-action transition probability matrix under policy π: 1 ∥Hπt1 Qπt2 − Hπt2 Qπt2 ∥∞ 1−γ γ = ∥(Pbπt1 − Pbπt2 )Qπt2 ∥∞ 1−γ 1 ≤ ∥Pbπt1 − Pbπt2 ∥∞ (1 − γ)2
∥Qπt1 − Qπt2 ∥∞ ≤
Since ∥Pbπt1 − Pbπt2 ∥∞ = max
X
s,a
= 2 max s,a
p(s′ | s, a)
s′
X
X
πt1 (a′ | s′ ) − πt2 (a′ | s′ )
a′ ′
p(s | s, a)dTV (πt1 (s′ ), πt2 (s′ ))
s′
≤ 2ωt1 −1,t2 , where the last inequality follows from Item (6) of this lemma, we have ∥Qπt1 − Qπt2 ∥∞ ≤ A.4.7
2ωt1 ,t2 −1 . (1 − γ)2
Proof of Lemma A.8
Recall that δt = maxs,a Qπt (s, a) − Qπt+1 (s, a) . Let δt′ = maxs,a Qπt+1 (s, a) − Qπt (s, a) . Then, we have ∥Qπt − Qπt+1 ∥∞ = max(δt , δt′ ).
40
For δt , we have shown in (5) that δt ≤
2ωt χt ∥Qt − Qπt ∥∞ + ωt . 1−γ 1−γ
(28)
To bound δt′ , by the monotonicity and translation invariance of the Bellman operator Hπt+1 , we have Qπt+1 = Hπt+1 Qπt+1 ≤ Hπt+1 (Qπt + δt′ 1) = Hπt+1 Qπt + γδt′ 1.
(29)
To further bound Hπt+1 Qπt , observe that Hπt+1 Qπt = (1 − ωt )Qπt + ωt Hπ̃t Qπt
(Lemma A.1)
≤ (1 − ωt )Qπt + ωt HQπt
(Hπ̃t Qπt ≤ HQπt )
≤ (1 − ωt )Qπt + ωt HQ∗
(HQπt ≤ HQ∗ )
= Qπt + ωt (Q∗ − Qπt ).
(HQ∗ = Q∗ )
Combining the previous inequality with (29), yields δt′ ≤ ωt ∥Q∗ − Qπt ∥∞ + γδt′ . Rearranging terms, we obtain δt′ ≤
ωt ∥Q∗ − Qπt ∥∞ . 1−γ
(30)
In view of (28) and (30), we have ∥Qπt − Qπt+1 ∥∞ = max(δt , δt′ ) ≤ δt + δt′ =
ωt (∥Q∗ − Qπt ∥∞ + 2∥Qt − Qπt ∥∞ + χt ) . 1−γ
B
Proof of Theorem 2.1 with the ETD-Based Critic
B.1
Analysis of the Actor
We begin by stating the actor drift inequalities. Proposition B.1. The following inequality holds for all t: ∥Q∗ − Qπt+1 ∥∞ ≤ 1 − ωt (1 − γ) ∥Q∗ − Qπt ∥∞ +
|
{z
}
actor drift
2ωt ∥Qt − Qπt ∥∞ + 1−γ |
{z
critic coupling error
}
ωt χt 1−γ
.
| {z }
temperature error
The following corollary follows, and is needed to combine the actor drift with a drift inequality for the critic. Corollary B.1. The following inequality holds for any t ≥ 0: ∥Q∗ − Qπt+1 ∥2∞ ≤ 1 − ωt (1 − γ) ∥Q∗ − Qπt ∥2∞ +
6ωt 5ωt ∥Qt − Qπt ∥2∞ + χ2 . 3 (1 − γ) (1 − γ)3 t
Since our actor analysis methodology is agnostic of the critic choice, the statements for Proposition B.1 and Corollary B.1, along with their proofs, are identical to those of Proposition 2.1 and 41
Corollary A.1, which are proved in Appendix A.1. We hence omit the proofs here.
B.2
Analysis of the Critic
We begin by reformulating the ETD-based critic update as a stochastic approximation algorithm. For any t ≥ 0, let {Ut } be a stochastic process defined as Ut = (St , At , St+1 ). It is clear that {Ut } is a Markov chain with a finite state space, denoted by U. Moreover, under Assumption 2.1, the Markov chain {Ut } admits a unique stationary distribution, denoted by µU , which satisfies µU (s1 , a1 , s2 ) = µb (s1 )πb (a1 |s1 )p(s2 |s1 , a1 ). Let FETD : Rmn × U × (∆m )n → Rmn be an operator such that given inputs Q ∈ Rmn , u = (s1 , a1 , s2 ) ∈ U and π ∈ (∆m )n , the (s, a)-th component of the output is defined as !
[FETD (Q, u, π)](s, a) =1{(s,a)=(s1 ,a1 )} R(s1 , a1 ) + γ
X
π(a|s2 )Q(s2 , a) + 1{(s,a)̸=(s1 ,a1 )} Q(s, a).
a∈A
The critic update in Algorithm 1, Line 8, under the ETD-based critic choice, can now be written compactly as
Qt+1 = Qt + αt FETD (Qt , Ut , πt+1 ) − Qt . Recall the operator F̄ : Rmn × (∆m )n → Rmn defined in Section 2.3.2 as F̄ (Q, π) = EY ∼µY FIS (Q, Y, π), where we recall that µY is the stationary distribution of the Markov chain {Yt } defined as Yt = (Ut , At+1 ), which satisfies µY (s1 , a1 , s2 , a2 ) = µU (s1 , a1 , s2 )πb (a2 | s2 ). We claim that EU ∼µU FETD (Q, U, π) = F̄ (Q, π), implying that the expected operators for both the updates coincide. To see this, note that for U = (s1 , a1 , s2 ), Y = (u, a2 ), we have
π(a2 |s2 ) R(s1 , a1 ) + γ Q(s2 , a2 ) + 1{(s,a)̸=(s1 ,a1 )} Q(s, a) πb (a2 |s2 )
F̄ (Q, π) = EY ∼µY 1{(s,a)=(s1 ,a1 )} "
= EU ∼µU 1{(s,a)=(s1 ,a1 )} R(s1 , a1 ) + γEa2 ∼πb (·|s2 )
π(a2 |s2 ) Q(s2 , a2 ) πb (a2 |s2 )
#
+ EU ∼µU 1{(s,a)̸=(s1 ,a1 )} Q(s, a) h
= EU ∼µU 1{(s,a)=(s1 ,a1 )} R(s1 , a1 ) + γEa2 ∼π(·|s2 ) Q(s2 , a2 )
i
+ EU ∼µU 1{(s,a)̸=(s1 ,a1 )} Q(s, a) = EU ∼µU FETD (Q, U, π).
It is now clear that the ETD-based critic update is a Markovian stochastic approximation scheme for tracking the solution to the (time-varying) fixed-point equation F̄ (Q, πt ) = Q. Next, we present several key properties of FETD and F̄ that facilitate the convergence analysis. In particular, we show that the equation F̄ (Q, πt ) = Q admits Qπt as its unique solution, and that F̄ (·, π) is a contractive operator with respect to a weighted ℓ2 norm. The proof of the following result is provided in Appendix B.4.4. Lemma B.1. There exists ν ∈ ∆nm with νmin ≥ (1 − γ)µb,min πb,min /(nm) such that:
42
(1) F̄ (·, π) is γc -contractive in ∥ · ∥ν for all π ∈ (∆m )n , where γc =
q
1 − (1 − γ)µb,min πb,min .
Moreover, the fixed-point equation F̄ (Q, π) = Q admits a unique solution Qπ . √ (2) FETD (·, u, π) is 1/ νmin -Lipschitz in the weighted ℓ2 norm ∥ · ∥ν and 1-Lipschitz in ∥ · ∥∞ , uniformly for all u ∈ U and π ∈ (∆m )n . (3) For all non-negative integers t1 < t2 , ∥F̄ (Q, πt1 ) − F̄ (Q, πt2 )∥∞ ≤ 2ωt1 ,t2 −1 ∥Q∥∞ for all Q ∈ Rmn . (4) For all non-negative integers t1 < t2 , ∥FETD (Q, u, πt1 ) − FETD (Q, u, πt2 )∥∞ ≤ 2ωt1 ,t2 −1 ∥Q∥∞ for all u ∈ U and Q ∈ Rmn . We now state and prove the drift inequality for the ETD-based critic. Recall that zt = min{k ≥ 1 | maxs∈S dTV Pπk−1 (s, ·), µb (·) ≤ ωt /2} and K = min{t ∈ N | t ≥ zt }. b Proposition B.2. Under Assumption 2.1, suppose that the stepsizes are non-increasing and satisfy ωt ≤
(1 − γ)3 (1 − γc )νmin αt . 16
Then, the following inequality holds for any t ≥ K:
EWt+1 ≤ 1 − αt (1 − γc ) EWt +
7αt αt−zt ,t−1 1−γ 1−γ ωt E ∥Q∗ − Qπt ∥2∞ + ωt Eχ2t + . 2 2 (1 − γ)2
Proof of Proposition B.2. We have, by the binomial decomposition, that Wt+1 =Wt + αt ⟨Qt − Qπt , F̄ (Qt , πt ) − Qt ⟩ν + αt ⟨Qt − Qπt , FETD (Qt , Ut , πt+1 ) − F̄ (Qt , πt )⟩ν |
{z
T1 : expected update term
}
|
{z
T2 : Markovian noise term
1 + ⟨Qt − Qπt , Qπt − Qπt+1 ⟩ν + ∥(Qt+1 − Qt ) + (Qπt − Qπt+1 )∥2ν . {z } |2 | {z } T3 : time-varying target term
}
(31)
T4 : residuals
We now bound the terms T1 , T2 , T3 and T4 . For the term T1 , we have, by the fact that Qπt is the fixed point of F̄ (·, πt ), that T1 = αt ⟨Qt − Qπt , F̄ (Qt , πt ) − Qt ⟩ν = αt ⟨Qt − Qπt , F̄ (Qt , πt ) − F̄ (Qπt , πt )⟩ν − αt ∥Qπt − Qt ∥2ν ≤ αt ∥Qt − Qπt ∥ν ∥F̄ (Qt , πt ) − F̄ (Qπt , πt )∥ν − αt ∥Qπt − Qt ∥2ν ≤ − αt (1 − γc )∥Qπt − Qt ∥2ν = − 2αt (1 − γc )Wt .
(32)
For the terms T2 , T3 , and T4 , they are bounded in the following sequence of lemmas. Lemma B.2. The following inequality holds for all t ≥ K: ET2 ≤
5αt αt−zt ,t−1 . (1 − γ)2
The proof of the above is presented in Appendix B.4.
43
Lemma B.3. The following inequality holds for all t ≥ 0: T3 ≤
1−γ 8ωt 1−γ Wt + ωt ∥Q∗ − Qπt ∥2∞ + ωt χ2t . √ (1 − γ)3 νmin 4 4
The above lemma and its proof are identical to Lemma A.3, which is proved in Appendix A.4.4. Hence, we omit the proof here. Lemma B.4. The following inequality holds for all t ≥ 0: T4 ≤
2αt2 . (1 − γ)2
The proof of the above is presented in Appendix B.4. We take expectation in (31) and substitute the bounds on T1 , ET2 , T3 , T4 to obtain 5αt αt−zt ,t−1 (1 − γ)2 1−γ 8ωt 1−γ + EWt + ωt E ∥Q∗ − Qπt ∥2∞ + ωt Eχ2t √ (1 − γ)3 νmin 4 4 2αt αt−zt ,t−1 + (1 − γ)2
EWt+1 ≤EWt − 2αt (1 − γc )EWt +
!
8ωt = 1 − 2αt (1 − γc ) + EWt √ (1 − γ)3 νmin 7αt αt−zt ,t−1 1−γ 1−γ ωt E ∥Q∗ − Qπt ∥2∞ + ωt Eχ2t + . + 4 4 (1 − γ)2 The result follows by bounding the perturbation term (in the coefficient of EWt ) in the above using the stepsize condition ωt ≤ (1 − γ)3 (1 − γc )νmin αt /16.
B.3
Combining the Actor and the Critic
We begin with a coupled drift inequality for the combined actor and critic error. Lemma B.5. Under the same conditions as Proposition B.2, the following inequality holds for all t ≥ K: h
i
h i ωt (1 − γ) 6ωt E ∥Q∗ − Qπt ∥2∞ + Wt + Eχ2 2 (1 − γ)3 t 7αt αt−zt ,t−1 . + (1 − γ)2
E ∥Q∗ − Qπt+1 ∥2∞ + Wt+1 ≤ 1 −
Proof of Lemma B.5. We add the critic drift (Proposition B.2) to the squared actor drift inequality from Corollary B.1 (after taking expectation) to obtain:
E[∥Q∗ − Qπt+1 ∥2∞ + Wt+1 ] ≤ 1 − ωt (1 − γ) E∥Q∗ − Qπt ∥2∞ +
6ωt 5ωt E∥Qt − Qπt ∥2∞ + Eχ2 3 (1 − γ) (1 − γ)3 t 44
ωt (1 − γ) ωt (1 − γ) 2 7αt αt−zt ,t−1 E∥Q∗ − Qπt ∥2∞ + Eχt + 2 2 (1 − γ)2 6ωt ωt (1 − γ) E ∥Q∗ − Qπt ∥2∞ + Eχ2 ≤ 1− 2 (1 − γ)3 t 7αt αt−zt ,t−1 12ωt EWt + + 1 − αt (1 − γc ) + 3 (1 − γ) νmin (1 − γ)2 7αt αt−zt ,t−1 ωt (1 − γ) αt (1 − γc ) 6ωt ≤ 1− E ∥Q∗ − Qπt ∥2∞ + 1 − EWt + Eχ2 + . 2 4 (1 − γ)3 t (1 − γ)2 (ωt ≤ (1 − γ)3 (1 − γc )νmin αt /16)
+ 1 − αt (1 − γc ) EWt +
Due to the stepsize condition ωt ≤ (1 − γ)3 (1 − γc )νmin αt /16, the coefficient of E ∥Q∗ − Qπt ∥2∞ in the above is larger than that of EWt . Using (1 − ωt (1 − γ)/2) as the common coefficient for both EWt and E ∥Q∗ − Qπt ∥2∞ gives the result. B.3.1
Solving the Recursion
To prove Theorem 2.1 for the ETD-based critic, we first verify the conditions for Lemma B.5 by showing the existence of the constant threshold C̃r . By choosing α, ω such that Cr ≤ C̃r :=
(1 − γ)3 (1 − γc )νmin , 16
the condition ωt ≤ (1 − γ)3 (1 − γc )νmin αt /16 is satisfied for any of the stepsize sequences considered in Theorem 2.1. Thus, the stepsize conditions of Lemma B.5, the coupled drift lemma, hold for all t. Moreover, note that since νmin ≥ (1 − γ)πb,min µb,min /(mn) (cf. Lemma B.1), the threshold C̃r is a constant depending only on (n, m, p, γ, πb ), as claimed in Theorem 2.1. We now simplify the coupled drift from Lemma B.5. It follows directly from [12, Lemma 5.1] p that under Condition 2.1 with parameter τ ≥ 0, we have that χt ≤ τ /(t + h)η/2 = τ ωt /ω for all t. Now note that for constant stepsizes, αt−zt ,t−1 = αzt ≤ 2αt zt . For diminishing stepsizes, let h be large enough so that zt ≤ (t + h)/2 for all t ≥ K (possible since zt is logarithmic in t). This implies that αt−zt ,t−1 ≤
αzt αzt ≤ η ≤ 2αt zt . η (t − zt + h) (t + h)/2
The coupled drift from Lemma B.5 hence reduces to h
∗
E ∥Q
− Qπt+1 ∥2∞ + Wt+1
i
h i ωt (1 − γ) 6τ 2 ωt2 14αt2 zt E ∥Q∗ − Qπt ∥2∞ + Wt + + ≤ 1− , 2 (1 − γ)3 ω (1 − γ)2
for all t ≥ K. Applying the above repeatedly, we have for all T ≥ K, that h
i
h
E ∥Q∗ − QπT ∥2∞ + WT ≤E ∥Q∗ − QπK ∥2∞ + WK
−1 i TY t=K
+
TX −1
TY −1
1−
ωt (1 − γ) 2
6τ 2 ωu (1 − γ) ω2 1− (1 − γ)3 ω t=K t u=t+1 2
45
TY −1 TX −1 14 ωu (1 − γ) 2 α z 1− . t t 2 (1 − γ) t=K 2 u=t+1
+ Qj
We define notation Πi,j := h
∗
E ∥Q
− QπT ∥2∞ + WT
u=i
i
h
1 − ωu (1 − γ)/2 . Since zt ≤ zT for all t ≤ T , it follows that ∗
≤E ∥Q + ≤
− QπK ∥2∞ + WK
i
−1 7zT TX ΠK,T −1 + α2 Πt+1,T −1 (1 − γ)2 t=K t
TX −1 6τ 2 ω 2 Πt+1,T −1 (1 − γ)3 ω t=K t
−1 TX −1 3ΠK,T −1 14zT TX 6τ 2 2 + α Π + ω 2 Πt+1,T −1 , t+1,T −1 2(1 − γ)2 (1 − γ)2 t=K t (1 − γ)3 ω t=K t
(33) where the last line follows since 1 ∥Q∗ − QπK ∥2∞ + WK = ∥Q∗ − QπK ∥2∞ + ∥QK − QπK ∥2ν 2 1 1 ≤ + (1 − γ)2 2(1 − γ)2 3 , = 2(1 − γ)2 which in turn, holds since Qt (s, a) ∈ [0, 1/(1 − γ)] for all (s, a) (cf. Lemma B.7 (2)). Now note that ωt = Cr αt and recall the notation METD = (1 − γ)−2 . Substituting in (33), we have h
∗
E ∥Q
− QπT ∥2∞ + WT
i
! T −1 X
6τ 2 14METD zT + 3 (1 − γ) ω Cr2
3ΠK,T −1 ≤ ET := + 2(1 − γ)2
ωt2 Πt+1,T −1 . (34)
t=K
The remainder of the proof follows by bounding the term ET for the specific stepsizes. (1) Constant stepsizes.
When αt = α and ωt = ω for all t, we have,
3 ω(1 − γ) ET ≤ 1− 2 2(1 − γ) 2
T −K
3 ω(1 − γ) 1− ≤ 2(1 − γ)2 2
T −K
+ +
7METD zω 6τ 2 + 3 (1 − γ) ω Cr2
! T −1 X
ω
T −1−t
ω(1 − γ) 1− 2
t
= 2/ ω(1 − γ) . Sub-
2
t=K
12τ 2 28METD ωzω + , (1 − γ)4 (1 − γ)Cr2
where the last step follows from the geometric sum stituting the above in (34) proves Theorem 2.1 (1).
46
P∞
t=0
1 − ω(1 − γ)/2
(2) Harmonic stepsizes. A.7] that ET ≤
3 2(1 − γ)2
+
When αt = α/(t + h) and ωt = ω/(t + h), we have by [14, Lemma
K +h T +h
ω(1−γ)/2
6τ 2 14METD zT + 3 (1 − γ) ω Cr2
!
×
8ω 2 2 − ω(1 − γ) (T + h)ω(1−γ)/2 2
ω<
ω log(T + h) T +h 8eω 2 ω(1 − γ) − 2 (T + h)
2 , 1−γ
2 , 1−γ 2 ω> . 1−γ ω=
Substituting the above in (34) proves Theorem 2.1 (2). When αt = α/(t + h)η and ωt = ω/(t + h)η for η ∈ (0, 1), we have
(3) Polynomial stepsizes. by [14, Lemma A.8] that
ω(1 − γ) 3 1−η 1−η exp − (T + h) − (K + h) 2(1 − γ)2 2(1 − η)
ET ≤
+
6τ 2 14METD zT + 3 (1 − γ) ω Cr2
!
8ω . (T + h)η
Substituting the above in (34) proves Theorem 2.1 (3). B.3.2
Proof of Corollary 2.2
Let ϵ > 0 be sufficiently small. In order to ensure E ∥Q∗ − Qπt ∥∞ < ϵ, it suffices to ensure E ∥Q∗ − Qπt ∥2∞ < ϵ2 due to Jensen’s inequality. To that end, we consider harmonic stepsizes with ω = 3/(1 − γ) > 2/(1 − γ) and α=
16ω 48 = , (1 − γ)3 (1 − γc )νmin (1 − γ)4 (1 − γc )νmin
which ensures Cr ≤ C̃r . We have by Theorem 2.1 that for all T ≥ K, ∗
E ∥Q
− QπT ∥2∞ ≤
3 (1 − γ)2
K +h T +h
3/2
+
zT 48eτ 2 ω 9 × 482 × 216 × 8e + . 2 3 10 2 (1 − γ) (T + h) (1 − γ) (1 − γc ) νmin T + h |
{z
DT
}
Observe also that DT , the third term in the above, is asymptotically larger than the other two terms as zT is logarithmic in T . For having E ∥Q∗ − QπT ∥2∞ = O(ϵ2 ), it hence suffices to have DT = O(ϵ2 ). We shall now simplify DT . From the definition of γc in Lemma B.1, it follows that 1 − γc ≥ (1 − γ)πb,min µb,min /2. Lemma B.1 also gives us that νmin ≥ (1 − γ)πb,min µb,min /(mn). Further, we
47
have by geometric mixing, that log(4/ωT ) +1 log(1/σb ) log 4(1 − γ)(T + h)/3 +1 = log(1/σb ) log T =O . log(1/σb )
zT ≤
Substituting these bounds in the expression for DT , we have that m 2 n2 log T 4 4 14 (1 − γ) πb,min µb,min log(1/σb ) T
DT = O
!
.
Denoting the coefficient of (log T )/T in the above by Λ, it suffices to have (log T )/T = O ϵ2 /Λ . This is ensured by
Λ Λ log 2 2 ϵ ϵ log(1/ϵ) =O Λ ϵ2
T =O
!
=O
B.4
log(1/ϵ) m 2 n2 . 4 4 14 ϵ2 (1 − γ) πb,min µb,min log(1/σb )
Proofs of All Technical Lemmas
The following two lemmas will be used extensively. Lemma B.6. For the policy iterates {πt } generated by Algorithm 1, we have ∥Qπt − Qπt+1 ∥∞ ≤
ωt ∥Q∗ − Qπt ∥∞ + 2∥Qt − Qπt ∥∞ + χt , 1−γ
∀ t ≥ 0.
The statement and the proof of the above are identical to Lemma A.8, which is proved in Appendix A.4.7. We hence omit the proof here. Lemma B.7. The following hold. (1) For any Q ∈ Rmn , y ∈ Y, u ∈ U , and π ∈ (∆m )n , we have ∥FETD (Q, u, π)∥∞ ≤ 1 + γ∥Q∥∞ ,
∥F̄ (Q, π)∥∞ ≤ 1 + γ∥Q∥∞ .
(2) For all t ≥ 0, Qt (s, a) ∈ [0, 1/(1 − γ)] for all (s, a). α 1 ,t2 −1 (3) For all t1 , t2 ≥ 0 (assuming t1 < t2 ), we have ∥Qt1 − Qt2 ∥∞ ≤ t1−γ . (4) maxs∈S dTV πt1 (s), πt2 (s) ≤ ωt1 ,t2 −1 . 2ωt1 ,t2 −1 (5) For any t1 , t2 ≥ 0 (assuming t1 < t2 ), we have ∥Qπt1 − Qπt2 ∥∞ ≤ (1−γ) 2 . The proof of Lemma B.7 is presented in Appendix B.4.3.
48
B.4.1
Proof of Lemma B.2
For any t ≥ K, we have D
E
Qt − Qπt , FETD (Qt , Ut , πt+1 ) − F̄ (Qt , πt )
D
= Qt−zt − Q
πt−zt
ν
, FETD (Qt−zt , Ut , πt−zt ) − F̄ (Qt−zt , πt−zt )
|
E ν
{z
}
T21
+ ⟨Qt − Qπt , FETD (Qt , Ut , πt+1 ) − FETD (Qt−zt , Ut , πt+1 )⟩ν |
{z
}
T22
D
E
+ Qt − Qπt , F̄ (Qt−zt , πt−zt ) − F̄ (Qt , πt−zt ) |
{z
ν
}
T23
+ ⟨Qt − Qπt , FETD (Qt−zt , Ut , πt+1 ) − FETD (Qt−zt , Ut , πt−zt )⟩ν |
{z
}
T24
E
D
+ Qt − Qπt , F̄ (Qt , πt−zt ) − F̄ (Qt , πt )
ν
{z
|
}
T25
D
+ (Qt − Qπt ) − (Qt−zt − Qπt−zt ), FETD (Qt−zt , Ut , πt+1 ) − F̄ (Qt−zt , πt−zt )
E
{z
|
ν
.
(35)
}
T26
We next bound each term on the right-hand side of the previous inequality. The term T21 . Let Ft be the sigma-algebra generated by {(Si , Ai )}0≤i≤t . Since Qt−zt and πt−zt are Ft−zt -measurable, we apply the tower property to obtain h
ET21 = E ⟨Qt−zt − Qπt−zt , FETD (Qt−zt , Ut , πt−zt ) − F̄ (Qt−zt , πt−zt )⟩ν h
i
= E ⟨Qt−zt − Qπt−zt , E[FETD (Qt−zt , Ut , πt−zt )|Ft−zt ] − F̄ (Qt−zt , πt−zt )⟩ν h
i
≤ E ∥Qt−zt − Qπt−zt ∥ν ∥E[FETD (Qt−zt , Ut , πt−zt )|Ft−zt ] − F̄ (Qt−zt , πt−zt )∥ν
i
(36)
Since Qt−zt (s, a) ∈ [0, 1/(1−γ)] for all (s, a) (cf. Lemma B.7, (2)), we have that ∥Qt−zt −Qπt−zt ∥ν ≤ 1/(1 − γ). As for the term ∥E[FIS (Qt−zt , Yt , πt−zt )|Ft−zt ] − F̄IS (Qt−zt , πt−zt )∥ν on the right-hand side of (36), we have ∥E[FETD (Qt−zt , Yt , πt−zt )|Ft−zt ] − F̄ (Qt−zt , πt−zt )∥ν ≤ max s∈S
P zt −1 (s, s1 ) − µb (s1 ) πb (a1 |s1 )p(s2 | s1 , a1 )πb (a2 |s2 )∥FETD (Qt−zt , y, πt−zt )∥∞
X y=(s1 ,a1 ,s2 ,a2 )
≤ 1 + γ∥Qt−zt ∥∞ max s∈S
X
P zt −1 (s, s1 ) − µb (s1 )
(Lemma B.7 (1))
s1 ∈S
X 1 max P zt −1 (s, s1 ) − µb (s1 ) 1 − γ s∈S s ∈S 1 ωt ≤ , 1−γ
≤
(Lemma B.7 (2))
49
where the last inequality follows from the definition of zt , where we recall that zt = min{k ≥ 1 | maxs∈S dTV Pπk−1 (s, ·), µb (·) ≤ ωt /2}, which exists and is finite due to geometric mixing. b Substituting in (36), we have ET21 ≤ The term T22 + T23 .
ωt . (1 − γ)2
(37)
By the Cauchy-Schwarz inequality, we have
T22 + T23 ≤ ∥Qt − Qπt ∥ν ∥F̄ (Qt−zt , πt−zt ) − F̄ (Qt , πt−zt )∥ν + ∥Qt − Qπt ∥ν ∥FETD (Qt , Ut , πt+1 ) − FETD (Qt−zt , Ut , πt+1 )∥ν
(38)
Since F̄ (·, πt−zt ) is a contraction mapping with respect to ∥ · ∥∞ (cf. Lemma B.1 (1)), we have ∥F̄ (Qt−zt , πt−zt ) − F̄ (Qt , πt−zt )∥ν ≤ ∥F̄ (Qt−zt , πt−zt ) − F̄ (Qt , πt−zt )∥∞ ≤ ∥Qt − Qt−zt ∥∞ αt−zt ,t−1 ≤ . 1−γ
(Lemma B.7, (3))
Since FETD (·, y, π) is 1-Lipschitz continuous with respect to ∥ · ∥∞ (cf. Lemma B.1), we similarly have ∥FETD (Qt , Ut , πt+1 ) − FETD (Qt−zt , Ut , πt+1 )∥ν ≤
αt−zt ,t−1 . 1−γ
Substituting the previous two inequalities in (38), we obtain 2αt−zt ,t−1 ∥Qt − Qπt ∥ν 1−γ 2αt−zt ,t−1 ≤ , (1 − γ)2
T22 + T23 ≤
(39)
where the last inequality follows since Qπt (s, a) ∈ [0, 1/(1 − γ)] for all (s, a) (cf. Lemma B.7, (2)). The term T24 + T25 .
By the Cauchy-Schwarz inequality, we have
T24 + T25 ≤ ∥Qt − Qπt ∥ν ∥F̄ (Qt , πt−zt ) − F̄ (Qt , πt )∥ν + ∥Qt − Qπt ∥ν ∥FETD (Qt−zt , Ut , πt+1 ) − FETD (Qt−zt , Ut , πt−zt )∥ν
(40)
For the term ∥F̄ (Qt , πt−zt ) − F̄ (Qt , πt )∥ν on the right-hand side of (40), we have by Lemma B.1 (3), that ∥F̄ (Qt , πt−zt ) − F̄ (Qt , πt )∥ν ≤ ∥F̄ (Qt , πt−zt ) − F̄ (Qt , πt )∥∞ ≤ 2ωt−zt ,t−1 ∥Qt ∥∞ 2ωt−zt ,t−1 ≤ , 1−γ where the last inequality follows since ∥Qt ∥∞ ≤ 1/(1 − γ) (cf. Lemma B.7, (2)). 50
For the term ∥FETD (Qt−zt , Ut , πt+1 ) − FETD (Qt−zt , Ut , πt−zt )∥ν on the right-hand side of (40), we similarly have by Lemma B.1 (4), that ∥FETD (Qt−zt , Ut , πt+1 ) − FETD (Qt−zt , Ut , πt−zt )∥ν ≤
2ωt−zt ,t . 1−γ
Substituting the previous two inequalities in (40), we obtain 2ωt−zt ,t ∥Qt − Qπt ∥ν 1−γ 2ωt−zt ,t ≤ , (1 − γ)2
T24 + T25 ≤
(41)
where the last line follows since Qt (s, a) ∈ [0, 1/(1 − γ)] for all (s, a) (cf. Lemma B.7 (2)). The term T26 .
By the Cauchy–Schwarz inequality, we have
T26 ≤ ∥(Qt − Qπt ) − (Qt−zt − Qπt−zt )∥ν ≤ ∥Qt − Qt−zt ∥ν + ∥Q
πt
−Q
πt−zt
)∥ν
FETD (Qt−zt , Yt , πt+1 ) − F̄ (Qt−zt , πt−zt )
ν
FETD (Qt−zt , Yt , πt+1 ) − F̄ (Qt−zt , πt−zt )
ν
(42)
For the first term on the right-hand side of (42), we have by Lemma B.7 (3) and (5) that ∥Qt − Qt−zt ∥ν + ∥Qπt − Qπt−zt ∥ν ≤ ∥Qt − Qt−zt ∥∞ + ∥Qπt − Qπt−zt ∥∞ αt−zt ,t−1 2ωt−zt ,t−1 + . ≤ 1−γ (1 − γ)2
(43)
For the second term on the right-hand side of (42), we have by Lemma B.7 (1), that ∥FETD (Qt−zt , Ut , πt+1 ) − F̄ (Qt−zt , πt−zt )∥ν
(44)
≤ ∥FETD (Qt−zt , Ut , πt+1 )∥∞ + ∥F̄ (Qt−zt , πt−zt )∥∞ ≤ 2 + 2γ ∥Qt−zt ∥∞ 2 ≤ , 1−γ
(45)
where the last line follows since ∥Qt−zt ∥∞ ≤ 1/(1 − γ) (cf. Lemma B.7 (2)). Substituting the bounds (43) and (45) in (42), we have T26 ≤ Combining everything together.
2αt−zt ,t−1 4ωt−zt ,t−1 + . (1 − γ)2 (1 − γ)3
(46)
Substituting (37), (39), (41) and (46) in (35), we obtain
D
E
E Qt − Qπt , FETD (Qt , Yt , πt+1 ) − F̄ (Qt , πt ) ≤
51
2αt−zt ,t−1 2ωt−zt ,t ωt + + (1 − γ)2 (1 − γ)2 (1 − γ)2 2αt−zt ,t−1 2ωt−zt ,t−1 + + (1 − γ)2 (1 − γ)3
≤
5αt−zt ,t−1 , (1 − γ)2
where the last inequality follows from the stepsize condition ωt ≤ (1 − γ)3 (1 − γc )νmin αt /16. It now follows that ET2 ≤ B.4.2
5αt αt−zt ,t−1 . (1 − γ)2
Proof of Lemma B.4
Observe that 1 T4 = ∥(Qt+1 − Qt ) + (Qπt − Qπt+1 )∥2ν 2 ≤ ∥Qt+1 − Qt ∥2∞ + ∥Qπt − Qπt+1 ∥2∞ αt2 4ωt2 + (1 − γ)2 (1 − γ)4 2αt2 ≤ . (1 − γ)2 ≤
B.4.3
(Lemma B.7 (3) and (5)) (ωt ≤ (1 − γ)3 (1 − γc )νmin αt /16)
Proof of Lemma B.7
(1) By definition of the operator FETD , for any Q ∈ Rmn , u = (s1 , a1 , s2 ) ∈ U, and π, we have for any (s, a) that |[FETD (Q, y, π)](s, a)| ≤ (1 − 1{(s,a)=(s1 ,a1 )} )|Q(s, a)| + 1{(s,a)=(s1 ,a1 )} R(s1 , a1 ) + γ
X
π(a| s2 )Q(s2 , a)
a∈A
≤ (1 − 1{(s,a)=(s1 ,a1 )} )∥Q∥∞ + 1{(s,a)=(s1 ,a1 )} (1 + γ∥Q∥∞ ) ≤ 1 + γ∥Q∥∞ . It follows that ∥FETD (Q, u, π)∥∞ ≤ 1 + ∥Q∥∞ . Since F̄ (Q, π) = EU ∼µU FETD (Q, U, π), it follows immediately from the above that ∥F̄ (Q, π)∥∞ ≤ 1 + ∥Q∥∞ . (2) We proceed via induction. Clearly Q0 (s, a) = 0 ∈ [0, 1/(1 − γ)] for all (s, a). If Qt (s, a) ∈ [0, 1/(1 − γ)] for all (s, a) for some t ≥ 0, then by the ETD-based critic update in Algorithm 1, Lines 8 & 10, we have that Qt+1 (s, a) = Qt (s, a) ∈ [0, 1/(1 − γ)] for all (s, a) ̸= (St , At ) and !
Qt+1 (St , At ) = (1 − αt )Qt+1 (St , At ) + αt R(St , At ) + γ
X a∈A
52
πt+1 (a | St+1 )Qt (St+1 , a)
1 − αt γ + αt 1 + 1−γ 1−γ 1 = . 1−γ
≤
Moreover, since R(St , At ), πt+1 (a | St+1 ), Q(s, a), αt ≥ 0 for all (s, a), it follows that Qt+1 (St , At ) ≥ 0. This concludes the induction. (3) Note that for any t ≥ 0, we have ∥Qt+1 − Qt ∥∞ = αt R(St , At ) + γ
X
π(a | St+1 )Qt (St+1 , a) − Qt (St , At ) ≤
a∈A
αt , 1−γ
because R(St , At ) ∈ [0, 1] and Qt (s, a) ∈ [0, 1/(1 − γ)] for all (s, a). Repeatedly applying from t1 to t2 − 1 yields the result. Items (4), (5), and their proofs are identical to Lemma A.7 (4), (5), which are proved in Appendix A.4.6. We hence omit the proofs here. B.4.4
Proof of Lemma B.1
(1) The result and its proof are identical to Lemma 2.1 (1), which is proved in Appendix A.4.2. The proof is hence omitted. (2) For any Q, Q′ ∈ Rmn , u = (s1 , a1 , s2 ) ∈ U and policy π ∈ (∆m )n , we have for any (s, a) that |[FETD (Q, u, π)](s, a) − [FETD (Q′ , u, π)](s, a)| ≤ (1 − 1{(s,a)=(s1 ,a1 )} )|Q(s, a) − Q′ (s, a)| + 1{(s,a)=(s1 ,a1 )}
X
πt+1 (a | s2 )|Q(s2 , a) − Q′ (s2 , a)|
a∈A ′
≤ ∥Q − Q ∥∞ . Therefore, we have ∥FETD (Q, u, π) − FETD (Q′ , u, π)∥∞ ≤ ∥Q − Q′ ∥∞ . (3) The result and its proof are identical to Lemma 2.1 (3), which is proved in Appendix A.4.2. The proof is hence omitted. (4) For any Q ∈ Rmn and u = (s1 , a1 , s2 ) ∈ U, we have [FETD (Q, u, πt1 ) − FETD (Q, u, πt2 )](s, a) !
= 1{(s,a)=(s1 ,a1 )} γ
X
πt1 (a | s2 )Q(s2 , a) −
a∈A
X
πt2 (a | s2 )Q(s2 , a) .
a∈A
Therefore, we have ∥FETD (Q, u, πt1 ) − FETD (Q, u, πt2 )∥∞ ≤ γ∥πt1 − πt2 ∥1 ∥Q∥∞
≤ 2 max dTV πt1 (s), πt2 (s) ∥Q∥∞ . s
53
The result then follows by combining the above with Lemma B.7 (4).
C
Discussion of Our Assumption
In this section, we first justify the minimality of Assumption 2.1 and discuss related assumptions in the literature. Proposition C.1. Assumption 2.1 is minimal for state-space exploration in the following sense: if no policy induces an irreducible state trajectory on the full state space S, then no algorithm based on a single trajectory of Markovian samples can visit every state infinitely often. Proof. Consider the directed graph G on S, where there is an edge from s to s′ if there exists an action a ∈ A such that p(s′ | s, a) > 0. If G is strongly connected, then any positive policy2 induces an irreducible Markov chain on S. Therefore, if no policy induces an irreducible state trajectory, then G is not strongly connected. Now consider any algorithm that generates a single trajectory {St , At }t≥0 . If this trajectory visits every state infinitely often, then for any two states s, s′ ∈ S, there exist times t1 < t2 such that St1 = s and St2 = s′ . The realized transitions from time t1 to time t2 form a directed path from s to s′ in G. Since every state is visited infinitely often, the same argument gives a directed path from s′ to s. Hence G must be strongly connected, which contradicts the fact that G is not strongly connected. Therefore, no single-trajectory algorithm can generate a sample path that visits every state infinitely often. We next show that if the behavior policy is positive, then Assumption 2.1 implies that the Markov chain induced by the behavior policy is irreducible. Lemma C.1. The following are equivalent: (1) There exists a policy π whose induced state trajectory is irreducible. (2) Every positive policy πb induces an irreducible state trajectory. Proof. The implication (2)⇒(1) is immediate. For (1)⇒(2), suppose that π induces an irreducible Markov chain on S, and let πb be any positive policy. Since πb (a | s) > 0 for all (s, a) and the state-action space is finite, there exists α ∈ (0, 1) such that πb (a | s) ≥ απ(a | s) for all (s, a). Therefore, for any s, s′ ∈ S, Pπb (s, s′ ) =
X
πb (a | s)p(s′ | s, a) ≥ α
a∈A
X
π(a | s)p(s′ | s, a) = αPπ (s, s′ ).
a∈A
It follows that, for any T ≥ 1, PπTb (s, s′ ) ≥ αT PπT (s, s′ ). Since the Markov chain induced by π is irreducible, for every pair s, s′ ∈ S there exists T such that PπT (s, s′ ) > 0. Hence PπTb (s, s′ ) > 0, which implies that the Markov chain induced by πb is irreducible. 2
We call a policy π positive if π(a | s) > 0 for all s ∈ S and a ∈ A
54
Lazy-chain construction [52]. The preceding lemma shows that Assumption 2.1, together with the positivity of πb , implies irreducibility of the Markov chain induced by πb . We now explain why aperiodicity can be imposed without loss of generality through the standard lazy-chain construction. Given a state-action trajectory {St , At } generated by a policy π, let Pπ denote the corresponding state-action transition kernel. Fix λ ∈ (0, 1). The lazy version of this chain is defined by using the transition kernel Pπ′ := (1 − λ)Pπ + λI. Equivalently, at each step the chain stays at the current state-action pair with probability λ, and follows the original transition kernel Pπ with probability 1 − λ. This construction can be implemented online by repeating each observed state-action-reward tuple for a geometrically distributed number of times before advancing to the next transition. It is clear that Pπ′ has the same stationary distribution as Pπ . Moreover, if Pπ is irreducible, then Pπ′ is also irreducible. Since Pπ′ has a self-loop probability at least λ at every state-action pair, it is aperiodic. Therefore, on a finite state-action space, irreducibility and aperiodicity imply geometric mixing [34, Theorem 4.9].
C.1
Comparison with Assumptions from Existing Literature
We now compare Assumption 2.1 with commonly used assumptions in the actor–critic literature. We focus on three aspects: (i) mixing requirements, (ii) exploration conditions, and (iii) policy smoothness assumptions. Uniform ergodicity across policies. A frequently adopted assumption concerns uniform geometric mixing of the Markov chains induced by a class of policies. Let Θ be a parameter space for policies. The following assumption appears frequently in the literature [64, Assumption 4.2], [42, Assumption 2], [68, Assumption 2], [10, Assumption 3.2]. Assumption C.1. For any policy parameter θ ∈ Θ, the policy πθ induces a unique stationary distribution µθ on the state trajectory. Moreover, there exist constants c > 0 and ρ ∈ (0, 1) such that sup max dTV Pπtθ (s, ·), µθ (·) ≤ cρt ,
θ∈Θ s∈S
∀t ≥ 0,
where Pπθ denotes the state transition matrix induced by πθ . Assumption C.1 is substantially stronger than Assumption 2.1. It not only requires every policy in the parameterized class to induce an ergodic Markov chain, but also imposes a common geometric mixing rate over the entire class. Even if a similar condition is imposed only on the policies generated along the algorithm trajectory, it remains algorithm-dependent, since verifying it requires controlling the very policy sequence whose convergence is being analyzed. In contrast, Assumption 2.1 is purely structural: it only requires the existence of one policy that induces an irreducible Markov chain on the state space. As shown in Proposition C.1, this condition is minimal for state-space exploration. In our analysis, the existence of a stationary distribution
55
and geometric mixing follow from Assumption 2.1, the positivity of the fixed behavior policy πb , and the lazy-chain construction above. Exploration conditions. In analyses involving linear function approximation, a common exploration-type condition is imposed through the feature covariance structure. Let φ : S ×A → Rd be the feature map, and let µθ be the stationary distribution of the state trajectory under πθ . The following condition appears frequently in equivalent forms [32, Assumption 3.1], [31, Assumption 3.1], [42, Assumption 6], [64, Assumption 4.1]. Assumption C.2. Let Aθ = Es∼µθ , a∼πθ (·|s), s′ ∼p(·|s,a), a′ ∼πθ (·|s′ ) φ(s, a) γφ(s′ , a′ ) − φ(s, a)
⊤
.
There exists λ > 0 such that Aθ + λI is negative semidefinite for all θ ∈ Θ. The following lemma shows that, in the tabular case, this condition fails near optimal policies whenever a suboptimal action exists. Lemma C.2. Consider the tabular case. Suppose that there exist a state s ∈ S and actions a1 , a2 ∈ A such that Q∗ (s, a1 ) < Q∗ (s, a2 ). Let π ∗ be an optimal policy satisfying π ∗ (a1 | s) = 0. Then, for any λ > 0, there exists δ > 0 such that Aπ + λI is not negative semidefinite for every policy π satisfying dTV (π, π ∗ ) < δ. Consequently, global convergence to an optimal policy and the validity of Assumption C.2 along the algorithm trajectory cannot hold simultaneously for general tabular MDPs. Proof. In the tabular setting, the feature map is the identity over state-action pairs, and hence Aπ = Dπ (γ Pbπ − I),
where Dπ = diag µπ (s)π(a | s) | (s, a) ∈ S × A and Pbπ is the state-action transition kernel induced by π. Let e(s, a1 ) denote the standard basis vector corresponding to the state-action pair (s, a1 ). Then e(s, a1 )⊤ Aπ e(s, a1 ) = µπ (s)π(a1 | s) γ Pbπ ((s, a1 ), (s, a1 )) − 1 .
Since 0 ≤ Pbπ ((s, a1 ), (s, a1 )) ≤ 1, we have e(s, a1 )⊤ Aπ e(s, a1 ) ≥ −µπ (s)π(a1 | s) ≥ −π(a1 | s). Because π ∗ (a1 | s) = 0, there exists δ > 0 such that dTV (π, π ∗ ) < δ implies π(a1 | s) < λ/2. Therefore, e(s, a1 )⊤ (Aπ + λI)e(s, a1 ) = e(s, a1 )⊤ Aπ e(s, a1 ) + λ >
λ > 0. 2
Thus Aπ + λI is not negative semidefinite for any such policy π. The final claim follows because any algorithm that globally converges to π ∗ must eventually enter this neighborhood, where Assumption C.2 fails. 56
Since our analysis focuses on the tabular case, we do not impose such spectral exploration conditions. Instead, exploration is ensured through the positive behavior policy. Lemma C.2 shows that Assumption C.2 is incompatible with global convergence in general tabular MDPs whenever optimality requires eliminating suboptimal actions. Policy smoothness assumptions. Most of the actor–critic literature adopts an optimization viewpoint and analyzes the actor through policy gradients. Such analyses typically require Lipschitz continuity of policies and log-policy gradients. The following assumption appears frequently [10, Assumption 3.3], [42, Assumption 3], [64, Assumption 4.3]. Assumption C.3. The following hold for all θ, θ1 , θ2 ∈ Θ, s ∈ S, and a ∈ A: (1) There exists B > 0 such that ∥∇θ log πθ (a | s)∥ ≤ B. (2) There exists L > 0 such that ∥∇θ log πθ1 (a | s) − ∇θ log πθ2 (a | s)∥ ≤ L∥θ1 − θ2 ∥. (3) There exists L′ > 0 such that |πθ1 (a | s) − πθ2 (a | s)| ≤ L′ ∥θ1 − θ2 ∥. In the tabular case, where the policy is parameterized by itself, i.e., θ = π, the first condition ∂ log π(a | s) = 1/π(a | s) can be arbitrarily large as π(a | s) approaches fails because ∂π(a|s) zero. Similarly, since the map x 7→ 1/x is not Lipschitz near zero, the second condition also fails. Although the third condition is benign under this parametrization, the first two conditions rule out policies approaching the boundary of the simplex. This is restrictive for global optimality analysis in the tabular setting, where optimal policies are often deterministic and hence lie on the boundary of the policy simplex.
57