1 Introduction↩︎

Reinforcement learning (RL) has become increasingly impactful in solving sequential decision-making problems [1], ranging from game-playing AI [2] to large language models [3]. Mathematically, RL can be viewed as a data-driven framework for solving Markov decision processes (MDPs) [4]. 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 [5] and policy-space methods such as actor–critic [6], respectively.

For \(Q\)-learning, it has long been established that an \(\smash{\tilde{\mathcal{O}}(\epsilon^{-2})}\) sample complexity is achievable as long as the stationary behavior policy induces an irreducible and aperiodic Markov chain; see [7]–[9], among many others. The aperiodicity assumption has recently been relaxed in [10]–[12]. 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.

For actor–critic methods, existing results achieving an \(\tilde{\mathcal{O}}(\epsilon^{-2})\) sample complexity mostly rely on a nested-loop implementation [13]–[16], 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 [17]–[19]. 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 [20]–[23], with only a few exceptions [13], [16], [24]. 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 \(\tilde{\mathcal{O}}(\epsilon^{-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.

\(\bullet\) 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 \(\tilde{\mathcal{O}}(\epsilon^{-2})\) sample complexity. To the best of our knowledge, this is the first result attaining near-minimax sample complexity (with respect to \(\epsilon\)) without relying on a nested-loop implementation, timescale separation, or strong, potentially algorithm-dependent assumptions.

\(\bullet\) 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 [25], 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.

1.2 Related Literature↩︎

Actor–critic methods [6] 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 [26], while policy improvement is performed via variants of policy gradient methods [27], [28] or approximate policy iteration [29]. Asymptotic convergence guarantees for actor–critic methods have been established for decades [6], [30]. 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: nested-loop 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, \(\tilde{\mathcal{O}}(\epsilon^{-2})\) sample complexity has been achieved in both tabular and function approximation settings [14], [15], [21], [24], [31]–[33]. However, most existing results rely on strong uniform ergodicity assumptions on the policies generated by the algorithm, or simply on all policies [15], [21], [31], [33], [34], with only a few exceptions [13], [16], [24]. 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 [35]–[37] or a single-timescale structure [22], [23], [38]. Regardless of timescale separation, existing results either lack global convergence guarantees [23], [35], rely on strong assumptions [39], [40], or yield suboptimal sample complexity bounds [36], [40]. Our work establishes near-optimal sample complexity guarantees with respect to \(\epsilon\) 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 [1]. While the tabular setting is a special case of function approximation, we emphasize that existing results on actor–critic with function approximation [23], [33], [35], [41] 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., [35], [23], and [33]. These assumptions and their incompatibility with the tabular setting are detailed in Appendix 6.1.

2.3pt

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 [44]. Importance sampling is typically used to correct this discrepancy [45]–[47]. Off-policy actor–critic methods have been studied in the literature [24], [48], [49], achieving \(\tilde{\mathcal{O}}(\epsilon^{-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-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 [4] is defined by a tuple \((\mathcal{S}, \mathcal{A}, p, \mathcal{R}, \gamma)\), where \(\mathcal{S}\) is the state space of size \(n\), \(\mathcal{A}\) is the action space of size \(m\), \(p\) is the transition probability kernel, \(\mathcal{R}:\mathcal{S}\times\mathcal{A}\to[0,1]\) is the reward function, and \(\gamma\in(0,1)\) is the discount factor. Given a policy \(\pi\), its \(Q\)-function \(Q^\pi:\mathcal{S}\times\mathcal{A}\to\mathbb{R}\) is defined as \(Q^\pi(s,a)=\mathbb{E}\left[\sum_{t=0}^\infty \gamma^t \mathcal{R}(S_t,A_t) \mid S_0=s, A_0=a\right]\) for all \((s,a)\in\mathcal{S}\times\mathcal{A}\). Note that \(Q^\pi\) can be alternatively viewed as a vector in \(\mathbb{R}^{mn}\). The goal is to learn an optimal policy \(\pi^*\) 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 [27], and natural policy gradient [28]. 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 \(Q\)-learning [5], and policy-space methods translate to the popular actor–critic framework, in which an agent iteratively performs policy evaluation and policy improvement [6].

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.

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 \(\tilde{\pi}_t\), which is computed from the current policy \(\pi_t\), the current \(Q\)-function estimate \(Q_t\), and a temperature parameter \(\tau_t\) through a generic update map \(G(\cdot)\). 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 \(\rho_{t+1}\) denotes the importance-sampling ratio. The second directly computes the expected \(Q\)-function at the next state \(S_{t+1}\); we refer to this variant as expected temporal difference (ETD). In both cases, \(\Delta_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.

The Actor for Policy Improvement. In each iteration of Algorithm 1, the agent computes \(\tilde{\pi}_t\) via the update map \(G(\cdot)\) and then updates its policy by taking an incremental step toward \(\tilde{\pi}_t\) with stepsize \(\omega_t\). As for the function \(G\), popular choices include natural policy gradient and approximate policy iteration with \(\epsilon\)-greedy or softmax updates, as presented below.

Natural Policy Gradient: Define the function \(G\) as \[\begin{align} [G(\pi,Q,\tau)](s,a) =\frac{\pi(a| s)\exp(Q(s,a)/\tau)}{\sum_{a'}\pi(a'|s)\exp(Q(s,a')/\tau)},\quad\forall\,(s,a). \end{align}\] Note that if the critic estimate is accurate, i.e., \(Q_t=Q^{\pi_t}\), the update \(\tilde{\pi}_t=G(\pi_t,Q_t,\tau_t)\) coincides with the natural policy gradient update [50].

Approximate Policy Iteration with Softmax Update: Define the function \(G\) as \[\begin{align} [G(\pi,Q,\tau)](s,a) =\frac{\exp(Q(s,a)/\tau)}{\sum_{a'}\exp(Q(s,a')/\tau)},\quad\forall\,(s,a), \end{align}\] which corresponds to a “soft” version of policy iteration.

Approximate Policy Iteration with \(\epsilon\)-Greedy Update: Define the function \(G\) as \[\begin{align} [G(\pi,Q,\tau)](s,a)=\begin{dcases} \tau/m+1-\tau,& a=\arg\max_{a'\in\mathcal{A}} Q(s,a'),\\ \tau/m,&\text{otherwise,} \end{dcases} \end{align}\] where the tie-breaking rule can be arbitrary. This is the usual \(\epsilon\)-greedy update with exploration level \(\epsilon=\tau\). We use the notation \(\tau\) only to keep the temperature parameter consistent across the three actor updates. Although \(\epsilon\) does not appear in the definition, the name \(\epsilon\)-greedy is retained for consistency with the literature [51].

Note that as the tunable parameter \(\tau\) approaches zero, all three updates reduce to policy iteration [28], thereby enabling a unified analysis. For ease of terminology, we will uniformly refer to \(\tau_t\) in Algorithm 1 as the temperature parameter.

The Critic for Policy Evaluation. Our critic update is an off-policy variant of TD-learning [26], 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 [47], [52]. 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 [22], [35], [36]. While off-policy learning is both practically and theoretically justified, it introduces a mismatch between the behavior policy \(\pi_b\) and the target policy \(\pi_{t+1}\). Recall that the goal of the critic is to estimate the \(Q\)-function \(Q^{\pi_{t+1}}\) associated with \(\pi_{t+1}\), while samples are generated from \(\pi_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 \((S_t,A_t)\), the temporal difference \(\Delta_t\) is constructed as a conditionally unbiased estimator of the Bellman error \[\begin{align} \mathcal{R}(S_t,A_t) + \gamma \underbrace{ \sum_{s'\in\mathcal{S}} p(s'\mid S_t,A_t) \sum_{a'\in\mathcal{A}} \pi_{t+1}(a'\mid s') Q_t(s',a') }_{:=E_1} - Q_t(S_t,A_t). \end{align}\] The key quantity to estimate is \(E_1\). Since \(S_{t+1}\sim p(\cdot\mid S_t,A_t)\), one can construct an unbiased estimator of \(E_1\) using \(A_{t+1}\sim \pi_b(\cdot\mid S_{t+1})\) via importance sampling, which corrects the mismatch between \(\pi_{t+1}\) and \(\pi_b\) [46], [47]. This yields the IS-based approach in Lines 5–6 of Algorithm 1. Alternatively, since \(\pi_{t+1}\) is known, one can directly compute an unbiased estimator of \(E_1\) given \(S_{t+1}\) as \(\sum_{a'\in\mathcal{A}} \pi_{t+1}(a'\mid S_{t+1}) Q_t(S_{t+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.

2.2 Convergence Rates↩︎

We now state the only exploration assumption used in our analysis.

Assumption 1 is purely existential: the policy \(\pi\) 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 6, 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 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 [22], [23], [35]. Such conditions are not only stronger than Assumption 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 6.1.

For our main result, we consider stepsize sequences \(\left\{\alpha_t,\omega_t\right\}\) of the form \(\alpha_t = \alpha/(t+h)^\eta\) and \(\omega_t = \omega/(t+h)^\eta\), where \(\alpha,\omega,h>0\) and \(\eta\in[0,1]\) are constants. Let \(C_r=\omega/\alpha\in(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 [17], [18], [55]–[57].

Next, we state a condition on the choice of the temperature parameter \(\tau_t\) in Algorithm 1.

Let \(z_t\) be the mixing time of the Markov chain \(\{S_t\}\) under \(\pi_b\) with precision \(\omega_t\), defined as \(z_t := \min\left\{k\geq 1\mid \max_{s\in\mathcal{S}}\mathrm{d}_{\mathrm{TV}}\big(P_{\pi_b}^{k-1}(s,\cdot),\mu_b(\cdot)\big) \leq \omega_t/2\right\}\). When using a constant stepsize \(\omega_t\equiv \omega\), we simply write \(z_\omega\). We also define a related quantity \(K = K_{\omega,h,\eta} := \min\{t\in\mathbb{N}\mid t\geq z_t\}\). Due to geometric mixing, this quantity is well defined and finite for our choice of stepsizes.

Recall that \(Q^*\) is the \(Q\)-function of an optimal policy, whereas \(Q^{\pi_T}\) is the \(Q\)-function of the last policy iterate \(\pi_T\). Thus, the left-hand side measures the mean-square optimality gap of \(\pi_T\). On the right-hand side, the bounds decompose into three terms (for the diminishing-stepsize cases, after expanding \(M'_{\mathrm{critic},T}\)): the optimization bias, the error induced by a nonzero temperature, and the stochastic error. For approximate policy iteration with either exponential softmax or \(\epsilon\)-greedy updates, setting \(\tau=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 \(\tau\), which 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 [28], [56], [57].

To obtain the optimal convergence rate in Theorem 1, we use harmonic stepsizes with \(\omega>2/(1-\gamma)\). 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 \(\omega\), 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-\gamma)^{-1},\pi_{b,\min}\), and \(\mu_{b,\min}\) (cf. Eq. ?? ). 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 1 is presented in Section 2.3. As a direct consequence, we obtain the following sample complexity bound.

To the best of our knowledge, this is the first last-iterate convergence result for a single-loop actor–critic algorithm achieving \(\tilde{\mathcal{O}}(\epsilon^{-2})\) sample complexity, which is minimax optimal with respect to \(\epsilon\) up to logarithmic factors [58]. Notably, we do not impose strong, algorithm-dependent assumptions on the policies generated along the algorithm trajectory. While the dependence on \(\epsilon\) is near optimal, the dependence on problem-specific constants such as \(n\), \(m\), and \((1-\gamma)^{-1}\) is likely suboptimal. Recall that even for value-based methods such as \(Q\)-learning [5], attaining minimax sample complexity with respect to all constants requires more refined techniques, such as variance reduction [59]. Developing analogous algorithmic or technical improvements for single-loop actor–critic methods is an interesting direction for future work.

2.3 Proof of Theorem 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 [25], [60], [61]. 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 \(V_t\), which depends on \(Q^*-Q^{\pi_t}\) and captures the suboptimality gap of the policy \(\pi_t\). For the critic, we denote the Lyapunov function by \(W_t\), which depends on \(Q_t-Q^{\pi_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 \[\begin{align} \mathbb{E}V_{t+1} \le (1 - \kappa_1 \omega_t)\mathbb{E}V_t +D_{1,t} \mathbb{E}W_t + o(\omega_t), \quad \mathbb{E}W_{t+1} \le (1 - \kappa_2 \alpha_t)\mathbb{E}W_t + D_{2,t} \mathbb{E}V_t + o(\alpha_t),\label{eq:desired95drift} \end{align}\tag{1}\] where \(\kappa_1,\kappa_2\) are positive constants, and \(D_{1,t},D_{2,t}\) depend on the stepsizes. These drift inequalities are coupled: \(W_t\) appears as an additive error term in the drift inequality for \(V_t\), and vice versa. To solve the recursions, it is essential to ensure, while deriving the separate drift inequalities, that \(D_{2,t}<\kappa_1\omega_t\) and \(D_{1,t}<\kappa_2\alpha_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 \(V_t+W_t\), which, upon iteration, yields the convergence of Algorithm 1. This idea is inspired by the small-gain analysis of continuous-time dynamical systems [62]. Related approaches have been used in actor–critic analysis, but only to establish stationary-point convergence [23].

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 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 \(\pi\), let \(\mathcal{H}_\pi:\mathbb{R}^{mn}\to \mathbb{R}^{mn}\) be the Bellman operator associated with \(\pi\), defined as \[\begin{align} [\mathcal{H}_\pi(Q)](s,a)=\mathcal{R}(s,a)+\gamma \sum_{s'}p(s'\mid s,a)\sum_{a'}\pi(a'|s')Q(s',a'),\quad \forall\,(s,a). \end{align}\] Let \(\mathcal{H}:\mathbb{R}^{mn}\to \mathbb{R}^{mn}\) be the Bellman optimality operator defined as \[\begin{align} [\mathcal{H}(Q)](s,a)=\mathcal{R}(s,a)+\gamma \sum_{s'}p(s'\mid s,a)\max_{a'}Q(s',a'),\quad \forall\,(s,a). \end{align}\] We use \(\|Q^*-Q^{\pi_t}\|_\infty\) as our Lyapunov function for the actor.

The following proposition presents its Lyapunov drift inequality. See Appendix 4.1 for its proof.

In Proposition [prop:actor], 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., \(Q_t = Q^{\pi_t}\), and (ii) we perform a greedy update, i.e., \(\chi_t = 0\) and \(\omega_t \equiv 1\). In this case, Algorithm 1 reduces to policy iteration, and Proposition [prop:actor] simplifies to \(\infnorm{Q^* - Q^{\pi_{t+1}}} \le \gamma \infnorm{Q^* - Q^{\pi_t}}\), which is consistent with the geometric convergence of policy iteration [4].

The critic evaluation error \(\infnorm{Q_t - Q^{\pi_t}}\) will be analyzed in the next subsection. As for the last term \(\chi_t\), it captures the deviation from a greedy update and vanishes as \(\tau_t \to 0\) for all three update rules presented in Section 2.1. For this reason, we refer to the last term as the temperature error.

The complete proof of Proposition [prop:actor] is provided in Appendix 4.1. Here, we present a proof sketch highlighting the main ideas.

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^{\pi_t}\) [63]. Stochastic approximation with fixed targets has been extensively studied using Lyapunov methods [60], [64]. In particular, off-policy TD-learning with a fixed target policy has been analyzed via weighted \(\ell_2\)-norm Lyapunov functions [65]. 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\geq 0\), let \(\{Y_t\}\) be a stochastic process defined as \(Y_t=(S_t,A_t,S_{t+1},A_{t+1})\). It is clear that \(\{Y_t\}\) is a Markov chain with a finite state space, denoted by \(\mathcal{Y}\). Moreover, under Assumption 1, the Markov chain \(\{Y_t\}\) admits a unique stationary distribution, denoted by \(\mu_Y\), which satisfies \(\mu_Y(s_1,a_1,s_2,a_2)=\mu_b(s_1)\pi_b(a_1|s_1)p(s_2|s_1,a_1)\pi_b(a_2|s_2)\). Let \(F_\mathrm{IS}:\mathbb{R}^{mn}\times \mathcal{Y}\times {(\Delta^{m})}^n\to \mathbb{R}^{mn}\) be an operator such that given inputs \(Q \in \mathbb{R}^{mn}\), \(y = (s_1,a_1,s_2,a_2) \in \mathcal{Y}\) and \(\pi\in{(\Delta^{m})}^n\), the \((s,a)\)-th component of the output is defined as \[\begin{align} [F_\mathrm{IS}(Q,y,\pi)](s,a) =\mathbb{1}_{\{ (s,a)= (s_1,a_1)\}}\left(\mathcal{R}(s_1,a_1) + \gamma \frac{\pi(a_2|s_2)}{\pi_b(a_2| s_2)} Q(s_2,a_2)\right)+\mathbb{1}_{\{ (s,a)\neq (s_1,a_1)\}}Q(s,a). \end{align}\] The critic update in Algorithm 1, Line 10, can now be written compactly as \[\begin{align} Q_{t+1} = Q_t + \alpha_t \bigl(F_\mathrm{IS}(Q_t, Y_t, \pi_{t+1}) - Q_t\bigr). \end{align}\] We further define the operator \(\bar{F}: \mathbb{R}^{mn}\times {(\Delta^{m})}^n\to\mathbb{R}^{mn}\) as \(\bar{F}(Q,\pi)=\mathbb{E}_{Y\sim \mu_Y}[F_\mathrm{IS}(Q,Y,\pi)]\). 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 \(\bar{F}(Q,\pi_t)=Q\). While both \(F\) and \(\bar{F}\) depend on \(\pi_b\), since \(\pi_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 \(\bar{F}(Q,\pi_t)=Q\) admits \(Q^{\pi_t}\) as its unique solution, and that \(\bar{F}(\cdot,\pi)\) is a contractive operator with respect to a weighted \(\ell_2\) norm. For ease of presentation, for any nonnegative integers \(i\le j\), we use the shorthand \(\alpha_{i,j}:=\sum_{u=i}^j\alpha_u\) and \(\omega_{i,j}:=\sum_{u=i}^j\omega_u\). The proof of the following result is provided in Appendix 4.4.2.

These properties play distinct roles in the analysis: the contraction of \(\bar{F}\) ensures a negative drift; the Lipschitz continuity of \(F_\mathrm{IS}\) 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 1, we define the Lyapunov function for the critic as \(W_t := \|Q_t - Q^{\pi_t}\|_\nu^2/2\). The following result establishes a one-step drift inequality for the critic; the proof is provided in Appendix 4.2.

The first two terms on the right-hand side of the previous inequality are standard in the study of TD-learning for policy evaluation [60], [66]; 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 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 2 , which is crucial for establishing the cross-domination property in the next step of the proof.

2.3.3 Cross Domination↩︎

Propositions [prop:actor] and [prop:critic] establish Lyapunov drift inequalities for the actor and critic, respectively, both of the form in 1 . It therefore remains to combine these inequalities and solve the resulting recursion to obtain the convergence rate of Algorithm 1. In particular, combining Propositions [prop:actor] and [prop:critic] yields the following lemma, where we denote \(V_t=\infnorm{Q^*-Q^{\pi_t}}^2\) for simplicity.

The proof of Lemma 5 follows by squaring both sides of 2 , taking expectations, and adding the resulting bound to the critic drift inequality in Proposition [prop:critic]. See Appendix 4.3.1 for more details.

3 Conclusion↩︎

In this work, we establish the first \(\tilde{\mathcal{O}}(\epsilon^{-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-\gamma)\) 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 function approximation, commonly referred to as the deadly triad, can lead to instability [1]. While this deadly triad challenge can be addressed using gradient TD or TD with gradient correction [67], 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.

4 Proof of Theorem 1 with the IS-Based Critic↩︎

4.1 Analysis of the Actor↩︎

4.1.1 Proof of Proposition [prop:actor]↩︎

The following lemma is needed, whose proof is presented in Appendix 4.4.1.

As illustrated in Section 2.3.1, our proof of Proposition [prop:actor] 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^{\pi_t}\|_\infty\). We recall the following notation: \(\delta_t = \max_{s,a}\big(Q^{\pi_t}(s,a) - Q^{\pi_{t+1}}(s,a)\big)\) and \(\chi_t= \infnorm{\mathcal{H}Q_t-\mathcal{H}_{\tilde{\pi}_t}Q_t}\), and additionally define \(\xi_t := \infnorm{Q_t-Q^{\pi_t}}\). Throughout this proof and all upcoming appendices, inequalities between vectors are interpreted entry-wise.

4.1.1.1 Step 1: Approximate monotonic improvement.

Observe that by the definition of \(\delta_t\), we have \(Q^{\pi_{t+1}} \ge Q^{\pi_t} - \delta_t \mathbf{1}\). Using the Bellman equation, together with the monotonicity and translation invariance of the Bellman operator, we have \[\begin{align} Q^{\pi_{t+1}} =\,& \mathcal{H}_{\pi_{t+1}} Q^{\pi_{t+1}} \nonumber\\ \ge\,& \mathcal{H}_{\pi_{t+1}}(Q^{\pi_t} - \delta_t\mathbf{1}) \nonumber\\ =\,& \mathcal{H}_{\pi_{t+1}} Q^{\pi_t} - \gamma \delta_t \mathbf{1}\nonumber\\ =\,&(1-\omega_t)\mathcal{H}_{\pi_t}Q^{\pi_t} + \omega_t \mathcal{H}_{\tilde{\pi}_t}Q^{\pi_t}- \gamma \delta_t \mathbf{1}}\nonumber\\ =\,&(1-\omega_t)Q^{\pi_t} + \omega_t \mathcal{H}_{\tilde{\pi}_t}Q^{\pi_t}- \gamma \delta_t \mathbf{1}.\label{eq:mono} \end{align}\tag{3}\] Rearranging terms, we obtain \[\begin{align} Q^{\pi_t} - Q^{\pi_{t+1}} \le \omega_t\big(Q^{\pi_t}-\mathcal{H}_{\tilde{\pi}_t}Q^{\pi_t}\big) + \gamma\delta_t\mathbf{1} \le \omega_t(\mathcal{H}Q^{\pi_t} - \mathcal{H}_{\tilde{\pi}_t}Q^{\pi_t}) + \gamma\delta_t\mathbf{1}, \end{align}\] where the last inequality follows from \(\mathcal{H}Q^{\pi_t}\geq \mathcal{H}_{\pi_t}Q^{\pi_t} = Q^{\pi_t}\).

To proceed, observe that \[\begin{align} \mathcal{H}Q^{\pi_t} - \mathcal{H}_{\tilde{\pi}_t}Q^{\pi_t} =\,& \mathcal{H}Q^{\pi_t} - \mathcal{H}Q_t + \mathcal{H}Q_t-\mathcal{H}_{\tilde{\pi}_t}Q_t + \mathcal{H}_{\tilde{\pi}_t}Q_t - \mathcal{H}_{\tilde{\pi}_t}Q^{\pi_t}\\ \leq\,& \infnorm{\mathcal{H}Q^{\pi_t} - \mathcal{H}Q_t}\mathbf{1} + \infnorm{\mathcal{H}Q_t-\mathcal{H}_{\tilde{\pi}_t}Q_t}\mathbf{1} + \infnorm{\mathcal{H}_{\tilde{\pi}_t}Q_t - \mathcal{H}_{\tilde{\pi}_t}Q^{\pi_t}}\mathbf{1}\\ \leq \,&2\gamma\xi_t\mathbf{1} + \chi_t\mathbf{1}, \end{align}\] where the last inequality follows from the contraction property of the operators \(\mathcal{H}\) and \(\mathcal{H}_{\tilde{\pi}_t}\) and the definitions of \(\xi_t\) and \(\chi_t\).

Combining the previous two inequalities, we have \[\begin{align} Q^{\pi_t} - Q^{\pi_{t+1}}\leq \omega_t(2\gamma\xi_t\mathbf{1} + \chi_t\mathbf{1})+\gamma\delta_t\mathbf{1}. \end{align}\] Since the right-hand side is a constant vector, we must have \[\begin{align} \delta_t=\max_{s,a}(Q^{\pi_t}(s,a) - Q^{\pi_{t+1}}(s,a))\leq \omega_t(2\gamma\xi_t + \chi_t)+\gamma\delta_t. \end{align}\] Rearranging terms, we obtain \[\begin{align} \label{eq:delta95bound} \delta_t\leq \frac{\omega_t(2\gamma\xi_t + \chi_t)}{1-\gamma}. \end{align}\tag{4}\]

4.1.1.2 Step 2: A contractive recursion.

For any \(t\geq 0\), we have by Inequality 3 that \[\begin{align} Q^* - Q^{\pi_{t+1}} &\le (1-\omega_t)(Q^* - Q^{\pi_t}) + \omega_t(Q^* - \mathcal{H}_{\tilde{\pi}_t}Q^{\pi_t}) + \gamma\delta_t\mathbf{1}. \end{align}\] To control the term \(Q^*-\mathcal{H}_{\tilde{\pi}_t}Q^{\pi_t}\), note that \[\begin{align} Q^* - \mathcal{H}_{\tilde{\pi}_t}Q^{\pi_t} &= \mathcal{H}Q^* - \mathcal{H}Q^{\pi_t} + \mathcal{H}Q^{\pi_t} - \mathcal{H}_{\tilde{\pi}_t}Q^{\pi_t}\\ &\leq\gamma\infnorm{Q^*-Q^{\pi_t}}\mathbf{1} + (2\gamma\xi_t+\chi_t)\mathbf{1}, \end{align}\] where the last inequality follows from the contraction property of \(\mathcal{H}\) and the previous bound on \(\mathcal{H}Q^{\pi_t}-\mathcal{H}_{\tilde{\pi}_t}Q^{\pi_t}\). Therefore, we have \[\begin{align} Q^* - Q^{\pi_{t+1}} \leq \,& (1-\omega_t) (Q^* - Q^{\pi_t}) + \omega_t\big(\gamma\infnorm{Q^*-Q^{\pi_t}}+ 2\gamma\xi_t + \chi_t\big)\mathbf{1} + \gamma\delta_t\mathbf{1}\\ \leq \,&(1-\omega_t) \|Q^* - Q^{\pi_t}\|_\infty\mathbf{1} + \omega_t\big(\gamma\infnorm{Q^*-Q^{\pi_t}}+ 2\gamma\xi_t + \chi_t\big)\mathbf{1} + \gamma\delta_t\mathbf{1}\\ =\,&(1-(1-\gamma)\omega_t) \|Q^* - Q^{\pi_t}\|_\infty\mathbf{1} + \omega_t\big( 2\gamma\xi_t + \chi_t\big)\mathbf{1} + \gamma\delta_t\mathbf{1}. \end{align}\] Since \(Q^* - Q^{\pi_{t+1}}\geq 0\) and the right-hand side of the previous inequality is a constant vector, we have \[\begin{align} \infnorm{Q^*-Q^{\pi_{t+1}}} \leq \,&\big(1-\omega_t(1-\gamma)\big)\infnorm{Q^*-Q^{\pi_t}} + \omega_t(2\gamma\xi_t + \chi_t) + \gamma\delta_t\\ \leq \,&\big(1-\omega_t(1-\gamma)\big) \|Q^* - Q^{\pi_t}\|_\infty + \frac{2\omega_t}{1-\gamma}\xi_t + \frac{\omega_t}{1-\gamma}\chi_t, \end{align}\] where the last inequality follows from the upper bound of \(\delta_t\) in Inequality 4 .

4.1.2 Establishing the Drift Inequality for the Squared Norm Error↩︎

The following corollary follows from Proposition [prop:actor], which is needed to combine the actor drift with the critic drift.

4.2 Analysis of the Critic↩︎

We first state the complete version of Proposition [prop:critic], with explicit expressions for all constants. Recall that \(z_t = \min\{k\geq 1\mid \max_{s\in\mathcal{S}}\mathrm{d}_{\mathrm{TV}}\big(P_{\pi_b}^{k-1}(s,\cdot),\mu_b(\cdot)\big) \leq \omega_t/2\}\) and \(K = \min\{t\in\mathbb{N}\mid t\geq z_t\}\).

4.3 Combining the Actor and Critic↩︎

4.3.1 Proof of Lemma 5↩︎

We begin by stating the complete result with the exact stepsizes and constants.

4.3.2 Solving the Recursion↩︎

The following lemma will be useful. Recall that \(K = \min\{k\in\mathbb{N}\mid k\geq z_k\}\).

To prove Theorem 1 for the IS-based critic, we first verify the conditions of Lemma 10. We begin by noting that, due to geometric mixing, \(z_t\leq \log(4/\omega_t)/\log(1/\sigma_b)+1\) is at most logarithmic in \(t\) for any of the stepsize sequences considered. It follows that \(\alpha_{t-z_t,t-1}\leq \alpha z_t/(t+h-z_t)^\eta\) is uniformly bounded over all \(t\in \mathbb{N}\). Therefore, the condition \(\alpha_{t-z_t,t-1}\leq \pi_{b,\min}^2\nu_{\min}(1-\gamma_c)/200\) can be ensured by choosing \(\alpha\) small enough for constant stepsizes, and by choosing \(h\) large enough for diminishing stepsizes with \(\eta\in(0,1]\).

We now prove the existence of the constant threshold \(\tilde{C}_r\). By choosing \(\alpha\) and \(\omega\) such that \[\begin{align} C_r &\leq \tilde{C}_{r} := \frac{(1-\gamma)^3(1-\gamma_c)\nu_{\min}}{20}, \end{align}\] the stepsize condition \(\omega_t \leq (1-\gamma)^3(1-\gamma_c)\nu_{\min}\alpha_t/20\) is satisfied for any of the stepsize sequences considered in Theorem 1. Thus, the stepsize conditions of Lemma 10, the coupled drift lemma, hold for all \(t\). Moreover, since \(\nu_{\min}\geq (1-\gamma)\pi_{b,\min}\mu_{b,\min}/(mn)\) (cf. Lemma 1), the threshold \(\tilde{C}_r\) is a constant depending only on \((n,m,p,\gamma,\pi_b)\), as claimed in Theorem 1.

We now simplify the coupled drift from Lemma 18. It follows directly from [24] that under Condition [cond:temp] with parameter \(\tau\ge 0\), we have that \(\chi_t\le \tau/(t+h)^{\eta/2}=\tau\sqrt{\omega_t/\omega}\) for all \(t\). Now note that for constant stepsizes, \(\alpha_{t-z_t,t-1}=\alpha z_t\leq2\alpha_tz_t\). For diminishing stepsizes, let \(h\) be large enough so that \(z_t\leq (t+h)/2\) for all \(t\geq K\) (possible since \(z_t\) is logarithmic in \(t\)). This implies that \[\begin{align} \alpha_{t-z_t,t-1} \leq \frac{\alpha z_t}{(t-z_t+h)^\eta} \leq\frac{\alpha z_t}{\big((t+h)/2\big)^\eta} \leq 2\alpha_tz_t. \end{align}\] The coupled drift from Lemma 10 hence reduces to \[\begin{align} \mathbb{E}\left[\|Q^*-Q^{\pi_{t+1}}\|_\infty^2 + W_{t+1}\right] &\leq \left(1-\frac{\omega_t(1-\gamma)}{2}\right) \mathbb{E}\left[\|Q^*-Q^{\pi_t}\|_\infty^2 + W_t\right] \\ &\quad+ \frac{6\tau^2\omega_t^2}{(1-\gamma)^3\omega} + \frac{216mn\alpha_t^2z_t}{(1-\gamma)^3\pi_{b,\min}^3\mu_{b,\min}}, \end{align}\] for all \(t\geq K\). Applying the above recursively yields the following for all \(T\geq K\): \[\begin{align} \mathbb{E}\left[\infnorm{Q^*-Q^{\pi_T}}^2+W_T\right] \leq&\, \mathbb{E}\left[\infnorm{Q^*-Q^{\pi_K}}^2+W_K\right] \prod_{t=K}^{T-1}\left(1-\frac{\omega_t(1-\gamma)}{2}\right)\\ &+ \frac{6\tau^2}{(1-\gamma)^3\omega} \sum_{t=K}^{T-1}\omega_t^2 \prod_{u=t+1}^{T-1}\left(1-\frac{\omega_u(1-\gamma)}{2}\right) \\ &+ \frac{216mn}{(1-\gamma)^3\pi_{b,\min}^3\mu_{b,\min}} \sum_{t=K}^{T-1}\alpha_t^2z_t \prod_{u=t+1}^{T-1}\left(1-\frac{\omega_u(1-\gamma)}{2}\right). \end{align}\] Define \(\Pi_{i,j}:=\prod_{u=i}^j\big(1-\omega_u(1-\gamma)/2\big)\). From Lemma 11 and the fact that \(z_t\leq z_T\) for all \(t\leq T\), it follows that \[\begin{align} \mathbb{E}\left[\|Q^*-Q^{\pi_{T}}\|_\infty^2 + W_{T}\right] \leq&\, \frac{3\Pi_{K,T-1}}{(1-\gamma)^2} + \frac{216mnz_{T}}{(1-\gamma)^3\pi_{b,\min}^3\mu_{b,\min}} \sum_{t=K}^{T-1}\alpha_t^2\Pi_{t+1,T-1}\\ &+ \frac{6\tau^2}{(1-\gamma)^3\omega} \sum_{t=K}^{T-1}\omega_t^2\Pi_{t+1,T-1}. \end{align}\] Note that \(\omega_t=C_r\alpha_t\) and recall the notation \(M_\mathrm{IS} = mn(1-\gamma)^{-3}\pi_{b,\min}^{-3}\mu_{b,\min}^{-1}\). Substituting this into the above gives \[\begin{align} \mathbb{E}\left[\infnorm{Q^*-Q^{\pi_T}}^2+W_T\right] \leq E_T := \frac{3\Pi_{K,T-1}}{(1-\gamma)^2} + \left(\frac{6\tau^2}{(1-\gamma)^3\omega} + \frac{216M_\mathrm{IS}z_T}{C_r^2}\right) \sum_{t=K}^{T-1}\omega_t^2\Pi_{t+1,T-1}. \label{eq:master} \end{align}\tag{8}\]

The remainder of the proof follows by bounding the term \(E_T\) for the specific stepsize sequences.

4.3.2.1 (1) Constant stepsizes.

When \(\alpha_t = \alpha\) and \(\omega_t = \omega\) for all \(t\), we have \[\begin{align} E_T &\leq \frac{3}{(1-\gamma)^2} \left(1-\frac{\omega(1-\gamma)}{2}\right)^{T-K} + \left(\frac{6\tau^2}{(1-\gamma)^3\omega} + \frac{216M_\mathrm{IS}z_\omega}{C_r^2}\right) \sum_{t=K}^{T-1}\omega^2 \left(1-\frac{\omega(1-\gamma)}{2}\right)^{T-1-t}\\ &\leq \frac{3}{(1-\gamma)^2} \left(1-\frac{\omega(1-\gamma)}{2}\right)^{T-K} + \frac{12\tau^2}{(1-\gamma)^4} + \frac{432M_\mathrm{IS}\omega z_\omega}{(1-\gamma)C_r^2}, \end{align}\] where the last step follows from the geometric sum \(\sum_{t=0}^\infty\big(1-\omega(1-\gamma)/2\big)^t = {2}/{\big(\omega(1-\gamma)\big)}\). Substituting the above into 8 proves Theorem 1 (1).

4.3.2.2 (2) Harmonic stepsizes.

When \(\alpha_t = \alpha/(t+h)\) and \(\omega_t=\omega/(t+h)\), by [7], we have \[\begin{align} E_T \leq&\, \frac{3}{(1-\gamma)^2} \left(\frac{K+h}{T+h}\right)^{\omega(1-\gamma)/2}\\ &+ \left(\frac{6\tau^2}{(1-\gamma)^3\omega} + \frac{216M_\mathrm{IS}z_T}{C_r^2}\right) \times \begin{dcases} \frac{8\omega^2}{\big(2-\omega(1-\gamma)\big)(T+h)^{\omega(1-\gamma)/2}}, & \omega < \frac{2}{1-\gamma},\\ \frac{\omega^2\log(T+h)}{T+h}, & \omega = \frac{2}{1-\gamma},\\ \frac{8e\omega^2}{\big(\omega(1-\gamma)-2\big)(T+h)}, & \omega > \frac{2}{1-\gamma}. \end{dcases} \end{align}\] Substituting the above into 8 proves Theorem 1 (2).

4.3.2.3 (3) Polynomial stepsizes.

When \(\alpha_t = \alpha/(t+h)^\eta\) and \(\omega_t = \omega/(t+h)^\eta\) for \(\eta\in (0,1)\), by [7], we have \[\begin{align} E_T \leq&\, \frac{3}{(1-\gamma)^2} \exp\left[ -\frac{\omega(1-\gamma)}{2(1-\eta)} \Big((T+h)^{1-\eta}-(K+h)^{1-\eta}\Big) \right]\\&+ \left(\frac{6\tau^2}{(1-\gamma)^3\omega} + \frac{216M_\mathrm{IS}z_T}{C_r^2}\right) \frac{8\omega}{(T+h)^\eta}. \end{align}\] Substituting the above into 8 proves Theorem 1 (3).

4.3.3 Proof of Corollary 1↩︎

Let \(\epsilon>0\) be sufficiently small. In order to ensure \(\mathbb{E}\infnorm{Q^*-Q^{\pi_t}} < \epsilon\), it suffices to ensure \(\mathbb{E}\infnorm{Q^*-Q^{\pi_t}}^2< \epsilon^2\) due to Jensen’s inequality. To that end, we consider harmonic stepsizes with \(\omega = 3/(1-\gamma) > 2/(1-\gamma)\) and \[\begin{align} \alpha = \frac{20\omega}{(1-\gamma)^3(1-\gamma_c)\nu_{\min}} = \frac{60}{(1-\gamma)^4(1-\gamma_c)\nu_{\min}}, \end{align}\] which ensures \(C_r\leq\tilde{C}_r\). Further, for sufficiently large \(h\), the condition \(\alpha_{t-z_t,t-1}\leq(1-\gamma_c)\pi_{b,\min}^2\nu_{\min}/200\) is also satisfied. Therefore, by Theorem 1, for all \(T \geq K\), \[\begin{align} \mathbb{E}\infnorm{Q^*-Q^{\pi_T}}^2 \leq&\, \frac{3}{(1-\gamma)^2}\left(\frac{K+h}{T+h}\right)^{3/2} + \frac{48e\tau^2\omega}{(1-\gamma)^3(T+h)} \\ &+ \underbrace{ \frac{9\times 60^2\times 216\times 8e \times mn}{(1-\gamma)^{11}(1-\gamma_c)^2\pi_{b,\min}^3\mu_{b,\min}\nu_{\min}^2} \frac{z_T}{T+h} }_{D_T}. \end{align}\] Observe that \(D_T\), the third term above, is asymptotically larger than the other two terms since \(z_T\) is logarithmic in \(T\). To ensure \(\mathbb{E}\infnorm{Q^*-Q^{\pi_T}}^2=\mathcal{O}(\epsilon^{2})\), it therefore suffices to have \(D_T = \mathcal{O}(\epsilon^{2})\).

We now simplify \(D_T\). From the definition of \(\gamma_c\) in Lemma 1, it follows that \(1-\gamma_c\geq {(1-\gamma)\pi_{b,\min}\mu_{b,\min}}/{2}\). Lemma 1 also gives \(\nu_{\min}\geq (1-\gamma)\pi_{b,\min}\mu_{b,\min}/(mn)\). Further, by geometric mixing, we have that \[\begin{align} z_T &\leq \frac{\log(4/\omega_T)}{\log(1/\sigma_b)}+1 \\ &= \frac{\log\big(4(1-\gamma)(T+h)/3\big)}{\log(1/\sigma_b)}+1 \\ &= \mathcal{O}\left(\frac{\log T}{\log(1/\sigma_b)}\right). \end{align}\] Substituting these bounds into the expression for \(D_T\), we obtain \[\begin{align} D_T = \mathcal{O}\left( \frac{m^3n^3}{(1-\gamma)^{15}\pi_{b,\min}^7\mu_{b,\min}^5\log(1/\sigma_b)} \frac{\log T}{T} \right). \end{align}\] Denoting the coefficient of \((\log T)/T\) in the above by \(\Lambda\), it suffices to have \((\log T)/T = \mathcal{O}\left(\epsilon^2/\Lambda\right)\). This is ensured by \[\begin{align} T &= \mathcal{O}\left(\frac{\Lambda}{\epsilon^2}\log\left(\frac{\Lambda}{\epsilon^2}\right)\right) \\ &= \mathcal{O}\left(\Lambda\frac{\log(1/\epsilon)}{\epsilon^2}\right) \\ &= \mathcal{O}\left( \frac{m^3n^3}{(1-\gamma)^{15}\pi_{b,\min}^7\mu_{b,\min}^5\log(1/\sigma_b)} \frac{\log(1/\epsilon)}{\epsilon^2} \right). \end{align}\]

4.4 Proofs of All Technical Lemmas↩︎

4.4.1 Proof of Lemma 6↩︎

By definition of the Bellman operator, for any \((s,a)\), we have \[\begin{align} [\mathcal{H}_\pi Q](s,a) =\,& \mathcal{R}(s,a) +\gamma \sum_{s'\in\mathcal{S}} p(s'\mid s,a) \sum_{a'\in\mathcal{A}} \left((1-\alpha)\pi_1(a'\mid s')+\alpha\pi_2(a'\mid s')\right)Q(s',a')\\ =\,& (1-\alpha)\left[\mathcal{R}(s,a) +\gamma \sum_{s'\in\mathcal{S}} p(s'\mid s,a) \sum_{a'\in\mathcal{A}}\pi_1(a'\mid s')Q(s',a')\right]\\ &+\alpha\left[\mathcal{R}(s,a) +\gamma \sum_{s'\in\mathcal{S}} p(s'\mid s,a) \sum_{a'\in\mathcal{A}}\pi_2(a'\mid s')Q(s',a')\right]\\ =\,& (1-\alpha)[\mathcal{H}_{\pi_1}Q](s,a) +\alpha[\mathcal{H}_{\pi_2}Q](s,a). \end{align}\]

4.4.2 Proof of Lemma 1↩︎

The following lemma will be useful in proving Lemma 1; its proof is presented in Appendix 4.4.6.

We now return to the proof of Lemma 1.

(1) By the tower property of conditional expectations and the Markov property, we have \[\begin{align} \label{eq:expression:barF} \bar{F}(Q,\pi)=(I-D)Q+D\mathcal{H}_\pi(Q), \end{align}\tag{9}\] where \(D\in\mathbb{R}^{mn\times mn}\) is the diagonal matrix with diagonal entries \(\{\mu_b(s)\pi_b(a\mid s)\}_{(s,a)\in\mathcal{S}\times \mathcal{A}}\). The existence of the weighted \(\ell_2\) norm \(\|\cdot\|_\nu\) and the contraction property then follow from [65]. In view of 9 , \(Q^\pi\) is clearly a fixed point of \(\bar{F}(\cdot,\pi)\). The fact that it is the unique fixed point follows from \(\bar{F}(\cdot,\pi)\) being a contraction mapping and the Banach fixed-point theorem [68].

(2) For any \(Q,Q'\in\mathbb{R}^{mn}\), \(y=(s_1,a_1,s_2,a_2)\in\mathcal{Y}\), and \(\pi\), we have for any \((s,a)\) that \[\begin{align} |[F_{\mathrm{IS}}(Q,y,\pi)](s,a)-[F_{\mathrm{IS}}(Q',y,\pi)](s,a)| \leq \,&(1-\mathbb{1}_{\{(s,a)=(s_1,a_1)\}})|Q(s,a)-Q'(s,a)|\\ &+\frac{\mathbb{1}_{\{(s,a)=(s_1,a_1)\}}}{\pi_{b,\min}}|Q(s_2,a_2)-Q'(s_2,a_2)|\\ \leq \,&\frac{1}{\pi_{b,\min}}\|Q-Q'\|_\infty. \end{align}\] Therefore, we have \[\begin{align} \|F_{\mathrm{IS}}(Q,y,\pi)-F_{\mathrm{IS}}(Q',y,\pi)\|_\nu \leq\,& \|F_{\mathrm{IS}}(Q,y,\pi)-F_{\mathrm{IS}}(Q',y,\pi)\|_\infty\\ \leq \,&\frac{\|Q-Q'\|_\infty}{\pi_{b,\min}}\\ \leq\,& \frac{\|Q-Q'\|_\nu}{\pi_{b,\min}\sqrt{\nu_{\min}}}. \end{align}\]

(3) For any two policies \(\pi\) and \(\pi'\), we have the following where \(\widehat{P}_\pi\) and \(\widehat{P}_{\pi'}\) denote their state-action transition probability matrices. \[\begin{align} \|\bar{F}(Q,\pi)-\bar{F}(Q,\pi')\|_\infty =\,&\|D(\mathcal{H}_\pi(Q)-\mathcal{H}_{\pi'}(Q))\|_\infty\\ =\,&\gamma \|D(\widehat{P}_\pi-\widehat{P}_{\pi'})Q\|_\infty\\ \leq \,&\gamma \|D\|_\infty\|\widehat{P}_\pi-\widehat{P}_{\pi'}\|_\infty\|Q\|_\infty\\ \leq \,&\|\widehat{P}_\pi-\widehat{P}_{\pi'}\|_\infty\|Q\|_\infty. \end{align}\] Since \[\begin{align} \|\widehat{P}_\pi-\widehat{P}_{\pi'}\|_\infty \leq \max_{s,a}\sum_{s'} p(s'\mid s,a)\|\pi(s')-\pi'(s')\|_1 \leq 2\max_{s'}\mathrm{d_{TV}}(\pi(s'),\pi'(s')), \end{align}\] we further obtain \[\begin{align} \|\bar{F}(Q,\pi)-\bar{F}(Q,\pi')\|_\infty \leq 2\|Q\|_\infty\max_{s'}\mathrm{d_{TV}}(\pi(s'),\pi'(s')). \end{align}\] The result then follows by combining the above inequality with Lemma 12 (4).

(4) For any \(Q\in\mathbb{R}^{mn}\) and \(y=(s_1, a_1, s_2, a_2)\in\mathcal{Y}\), we have \[\begin{align} &[F_{\mathrm{IS}}(Q, y, \pi_{t_1})-F_{\mathrm{IS}}(Q, y, \pi_{t_2})](s,a) \\&= \frac{\mathbb{1}_{\{(s,a)=(s_1, a_1)\}}\gamma}{\pi_{b}(a_2\mid s_2)}\big(\pi_{t_1}(a_2\mid s_2)-\pi_{t_2}(a_2\mid s_2)\big)Q(s_2, a_2). \end{align}\] Therefore, we have \[\begin{align} \|F_{\mathrm{IS}}(Q, y, \pi_{t_1})-F_{\mathrm{IS}}(Q, y, \pi_{t_2})\|_\nu &\leq \infnorm{F_{\mathrm{IS}}(Q, y, \pi_{t_1})-F_{\mathrm{IS}}(Q, y, \pi_{t_2})} \\ &\leq \frac{\gamma}{\pi_{b,\min}}\infnorm{\pi_{t_1}-\pi_{t_2}}\infnorm{Q}\\ &\leq \frac{2\max_{s}\mathrm{d_{TV}}(\pi_{t_1}(s), \pi_{t_2}(s))}{\pi_{b,\min}}\|Q\|_\infty\\ &\leq\frac{2\max_{s}\mathrm{d_{TV}}(\pi_{t_1}(s), \pi_{t_2}(s))}{\pi_{b,\min}\sqrt{\nu_{\min}}}\|Q\|_\nu. \end{align}\] The result then follows by combining the above with Lemma 12 (4).

4.4.3 Proof of Lemma 7↩︎

For any \(t\geq K\), we have \[\begin{align} &\left\langle Q_t - Q^{\pi_t}, F_\mathrm{IS}(Q_t, Y_t, \pi_{t+1}) - \bar{F}(Q_t, \pi_t) \right\rangle_\nu \nonumber\\ =& \underbrace{\left\langle Q_{t-z_t} - Q^{\pi_{t-z_t}}, F_\mathrm{IS}(Q_{t-z_t}, Y_t, \pi_{t-z_t}) - \bar{F}(Q_{t-z_t}, \pi_{t-z_t}) \right\rangle_\nu}_{T_{21}}\nonumber\\ &+ \underbrace{\left\langle Q_{t} - Q^{\pi_{t}}, F_\mathrm{IS}(Q_t, Y_t, \pi_{t+1}) - F_\mathrm{IS}(Q_{t-z_t}, Y_t, \pi_{t+1}) \right\rangle_\nu}_{T_{22}}\nonumber\\ &+\underbrace{\left\langle Q_{t} - Q^{\pi_{t}}, \bar{F}(Q_{t-z_t}, \pi_{t-z_t}) - \bar{F}(Q_{t}, \pi_{t-z_t}) \right\rangle_\nu}_{T_{23}}\nonumber\\ &+ \underbrace{\left\langle Q_{t} - Q^{\pi_{t}}, F_\mathrm{IS}(Q_{t-z_t}, Y_t ,\pi_{t+1}) - F_\mathrm{IS}(Q_{t-z_t}, Y_t, \pi_{t-z_t}) \right\rangle_\nu}_{T_{24}}\nonumber\\ &+\underbrace{\left\langle Q_{t} - Q^{\pi_{t}}, \bar{F}(Q_{t}, \pi_{t-z_t}) - \bar{F}(Q_{t}, \pi_t) \right\rangle_\nu}_{T_{25}}\nonumber\\ &+\underbrace{\left\langle (Q_{t} - Q^\pi_{t})-(Q_{t-z_t} - Q^{\pi_{t-z_t}}), F_\mathrm{IS}(Q_{t-z_t}, Y_t, \pi_{t+1}) - \bar{F}(Q_{t-z_t}, \pi_{t-z_t}) \right\rangle_\nu}_{T_{26}}.\label{eq:T295decomposition} \end{align}\tag{10}\]

We next bound each term on the right-hand side of the previous inequality.

4.4.3.1 The term \(T_{21}\).

Let \(\mathcal{F}_t\) be the sigma-algebra generated by \(\{(S_i,A_i)\}_{0\leq i\leq t}\). Since \(Q_{t-z_t}\) and \(\pi_{t-z_t}\) are \(\mathcal{F}_{t-z_t}\)-measurable, we apply the tower property to obtain \[\begin{align} \mathbb{E}T_{21} =\,& \mathbb{E}\left[\langle Q_{t-z_t}-Q^{\pi_{t-z_t}}, F_{\mathrm{IS}}(Q_{t-z_t}, Y_t, \pi_{t-z_t})-\bar F_{\mathrm{IS}}(Q_{t-z_t}, \pi_{t-z_t}) \rangle_\nu\right] \nonumber\\ =\,& \mathbb{E}\left[\langle Q_{t-z_t}-Q^{\pi_{t-z_t}}, \mathbb{E}[F_{\mathrm{IS}}(Q_{t-z_t}, Y_t, \pi_{t-z_t})|\mathcal{F}_{t-z_t}] -\bar F_{\mathrm{IS}}(Q_{t-z_t}, \pi_{t-z_t}) \rangle_\nu\right]\nonumber\\ \leq \,&\mathbb{E}\left[\|Q_{t-z_t}-Q^{\pi_{t-z_t}}\|_\nu \|\mathbb{E}[F_{\mathrm{IS}}(Q_{t-z_t}, Y_t, \pi_{t-z_t})|\mathcal{F}_{t-z_t}] -\bar F_{\mathrm{IS}}(Q_{t-z_t}, \pi_{t-z_t})\|_\nu\right]\label{eq:T2195decomposition} \end{align}\tag{11}\] To bound \(\|Q_{t-z_t}-Q^{\pi_{t-z_t}}\|_\nu\), using Lemma 12 Items (3) and (5), we have \[\begin{align} \|Q_{t-z_t}-Q^{\pi_{t-z_t}}\|_\nu \le\,& \|Q_t-Q^{\pi_t}\|_\nu + \|Q_t-Q_{t-z_t}\|_\nu + \|Q^{\pi_t}-Q^{\pi_{t-z_t}}\|_\nu\nonumber\\ \leq \,&\|Q_t-Q^{\pi_t}\|_\nu+\frac{4\alpha_{t-z_t,t-1}}{\pi_{b,\min}\sqrt{\nu_{\min}}}\|Q_{t}-Q^{\pi_{t}}\|_\nu + \frac{6\alpha_{t-z_t,t-1}}{(1-\gamma)\pi_{b,\min}\sqrt{\nu_{\min}}}+\frac{2\omega_{t-z_t,t-1}}{(1-\gamma)^2}\nonumber\\ \leq \,&2\|Q_t-Q^{\pi_t}\|_\nu + \frac{2}{1-\gamma},\label{eq:T21:term1} \end{align}\tag{12}\] where the last inequality follows from \(\alpha_{t-z_t,t-1}\leq \pi_{b,\min}^2\nu_{\min}(1-\gamma_c)/200\leq \pi_{b,\min}\sqrt{\nu_{\min}}/4\), and \(\omega_{t-z_t,t-1}\leq\alpha_{t-z_t,t-1}\leq(1-\gamma)/2\).

As for the term \(\|\mathbb{E}[F_{\mathrm{IS}}(Q_{t-z_t}, Y_t, \pi_{t-z_t})|\mathcal{F}_{t-z_t}] -\bar F_{\mathrm{IS}}(Q_{t-z_t}, \pi_{t-z_t})\|_\nu\) on the right-hand side of 11 , we have \[\begin{align} &\|\mathbb{E}[F_{\mathrm{IS}}(Q_{t-z_t}, Y_t, \pi_{t-z_t})|\mathcal{F}_{t-z_t}] -\bar F_{\mathrm{IS}}(Q_{t-z_t}, \pi_{t-z_t})\|_\nu\\ \leq \,&\max_{s\in\mathcal{S}}\sum_{y=(s_1,a_1,s_2,a_2)\in\mathcal{Y}}\left|P^{z_t-1}(s,s_1)-\mu_b(s_1)\right|\pi_b(a_1|s_1)p(s_2\mid s_1,a_1)\pi_b(a_2|s_2)\|F_{\mathrm{IS}}(Q_{t-z_t},y,\pi_{t-z_t})\|_\nu\\ \leq \,&\left(1+\frac{\|Q_{t-z_t}\|_\nu}{\pi_{b,\min}\sqrt{\nu_{\min}}}\right)\max_{s\in\mathcal{S}}\sum_{s_1\in\mathcal{S}}\left|P^{z_t-1}(s,s_1)-\mu_b(s_1)\right| (1)}\\ \leq \,&\left(1+\frac{\|Q_{t-z_t}\|_\nu}{\pi_{b,\min}\sqrt{\nu_{\min}}}\right)\omega_t. \end{align}\] Here, the last inequality follows from the definition of \(z_t\), where we recall that \(z_t = \min\{k\geq 1\mid \max_{s\in\mathcal{S}}\mathrm{d_{TV}}\big(P_{\pi_b}^{k-1}(s,\cdot), \mu_b(\cdot)\big)\leq\omega_t/2\}\), which exists and is finite due to geometric mixing.

To proceed, observe that \[\begin{align} \|Q_{t-z_t}\|_\nu\leq \,&\|Q_{t-z_t}-Q_t\|_\nu+\|Q_t-Q^{\pi_t}\|_\nu+\|Q^{\pi_t}\|_\nu\\ \leq \,&\frac{4\alpha_{t-z_t,t-1}}{\pi_{b,\min}\sqrt{\nu_{\min}}}\|Q_{t}-Q^{\pi_{t}}\|_\nu + \frac{6\alpha_{t-z_t,t-1}}{(1-\gamma)\pi_{b,\min}\sqrt{\nu_{\min}}}+\|Q_t-Q^{\pi_t}\|_\nu+\frac{1}{1-\gamma} (3)}\\ \leq \,&2\|Q_t-Q^{\pi_t}\|_\nu+\frac{5}{2(1-\gamma)}, \end{align}\] where the last inequality follows from \(\alpha_{t-z_t,t-1}\leq \pi_{b,\min}\sqrt{\nu_{\min}}/4\). Therefore, we have \[\begin{align} \|\mathbb{E}[F_{\mathrm{IS}}(Q_{t-z_t}, Y_t, \pi_{t-z_t})|\mathcal{F}_{t-z_t}] -\bar F_{\mathrm{IS}}(Q_{t-z_t}, \pi_{t-z_t})\|_\nu\leq \frac{\omega_t}{\pi_{b,\min}\sqrt{\nu_{\min}}}\left(2\|Q_t-Q^{\pi_t}\|_\nu+\frac{3}{1-\gamma}\right).\label{eq:T21:term2} \end{align}\tag{13}\] Finally, substituting 12 and 13 in 11 , we obtain \[\begin{align} \mathbb{E}T_{21}\leq \,&\frac{\omega_t}{\pi_{b,\min}\sqrt{\nu_{\min}}}\mathbb{E}\left[\left(2\|Q_t-Q^{\pi_t}\|_\nu + \frac{3}{1-\gamma}\right)^2\right]\nonumber\\ \leq \,&\frac{2\omega_t}{\pi_{b,\min}\sqrt{\nu_{\min}}}\mathbb{E}\left[4\|Q_t-Q^{\pi_t}\|_\nu^2 + \frac{9}{(1-\gamma)^2}\right]}\nonumber\\ = \,&\frac{16\omega_t}{\pi_{b,\min}\sqrt{\nu_{\min}}}\mathbb{E}W_t +\frac{18\omega_t}{\pi_{b,\min}\sqrt{\nu_{\min}}(1-\gamma)^2}.\label{eq:T2195bound} \end{align}\tag{14}\]

4.4.3.2 The term \(T_{22}+T_{23}\).

By the Cauchy-Schwarz inequality, we have \[\begin{align} T_{22}+T_{23} \leq \,& \|Q_t-Q^{\pi_t}\|_\nu \|\bar{F}(Q_{t-z_t}, \pi_{t-z_t})-\bar{F}(Q_t, \pi_{t-z_t})\|_\nu \nonumber\\ &+\|Q_t-Q^{\pi_t}\|_\nu \|F_{\mathrm{IS}}(Q_t, Y_t, \pi_{t+1})-F_{\mathrm{IS}}(Q_{t-z_t}, Y_t, \pi_{t+1})\|_\nu\label{eq:T2243T23} \end{align}\tag{15}\] Since \(\bar{F}(\cdot,\pi_{t-z_t})\) is a contraction mapping with respect to \(\|\cdot\|_\nu\) (cf. Lemma 1 (1)), we have \[\begin{align} \|\bar{F}(Q_{t-z_t}, \pi_{t-z_t})-\bar{F}(Q_t, \pi_{t-z_t})\|_\nu\leq \|Q_t-Q_{t-z_t}\|_\nu. \end{align}\] Since \(F_{\mathrm{IS}}(\cdot,y,\pi)\) is Lipschitz continuous with respect to \(\|\cdot\|_\nu\) (cf. Lemma 1 (2)), we have \[\begin{align} \|F_{\mathrm{IS}}(Q_t, Y_t, \pi_{t+1})-F_{\mathrm{IS}}(Q_{t-z_t}, Y_t, \pi_{t+1})\|_\nu\leq \,&\frac{1}{\pi_{b,\min}\sqrt{\nu_{\min}}} \|Q_t-Q_{t-z_t}\|_\nu. \end{align}\] Substituting the previous two inequalities in 15 , we obtain \[\begin{align} T_{22}+T_{23}\leq \,&\frac{2}{\pi_{b,\min}\sqrt{\nu_{\min}}}\|Q_t-Q^{\pi_t}\|_\nu \|Q_t-Q_{t-z_t}\|_\nu\nonumber\\ \leq \,&\frac{4\alpha_{t-z_t,t-1}}{\pi_{b,\min}^2\nu_{\min}}\|Q_t-Q^{\pi_t}\|_\nu\left(2\|Q_{t}-Q^{\pi_{t}}\|_\nu + \frac{3}{1-\gamma}\right) (3)}\nonumber\\ = \,&\frac{4\alpha_{t-z_t,t-1}}{\pi_{b,\min}^2\nu_{\min}}\left(2\|Q_{t}-Q^{\pi_{t}}\|_\nu^2 + \frac{3}{1-\gamma}\|Q_t-Q^{\pi_t}\|_\nu\right)\nonumber\\ \leq \,&\frac{4\alpha_{t-z_t,t-1}}{\pi_{b,\min}^2\nu_{\min}}\left(2\|Q_{t}-Q^{\pi_{t}}\|_\nu^2 +\|Q_t-Q^{\pi_t}\|_\nu^2+\frac{9}{4(1-\gamma)^2}\right)\nonumber\\ =\,&\frac{24\alpha_{t-z_t,t-1}}{\pi_{b,\min}^2\nu_{\min}}W_t+\frac{9\alpha_{t-z_t,t-1}}{\pi_{b,\min}^2\nu_{\min}(1-\gamma)^2}.\label{eq:T222395bound} \end{align}\tag{16}\]

4.4.3.3 The term \(T_{24}+T_{25}\).

By the Cauchy-Schwarz inequality, we have \[\begin{align} T_{24}+T_{25}\leq \,&\|Q_t-Q^{\pi_t}\|_\nu \|\bar{F}(Q_t, \pi_{t-z_t}) - \bar{F}(Q_t, \pi_t)\|_\nu\nonumber\\ &+\|Q_t-Q^{\pi_t}\|_\nu\|{F}(Q_{t-z_t}, Y_t, \pi_{t+1}) - {F}(Q_{t-z_t}, Y_t, \pi_{t-z_t}) \|_\nu\label{eq:T2425:decomposition} \end{align}\tag{17}\] For the term \(\|\bar{F}(Q_t, \pi_{t-z_t}) - \bar{F}(Q_t, \pi_t)\|_\nu\) on the right-hand side of 17 , we have by Lemma 1 (3) that \[\begin{align} \|\bar{F}(Q_t, \pi_{t-z_t}) - \bar{F}(Q_t, \pi_t)\|_\nu\leq\,&\|\bar{F}(Q_t, \pi_{t-z_t}) - \bar{F}(Q_t, \pi_t)\|_\infty\\ \leq \,&2\omega_{t-z_t,t-1}\|Q_t\|_\infty\\ \leq \,&2\omega_{t-z_t,t-1}\left(\|Q_t-Q^{\pi_t}\|_\infty+\|Q^{\pi_t}\|_\infty\right)\\ \leq \,&2\omega_{t-z_t,t-1}\left(\frac{1}{\sqrt{\nu_{\min}}}\|Q_t-Q^{\pi_t}\|_\nu+\frac{1}{1-\gamma}\right) \end{align}\] For the term \(\|{F}(Q_{t-z_t}, Y_t, \pi_{t+1}) - {F}(Q_{t-z_t}, Y_t, \pi_{t-z_t}) \|_\nu\) on the right-hand side of 17 , we have by Lemma 1 (4) and Lemma 12 (3) that \[\begin{align} \|{F}(Q_{t-z_t}, Y_t, \pi_{t+1}) - {F}(Q_{t-z_t}, Y_t, \pi_{t-z_t}) \|_\nu\leq \,& \|{F}(Q_{t-z_t}, Y_t, \pi_{t+1}) - {F}(Q_{t-z_t}, Y_t, \pi_{t-z_t}) \|_\infty\\ \leq&\, \frac{2\omega_{t-z_t, t}}{\pi_{b,\min}}\|Q_{t-z_t}\|_\infty\\ \leq \,&\frac{2\omega_{t-z_t, t}}{\pi_{b,\min}}\left(2\|Q_t-Q^{\pi_t}\|_\infty + \frac{3}{1-\gamma}\right)\\ \leq \,&\frac{2\omega_{t-z_t, t}}{\pi_{b,\min}}\left(\frac{2\|Q_t-Q^{\pi_t}\|_\nu}{\sqrt{\nu_{\min}}} + \frac{3}{1-\gamma}\right). \end{align}\] Substituting the previous two inequalities in 17 , we obtain \[\begin{align} T_{24}+T_{25}\leq \,&\frac{2\omega_{t-z_t, t}}{\pi_{b,\min}}\|Q_t-Q^{\pi_t}\|_\nu\left[\frac{3}{\sqrt{\nu_{\min}}}\|Q_t-Q^{\pi_t}\|_\nu+\frac{4}{1-\gamma}\right]\nonumber\\ =\,&\frac{2\omega_{t-z_t, t}}{\pi_{b,\min}}\left[\frac{3}{\sqrt{\nu_{\min}}}\|Q_t-Q^{\pi_t}\|_\nu^2+\frac{4}{1-\gamma}\|Q_t-Q^{\pi_t}\|_\nu\right]\nonumber\\ \leq \,&\frac{2\omega_{t-z_t, t}}{\pi_{b,\min}}\left[\frac{3}{\sqrt{\nu_{\min}}}\|Q_t-Q^{\pi_t}\|_\nu^2+\frac{1}{\sqrt{\nu_{\min}}}\|Q_t-Q^{\pi_t}\|_\nu^2+\frac{4\sqrt{\nu_{\min}}}{(1-\gamma)^2}\right]\nonumber\\ \leq \,&\frac{16\omega_{t-z_t, t}}{\pi_{b,\min}\sqrt{\nu_{\min}}}W_t+\frac{8\omega_{t-z_t, t}}{\pi_{b,\min}(1-\gamma)^2}.\label{eq:T242595bound} \end{align}\tag{18}\]

4.4.3.4 The term \(T_{26}\).

By the Cauchy–Schwarz inequality, we have \[\begin{align} \label{eq:T2595breakup} T_{26} \le\,& \left\| (Q_t - Q^{\pi_t}) - (Q_{t-z_t}-Q^{\pi_{t-z_t}}) \right\|_\nu \; \left\| F_{\mathrm{IS}}(Q_{t-z_t}, Y_t, \pi_{t+1}) - \bar F_{\mathrm{IS}}(Q_{t-z_t}, \pi_{t-z_t}) \right\|_\nu\nonumber\\ \leq \,&\big(\| Q_t - Q_{t-z_t}\|_\nu+\|Q^{\pi_t}-Q^{\pi_{t-z_t}}) \|_\nu\big) \; \left\|F_{\mathrm{IS}}(Q_{t-z_t}, Y_t, \pi_{t+1}) - \bar F_{\mathrm{IS}}(Q_{t-z_t}, \pi_{t-z_t})\right\|_\nu \end{align}\tag{19}\] For the first term on the right-hand side of 19 , we have by Lemma 12 (3) and (5) that \[\begin{align} \|Q_t-Q_{t-z_t}\|_\nu + \|Q^{\pi_t}-Q^{\pi_{t-z_t}}\|_\nu \le\,& \frac{4\alpha_{t-z_t,t-1}}{\pi_{b,\min}\sqrt{\nu_{\min}}} \|Q_t-Q^{\pi_t}\|_\nu + \frac{6\alpha_{t-z_t,t-1}}{(1-\gamma)\pi_{b,\min}\sqrt{\nu_{\min}}} + \frac{2\omega_{t-z_t,t-1}}{(1-\gamma)^2}.\label{eq:T2595first95factor} \end{align}\tag{20}\] For the second term on the right-hand side of 19 , we have by Lemma 12 (1) and (2) that \[\begin{align} \|F_{\mathrm{IS}}(Q_{t-z_t}, Y_t, \pi_{t+1}) - \bar F_{\mathrm{IS}}(Q_{t-z_t}, \pi_{t-z_t})\|_\nu &\leq \|F_{\mathrm{IS}}(Q_{t-z_t}, Y_t, \pi_{t+1})\|_\nu+\|\bar{F}(Q_{t-z_t}, \pi_{t-z_t})\|_\nu \nonumber\\ &\le 2 + \frac{\|Q_{t-z_t}\|_\nu}{\pi_{b,\min}\sqrt{\nu_{\min}}} + \|Q_{t-z_t}\|_\nu \nonumber\\ &\le 2 + \frac{3\|Q_{t-z_t}\|_\nu}{2\pi_{b,\min}\sqrt{\nu_{\min}}}\leq 1/2}\nonumber\\ &\le 2 + \frac{3}{2\pi_{b,\min}\sqrt{\nu_{\min}}}\left(\frac{3}{1-\gamma}+2\|Q_t-Q^{\pi_t}\|_\nu\right)\nonumber\\ &\leq \frac{3\|Q_t-Q^{\pi_t}\|_\nu}{\pi_{b,\min}\sqrt{\nu_{\min}}} + \frac{5}{(1-\gamma)\pi_{b,\min}\sqrt{\nu_{\min}}}. \label{T2595second95factor} \end{align}\tag{21}\] Substituting the bounds 20 and 21 in 19 , since \(\omega_t\leq \alpha_t(1-\gamma)\) and \(\pi_{b,\min}\leq 1/2\), we have \[\begin{align} T_{26}\leq \,&\left(\frac{4\alpha_{t-z_t,t-1}}{\pi_{b,\min}\sqrt{\nu_{\min}}} \|Q_t-Q^{\pi_t}\|_\nu + \frac{6\alpha_{t-z_t,t-1}}{(1-\gamma)\pi_{b,\min}\sqrt{\nu_{\min}}} + \frac{2\omega_{t-z_t,t-1}}{(1-\gamma)^2}\right)\nonumber\\ &\times \left(\frac{3\|Q_t-Q^{\pi_t}\|_\nu}{\pi_{b,\min}\sqrt{\nu_{\min}}} + \frac{5}{(1-\gamma)\pi_{b,\min}\sqrt{\nu_{\min}}}\right)\nonumber\\ \leq \,&\alpha_{t-z_t,t-1}\left(\frac{4}{\pi_{b,\min}\sqrt{\nu_{\min}}} \|Q_t-Q^{\pi_t}\|_\nu + \frac{7}{(1-\gamma)\pi_{b,\min}\sqrt{\nu_{\min}}}\right)^2\nonumber\\ \leq \,&\frac{64\alpha_{t-z_t,t-1}}{\pi_{b,\min}^2\nu_{\min}} W_t + \frac{98\alpha_{t-z_t,t-1}}{(1-\gamma)^2\pi_{b,\min}^2\nu_{\min}},\label{eq:T2695bound} \end{align}\tag{22}\] where the last line follows from \((a+b)^2\leq 2(a^2+b^2)\).

4.4.3.5 Combining everything together.

Substituting 14 , 16 , 18 and 22 in 10 , we obtain \[\begin{align} \mathbb{E}\left\langle Q_t - Q^{\pi_t}, F_{\mathrm{IS}}(Q_t, Y_t, \pi_{t+1}) - \bar{F}(Q_t, \pi_t) \right\rangle\leq \,&\frac{16\omega_t}{\pi_{b,\min}\sqrt{\nu_{\min}}}\mathbb{E}W_t +\frac{18\omega_t}{\pi_{b,\min}\sqrt{\nu_{\min}}(1-\gamma)^2}\\ &+\frac{24\alpha_{t-z_t,t-1}}{\pi_{b,\min}^2\nu_{\min}}\mathbb{E}W_t+\frac{9\alpha_{t-z_t,t-1}}{\pi_{b,\min}^2\nu_{\min}(1-\gamma)^2}\\ &+\frac{16\omega_{t-z_t, t}}{\pi_{b,\min}\sqrt{\nu_{\min}}}\mathbb{E}W_t+\frac{8\omega_{t-z_t, t}}{\pi_{b,\min}(1-\gamma)^2}\\ &+\frac{64\alpha_{t-z_t,t-1}}{\pi_{b,\min}^2\nu_{\min}} \mathbb{E}W_t + \frac{98\alpha_{t-z_t,t-1}}{(1-\gamma)^2\pi_{b,\min}^2\nu_{\min}}\\ \leq \,&\frac{90\alpha_{t-z_t,t-1}}{\pi_{b,\min}^2\nu_{\min}} \mathbb{E}W_t + \frac{100\alpha_{t-z_t,t-1}}{(1-\gamma)^2\pi_{b,\min}^2\nu_{\min}}, \end{align}\] where the last inequality follows from \[\begin{align} \omega_t\leq \frac{\alpha_{t-1,t-z_t}}{16\pi_{b,\min}\sqrt{\nu_{\min}}}, \end{align}\] which itself is a consequence of the stepsize condition \(\omega_t\leq (1-\gamma)^3(1-\gamma_c)\nu_{\min}\alpha_t/20\). It now follows that \[\begin{align} \mathbb{E}T_2\leq \frac{90\alpha_t\alpha_{t-z_t,t-1}}{\pi_{b,\min}^2\nu_{\min}} \mathbb{E}W_t + \frac{100\alpha_t\alpha_{t-z_t,t-1}}{(1-\gamma)^2\pi_{b,\min}^2\nu_{\min}}. \end{align}\]

4.4.4 Proof of Lemma 8↩︎

The following lemma will be useful in proving Lemma 8; its proof is presented in Appendix 4.4.7.

Returning to the proof of Lemma 8, observe that \[\begin{align} T_3 =\,&\langle Q_t - Q^{\pi_t}, Q^{\pi_t}-Q^{\pi_{t+1}}\rangle_\nu\nonumber\\ \leq \,&\|Q_t - Q^{\pi_t}\|_\nu \|Q^{\pi_t}-Q^{\pi_{t+1}}\|_\nu\nonumber\\ \leq \,& \|Q_t - Q^{\pi_t}\|_\nu \|Q^{\pi_t}-Q^{\pi_{t+1}}\|_\infty\nonumber\\ \leq \,&\frac{\omega_t}{1-\gamma} \|Q_t-Q^{\pi_t}\|_\nu \left(2\|Q_t-Q^{\pi_t}\|_\infty+ \|Q^*-Q^{\pi_t}\|_\infty+ \chi_t \right)}\nonumber\\ \leq \,&\frac{\omega_t}{1-\gamma} \|Q_t-Q^{\pi_t}\|_\nu \left(\frac{2}{\sqrt{\nu_{\min}}}\|Q_t-Q^{\pi_t}\|_\nu+ \|Q^*-Q^{\pi_t}\|_\infty+ \chi_t \right)\nonumber\\ =\,&\frac{4\omega_t}{(1-\gamma)\sqrt{\nu_{\min}}}W_t+\frac{\omega_t}{1-\gamma} \|Q_t-Q^{\pi_t}\|_\nu \|Q^*-Q^{\pi_t}\|_\infty+\frac{\omega_t}{1-\gamma} \|Q_t-Q^{\pi_t}\|_\nu \chi_t.\label{T25} \end{align}\tag{23}\]

To proceed, note that by the AM-GM inequality, we have for any \(C_1,C_2>0\) that \[\begin{align} \|Q_t-Q^{\pi_t}\|_\nu \|Q^*-Q^{\pi_t}\|_\infty &\le \frac{C_1}{2} \|Q_t-Q^{\pi_t}\|_\nu^2 + \frac{1}{2C_1} \|Q^*-Q^{\pi_t}\|_\infty^2, \\ \|Q_t-Q^{\pi_t}\|_\nu \chi_t &\le \frac{C_2}{2} \|Q_t-Q^{\pi_t}\|_\nu^2 + \frac{1}{2C_2} \chi_t^2. \end{align}\] Substituting the above in 23 yields \[\begin{align} T_3 \le\,& \frac{\omega_t}{1-\gamma} \Bigg( \left( \frac{2}{\sqrt{\nu_{\min}}} + \frac{C_1}{2} + \frac{C_2}{2} \right) \|Q_t-Q^{\pi_t}\|_\nu^2 + \frac{1}{2C_1} \|Q^*-Q^{\pi_t}\|_\infty^2 + \frac{1}{2C_2} \chi_t^2 \Bigg)\\ =\,& \frac{\omega_t}{1-\gamma} \Bigg( \left( \frac{4}{\sqrt{\nu_{\min}}} + C_1 + C_2 \right) W_t + \frac{1}{2C_1} \|Q^*-Q^{\pi_t}\|_\infty^2 + \frac{1}{2C_2} \chi_t^2 \Bigg)\\ =\,&\frac{8\omega_t}{(1-\gamma)^3\sqrt{\nu_{\min}}}W_t+\frac{1-\gamma}{4}\omega_t\|Q^*-Q^{\pi_t}\|_\infty^2+\frac{1-\gamma}{4}\omega_t\chi_t^2, \end{align}\] where the last inequality follows by choosing \(C_1=C_2=2/(1-\gamma)^2\).

4.4.5 Proof of Lemma 9↩︎

Observe that \[T_4 = \frac{1}{2} \|(Q_{t+1}-Q_t)+(Q^{\pi_t}-Q^{\pi_{t+1}})\|_\nu^2 \le \|Q_{t+1}-Q_t\|_\nu^2 + \|Q^{\pi_t}-Q^{\pi_{t+1}}\|_\nu^2.\label{26}\tag{24}\] For the first term on the right-hand side of 24 , the IS-based critic update, that \[\begin{align} \|Q_{t+1}-Q_t\|_\nu^2 =\,& \alpha_t^2\nu_{(S_t,A_t)} \big(\mathcal{R}(S_t,A_t) + \gamma\rho_{t+1}Q_t(S_{t+1},A_{t+1}) - Q_t(S_t,A_t)\big)^2\nonumber\\ \leq \,&\alpha_t^2 \left(1 + \frac{1}{\pi_{b,\min}}\|Q_t\|_\infty + \|Q_t\|_\infty\right)^2\nonumber\\ \leq \,&\alpha_t^2 \left(1 + \frac{3}{2\pi_{b,\min}}\|Q_t\|_\infty \right)^2\leq 1/2}\nonumber\\ \leq \,&\alpha_t^2 \left(1 + \frac{3}{2\pi_{b,\min}}\|Q_t-Q^{\pi_t}\|_\infty +\frac{3}{2\pi_{b,\min}}\|Q^{\pi_t}\|_\infty\right)^2\nonumber\\ \leq \,&\alpha_t^2 \left(1 + \frac{3}{2\pi_{b,\min}\sqrt{\nu_{\min}}}\|Q_t-Q^{\pi_t}\|_\nu +\frac{3}{2\pi_{b,\min}(1-\gamma)}\right)^2\nonumber\\ \leq \,&\alpha_t^2 \left( \frac{3}{2\pi_{b,\min}\sqrt{\nu_{\min}}}\|Q_t-Q^{\pi_t}\|_\nu +\frac{2}{\pi_{b,\min}(1-\gamma)}\right)^2\leq 1/2}\nonumber\\ \leq \,& \frac{9\alpha_t^2}{\pi_{b,\min}^2\nu_{\min}}W_t +\frac{8\alpha_t^2}{\pi_{b,\min}^2(1-\gamma)^2}.\label{28} \end{align}\tag{25}\]

For the second term on the right-hand side of 24 , we have by Lemma 13 that \[\begin{align} \|Q^{\pi_t}-Q^{\pi_{t+1}}\|_\nu^2 \le\,& \|Q^{\pi_t}-Q^{\pi_{t+1}}\|_\infty^2\nonumber\\ \le\,& \frac{\omega_t^2}{(1-\gamma)^2}\left(\|Q^*-Q^{\pi_t}\|_\infty + 2\|Q_t-Q^{\pi_t}\|_\infty + \chi_t\right)^2\nonumber\\ \le\,& \frac{\omega_t^2}{(1-\gamma)^2}\left(\|Q^*-Q^{\pi_t}\|_\infty + \frac{2}{\sqrt{\nu_{\min}}}\|Q_t-Q^{\pi_t}\|_\nu + \chi_t\right)^2\nonumber\\ =\,&\frac{24\omega_t^2}{\nu_{\min}(1-\gamma)^2}W_t+\frac{3\omega_t^2}{(1-\gamma)^2}\|Q^*-Q^{\pi_t}\|_\infty^2 + \frac{3\omega_t^2\chi_t^2}{(1-\gamma)^2},\label{29} \end{align}\tag{26}\] where the last inequality follows from \((a+b+c)^2\leq 3(a^2+b^2+c^2)\) for any \(a,b,c\in\mathbb{R}\).

Substituting the two bounds 25 and 26 in 24 yields the desired result.

4.4.6 Proof of Lemma 12↩︎

(1) By definition of the operator \(F_\mathrm{IS}\), for any \(Q \in \mathbb{R}^{mn}\), \(y = (s_1,a_1,s_2,a_2) \in \mathcal{Y}\), and policy \(\pi\in{(\Delta^m)}^n\), we have for any \((s,a)\) that \[\begin{align} \left|[F_{\mathrm{IS}}(Q, y, \pi)](s,a)\right|\leq \,&(1-\mathbb{1}_{\{(s,a)= (s_1,a_1)\}})|Q(s,a)|\\ &+\mathbb{1}_{\{(s,a)=(s_1,a_1)\}}\left|\mathcal{R}(s_1,a_1) + \gamma\frac{\pi(a_2\mid s_2)}{\pi_b(a_2\mid s_2)}Q(s_2,a_2)\right|\\ \leq \,&(1-\mathbb{1}_{\{(s,a)= (s_1,a_1)\}})\|Q\|_\infty+\mathbb{1}_{\{(s,a)=(s_1,a_1)\}}\left(1+ \frac{1}{\pi_{b,\min}}\|Q\|_\infty\right)\\ \leq \,&1+ \frac{1}{\pi_{b,\min}}\|Q\|_\infty. \end{align}\] It follows that \[\begin{align} \|F_{\mathrm{IS}}(Q, y, \pi)\|_\infty \leq 1+ \frac{1}{\pi_{b,\min}}\|Q\|_\infty. \end{align}\] Since \(\|\cdot\|_\nu \leq \|\cdot\|_\infty \leq \|\cdot\|_\nu/\sqrt{\nu_{\min}}\), we have \[\begin{align} \|F_{\mathrm{IS}}(Q, y, \pi)\|_\nu \leq 1+ \frac{1}{\pi_{b,\min}\sqrt{\nu_{\min}}}\|Q\|_\nu. \end{align}\]

(2) For any policy \(\pi\), since \(\bar{F}(\cdot,\pi)\) is a contraction mapping with respect to \(\|\cdot\|_\nu\) (cf. Lemma 1), we have \[\begin{align} \|\bar{F}(Q, \pi)\|_\nu &\le \|\bar{F}(0, \pi)\|_\nu + \|\bar{F}(Q, \pi_{t+1})-\bar{F}(0, \pi)\|_\nu\\ &\le \|\bar{F}(0, \pi)\|_\nu+ \|Q\|_\nu\\ &\leq 1+\|Q\|_\nu, \end{align}\] where the last inequality follows from \(\|\bar{F}(0, \pi)\|_\nu\leq 1\).

(3) The first two inequalities are direct consequences of [7]. Since \[\begin{align} \|Q_{t_1} - Q_{t_2}\|_\nu \le\,& 4\alpha_{t_1,t_2-1} + \frac{4\alpha_{t_1,t_2-1}}{\pi_{b,\min}\sqrt{\nu_{\min}}} \|Q_{t_2}\|_\nu\\ \le\,& 4\alpha_{t_1,t_2-1} + \frac{4\alpha_{t_1,t_2-1}}{\pi_{b,\min}\sqrt{\nu_{\min}}} \|Q_{t_2} - Q^{\pi_{t_2}}\|_\nu + \frac{4\alpha_{t_1,t_2-1}}{\pi_{b,\min}\sqrt{\nu_{\min}}} \|Q^{\pi_{t_2}}\|_\nu\\ \leq \,& \frac{4\alpha_{t_1,t_2-1}}{\pi_{b,\min}\sqrt{\nu_{\min}}} \|Q_{t_2} - Q^{\pi_{t_2}}\|_\nu + \frac{6\alpha_{t_1,t_2-1}}{\pi_{b,\min}\sqrt{\nu_{\min}}(1-\gamma)},\leq 1/2} \end{align}\] we obtain the third inequality. The fourth inequality follows by an identical argument.

Using the triangle inequality, we have $$\begin{align}
\|Q_{t_1}\|_\nu
\le\,&
\|Q_{t_1}-Q_{t_2}\|_\nu
+
\|Q_{t_2}-Q^{\pi_{t_2}}\|_\nu
+
\|Q^{\pi_{t_2}}\|_\nu\\
\leq \,&\frac{4\alpha_{t_1,t_2-1}}{\pi_{b,\min}\sqrt{\nu_{\min}}}
\|Q_{t_2} - Q^{\pi_{t_2}}\|_\nu
+
\frac{6\alpha_{t_1,t_2-1}}{\pi_{b,\min}\sqrt{\nu_{\min}}(1-\gamma)}
+\|Q_{t_2} - Q^{\pi_{t_2}}\|_\nu
+\frac{1}{1-\gamma}\\
\leq \,&2\|Q_{t_2} - Q^{\pi_{t_2}}\|_\nu
+\frac{3}{1-\gamma},
\end{align}$$ where the last inequality follows from
$\alpha_{t_1,t_2-1}\leq \pi_{b,\min}\sqrt{\nu_{\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\in\mathcal{S}\) that \[\begin{align} \mathrm{d_{TV}}\big(\pi_{t_1}(s),\pi_{t_2}(s)\big) = \frac{1}{2}\max_s\|\pi_{t_1}(s)-\pi_{t_2}(s)\|_1 \leq \frac{1}{2}\max_s\sum_{t=t_1}^{t_2-1}\|\pi_{t+1}(s)-\pi_t(s)\|_1. \end{align}\] Since \(\|\pi_{t+1}(s)-\pi_t(s)\|_1=\omega_t\|\tilde{\pi}_t(s)-\pi_t(s)\|_1\leq 2\omega_t\), we have \[\begin{align} \max_{s\in\mathcal{S}}\mathrm{d_{TV}}(\pi_{t_1}(s),\pi_{t_2}(s)) \leq \omega_{t_1,t_2-1}. \end{align}\]

(5) Using the Bellman equations for \(Q^{\pi_{t_1}}\) and \(Q^{\pi_{t_2}}\), we have \[\begin{align} \|Q^{\pi_{t_1}} - Q^{\pi_{t_2}}\|_\infty &= \|\mathcal{H}_{\pi_{t_1}}Q^{\pi_{t_1}} - \mathcal{H}_{\pi_{t_2}}Q^{\pi_{t_2}}\|_\infty \\ &\le \|\mathcal{H}_{\pi_{t_1}}Q^{\pi_{t_1}} - \mathcal{H}_{\pi_{t_1}}Q^{\pi_{t_2}}\|_\infty + \|\mathcal{H}_{\pi_{t_1}}Q^{\pi_{t_2}} - \mathcal{H}_{\pi_{t_2}}Q^{\pi_{t_2}}\|_\infty \\ &\le \gamma \|Q^{\pi_{t_1}} - Q^{\pi_{t_2}}\|_\infty + \|\mathcal{H}_{\pi_{t_1}}Q^{\pi_{t_2}} - \mathcal{H}_{\pi_{t_2}}Q^{\pi_{t_2}}\|_\infty. \end{align}\] Rearranging terms, we obtain the following where \(\widehat{P}_\pi\) denotes the state-action transition probability matrix under policy \(\pi\): \[\begin{align} \|Q^{\pi_{t_1}} - Q^{\pi_{t_2}}\|_\infty \le\,& \frac{1}{1-\gamma} \|\mathcal{H}_{\pi_{t_1}}Q^{\pi_{t_2}} - \mathcal{H}_{\pi_{t_2}}Q^{\pi_{t_2}}\|_\infty\\ =\,&\frac{\gamma}{1-\gamma} \|(\widehat{P}_{\pi_{t_1}}-\widehat{P}_{\pi_{t_2}})Q^{\pi_{t_2}}\|_\infty\\ \leq \,&\frac{1}{(1-\gamma)^2} \|\widehat{P}_{\pi_{t_1}}-\widehat{P}_{\pi_{t_2}}\|_\infty \end{align}\]

Since
$$\begin{align} \|\widehat{P}_{\pi_{t_1}}-\widehat{P}_{\pi_{t_2}}\|_\infty=\,&\max_{s,a}\sum_{s'}p(s'\mid s,a)\sum_{a'}\left|\pi_{t_1}(a'\mid s')-\pi_{t_2}(a'\mid s')\right|\\ = \,&2\max_{s,a}\sum_{s'}p(s'\mid s,a)\mathrm{d_{TV}}(\pi_{t_1}(s'),\pi_{t_2}(s'))\\ \leq \,&2\omega_{t_1-1,t_2},
\end{align}$$ where the last inequality follows from Item (6) of
this lemma, we have
$$\begin{align} \|Q^{\pi_{t_1}} - Q^{\pi_{t_2}}\|_\infty\leq \frac{2\omega_{t_1,t_2-1}}{(1-\gamma)^2}.
\end{align}$$

4.4.7 Proof of Lemma 13↩︎

Recall that \(\delta_t =\max_{s,a}\big(Q^{\pi_{t}}(s,a)-Q^{\pi_{t+1}}(s,a)\big)\). Let \(\delta_t'= \max_{s,a} \big(Q^{\pi_{t+1}}(s,a) - Q^{\pi_t}(s,a)\big)\). Then, we have \(\|Q^{\pi_t}-Q^{\pi_{t+1}}\|_\infty= \max(\delta_t,\delta_t')\).

For \(\delta_t\), we have shown in 4 that \[\begin{align} \label{eq1:lem:target95shift} \delta_t \le \frac{2\omega_t}{1-\gamma} \|Q_t-Q^{\pi_t}\|_\infty + \omega_t\frac{\chi_t}{1-\gamma}. \end{align}\tag{27}\]

To bound \(\delta_t'\), by the monotonicity and translation invariance of the Bellman operator \(\mathcal{H}_{\pi_{t+1}}\), we have \[\begin{align} Q^{\pi_{t+1}} = \mathcal{H}_{\pi_{t+1}} Q^{\pi_{t+1}} \le \mathcal{H}_{\pi_{t+1}}(Q^{\pi_t} + \delta_t' \mathbf{1}) = \mathcal{H}_{\pi_{t+1}} Q^{\pi_t} + \gamma \delta_t' \mathbf{1}. \label{eq:initial95improvement95bound} \end{align}\tag{28}\] To further bound \(\mathcal{H}_{\pi_{t+1}} Q^{\pi_t}\), observe that \[\begin{align} \mathcal{H}_{\pi_{t+1}} Q^{\pi_t} =\,& (1 - \omega_t) Q^{\pi_t} + \omega_t \mathcal{H}_{\tilde{\pi}_t} Q^{\pi_t} }\\ \leq\,& (1 - \omega_t) Q^{\pi_t} + \omega_t \mathcal{H} Q^{\pi_t} _{\tilde{\pi}_t} Q^{\pi_t} \leq \mathcal{H} Q^{\pi_t}}\\ \leq\,& (1 - \omega_t) Q^{\pi_t} + \omega_t \mathcal{H} Q^*Q^{\pi_t} \leq \mathcal{H} Q^*}\\ =\,& Q^{\pi_t} + \omega_t (Q^* - Q^{\pi_t})Q^* = Q^*}. \end{align}\] Combining the previous inequality with 28 , yields \(\delta_t' \leq \omega_t \|Q^* - Q^{\pi_t}\|_\infty + \gamma \delta_t'\). Rearranging terms, we obtain \[\begin{align} \label{eq2:lem:target95shift} \delta_t' \leq \frac{\omega_t \|Q^* - Q^{\pi_t}\|_\infty}{1 - \gamma}. \end{align}\tag{29}\]

In view of 27 and 29 , we have \[\begin{align} \|Q^{\pi_t}-Q^{\pi_{t+1}}\|_\infty = \max(\delta_t,\delta_t') \leq \delta_t + \delta_t' = \frac{\omega_t}{1-\gamma}\left(\|Q^*-Q^{\pi_t}\|_\infty + 2\|Q_t-Q^{\pi_t}\|_\infty + \chi_t\right). \end{align}\]

5 Proof of Theorem 1 with the ETD-Based Critic↩︎

5.1 Analysis of the Actor↩︎

We begin by stating the actor drift inequalities.

The following corollary follows, and is needed to combine the actor drift with a drift inequality for the critic.

Since our actor analysis methodology is agnostic of the critic choice, the statements for Proposition [prop:actor95ETD] and Corollary 3, along with their proofs, are identical to those of Proposition [prop:actor] and Corollary 2, which are proved in Appendix 4.1. We hence omit the proofs here.

5.2 Analysis of the Critic↩︎

We begin by reformulating the ETD-based critic update as a stochastic approximation algorithm. For any \(t\geq 0\), let \(\{U_t\}\) be a stochastic process defined as \(U_t=(S_t,A_t,S_{t+1})\). It is clear that \(\{U_t\}\) is a Markov chain with a finite state space, denoted by \(\mathcal{U}\). Moreover, under Assumption 1, the Markov chain \(\{U_t\}\) admits a unique stationary distribution, denoted by \(\mu_U\), which satisfies \(\mu_U(s_1,a_1,s_2)=\mu_b(s_1)\pi_b(a_1|s_1)p(s_2|s_1,a_1)\). Let \(F_\mathrm{ETD}:\mathbb{R}^{mn}\times \mathcal{U}\times {(\Delta^{m})}^n\to \mathbb{R}^{mn}\) be an operator such that given inputs \(Q \in \mathbb{R}^{mn}\), \(u = (s_1,a_1,s_2) \in \mathcal{U}\) and \(\pi\in{(\Delta^{m})}^n\), the \((s,a)\)-th component of the output is defined as \[\begin{align} [F_\mathrm{ETD}(Q,u,\pi)](s,a) =&\mathbb{1}_{\{ (s,a)= (s_1,a_1)\}}\left(\mathcal{R}(s_1,a_1) + \gamma \sum_{a\in\mathcal{A}}\pi(a|s_2) Q(s_2,a)\right)+\mathbb{1}_{\{ (s,a)\neq (s_1,a_1)\}}Q(s,a). \end{align}\] The critic update in Algorithm 1, Line 8, under the ETD-based critic choice, can now be written compactly as \[\begin{align} Q_{t+1} = Q_t + \alpha_t \bigl(F_\mathrm{ETD}(Q_t, U_t, \pi_{t+1}) - Q_t\bigr). \end{align}\]

Recall the operator \(\bar{F}:\mathbb{R}^{mn}\times{(\Delta^{m})}^n\to\mathbb{R}^{mn}\) defined in Section 2.3.2 as \(\bar{F}(Q,\pi) = \mathbb{E}_{Y\sim\mu_Y}F_\mathrm{IS}(Q,Y,\pi)\), where we recall that \(\mu_Y\) is the stationary distribution of the Markov chain \(\{Y_t\}\) defined as \(Y_t =(U_t,A_{t+1})\), which satisfies \(\mu_Y(s_1,a_1,s_2,a_2) = \mu_U(s_1,a_1,s_2)\pi_{b}(a_2\mid s_2)\). We claim that \(\mathbb{E}_{U\sim\mu_U}F_\mathrm{ETD}(Q,U,\pi) = \bar{F}(Q,\pi)\), implying that the expected operators for both the updates coincide. To see this, note that for \(U = (s_1,a_1,s_2), Y = (u,a_2)\), we have \[\begin{align} \bar{F}(Q,\pi) =\,& \mathbb{E}_{Y\sim\mu_Y}\left[\mathbb{1}_{\{ (s,a)= (s_1,a_1)\}}\left(\mathcal{R}(s_1,a_1) + \gamma \frac{\pi(a_2|s_2)}{\pi_b(a_2|s_2)} Q(s_2,a_2)\right)+\mathbb{1}_{\{ (s,a)\neq (s_1,a_1)\}}Q(s,a)\right]\\ =\,& \mathbb{E}_{U\sim\mu_U}\Bigg[\mathbb{1}_{\{ (s,a)= (s_1,a_1)\}}\left(\mathcal{R}(s_1,a_1) + \gamma \mathbb{E}_{a_2\sim\pi_{b}(\cdot\mid s_2)}\left[ \frac{\pi(a_2|s_2)}{\pi_b(a_2|s_2)} Q(s_2,a_2)\right]\right)\Bigg]\\ &+\mathbb{E}_{U\sim\mu_{U}}\big[\mathbb{1}_{\{ (s,a)\neq (s_1,a_1)\}}Q(s,a)\big]\\ =\,& \mathbb{E}_{U\sim\mu_U}\Big[\mathbb{1}_{\{ (s,a)= (s_1,a_1)\}}\big(\mathcal{R}(s_1,a_1) + \gamma \mathbb{E}_{a_2\sim\pi(\cdot\mid s_2)}Q(s_2,a_2)\big)\Big]\\ &+\mathbb{E}_{U\sim\mu_{U}}\big[\mathbb{1}_{\{ (s,a)\neq (s_1,a_1)\}}Q(s,a)\big]\\ =\,&\mathbb{E}_{U\sim\mu_{U}}F_\mathrm{ETD}(Q,U,\pi). \end{align}\]

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 \(\bar{F}(Q,\pi_t)=Q\).

Next, we present several key properties of \(F_\mathrm{ETD}\) and \(\bar{F}\) that facilitate the convergence analysis. In particular, we show that the equation \(\bar{F}(Q,\pi_t)=Q\) admits \(Q^{\pi_t}\) as its unique solution, and that \(\bar{F}(\cdot,\pi)\) is a contractive operator with respect to a weighted \(\ell_2\) norm. The proof of the following result is provided in Appendix 5.4.4.

We now state and prove the drift inequality for the ETD-based critic. Recall that \(z_t = \min\{k\geq 1\mid \max_{s\in\mathcal{S}}\mathrm{d}_{\mathrm{TV}}\big(P_{\pi_b}^{k-1}(s,\cdot),\mu_b(\cdot)\big) \leq \omega_t/2\}\) and \(K = \min\{t\in\mathbb{N}\mid t\geq z_t\}\).

5.3 Combining the Actor and the Critic↩︎

We begin with a coupled drift inequality for the combined actor and critic error.

5.3.1 Solving the Recursion↩︎

To prove Theorem 1 for the ETD-based critic, we first verify the conditions for Lemma 18 by showing the existence of the constant threshold \(\tilde{C}_r\). By choosing \(\alpha,\omega\) such that \[\begin{align} C_r\leq \tilde{C}_r := \frac{(1-\gamma)^3(1-\gamma_c)\nu_{\min}}{16}, \end{align}\] the condition \(\omega_t\leq(1-\gamma)^3(1-\gamma_c)\nu_{\min}\alpha_t/16\) is satisfied for any of the stepsize sequences considered in Theorem 1. Thus, the stepsize conditions of Lemma 18, the coupled drift lemma, hold for all \(t\). Moreover, note that since \(\nu_{\min}\geq(1-\gamma)\pi_{b,\min}\mu_{b,\min}/(mn)\) (cf. Lemma 14), the threshold \(\tilde{C}_r\) is a constant depending only on \((n,m,p,\gamma,\pi_b)\), as claimed in Theorem 1.

We now simplify the coupled drift from Lemma 18. It follows directly from [24] that under Condition [cond:temp] with parameter \(\tau\ge 0\), we have that \(\chi_t\le \tau/(t+h)^{\eta/2}=\tau\sqrt{\omega_t/\omega}\) for all \(t\). Now note that for constant stepsizes, \(\alpha_{t-z_t,t-1}=\alpha z_t\leq2\alpha_tz_t\). For diminishing stepsizes, let \(h\) be large enough so that \(z_t\leq (t+h)/2\) for all \(t\geq K\) (possible since \(z_t\) is logarithmic in \(t\)). This implies that \[\begin{align} \alpha_{t-z_t,t-1} \leq \frac{\alpha z_t}{(t-z_t+h)^\eta} \leq\frac{\alpha z_t}{\big((t+h)/2\big)^\eta} \leq 2\alpha_tz_t. \end{align}\] The coupled drift from Lemma 18 hence reduces to \[\begin{align} \mathbb{E}\left[\|Q^*-Q^{\pi_{t+1}}\|_\infty^2 + W_{t+1}\right] &\le \left(1-\frac{\omega_t(1-\gamma)}{2}\right) \mathbb{E}\left[\|Q^*-Q^{\pi_t}\|_\infty^2 + W_t\right] + \frac{6\tau^2\omega_t^2}{(1-\gamma)^3\omega} + \frac{14\alpha_t^2z_t}{(1-\gamma)^2}, \end{align}\]

for all \(t\geq K\). Applying the above repeatedly, we have for all \(T\geq K\), that \[\begin{align} \mathbb{E}\left[\infnorm{Q^*-Q^{\pi_T}}^2+W_T\right] \leq& \mathbb{E}\left[\infnorm{Q^*-Q^{\pi_K}}^2+W_K\right]\prod_{t=K}^{T-1}\left(1-\frac{\omega_t(1-\gamma)}{2}\right)\\ &+ \frac{6\tau^2}{(1-\gamma)^3\omega}\sum_{t=K}^{T-1}\omega_t^2\prod_{u=t+1}^{T-1}\left(1-\frac{\omega_u(1-\gamma)}{2}\right) \\ &+ \frac{14}{(1-\gamma)^2}\sum_{t=K}^{T-1}\alpha_t^2z_t\prod_{u=t+1}^{T-1}\left(1-\frac{\omega_u(1-\gamma)}{2}\right). \end{align}\] We define notation \(\Pi_{i,j}:=\prod_{u=i}^j\big(1-\omega_u(1-\gamma)/2\big)\). Since \(z_t\leq z_T\) for all \(t\leq T\), it follows that \[\begin{align} \mathbb{E}\left[\|Q^*-Q^{\pi_{T}}\|_\infty^2 + W_{T}\right] \le& \mathbb{E}\left[\infnorm{Q^*-Q^{\pi_K}}^2+W_K\right]\Pi_{K,T-1} + \frac{7z_{T}}{(1-\gamma)^2}\sum_{t=K}^{T-1}\alpha_t^2\Pi_{t+1,T-1}\nonumber\\ &+ {\frac{6\tau^2}{(1-\gamma)^3\omega}\sum_{t=K}^{T-1}\omega_t^2\Pi_{t+1,T-1}}\nonumber\\ \leq&\frac{3\Pi_{K,T-1}}{2(1-\gamma)^2} + \frac{14z_{T}}{(1-\gamma)^2}\sum_{t=K}^{T-1}\alpha_t^2\Pi_{t+1,T-1}+{\frac{6\tau^2}{(1-\gamma)^3\omega}\sum_{t=K}^{T-1}\omega_t^2\Pi_{t+1,T-1}}\label{eq:little95master95ETD}, \end{align}\tag{32}\] where the last line follows since \[\begin{align} \infnorm{Q^*-Q^{\pi_K}}^2+W_K &= \infnorm{Q^*-Q^{\pi_K}}^2+\frac{1}{2}\|Q_K-Q^{\pi_K}\|_\nu^2\\ &\leq \frac{1}{(1-\gamma)^2}+\frac{1}{2(1-\gamma)^2}\\ &=\frac{3}{2(1-\gamma)^2}, \end{align}\] which in turn, holds since \(Q_t(s,a)\in[0,1/(1-\gamma)]\) for all \((s,a)\) (cf. Lemma 20 (2)).

Now note that \(\omega_t=C_r\alpha_t\) and recall the notation \(M_\mathrm{ETD} = (1-\gamma)^{-2}\). Substituting in 32 , we have \[\mathbb{E}\left[\infnorm{Q^*-Q^{\pi_T}}^2+W_T\right] \leq E_T:= \frac{3\Pi_{K,T-1}}{2(1-\gamma)^2} + \left(\frac{6\tau^2}{(1-\gamma)^3\omega}+\frac{14M_\mathrm{ETD}z_T}{C_r^2}\right)\sum_{t=K}^{T-1}\omega_t^2\Pi_{t+1,T-1}.\label{eq:master95ETD}\tag{33}\]

The remainder of the proof follows by bounding the term \(E_T\) for the specific stepsizes.

5.3.1.1 (1) Constant stepsizes.

When \(\alpha_t = \alpha\) and \(\omega_t = \omega\) for all \(t\), we have, \[\begin{align} E_T &\leq \frac{3}{2(1-\gamma)^2}\left(1-\frac{\omega(1-\gamma)}{2}\right)^{T-K}+\left(\frac{6\tau^2}{(1-\gamma)^3\omega}+\frac{7M_\mathrm{ETD}z_\omega}{C_r^2}\right)\sum_{t=K}^{T-1}\omega^2\left(1-\frac{\omega(1-\gamma)}{2}\right)^{T-1-t}\\ &\leq \frac{3}{2(1-\gamma)^2}\left(1-\frac{\omega(1-\gamma)}{2}\right)^{T-K}+\frac{12\tau^2}{(1-\gamma)^4}+\frac{28M_\mathrm{ETD}\omega z_\omega}{(1-\gamma)C_r^2}, \end{align}\] where the last step follows from the geometric sum \(\sum_{t=0}^\infty\big(1-\omega(1-\gamma)/2\big)^t = {2}/{\big(\omega(1-\gamma)\big)}\). Substituting the above in 33 proves Theorem 1 (1).

5.3.1.2 (2) Harmonic stepsizes.

When \(\alpha_t = \alpha/(t+h)\) and \(\omega_t=\omega/(t+h)\), we have by [7] that \[\begin{align} E_T \leq& \frac{3}{2(1-\gamma)^2}\left(\frac{K+h}{T+h}\right)^{\omega(1-\gamma)/2}\\ &+ \left(\frac{6\tau^2}{(1-\gamma)^3\omega}+\frac{14M_\mathrm{ETD}z_T}{C_r^2}\right)\times\begin{dcases} \frac{8\omega^2}{\big(2-\omega(1-\gamma)\big)(T+h)^{\omega(1-\gamma)/2}} & \omega < \frac{2}{1-\gamma},\\ \frac{\omega^2\log(T+h)}{T+h} & \omega = \frac{2}{1-\gamma},\\ \frac{8e\omega^2}{\big(\omega(1-\gamma)-2\big)(T+h)} & \omega > \frac{2}{1-\gamma}. \end{dcases} \end{align}\] Substituting the above in 33 proves Theorem 1 (2).

5.3.1.3 (3) Polynomial stepsizes.

When \(\alpha_t = \alpha/(t+h)^\eta\) and \(\omega_t = \omega/(t+h)^\eta\) for \(\eta\in (0,1)\), we have by [7] that \[\begin{align} E_T\leq& \frac{3}{2(1-\gamma)^2}\exp\left[-\frac{\omega(1-\gamma)}{2(1-\eta)}\Big((T+h)^{1-\eta}-(K+h)^{1-\eta}\Big)\right] \\ &+ \left(\frac{6\tau^2}{(1-\gamma)^3\omega}+\frac{14M_\mathrm{ETD}z_T}{C_r^2}\right)\frac{8\omega}{(T+h)^\eta}. \end{align}\] Substituting the above in 33 proves Theorem 1 (3).

5.3.2 Proof of Corollary 1↩︎

Let \(\epsilon>0\) be sufficiently small. In order to ensure \(\mathbb{E}\infnorm{Q^*-Q^{\pi_t}} < \epsilon\), it suffices to ensure \(\mathbb{E}\infnorm{Q^*-Q^{\pi_t}}^2< \epsilon^2\) due to Jensen’s inequality. To that end, we consider harmonic stepsizes with \(\omega = 3/(1-\gamma) > 2/(1-\gamma)\) and \[\begin{align} \alpha = \frac{16\omega}{(1-\gamma)^3(1-\gamma_c)\nu_{\min}} = \frac{48}{(1-\gamma)^4(1-\gamma_c)\nu_{\min}}, \end{align}\] which ensures \(C_r\leq\tilde{C}_r\). We have by Theorem 1 that for all \(T \geq K\), \[\begin{align} \mathbb{E}\infnorm{Q^*-Q^{\pi_T}}^2 \leq \frac{3}{(1-\gamma)^2}\left(\frac{K+h}{T+h}\right)^{3/2} + \frac{48e\tau^2\omega}{(1-\gamma)^3(T+h)}+ \underbrace{\frac{9\times 48^2 \times 216 \times 8e}{(1-\gamma)^{10}(1-\gamma_c)^2\nu_{\min}^2}\frac{z_T}{T+h}}_{D_T}. \end{align}\] Observe also that \(D_T\), the third term in the above, is asymptotically larger than the other two terms as \(z_T\) is logarithmic in \(T\). For having \(\mathbb{E}\infnorm{Q^*-Q^{\pi_T}}^2=\mathcal{O}(\epsilon^{2})\), it hence suffices to have \(D_T = \mathcal{O}(\epsilon^{2})\).

We shall now simplify \(D_T\). From the definition of \(\gamma_c\) in Lemma 14, it follows that \(1-\gamma_c\geq {(1-\gamma)\pi_{b,\min}\mu_{b,\min}}/{2}\). Lemma 14 also gives us that \(\nu_{\min}\geq (1-\gamma)\pi_{b,\min}\mu_{b,\min}/(mn)\). Further, we have by geometric mixing, that \[\begin{align} z_T &\leq \frac{\log(4/\omega_T)}{\log(1/\sigma_b)}+1 \\ &= \frac{\log\big(4(1-\gamma)(T+h)/3\big)}{\log(1/\sigma_b)}+1 \\ &= \mathcal{O}\left(\frac{\log T}{\log(1/\sigma_b)}\right). \end{align}\] Substituting these bounds in the expression for \(D_T\), we have that \[\begin{align} D_T = \mathcal{O}\left(\frac{m^2n^2}{(1-\gamma)^{14}\pi_{b,\min}^4\mu_{b,\min}^4\log(1/\sigma_b)}\frac{\log T}{T}\right). \end{align}\] Denoting the coefficient of \((\log T)/T\) in the above by \(\Lambda\), it suffices to have \((\log T)/T = \mathcal{O}\left(\epsilon^2/\Lambda\right)\). This is ensured by \[\begin{align} T &= \mathcal{O}\left(\frac{\Lambda}{\epsilon^2}\log\left(\frac{\Lambda}{\epsilon^2}\right)\right) \\ &= \mathcal{O}\left(\Lambda\frac{\log(1/\epsilon)}{\epsilon^2}\right) \\ &= \mathcal{O}\left(\frac{m^2n^2}{(1-\gamma)^{14}\pi_{b,\min}^4\mu_{b,\min}^4\log(1/\sigma_b)}\frac{\log(1/\epsilon)}{\epsilon^2}\right). \end{align}\]

5.4 Proofs of All Technical Lemmas↩︎

The following two lemmas will be used extensively.

The statement and the proof of the above are identical to Lemma 13, which is proved in Appendix 4.4.7. We hence omit the proof here.

The proof of Lemma 20 is presented in Appendix 5.4.3.

5.4.1 Proof of Lemma 15↩︎

For any \(t\geq K\), we have \[\begin{align} &\left\langle Q_t - Q^{\pi_t}, F_\mathrm{ETD}(Q_t, U_t, \pi_{t+1}) - \bar{F}(Q_t, \pi_t) \right\rangle_\nu \nonumber\\ =& \underbrace{\left\langle Q_{t-z_t} - Q^{\pi_{t-z_t}}, F_\mathrm{ETD}(Q_{t-z_t}, U_t, \pi_{t-z_t}) - \bar{F}(Q_{t-z_t}, \pi_{t-z_t}) \right\rangle_\nu}_{T_{21}}\nonumber\\ &+ \underbrace{\left\langle Q_{t} - Q^{\pi_{t}}, F_\mathrm{ETD}(Q_t, U_t, \pi_{t+1}) - F_\mathrm{ETD}(Q_{t-z_t}, U_t, \pi_{t+1}) \right\rangle_\nu}_{T_{22}}\nonumber\\ &+\underbrace{\left\langle Q_{t} - Q^{\pi_{t}}, \bar{F}(Q_{t-z_t}, \pi_{t-z_t}) - \bar{F}(Q_{t}, \pi_{t-z_t}) \right\rangle_\nu}_{T_{23}}\nonumber\\ &+ \underbrace{\left\langle Q_{t} - Q^{\pi_{t}}, F_\mathrm{ETD}(Q_{t-z_t}, U_t ,\pi_{t+1}) - F_\mathrm{ETD}(Q_{t-z_t}, U_t, \pi_{t-z_t}) \right\rangle_\nu}_{T_{24}}\nonumber\\ &+\underbrace{\left\langle Q_{t} - Q^{\pi_{t}}, \bar{F}(Q_{t}, \pi_{t-z_t}) - \bar{F}(Q_{t}, \pi_t) \right\rangle_\nu}_{T_{25}}\nonumber\\ &+\underbrace{\left\langle (Q_{t} - Q^\pi_{t})-(Q_{t-z_t} - Q^{\pi_{t-z_t}}), F_\mathrm{ETD}(Q_{t-z_t}, U_t, \pi_{t+1}) - \bar{F}(Q_{t-z_t}, \pi_{t-z_t}) \right\rangle_\nu}_{T_{26}}.\label{eq:T295decomposition95ETD} \end{align}\tag{34}\]

We next bound each term on the right-hand side of the previous inequality.

5.4.1.1 The term \(T_{21}\).

Let \(\mathcal{F}_t\) be the sigma-algebra generated by \(\{(S_i,A_i)\}_{0\leq i\leq t}\). Since \(Q_{t-z_t}\) and \(\pi_{t-z_t}\) are \(\mathcal{F}_{t-z_t}\)-measurable, we apply the tower property to obtain \[\begin{align} \mathbb{E}T_{21} =\,& \mathbb{E}\left[\langle Q_{t-z_t}-Q^{\pi_{t-z_t}}, F_{\mathrm{ETD}}(Q_{t-z_t}, U_t, \pi_{t-z_t})-\bar{F}(Q_{t-z_t}, \pi_{t-z_t}) \rangle_\nu\right] \nonumber\\ =\,& \mathbb{E}\left[\langle Q_{t-z_t}-Q^{\pi_{t-z_t}}, \mathbb{E}[F_\mathrm{ETD}(Q_{t-z_t}, U_t, \pi_{t-z_t})|\mathcal{F}_{t-z_t}] -\bar{F}(Q_{t-z_t}, \pi_{t-z_t}) \rangle_\nu\right]\nonumber\\ \leq \,&\mathbb{E}\left[\|Q_{t-z_t}-Q^{\pi_{t-z_t}}\|_\nu \|\mathbb{E}[F_\mathrm{ETD}(Q_{t-z_t}, U_t, \pi_{t-z_t})|\mathcal{F}_{t-z_t}] -\bar{F}(Q_{t-z_t}, \pi_{t-z_t})\|_\nu\right]\label{eq:T2195decomposition95ETD} \end{align}\tag{35}\] Since \(Q_{t-z_t}(s,a)\in[0,1/(1-\gamma)]\) for all \((s,a)\) (cf. Lemma 20, (2)), we have that \(\|Q_{t-z_t}-Q^{\pi_{t-z_t}}\|_\nu \leq 1/(1-\gamma)\).

As for the term \(\|\mathbb{E}[F_{\mathrm{IS}}(Q_{t-z_t}, Y_t, \pi_{t-z_t})|\mathcal{F}_{t-z_t}] -\bar F_{\mathrm{IS}}(Q_{t-z_t}, \pi_{t-z_t})\|_\nu\) on the right-hand side of 35 , we have \[\begin{align} &\|\mathbb{E}[F_{\mathrm{ETD}}(Q_{t-z_t}, Y_t, \pi_{t-z_t})|\mathcal{F}_{t-z_t}] -\bar{F}(Q_{t-z_t}, \pi_{t-z_t})\|_\nu\\ \leq \,&\max_{s\in\mathcal{S}}\sum_{y=(s_1,a_1,s_2,a_2)}\left|P^{z_t-1}(s,s_1)-\mu_b(s_1)\right|\pi_b(a_1|s_1)p(s_2\mid s_1,a_1)\pi_b(a_2|s_2)\|F_{\mathrm{ETD}}(Q_{t-z_t},y,\pi_{t-z_t})\|_\infty\\ \leq \,&\big(1+\gamma\|Q_{t-z_t}\|_\infty\big)\max_{s\in\mathcal{S}}\sum_{s_1\in\mathcal{S}}\left|P^{z_t-1}(s,s_1)-\mu_b(s_1)\right| (1)}\\ \leq& \frac{1}{1-\gamma} \max_{s\in\mathcal{S}}\sum_{s_1\in\mathcal{S}}\left|P^{z_t-1}(s,s_1)-\mu_b(s_1)\right| (2)} \\ \leq \,&\frac{\omega_t}{1-\gamma}, \end{align}\] where the last inequality follows from the definition of \(z_t\), where we recall that \(z_t = \min\{k\geq 1\mid \max_{s\in\mathcal{S}}\mathrm{d_{TV}}\big(P_{\pi_b}^{k-1}(s,\cdot), \mu_b(\cdot)\big)\leq\omega_t/2\}\), which exists and is finite due to geometric mixing.

Substituting in 35 , we have \[\begin{align} \mathbb{E}T_{21}\leq \,&\frac{\omega_t}{(1-\gamma)^2}.\label{eq:T2195bound95ETD} \end{align}\tag{36}\]

5.4.1.2 The term \(T_{22}+T_{23}\).

By the Cauchy-Schwarz inequality, we have \[\begin{align} T_{22}+T_{23} \leq \,& \|Q_t-Q^{\pi_t}\|_\nu \|\bar{F}(Q_{t-z_t}, \pi_{t-z_t})-\bar{F}(Q_t, \pi_{t-z_t})\|_\nu \nonumber\\ &+\|Q_t-Q^{\pi_t}\|_\nu \|F_{\mathrm{ETD}}(Q_t, U_t, \pi_{t+1})-F_{\mathrm{ETD}}(Q_{t-z_t}, U_t, \pi_{t+1})\|_\nu\label{eq:T2243T2395ETD} \end{align}\tag{37}\] Since \(\bar{F}(\cdot,\pi_{t-z_t})\) is a contraction mapping with respect to \(\|\cdot\|_\infty\) (cf. Lemma 14 (1)), we have \[\begin{align} \|\bar{F}(Q_{t-z_t}, \pi_{t-z_t})-\bar{F}(Q_t, \pi_{t-z_t})\|_\nu &\leq \|\bar{F}(Q_{t-z_t}, \pi_{t-z_t})-\bar{F}(Q_t, \pi_{t-z_t})\|_\infty\\ &\leq \|Q_t-Q_{t-z_t}\|_\infty\\ &\leq \frac{\alpha_{t-z_t,t-1}}{1-\gamma} , (3)}. \end{align}\] Since \(F_{\mathrm{ETD}}(\cdot,y,\pi)\) is \(1\)-Lipschitz continuous with respect to \(\|\cdot\|_\infty\) (cf. Lemma 14), we similarly have \[\begin{align} \|F_{\mathrm{ETD}}(Q_t, U_t, \pi_{t+1})-F_{\mathrm{ETD}}(Q_{t-z_t}, U_t, \pi_{t+1})\|_\nu\leq \frac{\alpha_{t-z_t,t-1}}{1-\gamma}. \end{align}\] Substituting the previous two inequalities in 37 , we obtain \[\begin{align} T_{22}+T_{23}\leq \,&\frac{2\alpha_{t-z_t,t-1}}{1-\gamma}\|Q_t-Q^{\pi_t}\|_\nu \nonumber\\ \leq \,&\frac{2\alpha_{t-z_t,t-1}}{(1-\gamma)^2},\label{eq:T222395bound95ETD} \end{align}\tag{38}\] where the last inequality follows since \(Q^{\pi_t}(s,a)\in[0,1/(1-\gamma)]\) for all \((s,a)\) (cf. Lemma 20, (2)).

5.4.1.3 The term \(T_{24}+T_{25}\).

By the Cauchy-Schwarz inequality, we have \[\begin{align} T_{24}+T_{25}\leq \,&\|Q_t-Q^{\pi_t}\|_\nu \|\bar{F}(Q_t, \pi_{t-z_t}) - \bar{F}(Q_t, \pi_t)\|_\nu\nonumber\\ &+\|Q_t-Q^{\pi_t}\|_\nu\|F_\mathrm{ETD}(Q_{t-z_t}, U_t, \pi_{t+1}) - F_\mathrm{ETD}(Q_{t-z_t}, U_t, \pi_{t-z_t}) \|_\nu\label{eq:T2425:decomposition95ETD} \end{align}\tag{39}\] For the term \(\|\bar{F}(Q_t, \pi_{t-z_t}) - \bar{F}(Q_t, \pi_t)\|_\nu\) on the right-hand side of 39 , we have by Lemma 14 (3), that \[\begin{align} \|\bar{F}(Q_t, \pi_{t-z_t}) - \bar{F}(Q_t, \pi_t)\|_\nu\leq\,&\|\bar{F}(Q_t, \pi_{t-z_t}) - \bar{F}(Q_t, \pi_t)\|_\infty\\ \leq \,&2\omega_{t-z_t,t-1}\|Q_t\|_\infty\\ \leq \,&\frac{2\omega_{t-z_t,t-1}}{1-\gamma}, \end{align}\] where the last inequality follows since \(\infnorm{Q_t}\leq1/(1-\gamma)\) (cf. Lemma 20, (2)).

For the term \(\|F_\mathrm{ETD}(Q_{t-z_t}, U_t, \pi_{t+1}) - F_\mathrm{ETD}(Q_{t-z_t}, U_t, \pi_{t-z_t}) \|_\nu\) on the right-hand side of 39 , we similarly have by Lemma 14 (4), that \[\begin{align} \|F_\mathrm{ETD}(Q_{t-z_t}, U_t, \pi_{t+1}) - F_\mathrm{ETD}(Q_{t-z_t}, U_t, \pi_{t-z_t}) \|_\nu\leq \frac{2\omega_{t-z_t,t}}{1-\gamma}. \end{align}\]

Substituting the previous two inequalities in 39 , we obtain \[\begin{align} T_{24}+T_{25}\leq \,&\frac{2\omega_{t-z_t, t}}{1-\gamma}\|Q_t-Q^{\pi_t}\|_\nu\nonumber\\ \leq & \frac{2\omega_{t-z_t,t}}{(1-\gamma)^2},\label{eq:T242595bound95ETD} \end{align}\tag{40}\] where the last line follows since \(Q_t(s,a)\in[0,1/(1-\gamma)]\) for all \((s,a)\) (cf. Lemma 20 (2)).

5.4.1.4 The term \(T_{26}\).

By the Cauchy–Schwarz inequality, we have \[\begin{align} \label{eq:T2595breakup95ETD} T_{26} \le\,& \left\| (Q_t - Q^{\pi_t}) - (Q_{t-z_t}-Q^{\pi_{t-z_t}}) \right\|_\nu \; \left\| F_\mathrm{ETD}(Q_{t-z_t}, Y_t, \pi_{t+1}) - \bar{F}(Q_{t-z_t}, \pi_{t-z_t}) \right\|_\nu\nonumber\\ \leq \,&\big(\| Q_t - Q_{t-z_t}\|_\nu+\|Q^{\pi_t}-Q^{\pi_{t-z_t}}) \|_\nu\big) \; \left\|F_\mathrm{ETD}(Q_{t-z_t}, Y_t, \pi_{t+1}) - \bar{F}(Q_{t-z_t}, \pi_{t-z_t})\right\|_\nu \end{align}\tag{41}\] For the first term on the right-hand side of 41 , we have by Lemma 20 (3) and (5) that \[\begin{align} \|Q_t-Q_{t-z_t}\|_\nu + \|Q^{\pi_t}-Q^{\pi_{t-z_t}}\|_\nu \le\,&\|Q_t-Q_{t-z_t}\|_\infty + \|Q^{\pi_t}-Q^{\pi_{t-z_t}}\|_\infty\nonumber\\ \leq &\frac{\alpha_{t-z_t,t-1}}{1-\gamma} + \frac{2\omega_{t-z_t,t-1}}{(1-\gamma)^2}.\label{eq:T2595first95factor95ETD} \end{align}\tag{42}\] For the second term on the right-hand side of 41 , we have by Lemma 20 (1), that \[\begin{align} &\|F_\mathrm{ETD}(Q_{t-z_t}, U_t, \pi_{t+1}) - \bar{F}(Q_{t-z_t}, \pi_{t-z_t})\|_\nu \\&\leq \|F_\mathrm{ETD}(Q_{t-z_t}, U_t, \pi_{t+1})\|_\infty+\|\bar{F}(Q_{t-z_t}, \pi_{t-z_t})\|_\infty \nonumber\\ &\le 2 + 2\gamma\infnorm{Q_{t-z_t}}\nonumber\\ &\leq \frac{2}{1-\gamma}, \label{T2595second95factor95ETD} \end{align}\tag{43}\] where the last line follows since \(\infnorm{Q_{t-z_t}}\leq 1/(1-\gamma)\) (cf. Lemma 20 (2)).

Substituting the bounds 42 and 43 in 41 , we have \[\begin{align} T_{26}\leq \,&\frac{2\alpha_{t-z_t,t-1}}{(1-\gamma)^2}+\frac{4\omega_{t-z_t,t-1}}{(1-\gamma)^3}.\label{eq:T2695bound95ETD} \end{align}\tag{44}\]

5.4.1.5 Combining everything together.

Substituting 36 , 38 , 40 and 44 in 34 , we obtain \[\begin{align} \mathbb{E}\left\langle Q_t - Q^{\pi_t}, F_\mathrm{ETD}(Q_t, Y_t, \pi_{t+1}) - \bar{F}(Q_t, \pi_t) \right\rangle\leq \,&\frac{\omega_t}{(1-\gamma)^2} + \frac{2\alpha_{t-z_t,t-1}}{(1-\gamma)^2} + \frac{2\omega_{t-z_t,t}}{(1-\gamma)^2}\\ &+\frac{2\alpha_{t-z_t,t-1}}{(1-\gamma)^2}+\frac{2\omega_{t-z_t,t-1}}{(1-\gamma)^3}\\ &\leq \frac{5\alpha_{t-z_t,t-1}}{(1-\gamma)^2}, \end{align}\] where the last inequality follows from the stepsize condition \(\omega_t\leq (1-\gamma)^3(1-\gamma_c)\nu_{\min}\alpha_t/16\). It now follows that \[\begin{align} \mathbb{E}T_2\leq \frac{5\alpha_t\alpha_{t-z_t,t-1}}{(1-\gamma)^2}. \end{align}\]

5.4.2 Proof of Lemma 17↩︎

Observe that \[\begin{align} T_4 &= \frac{1}{2} \|(Q_{t+1}-Q_t)+(Q^{\pi_t}-Q^{\pi_{t+1}})\|_\nu^2\\ &\le \|Q_{t+1}-Q_t\|_\infty^2 + \|Q^{\pi_t}-Q^{\pi_{t+1}}\|_\infty^2\\ &\leq \frac{\alpha_t^2}{(1-\gamma)^2} + \frac{4\omega_t^2}{(1-\gamma)^4}(3) and (5)}\\ &\leq \frac{2\alpha_t^2}{(1-\gamma)^2} \alpha_t/16}. \end{align}\]

5.4.3 Proof of Lemma [lem:running95bounds95ETD]↩︎

(1) By definition of the operator \(F_\mathrm{ETD}\), for any \(Q \in \mathbb{R}^{mn}\), \(u = (s_1,a_1,s_2) \in \mathcal{U}\), and \(\pi\), we have for any \((s,a)\) that \[\begin{align} \left|[F_{\mathrm{ETD}}(Q, y, \pi)](s,a)\right|\leq \,&(1-\mathbb{1}_{\{(s,a)= (s_1,a_1)\}})|Q(s,a)|\\ &+\mathbb{1}_{\{(s,a)=(s_1,a_1)\}}\left|\mathcal{R}(s_1,a_1) + \gamma\sum_{a\in\mathcal{A}}\pi(a_\mid s_2)Q(s_2,a)\right|\\ \leq \,&(1-\mathbb{1}_{\{(s,a)= (s_1,a_1)\}})\|Q\|_\infty+\mathbb{1}_{\{(s,a)=(s_1,a_1)\}}\left(1+ \gamma\|Q\|_\infty\right)\\ \leq \,&1+ \gamma\|Q\|_\infty. \end{align}\] It follows that \[\begin{align} \|F_{\mathrm{ETD}}(Q, u, \pi)\|_\infty \leq 1+ \|Q\|_\infty. \end{align}\]

Since
$\bar{F}(Q,\pi)=\mathbb{E}_{U\sim\mu_U}F_\mathrm{ETD}(Q,U,\pi)$, it
follows immediately from the above that $$\begin{align}
\|\bar{F}(Q,\pi)\|_\infty \leq 1+ \|Q\|_\infty.
\end{align}$$

(2) We proceed via induction. Clearly \(Q_{0}(s,a)=0\in[0,1/(1-\gamma)]\) for all \((s,a)\). If \(Q_{t}(s,a)\in[0,1/(1-\gamma)]\) for all \((s,a)\) for some \(t\geq 0\), then by the ETD-based critic update in Algorithm 1, Lines 8 & 10, we have that \(Q_{t+1}(s,a) = Q_t(s,a)\in[0,1/(1-\gamma)]\) for all \((s,a)\neq (S_t, A_t)\) and \[\begin{align} Q_{t+1}(S_t,A_t) &= (1-\alpha_t)Q_{t+1}(S_t,A_t) + \alpha_t\left(\mathcal{R}(S_t,A_t) + \gamma\sum_{a\in\mathcal{A}}\pi_{t+1}(a\mid S_{t+1})Q_t(S_{t+1},a)\right)\\ &\leq \frac{1-\alpha_t}{1-\gamma}+\alpha_t\left(1+\frac{\gamma}{1-\gamma}\right)\\ &=\frac{1}{1-\gamma}. \end{align}\] Moreover, since \(\mathcal{R}(S_t,A_t), \pi_{t+1}(a\mid S_{t+1}), Q(s, a), \alpha_t \geq 0\) for all \((s,a)\), it follows that \(Q_{t+1}(S_t,A_t) \geq 0\). This concludes the induction.

(3) Note that for any \(t\geq 0\), we have \[\begin{align} \infnorm{Q_{t+1}-Q_t} = \alpha_t\left|\mathcal{R}(S_t,A_t)+\gamma\sum_{a\in\mathcal{A}}\pi(a\mid S_{t+1})Q_t(S_{t+1},a)-Q_t(S_t,A_t)\right|\leq \frac{\alpha_t}{1-\gamma}, \end{align}\] because \(\mathcal{R}(S_t,A_t)\in[0,1]\) and \(Q_t(s,a)\in[0,1/(1-\gamma)]\) for all \((s,a)\). Repeatedly applying from \(t_1\) to \(t_2-1\) yields the result.

Items (4), (5), and their proofs are identical to Lemma [lem:running95bounds] (4), (5), which are proved in Appendix 4.4.6. We hence omit the proofs here.

5.4.4 Proof of Lemma 14↩︎

(1) The result and its proof are identical to Lemma 1 (1), which is proved in Appendix 4.4.2. The proof is hence omitted.

(2) For any \(Q,Q'\in\mathbb{R}^{mn}, u = (s_1,a_1,s_2)\in\mathcal{U}\) and policy \(\pi\in{(\Delta^m)}^n\), we have for any \((s,a)\) that \[\begin{align} &|[F_{\mathrm{ETD}}(Q,u,\pi)](s,a)-[F_{\mathrm{ETD}}(Q',u,\pi)](s,a)|\\ &\leq \,(1-\mathbb{1}_{\{(s,a)=(s_1,a_1)\}})|Q(s,a)-Q'(s,a)|\\ &\quad+\mathbb{1}_{\{(s,a)=(s_1,a_1)\}}\sum_{a\in\mathcal{A}}\pi_{t+1}(a\mid s_2)|Q(s_2,a)-Q'(s_2,a)|\\ &\leq \,\|Q-Q'\|_\infty. \end{align}\] Therefore, we have \[\begin{align} \|F_{\mathrm{ETD}}(Q,u,\pi)-F_{\mathrm{ETD}}(Q',u,\pi)\|_\infty \leq \|Q-Q'\|_\infty. \end{align}\]

(3) The result and its proof are identical to Lemma 1 (3), which is proved in Appendix 4.4.2. The proof is hence omitted.

(4) For any \(Q\in\mathbb{R}^{mn}\) and \(u = (s_1,a_1,s_2)\in\mathcal{U}\), we have \[\begin{align} &[F_{\mathrm{ETD}}(Q, u, \pi_{t_1})-F_{\mathrm{ETD}}(Q, u, \pi_{t_2})](s,a)\\ &= \mathbb{1}_{\{(s,a)=(s_1, a_1)\}}\gamma\left(\sum_{a\in\mathcal{A}}\pi_{t_1}(a\mid s_2)Q(s_2, a)-\sum_{a\in\mathcal{A}}\pi_{t_2}(a\mid s_2)Q(s_2, a)\right). \end{align}\] Therefore, we have \[\begin{align} \infnorm{F_{\mathrm{ETD}}(Q, u, \pi_{t_1})-F_{\mathrm{ETD}}(Q, u, \pi_{t_2})} &\leq \gamma\|\pi_{t_1}-\pi_{t_2}\|_1\infnorm{Q}\\ &\leq 2\max_{s}\mathrm{d_{TV}}\big(\pi_{t_1}(s), \pi_{t_2}(s)\big)\infnorm{Q}. \end{align}\] The result then follows by combining the above with Lemma 20 (4).

6 Discussion of Our Assumption↩︎

In this section, we first justify the minimality of Assumption 1 and discuss related assumptions in the literature.

We next show that if the behavior policy is positive, then Assumption 1 implies that the Markov chain induced by the behavior policy is irreducible.

6.0.0.1 Lazy-chain construction [53].

The preceding lemma shows that Assumption 1, together with the positivity of \(\pi_b\), implies irreducibility of the Markov chain induced by \(\pi_b\). We now explain why aperiodicity can be imposed without loss of generality through the standard lazy-chain construction.

Given a state-action trajectory \(\{S_t,A_t\}\) generated by a policy \(\pi\), let \(P_\pi\) denote the corresponding state-action transition kernel. Fix \(\lambda\in(0,1)\). The lazy version of this chain is defined by using the transition kernel \[\begin{align} P'_\pi := (1-\lambda)P_\pi+\lambda I. \end{align}\] Equivalently, at each step the chain stays at the current state-action pair with probability \(\lambda\), and follows the original transition kernel \(P_\pi\) with probability \(1-\lambda\). 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'_\pi\) has the same stationary distribution as \(P_\pi\). Moreover, if \(P_\pi\) is irreducible, then \(P'_\pi\) is also irreducible. Since \(P'_\pi\) has a self-loop probability at least \(\lambda\) at every state-action pair, it is aperiodic. Therefore, on a finite state-action space, irreducibility and aperiodicity imply geometric mixing [54].

6.1 Comparison with Assumptions from Existing Literature↩︎

We now compare Assumption 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.

6.1.0.1 Uniform ergodicity across policies.

A frequently adopted assumption concerns uniform geometric mixing of the Markov chains induced by a class of policies. Let \(\Theta\) be a parameter space for policies. The following assumption appears frequently in the literature [35], [23], [42], [22].

Assumption 2 is substantially stronger than Assumption 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 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 [prop:minimal], this condition is minimal for state-space exploration. In our analysis, the existence of a stationary distribution and geometric mixing follow from Assumption 1, the positivity of the fixed behavior policy \(\pi_b\), and the lazy-chain construction above.

6.1.0.2 Exploration conditions.

In analyses involving linear function approximation, a common exploration-type condition is imposed through the feature covariance structure. Let \(\phi:\mathcal{S}\times\mathcal{A}\to\mathbb{R}^d\) be the feature map, and let \(\mu_\theta\) be the stationary distribution of the state trajectory under \(\pi_\theta\). The following condition appears frequently in equivalent forms [39], [40], [23], [35].

The following lemma shows that, in the tabular case, this condition fails near optimal policies whenever a suboptimal action exists.

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 22 shows that Assumption 3 is incompatible with global convergence in general tabular MDPs whenever optimality requires eliminating suboptimal actions.

6.1.0.3 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 [22], [23], [35].

In the tabular case, where the policy is parameterized by itself, i.e., \(\theta=\pi\), the first condition fails because \(\frac{\partial}{\partial \pi(a\mid s)}\log\pi(a\mid s)=1/\pi(a\mid s)\) can be arbitrarily large as \(\pi(a\mid s)\) approaches zero. Similarly, since the map \(x\mapsto 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.

References↩︎