Year: 2021

Abstract:
We show that the simplest actor-critic method — a linear softmax policy updated with TD through interaction with a linear MDP, but featuring no explicit regularization or exploration — does not merely find an optimal policy, but moreover prefers high entropy optimal policies. To demonstrate the strength of this bias, the algorithm not only has no regularization, no projections, and no exploration like ε-greedy, but is moreover trained on a single trajectory with no resets. The key consequence of the high entropy bias is that uniform mixing assumptions on the MDP, which exist in some form in all prior work, can be dropped: the implicit regularization of the high entropy bias is enough to ensure that all chains mix and an optimal policy is reached with high probability. As auxiliary contributions, this work decouples concerns between the actor and critic by writing the actor update as an explicit mirror descent, provides tools to uniformly bound mixing times within KL balls of policy space, and provides a projection-free TD analysis with its own implicit bias which can be run from an unmixed starting distribution.

heading: 1 OVERVIEW
text: Reinforcement learning methods navigate an environment and seek to maximize their reward (Sutton & Barto, 2018). A key tension is the tradeoff between exploration and exploitation: does a learner (also called an agent or policy) explore for new high-reward states, or does it exploit the best states it has already found? This is a sensitive part of RL algorithm design, as it is easy for methods to become blind to parts of the state space; to combat this, many methods have an explicit exploration component, for instance the ϵ-greedy method, which forces exploration in all states with probability ϵ (Sutton & Barto, 2018; Tokic, 2010). Similarly, many methods must use projections and regularization to smooth their estimates (Williams & Peng, 1991; Mnih et al., 2016; Cen et al., 2020).
This work considers actor-critic methods, where a policy (or actor) is updated via the suggestions of a critic. In this setting, prior work invokes a combination of explicit regularization and exploration to avoid getting stuck, and makes various fast mixing assumptions to help accurate exploration. For example, recent work with a single trajectory in the tabular case used both an explicit ϵ-greedy component and uniform mixing assumptions (Khodadadian et al., 2021), neural actor-critic methods use a combination of projections and regularization together with various assumptions on mixing and on the path followed through policy space (Cai et al., 2019; Wang et al., 2019), and even direct analyses of the TD subroutine in our linear MDP setting make use of both projection steps and an assumption of starting from the stationary distribution (Bhandari et al., 2018).
Contribution. This work shows that a simple linear actor-critic (cf. Algorithm 1) in a linear MDP (cf. Assumption 1.3) with a finite but non-tabular state space (cf. Assumption 1.1) finds an ϵ-optimal policy in poly(1/ϵ) samples, without any explicit exploration or projections in the algorithm and without any uniform mixing assumptions on the policy space (cf. Theorem 1.4). The algorithm and analysis avoid both via an implicit bias towards high entropy policies: the actor-critic policy path never leaves a Kullback-Leibler (KL) divergence ball of the maximum entropy optimal policy, and this firstly ensures implicit exploration, and secondly ensures fast mixing. In more detail:
1. Actor analysis via mirror descent. We write the actor update as an explicit mirror descent. While on the surface this does not change the method (e.g., in the tabular case, the method
is identical to natural policy gradient (Agarwal et al., 2021b)), it gives a clean optimization guarantee which carries a KL-based implicit bias consequence for free, and decouples concerns between the actor and critic.
2. Critic analysis via projection-free sampling tools within KL balls. The preceding mirror descent component guarantees that we stay within a small KL ball, if the statistical error of the critic is controlled. Concordantly, our sampling tools guarantee this statistical error is small, if we stay within a small KL ball. Concretely, we provide useful lemmas that every policy in a KL ball around the high entropy policy has uniformly upper bounded mixing times, and separately give a projection-free (implicitly regularized!) analysis of the standard temporal-difference (TD) update from any starting state (Sutton, 1988), whereas the closest TD analysis in the literature uses projections and requires the sampling process to be started from the stationary distribution (Bhandari et al., 2018). The mixing assumptions here contrast in general with prior work, which either makes explicit use of stationary distributions (Cai et al., 2019; Wang et al., 2019; Bhandari et al., 2018), or makes uniform mixing assumptions on all policies (Xu et al., 2020; Khodadadian et al., 2021).
Our final proof has the above actor and critic components feeding off each other: we use an induction to simultaneously establish that since the actor stayed in a small KL ball in previous iterations, then the new critic update is accurate, and similarly the accuracy of the previous critic updates ensures the actor continues to stay in a small KL ball. We feel these tools will be useful in other work.

heading: 1.1 SETTING AND MAIN RESULTS
text: We will now give the setting, main result, and algorithm in full. Further details on MDPs can be found in Section 1.3, but the actor-critic method appears in Algorithm 1. To start, the environment and policies are as follows. Assumption 1.1. The Markov Decision Process (MDP) has states s ∈ Rd and finitely many actions a ∈ A := {e1, . . . , ek}, and finite rewards r ∈ [0, 1]. States are observed in some feature encoding s ∈ Rd, but the state space S ⊆ {s ∈ Rd : 1/2 ≤ ∥s∥ ≤ 1} is assumed finite: |S| <∞. Policies are linear softmax policies: a policy is parameterized by a weight matrix W ∈ Rd×k, and given a state s ∈ Rd, uses a per-state softmax to sample a new action a:
a ∼ ϕ(sTW ·), where ϕ(sTWa) = exp(s TWa)∑
b∈A exp(s TWb)
. (1.1)
Let As denote the set of optimal actions for a given state s. It is assumed that As is nonempty for every s ∈ S; equivalently, for every state, there exists an optimal policy whose stationary distribution exists and places positive mass on that state. ♢
The choice of linear policies simplifies presentation and analysis, but the tools here should be applicable to other settings. This choice also allows direct comparison to the widely-studied implicit bias
Algorithm 1 Single-trajectory linear actor-critic. Inputs: actor iterations t and step size θ; critic iterations N and step size η. Initialize: actor weights W0 = 0 ∈ Rd×k, pre-softmax mapping p0(s, a) := sTW0a, policy π0 := ϕ(p0) (cf. eq. (1.1)); sample initial state/action/reward triple (s0,0, a0,0, r0,0). for i = 0, 1, 2, . . . , t− 1 do
Critic update: use πi to interact with the MDP, obtaining state/action/reward triples (si,j , ai,j , ri,j)j≤N by continuing the existing trajectory, and form TD estimates
Ui,j+1 := Ui,j − ηsi,j ( sTi,jUi,jai,j − γsTi,j+1Ui,jai,j+1 − ri,j ) aTi,j ,
with initial condition Ui,0 = 0. Set Ûi := 1N ∑
j<N Ui,j and Q̂i(s, a) := sTÛia, and also (si+1,0, ai+1,0, ri+1,0) := (si,N , ai,N , ri,N ) to continue the existing trajectory in next iteration. Actor update: set Wi+1 :=Wi + θÛi and pi+1 := pi + θQ̂i and πi+1 := ϕ(pi+1).
end for
of gradient descent in linear classification settings (Soudry et al., 2017; Ji & Telgarsky, 2018), as will be discussed further in Section 1.2. The choice of finite state space is to remove measure-theoretic concerns and to allow a simple characterization of the maximum entropy optimal policy. Lemma 1.2 (simplification of Lemma A.1). Under Assumption 1.1, there exists a unique maximum entropy policy π, which satisfies π(s, ·) = Uniform(As) for every state s.
To round out this introductory presentation of the actor, the last component is the update: pi+1 := pi + Q̂i and πi+1 := ϕ(pi+1). This is explicitly a mirror descent or dual averaging representation of the policy, where we use a mirror mapping ϕ to obtain the policy πi+1 from pre-softmax values pi+1. As mentioned before, this update appears in prior work in the tabular setting with natural policy gradient and actor-critic (Agarwal et al., 2021b; Khodadadian et al., 2021), and will be related to other methods in Section 1.2. We will further motivate this update in Section 2.
The final assumption and description of the critic are as follows. As will be discussed in Section 2, the policy becomes optimal if Q̂i is an accurate estimate of the true Q function. We employ a standard TD update with no projections or constraints. To guarantee that this linear model of Qi is accurate, we make a standard linear MDP assumption (Bradtke & Barto, 1996; Melo & Ribeiro, 2007; Jin et al., 2020). Assumption 1.3. In words, the linear MDP assumption is that the MDP rewards and transitions are modeled by linear functions. In more detail, for convenience first fix a canonical vector form for state/action pairs (s, a) ∈ Rd×k: let xsa ∈ Rdk denote the vector obtained via unrolling the matrix saT row-wise (whereby vector inner products with xsa match matrix inner products with saT). The linear MDP assumption is then that there exists a fixed vector y ∈ Rdk and a fixed matrix M ∈ Rd×dk so that for any state/action pair xsa and any subsequent state s′ ∈ Rd,
E[r | (s, a)] = xTsay, and E[s′ | (s, a)] =Mxsa. Lastly, suppose 1/2 ≤ ∥s∥ ≤ 1 for all s ∈ S. ♢
Though a strong assumption, it is not only common, but note also that since TD must continually interact with the MDP, then it would have little hope of accuracy if it can not model short-term MDP dynamics. Indeed, as is shown in Lemma C.3 (but appears in various forms throughout the literature), Assumption 1.3 implies that the fixed point of the TD update is the true Q function. This assumption and the closely related compatible linear function approximation assumption will be discussed in Section 1.2.
We now state our main result, which bounds not just the value function V (cf. Section 1.3) but also the KL divergence Kvsπ (π, πi) = Es′∼vsπ ∑ a π(s ′, a) ln π(s ′,a) πi(s′,a) , where vsπ is the visitation distribution of the maximum entropy optimal policy π when run from state s (cf. Section 1.3). Theorem 1.4. Suppose Assumptions 1.1 and 1.3 (which imply the (unique) maximum entropy optimal policy π is well-defined, and also irreducible and aperiodic). Given iteration count t, choose
θ = Θ
( 1
t13/16 ln(t)1/4
) , N = Θ ( t2 ln t ) , η = Θ ( 1√
N lnN
) ,
where the constants hidden inside each Θ(·) depend only on π and the MDP, but not on t. With these parameters in place, invoke Algorithm 1, and let (πi)i<t be the resulting sequence of policies. Then with probability at least 1− 1/t1/8, simultaneously for every state s ∈ Rd and every i ≤ t,
Kvsπ (π, πi) + θ(1− γ) ∑ j<i ( Vπ(s)− Vj(s) ) ≤ ln k + 1 (1− γ)2 .
Before outlining the proof structure and organization of the rest of the paper, a few comments on the interpretion of Theorem 1.4 are as follows. Remark 1.5 (Discussion of Theorem 1.4).
1. Implicit bias. Since π is optimal, the second term can be deleted, and the bound implies
max i≤t s∈S
Kvsπ (π, πi) ≤ ln k + 1
(1− γ)2 ;
since this holds for all i ≤ t, it controls the optimization path. This term is a direct consequence of our mirror descent setup, and is used to control the TD errors at every iteration. This implicit bias of the policy path stands therefore in stark contrast to the worstcase KL divergence between arbitrary softmax policies and π, which is infinite: to show sup{Kvsπ (π, ϕ(⟨W, ·⟩)) : W ∈ R
d×k, s ∈ S} = ∞, it suffices to consider a sequence (Wr)r≥1 so that π(s′, a)/ϕ((s′)TWra) → ∞ as r → ∞ for some (s′, a) with vsπ(s′) > 0 and π(s′, a) > 0.
2. Mixing time constants. The critic iterations N and step size η hide mixing time constants; these mixing time constants depend only on the KL bound ln k+ 1/(1− γ)2, and in particular there is no hidden growth in these terms with t. That is to say, mixing times are uniformly controlled over a fixed KL ball that does not depend on t; prior work by contrast makes strong mixing assumptions (Wang et al., 2019; Xu et al., 2020; Khodadadian et al., 2021).
3. High probability guarantee. Though prior work focuses on bounds in expectation, we chose a high probability guarantee to emphasize that the bound does not blow up, despite an arguably more strenuous setting.
4. Single trajectory. A single trajectory through the MDP is used to remove the option of the algorithm escaping from poor choices with resets; only the implicit bias can save it.
5. Rate. To reach a policy which whose value function is ϵ-close to optimal, a trajectory length (number of samples) of 1/ϵ16 is sufficient, ignoring log factors (it suffices to divide both sides of the bound by tθ(1−γ), set t = 1/ϵ16/3, and note the trajectory length is tN ). This is slower than the 1/ϵ6 given in the only other single-trajectory analysis in the literature Khodadadian et al. (2021), but by contrast that work makes uniform mixing assumptions (cf. Khodadadian et al. (2021, Lemma C.1)), requires the tabular setting, and uses ϵ-greedy for explicit exploration in each iteration. ♢
The proof of Theorem 1.4 and organization of the paper are as follows. After overviews of related work and notation in Sections 1.2 and 1.3, the first proof component, discussed in Section 2, is the outer loop of Algorithm 1, namely the update to the policy πi. As discussed before, this part of the analysis writes the policy update as a mirror descent, and conveniently decouples the suboptimality error into an actor error, which is handled by standard mirror descent tools and provides the implicit bias towards high entropy policies, and a critic error, namely the error of the estimated Q function Q̂i. The second component, discussed in Section 3, is therefore the TD analysis establishing that the estimate Q̂i is accurate, which not only requires an abstract TD guarantee (which, as mentioned, is projection-free and run from an arbitrary starting state, unlike prior work), but also requires tools to explicitly bound mixing times, rather than assuming mixing times are bounded.
This culminates in the proof of Theorem 1.4, which is sketched at the end of Section 3, and uses an induction combining the guarantees from the preceding two proof components at all times: it is established inductively that the next policy πi+1 has high entropy and low suboptimality because the previous Q function estimates (Q̂j)j≤i were accurate, and simultaneously that the next estimate Q̂i+1 is accurate because πi+1 has high entropy, which guarantees fast mixing. Section 4 concludes with some discussion and open problems, and the appendices contain the full proofs.

heading: 1.2 FURTHER RELATED WORK
text: For the standard background in reinforcement learning, see the book by Sutton & Barto (2018). Standard concepts and notation choices are presented below in Section 1.3.
Standard algorithms: PG/NPG and AC/NAC. The [natural] policy gradient ([N]PG) and natural actor-critic ([N]AC) are widely used in practice, and summarized briefly as follows. Policy gradient methods update the actor parameters W with gradient ascent on the value function Vπ(µ) for some state distribution µ (Williams, 1992; Sutton et al., 2000; Bagnell & Schneider, 2003; Liu et al., 2020; Fazel et al., 2018), whereas natural policy gradient multiplies ∇WVπ(µ) by an inverse Fisher matrix with the goal of improved convergence via a more relevant geometry (Kakade, 2001; Agarwal et al., 2021b). What policy gradient leaves open is how to estimate ∇WVπ(µ); actor-critic
methods go one step further and suggest updating the actor with policy gradient as above, but noting that ∇WVπ(µ) can be written as a function of Qπ , or rather an estimate thereof, and making this estimation the job of a separate subroutine, called the critic Konda & Tsitsiklis (2000). (Natural actor-critic uses natural policy gradient in the actor update (Peters & Schaal, 2008).) Actor-critic methods are perhaps the most widely-used instances of policy gradient, and come in many forms; the use of TD for the critic step is common (Williams, 1992; Sutton et al., 2000; Bagnell & Schneider, 2003; Liu et al., 2020; Fazel et al., 2018).
Linear MDPs and compatible function approximation. The linear MDP assumption (cf. Assumption 1.3) is used here to ensure that the TD step accurately estimates the true Q function, and is a somewhat common assumption in the literature, even when TD is not used (Bradtke & Barto, 1996; Melo & Ribeiro, 2007; Jin et al., 2020). As an example, the tabular setting satisfies Assumption 1.3, simply by encoding states as distinct standard basis vectors, namely S := {e1, . . . , e|S|} (Jin et al., 2020, Example 2.1); moreover, in this tabular setting, the actor update of Algorithm 1 agrees with NPG (Agarwal et al., 2021b). Interestingly, another common assumption, compatible linear function approximation, also guarantees our analysis goes through and that Algorithm 1 agrees with NPG, while being non-tabular in general. In detail, the compatible function approximation setting firstly requires that the actor update agrees with Q̂i in a certain sense (which holds in our setting by construction), and secondly that there exists a choice of critic parameters U so that the exact Q function Qπ can be represented with these parameters (Silver, 2015). If this assumption holds for every policy πi (and corresponding Qi) encountered in the algorithm, then the policy update of Algorithm 1 agrees with NPG and NAC (this is a standard fact; see for instance Silver (2015), or Agarwal et al. (2021a, Lemma 13.1)). Additionally, the proofs here also go through under this arguably weaker assumption: Assumption 1.3 is only used to ensure that TD finds not just a fixed point but the true Q function (cf. Lemma C.4), which is also guaranteed by the compatibility assumption. However, since this is an assumption on the trajectory and thus harder to interpret, we prefer Assumption 1.3 which explicitly holds for all possible policies.
Regularization and constraints. It is standard with neural policies to explicitly maintain a constraint on the network weights (Wang et al., 2019; Cai et al., 2019). Relatedly, many works both in theory and practice use explicit entropy regularization to prevent small probabilities (Williams & Peng, 1991; Mnih et al., 2016; Abdolmaleki et al., 2018), and which can seem to yield convergence rate improvements (Cen et al., 2020).
NPG and mirror descent. (For background on mirror descent, see Section 2 and appendix B.) The original and recent analyses of NPG had a mirror descent flavor, though mirror descent and its analysis were not explicitly invoked (Kakade, 2001; Agarwal et al., 2021b). Further connections to mirror descent have appeared many times (Geist et al., 2019; Shani et al., 2020), though with a focus on the design of new algorithms, and not for any implicit regularization effect or proof. Mirror descent is used heavily throughout the online learning literature (Shalev-Shwartz, 2011), and in work handling adversarial MDP settings (Zimin & Neu, 2013).
Temporal-difference update (TD). As discussed before, the TD update, originally presented by (Sutton, 1988), is standard in the actor-critic literature (Cai et al., 2019; Wang et al., 2019), and also appears in many other works cited in this section. As was mentioned, prior work requires various projections and initial state assumptions (Bhandari et al., 2018).
Implicit regularization in supervised learning. A pervasive topic in supervised learning is the implicit regularization effect of common descent methods; concretely, standard descent methods prefer low or even minimum norm solutions, which can be converted into generalization bounds. The present work makes use of a weak implicit bias, which only prefers smaller norms and does not necessarily lead to minimal norms; arguably this idea was used in the classical perceptron method (Novikoff, 1962), but was then shown in linear and shallow network cases of SGD applied to logistic regression (Ji & Telgarsky, 2018; 2019), which was then generalized to other losses (Shamir, 2020), and also applied to other settings (Chen et al., 2019). The more well-known strong implicit bias, namely the convergence to minimum norm solutions, has been observed with exponentially-tailed losses together with coordinate descent with linear predictors (Zhang & Yu, 2005; Telgarsky, 2013),
gradient descent with linear predictors (Soudry et al., 2017; Ji & Telgarsky, 2018), and deep learning in various settings (Lyu & Li, 2019; Chizat & Bach, 2020), just to name a few.

heading: 1.3 NOTATION
text: This brief notation section summarizes various concepts and notation used throughout; modulo a few inventions, the presentation mostly matches standard ones in RL (Sutton & Barto, 2018) and policy gradient (Agarwal et al., 2021b). A policy π : Rd × Rk → R maps state-action pairs to reals, and π(s, ·) will always be a probability distribution. Given a state, the agent samples an action from a ∼ π(s, ·), the environment returns some random reward (which has a fixed distribution conditioned on the observed (s, a) pair), and then uses a transition kernel to choose a new state given (s, a).
Taking τ to denote a random trajectory followed by a policy π interacting with the MDP from an arbitrary initial state distribution µ, the value V and Q functions are respectively
Vπ(µ) := E s0∼µ
τ=s0,a0,r0,s1,··· ∑ t≥0 γtrt,
Qπ(s, a) := E s0=s,a0=a
τ=s0,a0,r0,s1,··· ∑ t≥0 γtrt = Er0∼(s,a) ( r0 + γEs1∼(s,a)Vπ(s1) ) ,
where the simplified notation Vπ(s) = Vπ(δs) for Dirac distribution δs on state s will often be used, as well as the shorthand Vi = Vπi and Qi = Qπi . Additionally, let Aπ(s, a) := Qπ(s, a) − Vπ(s) denote the advantage function; note that the natural policy gradient update could interchangeably use Ai or Qi since they only differ by an action-independent constant, namely Vπ(s), which the softmax normalizes out. As in Assumption 1.1, the state space S is finite but a subset of Rd, specifically S ⊆ {s ∈ Rd : 1/2 ≤ ∥s∥ ≤ 1}, and the action space A is just the k standard basis vectors {e1, . . . , ek}. The other MDP assumption, namely of a linear MDP (cf. Assumption 1.3), will be used whenever TD guarantees are needed. Lastly, the discount factor γ ∈ (0, 1) has not been highlighted, but is standard in the RL literature, and will be treated as given and fixed throughout the present work.
A common tool in RL is the performance difference lemma (Kakade & Langford, 2002): letting vµπ denote the visitation distribution corresponding to policy π starting from µ, meaning
vµπ := 1
1− γ Es′∼µ ∑ t≥0 γtPr[st = s|s0 = s′],
the performance difference lemma can be written as
Vπ(µ)− Vπ′(µ) = 1
1− γ Es∼vµ π′ ∑ a Qπ(s, a)(π(s, a)− π′(s, a)) =: 1 1− γ 〈 Qπ, π − π′ 〉 vµ π′ ,
(1.2) where the final inner product notation will often be employed for convenience.
As mentioned above, sπ will denote the stationary distribution of a policy π whenever it exists. The only relevant assumption we make here, namely Assumption 1.1, is that the maximum entropy optimal policy π is aperiodic and irreducible, which implies it has a stationary distribution with positive mass on every state (Levin et al., 2006, Chapter 1). Via Lemma 3.1, it follows that all policies in a KL ball around π also have stationary distributions with positive mass on every state.
The max entropy optimal policy π is complemented by a (unique) optimal Q function Q and optimal advantage function A. The optimal Q function Q dominates all other Q functions, meaning Q(s, a) ≥ Qπ(s, a) for any policy π; for details and a proof, see Lemma A.1. In a few places, we need the Markov chain on states, Pπ , which is induced by a policy π: that is, the chain where given a state s, we sample a ∼ π(s, ·), and then transition to s′ ∼ (s, a), where the latter sampling is via the MDP’s transition kernel.
We use ∥µ−ν∥TV = supU⊆S |µ(U)−ν(U)| to denote the total variation distance, which is pervasive in mixing time analyses (Levin et al., 2006).

heading: 2 MIRROR DESCENT TOOLS
text: To see how nicely mirror descent and its guarantees fit with the NPG/NAC setup, first recall our updates: pi+1 := pi + Q̂i, and πi+1 := ϕ(pi+1) (e.g., matching NPG in the tabular case (Kakade, 2001; Agarwal et al., 2021b)). In the online learning literature (Shalev-Shwartz, 2011; Lattimore & Szepesvári, 2020), the basic mirror ascent (or dual averaging) guarantee is of the form∑
i<t
〈 Q̂i, π − πi 〉 ≤ O( √ t),
where notably Q̂i does not need to mean anything, and can be an arbitrary element of a vector space. The most common results are stated when Q̂i is the gradient of some convex function, but here instead we can use the performance difference lemma (cf. eq. (1.2)): recalling the inner product and visitation distribution notation from Section 1.3,〈
Q̂i, πi − π 〉 vµπ = ⟨Qi, πi − π⟩vµπ + 〈 Q̂i −Qi, πi − π 〉 vµπ
= (1− γ) ( Vi(µ)− Vπ(µ) ) + 〈 Q̂i −Qi, πi − π 〉 vµπ .
The term Q̂i −Qi is exactly what we will control with the TD analysis, and thus the mirror descent approach has neatly decoupled concerns into an actor term, and a critic term.
In order to apply the mirror descent framework, we need to choose a mirror mapping. Rather than using ϕ, we use a choice which bakes the measure vµπ from the inner product above into the dual object q! This may seem strange, but it does not change the induced policy, and thus is a degree of freedom, and allows us to state guarantees for all possible starting distributions for free.
Our full mirror descent setup is detailed in Appendix B, but culminates in the following guarantee. Lemma 2.1. Consider step size θ > 0, any reference policy π, any starting measure µ, and two treatments of the error Q̂i −Qi.
1. (Simplified bound.) Define Ci := sups,a |Q̂i(s, a)| for all i < t. Then Kvµπ (π, πt) + θ(1− γ) ∑ i<t ( Vπ(µ)− Vi(µ) ) ≤ Kvµπ (π, π0) + θ 2 ∑ i<t C2i
+ θ ∑ i<t 〈 Qi − Q̂i, πi − π 〉 vµπ .
2. (Refined bound.) Define ϵ̂i := sups,a |Q̂i(s, a)−Qi(s, a)|. Then
Kvµπ (π, πt) + θ(1− γ) ∑ i<t ( Vπ(µ)− Vi(µ) ) ≤ Kvµπ (π, π0) + θ 1− γ
+ θ ∑ i<t ( 2γϵ̂i 1− γ + ϵ̂i + ϵ̂i+1 ) ,
and additionally Vi and Q̂i are approximately monotone: for any state s and action a,
Vi+1(s) ≥ Vi(s)− 2ϵ̂i
1− γ and Q̂i+1(s, a) ≥ Q̂i(s, a)− 2γϵ̂i 1− γ − ϵ̂i − ϵ̂i+1.
Remark 2.2 (Regarding the mirror descent setup, Lemma 2.1).
1. Two rates. For the refined bound, it is most natural to set θ = 1, which requires O(1/ϵ) iterations to reach accuracy ϵ > 0; by contrast, the simplified guarantee requires O(1/ϵ2) iterations for the same ϵ > 0 with step size θ = 1/ √ t. We use the simplified form to prove Theorem 1.4,
since its TD error term is less stringent; indeed, the TD analysis we provide in Section 3 will not be able to give the uniform control needed for the refined bound. Still, we feel the refined bound is promising, and include it for sake of completeness, future work, and comparison to prior work.
2. Comparison to standard rates. Comparing the refined bound (with all ϵ̂i terms set to zero) to the standard NPG rate in the literature (Agarwal et al., 2021b), the rate is exactly recovered; as such, this mirror descent setup at the very least has not paid a price in rates.
3. Implicit regularization term. A conspicuous difference between these bounds and both the standard NPG bounds (Agarwal et al., 2021b, Theorem 5.3), but also many mirror descent treatments, is the term Kvµπ (π, πt); one could argue that this term is nonnegative and moreover we care more about the value function, so why not drop it, as is usual? It is precisely this term that gives our implicit regularization effect: instead, we can drop the value function term and uniformly upper bound the right hand side to get Kvµπ (π, πt) ≤ ln k + 2/(1 − γ)
2, which is how we control the entropy of the policy path, and prove Theorem 1.4. ♢

heading: 3 SAMPLING TOOLS
text: Via Lemma 2.1 above, our mirror descent black box analysis gives us a KL bound and a value function bound: what remains, and is the job of this section, is to control the Q function estimation error, namely terms of the form Qi − Q̂i. Our analysis here has two parts. The first part, as follows immediately, is that any bounded KL ball in policy space has uniformly controlled mixing times; the second part, which comes shortly thereafter, is our TD guarantees. Lemma 3.1. Let policy π̃ be given, and suppose the induced transition kernel on states Pπ̃ is irreducible and aperiodic (Levin et al., 2006, Section 1.3). Then π̃ has a stationary distribution sπ̃ , and moreover for any c > 0 and any measure ν which is positive on all states and a corresponding set of policies
Pc := { π : Kν(π̃, π) ≤ c } ,
there exist constants C,m1,m2 so that mixing is uniform over Pc, meaning for any t, and any π ∈ Pc with induced transition probabilities Pπ ,
sup s
∥P tπ(s, ·)− sπ∥TV ≤ m1e−m2t,
and for any state s and any π ∈ Pc, and any action a with π̃(s, a) > 0,
1 C ≤ π̃(s, a) π(s, a) ≤ C and 1 C ≤ sπ̃(s) sπ(s) ≤ C.
Remark 3.2 (Implicit vs explicit exploration). On the surface, Lemma 3.1 might seem quite nice. Worrying about it a little more, and especially after inspecting the proof, it is clear that the constants C, m1, and m2 can be quite bad. On the one hand, one may argue that this is inherent to implicit exploration, and something like ϵ-greedy is preferable, as it arguably gives an explicit control on all these quantities.
Some aspects of this situation are unavoidable, however. Consider a combination lock MDP, where a precise, hard to find sequence of actions must be followed to arrive at some good reward. Suppose this sequence has length n and we have a reference policy π̃ which takes each of these good actions with probability 1 − 1/n, whereby the probability of the sequence is (1 − 1/n)n ≈ 1/e; a policy π ∈ Pc with π(s, a)/π̃(s, a) ≤ 1/2 can drop the probability of this good sequence of actions all the way down to 1/2n! ♢
Next we present our TD analysis. As discussed in Section 1, by contrast with prior work, this analysis handles starting from an arbitrary state, and does not make use of any projections. The following guarantee is specialized to Algorithm 1; it is a corollary of a more general TD guarantee, given in Appendix C, which is stated without reference to Algorithm 1, and can be applied in other settings. Lemma 3.3 (See also Lemma C.4). Suppose the MDP and linear MDP assumptions (cf. Assumptions 1.1 and 1.3). Consider a policy πi in some iteration i of Algorithm 1, and suppose there exist mixing constants m ≥ 1 and c > 0 so that the induced transition kernel Pπi on S satisfies
sup s
∥P tπi(s, ·)− sπi∥TV ≤ me −ct.
Suppose the TD iterations N and step size η satisfy
N ≥ k, η ≤ 1 400 √ kN
, where k = ⌈ lnN + lnm
c
⌉ .
Then letting Ei denote expectation over the trajectory (si,j , ai,j)j≤N , the average TD iterate Ûi := 1 N ∑ j<N Ui,j satisfies
Ei ∥∥∥Ûi − Ūi∥∥∥2 + ηNEiE(s,a)∼(sπ,π) 〈saT, Ûi − Ūi〉2 ≤ 54(1− γ)2 ,
where Ūi is the minimum norm fixed point of the expected TD iteration at stationarity (cf. Lemma C.3), and thus 〈 saT, Ûi − Ūi 〉 = sTÛia− sTŪia = Q̂i(s, a)−Qi(s, a) for any (s, a).
The proof is intricate owing mainly to issues of statistical dependency. It is not merely an issue that the chain is not started from the stationary distribution; dropping the subscript i for convenience and letting xj+1 and xj denote the vectorized forms of sj+1aTj+1 and sja T j , and similarly letting uj denote the vectorized form ofUj , notice that xj+1, xj , uj are all statistically dependent. Indeed, even if xj is sampled from the stationary distribution (which also means xj+1 is distributed according to the stationary distribution as well), the conditional distribution of xj+1 given xj is not in general stationary! To deal with such issues, the proof chooses a very small step size which ensures the TD estimate evolves much more slowly than the mixing time of the chain. On a more technical level, whenever the proof encounters an inner product of the form 〈 xj , uj 〉 , it introduces a gap and instead
considers 〈 uj−k, xj 〉 , where uj−k − uj is small due to the small step size, and these two are nearly independent due to fast mixing.
A second component of the proof, which removes projection steps from prior work (Bhandari et al., 2018), is an implicit bias of TD, detailed as follows. Mirroring the MD statement in Lemma 2.1, the left hand side here has not only a Q̂i −Qi term as promised, but also a norm control ∥Ûi − Ūi∥2; in fact, this norm control holds for all intermediate TD iterations, and is used throughout the proof to control many error terms. Just like in the MD analysis, this term is an implicit regularization, and is how this work avoids the projection step needed in prior work (Bhandari et al., 2018).
All the pieces are now in place to sketch the proof of Theorem 1.4, which is presented in full in Appendix D. To start, instantiate Lemma 3.1 with KL divergence upper bound ln k + 2/(1 − γ)2, which gives the various mixing constants used throughout the proof (which we need to instantiate now, before seeing the sequence of policies, to avoid any dependence). With that out of the way, consider some iteration i, and suppose that for all iterations j < i, we have a handle both on the TD error, and also a guarantee that we are in a small KL ball around π (specifically, of radius ln k + 2/(1 − γ)2 as in Theorem 1.4). The right hand side of the simplified mirror descent bound in Lemma 2.1 only needs a control on all previous TD errors, therefore it implies both a bound on∑
j<i Vj(s) and onKvsπ (π, πi). But this KL control on πi means that the mixing and other constants we assumed at the start will hold for πi, and thus we can invoke Lemma 3.3 to bound the error on Q̂i−Qi, which we will use in the next loop of the induction. In this way, the actor and critic analyses complement each other and work together in each step of the induction.

heading: 4 DISCUSSION AND OPEN PROBLEMS
text: This work, in contrast to prior work in natural actor-critic and natural policy gradient methods, dropped many assumptions from the analysis, and components of the algorithms. The analysis was meant to be fairly general purpose and unoptimized. As such, there are many open problems.
Implicit vs explicit regularization/exploration. What are some situations where one is better than the other, and vice versa? The analysis here only says you can get away with doing everything implicitly, but not necessarily that this is the best option.
More general settings. The paper here is for linear MDPs, linear softmax policies, finite state and action spaces. How much does the implicit bias phenomenon (and this analysis) help in more general settings?

heading: B FULL MIRROR DESCENT SETUP AND PROOFS
text: This section first gives a basic mirror descent / dual averaging setup. This characterization is somewhat standard (Bubeck, 2015), though written with extra flexibility and with equalities to preserve implicit biases terms.
First, here is the basic notation (which, unlike the paper body, will allow a subscripted step size θi which can differ between iterations):
pi+1 := pi − θigi, θi > 0, qi := ∇ψ(pi), closed proper convex ψ, ⟪·, ·⟫ , bilinear pairing, D(p, pi) := ψ(p)− [ ψ(pi) + ⟪qi, p− pi⟫ ] , primal Bregman,
D∗(q, qi) := ψ ∗(q)− [ ψ∗(qi) + ⟪pi, q − qi⟫ ] , dual Bregman.
One nonstandard choice here is that the Bregman divergence bakes in a conjugate element, rather than using ∇ψ and ∇ψ∗; this gives an easy way to handle certain settings (like the boundary of the simplex) which run into non-uniqueness issues. Secondly, ⟪·, ·⟫ is just a bilinear form, and does not need to be interpreted as a standard inner product.
The standard Bregman identities used in mirror descent proofs are as follows:
D∗(q, qi)−D∗(q, qi+1)−D∗(qi+1, qi) = ⟪pi − pi+1, qi+1 − q⟫ , (B.1) D∗(qi+1, qi) = D(pi, pi+1), (B.2)
D∗(qi+1, qi) +D∗(qi, qi+1) = ⟪pi − pi+1, qi − qi+1⟫ , (B.3) D∗(q, qi) = ψ ∗(q) + ψ(pi)− ⟪pi, q⟫ ≥ 0. (B.4)
With these in hand, the core mirror descent guarantee is as follows. The bound is written with equalities to allow for careful handling of error terms. Note that this version of mirror descent does not interpret the “gradient” gi in any way, and treats it as a vector and no more. Lemma B.1. Suppose θi > 0. For any t and q where q ∈ dom(ψ∗),∑ i<t θi ⟪gi, qi − q⟫ = D∗(q, q0)−D∗(q, qt) + ∑ i<t D(pi+1, pi)
= D∗(q, q0)−D∗(q, qt) + ∑ i<t [⟪pi − pi+1, qi − qi+1⟫−D∗(qi+1, qi)] = D∗(q, q0) + θ0 ⟪g0, q0⟫−D∗(q, qt)− θt−1 ⟪gt, qt⟫−
∑ i<t D∗(qi+1, qi)
+ t−1∑ i=1 ⟪gi, qi⟫ (θi − θi−1) + ∑ i<t θi ⟪gi+1 − gi, qi+1⟫ .
Moreover, for any i, ⟪gi, qi+1⟫ ≤ ⟪gi, qi⟫.
Proof. For any fixed iterate i < t, by eqs. (B.1) to (B.3),
θi ⟪gi, qi − q⟫ = ⟪pi − pi+1, qi − q⟫ = ⟪pi − pi+1, qi − qi+1⟫+ ⟪pi − pi+1, qi+1 − q⟫ = ⟪pi − pi+1, qi − qi+1⟫+D∗(q, qi)−D∗(q, qi+1)−D∗(qi+1, qi) ∵ eq. (B.1) = D∗(q, qi)−D∗(q, qi+1) +D∗(qi, qi+1) ∵ eq. (B.3) = −D∗(q, qi) +D∗(q, qi+1) +D(pi+1, pi), ∵ eq. (B.2)
and additionally note
1 θi ⟪pi − pi+1, qi − qi+1⟫ = ⟪gi, qi − qi+1⟫ = ⟪gi+1 − gi, qi+1⟫− ⟪gi+1, qi+1⟫+ ⟪gi, qi⟫ .
The first equalities now follow by applying ∑
i<t to both sides and telescoping.
For the second part, for any i, by convexity of ψ,
0 ≤ ⟪pi − pi+1,∇ψ(pi)−∇ψ(pi+1)⟫ = θi ⟪gi, qi − qi+1⟫ , which rearranges to give ⟪gi, qi+1⟫ ≤ ⟪gi, qi⟫ since θi > 0.
All that remains is to instantiate the various mirror descent objects to match Algorithm 1, and control the various resulting terms. This culminates in Lemma 2.1; its proof is as follows.
Proof of Lemma 2.1. The core of both parts of the proof is to apply the mirror descent guarantees from Lemma B.1, using the following choices. To start, the primal update is given by
gi := −Q̂i, pi+1 := pi − θgi = pi + θQ̂i.
The mirror mapping and corresponding dual variables (with vµπ baked in) are ψ(p) := Es∼vµπ ln ∑ a∈A exp(p(s, a)) = ∑ s∈S vµπ(s) ln ∑ a∈A exp(p(s, a)),
[∇ψ(p)](s, a) = v µ π(s) exp(p(s, a))∑ b∈A exp(p(s, b)) ,
qi := ∇ψ(pi), qi(s, a) := v µ π(s)πi(s, a).
The primal Bregman divergence, which uses a dual iterate rather than the mirror map, is D(p, pi) := ψ(p)− [ ψ(pi)− ⟪qi, p− pi⟫ ] .
The inner product is the standard one: ⟪p, q⟫ := ∑ s∈S ∑ a∈A p(s, a)q(s, a).
Lastly, the dual Bregman divergence is given by
ψ∗(q) = { ⟪q, ln q⟫−∑s vµπ(s) ln vµπ(s), q ∈ ∆S×A, ∞ o.w.,
D∗(q, qi) := ψ ∗(q)− [ ψ∗(qi)− ⟪pi, q − qi⟫ ] = ⟪q, ln q⟫− ⟪qi, ln qi⟫
− ∑ s,a ln(qi(s, a)) + ln vµπ(s) + ln∑ b exp(pi(s, b) (q(s, a)− qi(s, a)) = ⟪q, ln q
qi ⟫ = Kvµπ (π, πi).
A key consequence of these constructions is that qi, treated for any fixed s as an unnormalized policy, agrees with πi := ϕ(pi) after normalization; that is to say, it gives the same policy, and the choice of vµπ baked into the definition is not needed by the algorithm, is only used in the analysis. The “gradient” gi = −Q̂i makes no use of it. Plugging this notation in to Lemma B.1 but making use of two of its equalities, and the performance difference lemma (cf. eq. (1.2)), then for any µ,
θ(1− γ) ∑ i<t ( Vi(µ)− Vπ(µ) ) = ∑ i<t θ ⟨Qi, πi − π⟩vµπ
= ∑ i<t θ 〈 Qi − Q̂i, πi − π 〉 vµπ + ∑ i<t 〈 θQ̂i, πi − π 〉 vµπ
= ∑ i<t θ 〈 Qi − Q̂i, πi − π 〉 vµπ − ∑ i<t ⟪θigi, qi − qπ⟫ . (B.5)
The proof now splits into the two different settings.
1. (Simplified bound.) By the above definitions and the first equality in Lemma B.1, − ∑ i<t ⟪θigi, qi − qπ⟫ = D∗(q, qt)−D∗(q, q0)− ∑ i<t D(pi+1, pi),
where the last term may be bounded in a way common in the online learning literature (ShalevShwartz, 2011): since ez ≤ 1 + z + z2 when z ≤ 1, setting Z(s, a) := Q̂i(s, a) − Ci for convenience (whereby Z(s, a) ≤ 0 ≤ 1 as needed by the preceding inequality), D(pi+1, pi)
= Es∼vµπ ( ln ∑ a exp(pi+1(s, a))− ln ∑ a exp(pi(s, a))− ∑ a πi(s, a)(pi+1(s, a)− pi(s, a)) )
= Es∼vµπ ln(∑ a πi(s, a) exp ( θQ̂i(s, a) )) − θ ∑ a πi(s, a)Q̂i(s, a)  = Es∼vµπ ln(∑ a πi(s, a) exp ( θZ(s, a) )) − θ ∑ a πi(s, a)Z(s, a)
 ≤ Es∼vµπ ln(∑ a πi(s, a)(1 + θZ(s, a) + θ 2Z(s, a)2) ) − θ ∑ a πi(s, a)Z(s, a)
 ≤ Es∼vµπ (∑ a πi(s, a)(1 + θZ(s, a) + θ 2Z(s, a)2)− 1− θ ∑ a πi(s, a)Z(s, a)
) = Es∼vµπ
∑ a πi(s, a)θ 2Z(s, a)2 ≤ θ2C2i ,
which together with the preceding as well as eq. (B.5) gives θ(1− γ) ∑ i<t ( Vi(µ)− Vπ(µ) ) = ∑ i<t θ 〈 Qi − Q̂i, πi − π 〉 vµπ − ∑ i<t ⟪θigi, qi − qπ⟫ .
≥ ∑ i<t θ 〈 Qi − Q̂i, πi − π 〉 vµπ +Kvµπ (π, πt)−Kvµπ (π, π0)− θ 2 ∑ i<t C2i ,
which gives the desired bound after rearranging.
2. (Refined bound.) By Lemma B.1 with the above choices and any measure vµπ , then〈 Q̂i, πi+1 〉 vµπ = − ⟪gi, qi+1⟫ ≥ − ⟪gi, qi⟫ = 〈 Q̂i, πi 〉 vµπ , (B.6)
and also − ∑ i<t ⟪θigi, qi − qπ⟫ = −D∗(q, q0)− θ ⟪g0, q0⟫+D∗(q, qt) + θ ⟪gt, qt⟫+ ∑ i<t D∗(qi+1, qi)
− ∑ i<t θ ⟪gi+1 − gi, qi+1⟫
≥ Kvµπ (π, πt)−Kvµπ (π, π0)− θ 1− γ + ∑ i<t θ 〈 Q̂i+1 − Q̂i, πi+1 〉 vµπ .
To simplify these further, first note by eq. (B.6) with measure vδsπi+1 for any state s and the performance difference lemma that
0 ≤ 〈 Q̂i, πi+1 − πi 〉 vδsπi+1
= 〈 Q̂i −Qi, πi+1 − πi 〉 vδsπi+1
+ ⟨Qi, πi+1 − πi⟩vδsπi+1 ≤ 2ϵ̂i + (1− γ) ( Vi+1(δs)− Vi(δs) ) ,
which rearranges to give
Vi+1(δs) ≥ Vi(δs)− 2ϵ̂i
1− γ ∀s,
which itself in turn implies〈 Q̂i+1 − Q̂i, πi+1 〉 vµπ ≥ ⟨Qi+1 −Qi, πi+1⟩vµπ − ϵ̂i − ϵ̂i+1
= γE s∼vµπ a∼πi+1(s,·) s′∼(s,a)
( Vi+1(δs′)− Vi(δs′) ) − ϵ̂i − ϵ̂i+1
≥ − 2γϵ̂i 1− γ − ϵ̂i − ϵ̂i+1.
(The preceding derivation works if vµπ is replaced with any measure on states.) Plugging this all back in to eq. (B.5) gives
Vt−1(µ)− Vπ(µ) ≥ 1
t ∑ i<t ( Vi(µ)− Vπ(µ) ) − ∑ i<t 2(1 + i)ϵi t(1− γ)
≥ Kvµπ (π, πt)−Kvµπ (π, π0) tθ(1− γ) − 1 t(1− γ)2 − 1 t(1− γ) ∑ i<t ( 2γϵi 1− γ + ϵi + ϵi+1 ) − ∑ i<t 2(1 + i)ϵi t(1− γ) ,
where the last term may be omitted for the summation version, and these expressions rearrange to give the final bounds.

heading: C SAMPLING PROOFS
text: As in the body, this section both provides tools to control mixing times, and also a generalized TD analysis.
C.1 MIXING TIME CONTROLS WITHIN KL BALLS
To control mixing times, these lemmas will use the notion of conductance:
Φ∗π := min S⊆|S|:sπ(S)≤1/2 Φπ(S), where Φπ(S) :=
∑ s∈S ∑ s′ ̸∈S sπ(s)Pπ(s, s ′)
sπ(S) .
This quantity was shown to control mixing times of reversible chains by Jerrum & Sinclair (1988) (for more discussion, see Levin et al. (2006, eq. (7.7), Theorem 12.4, Theorem 13.10)), but a later proof due to Lovasz & Simonovits (1990) requires chains to only be lazy, and does not need reversibility. Our chains can be made lazy by flipping a coin before each step, but in our setting we can avoid this and directly use the mixing time of the lazy chains to control the mixing time of the original chains.
As a first tool, note that if policies are similar, then their stationary distributions and conductances are also similar. Lemma C.1. Let constant c > 0 and an aperiodic irreducible policy π̃ be given, and define a set of policies whose action probabilities are similar:
P := { π : ∀s, a, π̃(s, a) > 0 1
c ≤ π(s, a) π̃(s, a)
≤ c } .
Then there exists a constant C > 0 so that the stationary distributions and conductances are also similar: for any π ∈ P and any state s,
1 C ≤ sπ(s, a) sπ̃(s, a) ≤ C, Φ∗π ≥ 1 C Φ∗π̃.
Proof. First note that since π̃ is aperiodic and irreducible, it has a stationary distribution sπ̃ where necessarily sπ̃(s) > 0 for all states s. Next, recall that the stationary distribution can be characterized in terms of hitting times (Levin et al., 2006, Proposition 1.19), meaning
sπ̃(s) = 1
E[min{t > 0 : st = s}|s0 = s] .
As discussed in proofs that the denominator is finite (Levin et al., 2006, proof of Lemma 1.13), letting Pπ and Pπ̃ corresponding to the state transitions induced by taking a step by π and π̃ respectively and then using the MDP dynamics to get to a state, there exist r > 0 and ϵ > 0 so that P jπ̃(s, s
′) > ϵ for any states s, s′ and any j ≥ r, therefore P jπ(s, s′) ≥ ϵc−j . In fact, for a fixed s, letting js ≥ 1 denote the smallest exponent so that P jsπ̃ (s, s) > 0, then Eπ̃[min{t > 0 : st = s}|s0 = s] ≥ js, meanwhile, as in Levin et al. (2006, proof of Lemma 1.13), defining τ+π := min t > 0 : st = s,
E[τ+π |s0 = s] = ∑ t≥0 Pr[τ+π > t|s0 = s]
≤ ∑ k≥0 jsPr[τ+π > kjs|s0 = s]
≤ js ∑ k≥0 (1− c−jsP jsπ̃ (s, s)) k
≤ js 1− c−jsP jsπ̃ (s, s) ≤ E[τ + π̃ |s0 = s]
1− c−jsP jsπ̃ (s, s) ,
where the denominator does not depend on π and thus the ratio is uniformly bounded over Pc. (We can produce a bound in the reverse direction trivially, by using sπ(s)/sπ̃(s) ≤ 1/sπ̃(s).) Let C0 denote the maximum of this ratio and c.
Bounding the conductance is an easy consequence of the definition of C0: using C0 to swap various terms depending on π with terms depending on π̃, it follows that
Φ∗π ≥ 1
C40 Φ∗π̃.
The proof is now complete by taking C := C40 as the chosen constant.
Next, we use the preceding fact to obtain mixing times; the proof will need to convert to lazy chains to invoke the mixing time bound due to Lovasz & Simonovits (1990), but then will use a characterization of mixing times via coupling times to reason about the original chain (Levin et al., 2006, Theorem 5.4). Lemma C.2. Let constant c > 0 and an aperiodic irreducible policy π̃ be given, and define a set of policies
P := { π : ∀s, a, π̃(s, a) > 0 1
c ≤ π(s, a) π̃(s, a)
≤ c } .
Then there exist constants m1,m2 > 0 so that for every π ∈ P and every t,
sup s
∥P tπ(s, ·)− sπ∥TV ≤ m1e−m2t.
Proof. For any policy π, let νπ denote the corresponding lazy chain: that is, in any state, νπ does nothing with probability 1/2 (it stays in the same state but does not interact with the MDP to receive any reward or transition), and otherwise with probability 1/2 uses π to interact with the MDP in its current state. Equivalently, if s ̸= s′, then Pνπ (s, s′) = Pπ(s, s′)/2, whereas Pνπ (s, s) = (1 + Pπ(s, s))/2. Define ν̃ := νπ̃ for convenience, and a new set of nearby policies:
Pν := P := { π : ∀s, s′ 1
c′ ≤ Pνπ (s, s
′)
Pν̃(s, s′) ≤ c′
} ,
where c′ is chosen so that, for every π ∈ P , and every pair of states (s, s′),
1 c′ ≤ Pπ(s, s′)Pπ̃(s, s′) ≤ c′;
this uniform constant c′ <∞ is guaranteed to exist by the existence of c. Notice that for any s ̸= s′,
1 c′ ≤ Pπ(s, s
′)
Pπ̃(s, s′) =
2Pνπ (s, s ′)
2Pν̃(s, s′) = Pνπ (s, s
′)
Pν̃(s, s′) = Pπ(s, s
′)
Pπ̃(s, s′) ≤ c′,
whereas in the case s = s′, it can be checked by multiplying through by denominators that if Pπ(s, s) ≥ Pπ̃(s, s), then
c′ ≥ Pπ(s, s) Pπ̃(s, s) ≥ (1 + Pπ(s, s))/2 (1 + Pπ̃(s, s))/2 = Pνπ (s, s) Pν̃(s, s) ≥ 1,
with an analogous relationship when Pπ(s, s) ≤ Pπ̃(s, s), which implies
c′ ≥ Pνπ (s, s) Pν̃(s, s) ≥ 1 c′ .
Consequently, it follows that Pν ⊇ P , and by Lemma C.1, that there exists a constant C so that every π ∈ P satisfies
1 C ≤ sνπ (s, a) sν̃(s, a) ≤ C, Φ∗νπ ≥ 1 C Φ∗ν̃ .
(One reason for the prevalence of lazy chains is that they always have unique stationary distributions (see, e.g., (Levin et al., 2006; Lovasz & Simonovits, 1990)), but as in the preceding, in our setting we always have stationary distributions automatically; thus we did not need to use laziness algorithmically, and can use it analytically.)
Since the conductance is uniformly bounded for every element of Pν , there exist positive constants m3,m4 so that for every π ∈ Pν , (Lovasz & Simonovits, 1990),
sup s
∥P tνπ (s, ·)− sνπ∥TV ≤ m3 exp(−m4t).
Now define pmin := mins sν̃(s)/C > 0, whereby it holds by the above that pmin ≤ infπ∈Pν mins sνπ (s). As such, by the preceding mixing bound, there exists a t0 so that, simultaneously for every π ∈ Pν , for all t ≥ t0, by the definition of total variation (instantiated on singletons), for every s′, sups P t νπ (s, s
′) ≥ pmin/2 > 0. Now consider some fixed π ∈ P , which also satisfies π ∈ Pν since Pν ⊇ P as above, and consider the coupling time of two sequences (x0, x1, . . .) and (y0, y1, . . .) obtained by running Pπ on each. Instead of running Pπ directly, simulate it as follows: use Pνπ , but discard from the sequence any steps which invoke the lazy option. Then, for t ≥ t0, the probability of both chains not choosing the lazy option and jumping to the same state is at least p := ∑ s(pmin/2)
2/4 > 0. As such, for any t ≥ t0, the probability that the two chains did not land on the same state somewhere between t0 and t is at most
(1− p)t−t0 ≤ (1− p)−t0 exp(−pt).
But this is exactly an upper bound on the coupling time, meaning by (Levin et al., 2006, Theorem 5.4) that
sup x0,y0
∥P tπ(x0, ·)− P tπ(y0, ·)∥TV ≤ (1− p)−t0 exp(−pt),
which in turn directly bounds the mixing time (Levin et al., 2006, Corollary 5.5), indeed with constants m1 := (1− p)−t0 and m2 = p. Since these constants do not depend on the specific policy π in any way, the mixing time has been uniformly controlled as desired.
With these tools in hand, we may now control mixing times uniformly over KL balls.
Proof of Lemma 3.1. Since π̃ is irreducible and aperiodic, it has a stationary distribution, and moreover this stationary distribution is positive on all states (Levin et al., 2006, Proposition 1.19), and
define π̃min := mins∈S π̃(s) > 0. By definition of Ksπ̃ and Pc, for any π ∈ Pc, letting (s′, a′) denote any pair which maximizes π̃(s, a)/π(s, a), and since ∑ a va ln va ≥ − ln k for any v ∈ ∆k,
c ≥ Kν(π̃, π) = ∑ s∈S ν(s) ∑ a π̃(s, a) ln π̃(s, a) π(s, a)
≥ ν(s′)π̃(s′, a′) ln π̃(s ′, a′)
π(s′, a′) + ∑ (s,a)̸=(s′,a′) ν(s) ∑ a π̃(s, a) ln π̃(s, a) π(s, a)
≥ ν(s′)π̃(s′, a′) ln π̃(s ′, a′)
π(s′, a′) + ν(s′) ∑ a̸=a′ π̃(s′, a) ln π̃(s′, a) π(s′, a)
≥ ν(s′)π̃(s′, a′) ln π̃(s ′, a′)
π(s′, a′) − ν(s′) ln k,
then π̃(s′, a′)
π(s′, a′) ≤ exp
( c
ν(s′)π̃(s′, a′) +
ln k
π̃(s′, a′)
) ,
where the right hand side does not depend on π; it follows that π̃(s, a)/π(s, a) is uniformly upper bounded over Pc. On the other hand, π̃(s, a)/π(s, a) ≥ π̃(s, a), so the ratio uniformly bounded in both directions over Pc, and let C0 denote this ratio. This in turn completes the proof: via Lemma C.1, the ratio of stationary distributions is also uniformly controlled, and via Lemma C.2, the mixing times are uniformly controlled. To obtain the final constants, it suffices to take the maximum of the relevant constants given by the preceding.
C.2 TD GUARANTEES
The first step is to characterize the fixed points of the TD update, which in turn motivates the linear MDP assumption (cf. Assumption 1.3), and is fairly standard (Bhandari et al., 2018). Lemma C.3. Let any policy π be given, and suppose x ∼ (sπ, π) is sampled from the stationary distribution (in vectorized state/action form), and x′ is a subsequent sample, and suppose ExxT is invertible. Then
ū := ∑ t≥0 ( γ [ ExxT ]−1 Ex(x′)T)t [ExxT]−1 Exr is a fixed point of the expected TD update, meaning
Eū = E ( ū− ηx (〈 x− γx′, ū 〉 − r )) = ū.
Moreover, under the linear MDP assumption (cf. Assumption 1.3), then xTsaū = Qπ(s, a). Lastly, if ū is the minimum norm fixed point, then ∥ū∥ ≤ 2/(1− γ).
Proof. For the fixed point claim, it suffices to show Ex (〈 x− γx′, ū 〉 − r ) = 0, but this is direct from the definition of ū, since Ex ( ⟨x− γx, ū⟩ − r
) = ([ ExxT ] − γ [ Ex(x′)T ]) ū− Exr
= ([ ExxT ] − γ [ Ex(x′)T ])∑ t≥0 ( γ [ ExxT ]−1 Ex(x′)T)t [ExxT]−1 Exr − Exr = [ ExxT
]∑ t≥0 ( γ [ ExxT ]−1 Ex(x′)T)t [ExxT]−1 Exr − [ ExxT
]∑ t≥1 ( γ [ ExxT ]−1 Ex(x′)T)t [ExxT]−1 Exr − Exr = [ ExxT ] ( γ [ ExxT ]−1 Ex(x′)T)0 [ExxT]−1 Exr − Exr = 0.
For the claims under the linear MDP assumption, using the notation from Assumption 1.3, letting Xπ denote the transition mapping induced by π, note by the tower property that
E ( x(x′)T ) = E ( xE [ (x′)T|x ]) = E ( xE [ (Xπv ′)T|x ]) = E ( x(XπMx) T ) = ExxTM TXTπ,
and therefore
xTsaū = x T sa ∑ t≥0 ( γ [ ExxT ]−1 Ex(x′)T)t [ExxT]−1 Exr = xTsa
∑ t≥0 ( γ [ ExxT ]−1 ExxTM TXπ)t [ExxT]−1 ExxTy = xTsa
∑ t≥0 ( γMTXTπ )t y
= Qπ(s, a).
Lastly, for the claim ∥ū∥ ≤ 2/(1 − γ), note that |Qπ(s, a)| ≤ 1/(1 − γ) since rewards lie within [0, 1], and since 1/2 ≤ ∥s∥ ≤ 1, assuming ū has minimum norm and letting X denote the span of all xsa in the support of the stationary distribution, and noting ∥xsa∥ = ∥s∥ · ∥a∥ ≥ 1/2, then
∥ū∥ = sup xsa∈X |ūTxsa| ∥s∥ ≤ 2 1− γ .
(The minimum norm property insured that ū ∈ X .)
Now comes the core TD guarantee. In comparison with prior work (Bhandari et al., 2018), the need for projections and starting from the stationary distribution are both dropped.
Lemma C.4. Let a policy π be given which interacts with an MDP whose states s ∈ Rd satisfy ∥s∥ ≤ 1, and whose action set is finite and represented as {e1, . . . , ek}; for convenience, let x = vec(seTk) denote a canonical vectorization of state/action pairs, as in the body of the paper. Let Pπ be the Markov chain on states induced by policy π, and assume it satisfies the following mixing time bound:
sup s
∥P tπ(s, ·)− sπ∥TV ≤ me−ct.
Let state/action/reward triples (sj , aj , rj)j<N be sampled via interaction of π with the MDP, where the initial state s0 is arbitrary, the random rewards satisfy rj ∈ [0, 1] almost surely, and write xj = vec(sjaTj), and let Ex⃗,r⃗ denote the expectation over this trajectory.
Consider the stochastic TD updates defined recursively via u0 = 0 and thereafter uj+1 := uj − ηxj ( uTxj − γuTxj+1 − rj ) ,
and let ū be a fixed point of the corresponding expected TD updates with stationary samples, meaning
Ex,r∼(sπ,π) x′∼x
x (〈 x− γx′, ū 〉 − r ) = 0,
where x is sampled from the stationary distribution and x′ is a subsequent sample, and assume ∥ū∥ ≤ 2/(1− γ).

heading: If the TD parameters N and η are chosen according to
text: N ≥ k, η ≤ 1 400 √ kN
, where k = ⌈ lnN + lnm
c
⌉ ,
then the average TD iterate û := 1N ∑ j<N uj satisfies
Ex⃗,r⃗ ( ∥û− ū∥2 + ηNExsa∼(sπ,π) ⟨xsa, ûN − ū⟩ 2 ) ≤ 54
(1− γ)2 .
Proof. The structure and primary concerns of the proof are as follows. The main issue is that uj , xj , xj+1 are statistically dependent; in fact, even in the unlikely but favorable situation that xj is distributed according to the stationary distribution (sπ, π), the conditional distribution of xj+1 given xj can still be far from stationary, even though xj+1 without conditioning is again stationary. The main trick used here is that η is so small relative to the mixing time that uj evolves much more slowly than xj , and thus any interaction between xj and uj can be replaced with an interaction between xj and uj−k, which are approximately independent. The structure of the proof then is to first establish a few deterministic worst-case estimates on the behavior in any consecutive k iterations, and then to perform an induction from k to N .
For notational convenience, since π is fixed in this proof, s is written for sπ , and E will denote expectation over the random trajectory (rather than the more verbose Ex⃗,r⃗, as in the statement).
Worst case control between any uj and uj−k. Proceeding with this first part of the proof, define Tj(u) := xj 〈 xj − γxj+1, u 〉 − xjrj ,
whereby
uj+1 = uj − ηTj(uj), ∥uj+1 − uj∥ = η∥xj 〈 xj − γxj , uj 〉 − xjrj∥ ≤ η ( (1 + γ)∥uj∥+ 1 ) , ∥uj − uj−k∥ ≤ j−1∑
i=j−k
∥ui+1 − ui∥ ≤ kη + η(1 + γ) j−1∑
i=j−k
∥uj∥. (C.1)
These inequalities will be useful in the induction as well, but now consider the first k iterations.
Controlling the first k iterations. Specifically, for any i ≤ k, it will be established via induction that ∥ui − ū∥ ≤ (1 + 1/(2k))i ( 2
1− γ
) + η ∑ l<i (1 + 1/(2k))l ( 3 1− γ ) .
The base case follows since u0 = 0 and ∥ū∥ ≤ 2/(1− γ). For the inductive step, since η(1 + γ) ≤ 1/(2k),
∥ui+1 − ū∥ = ∥ui − ū− η ⟨xi − γxi+1, ui − ū+ ū⟩ − ηxiri∥ ≤ (1 + η(1 + γ))∥ui − ū∥+ (1 + η(1 + γ))∥ū∥+ 1
≤ (1 + 1/(2k))i+1 ( 2
1− γ
) + η ∑ l<i (1 + 1/(2k))l+1 ( 2 1− γ ) + 2 + 2η + 2ηγ + 1− γ 1− γ
≤ (1 + 1/(2k))i+1 ( 2
1− γ
) + η ∑ l<i+1 (1 + 1/(2k))l ( 3 1− γ ) .
Since η(1 + γ) ≤ 1/(6k), it follows for every i ≤ k that (1 + η(1 + γ))i ≤ 2 and
∥ui − ū∥ ≤ 4 + 6ηk 1− γ ≤ 5 1− γ . (C.2)
This concludes the proof for the initial k iterations.
Controlling the remaining iterations via induction. The rest of the proof now proceeds via induction on iterations j′ between k and N ; specifically, given j′ ∈ {k − 1, . . . , N − 1}, it will be shown that
E∥uj′+1 − ū∥2 + Eη j′∑ i=k Ex∼(s,π) ⟨x, ui − ū⟩ 2 ≤ 26 (1− γ)2 . (C.3)
The base case j′ = k − 1 follows from eq. (C.2), thus consider j′ + 1 with j′ ≥ k − 1. The remainder of this inductive step will first introduce a variety of inequalities which need to hold for all j ∈ {k, . . . , j′}, before returning to consideration of j′ at the end. Before continuing with the core argument for a fixed j, there are a few useful inequalities to establish, which will be used many times.
• Combining the inductive hypothesis with eq. (C.1),
E∥uj − uj−k∥2 ≤ 2k2η2 + 2η2(1 + γ)2k j−1∑
i=j−k
E∥uj − ū+ ū∥2.
≤ 2k2η2 + 2η2(1 + γ)2k j−1∑
i=j−k
( 56
(1− γ)2 +
2
(1− γ)2
)
≤ 500k 2η2
(1− γ)2 . (C.4)
This is the explicit expression that will appear when moving between uj and uj−k to introduce (approximate) statistical independence.
• Next, we would like to argue that sj is distributed almost as the stationary distribution s, but must contend with dependence of elements of the chain. As such, consider the distribution of sj conditioned on the chain up through sj−k, and the corresponding xj = vec(sjaTj). Let yj ∼ (s, π) denote the random variable we want, meaning yj = vec(syjaTyj ) with (syj , ayj ) ∼ (s, π), and write xj as a mixture distribution where we first flip a coin of some bias, and then if it is heads we output yj , otherwise if tails we output some sample zj = vec(szja T zj ), where
the distribution of zj is worst-case in the sense that all we can say is it is bounded, meaning ∥zj∥ ≤ ∥szj∥ · ∥azj∥ ≤ 1. Viewing xj now as this mixture distribution, our goal is to bound the probability that xj = zj , and then split the analysis into two cases: one where xj = yj and things behave as we want, and one where xj = zj , and we only have worst-case controls.
To control these quantities and their probabilities, we can use a characterization of total variation distance in terms of couplings (Levin et al., 2006, Proposition 4.7): namely, letting Ej denote the “heads” event above where xj is a sample from yj , and thus ¬Ej corresponds to xj being a sample from zj , then Pr[¬Ej ] = ∥sj − s∥TV. Since we are conditioning on sj−k and can only depend on the randomness in the k Markov chain steps since then, using the assumed mixing time bound and choice of k gives us
Pr[¬Ej |sj−k] ≤ sup sj−k
∥P kπ (sj−k, ·)− s∥TV ≤ me−ck ≤ 1
N . (C.5)
Later in the proof, gaps in the chain of length k will be inserted, then the tower property of conditional expectation will be used to condition on the chain up through j − k, and lastly the above reasoning will be used to control xj via yj , zj , and Ej . A similar but more sophisticated idea for dealing with dependence appears in the literature on sampling from convex bodies via random walks (Vempala, 2005, Lemma 7.2); there too, it is necessary to consider samples only which are far apart in time.
• The last convenience inequality deals with Tj . Here it is convenient define perturbed versions which hold under Ej and ¬Ej :
Tj(u;Ej) := zj 〈 zj − γzj+1, u 〉 − zjrj , Ts(u) := Ex,r∼(s,π) x′∼x x 〈 x− γx′, u 〉 − rx.
Indeed, to deal with all these forms simultaneously, define a general form Tν(u) := Ex,x′,r∼νx 〈 x− γx′, u 〉 − rx, where ν is some distribution over (x, r, x′); for instance, it can simply deterministically return (xj , rj , xj+1, or (zj , rj , zj+1), or sample from (s, π); in this way, Tj and Tj(·;Ej) and Ts can be handled simultaneously with a single proof: for any i ≤ j, by the inductive hypothesis (cf. eq. (C.3)), and some worst-case handling of ν,
E∥Tν(ui)∥2 = E ∥∥∥Ex,r,x′∼νx 〈x− γx′, ui − ū+ ū〉+ xr∥∥∥2
≤ E4 ( (1 + γ)2∥ui − ū∥2 + (1 + γ)2∥ū∥2 + 1 ) ≤ 4 ( (1 + γ)226 + (1 + γ)2 + (1− γ)2 ) (1− γ)2
≤ 500 (1− γ)2 . (C.6)
Using similar worst-case reasoning, for any ν and u and u′,
∥Tν(u)− Tν(u′)∥2 = ∥∥∥Ex,r,x′∼νx 〈x− γx′, u〉− xr − x 〈x− γx′, u′〉+ xr∥∥∥2
= ∥∥∥Ex,r,x′∼νx 〈x− γx′, u− u′〉∥∥∥2
≤ Ex,r,x′∼ν∥x∥2 · ∥x− γx′∥2 · ∥u− u′∥2
≤ (1 + γ)2∥u− u′∥2. (C.7)
Now comes the main part of the inductive step. Expanding the square and making one appeal to eq. (C.6) with Tν = Tj ,
E∥uj+1 − ū∥2 = E∥uj − ū∥2 − 2ηE 〈 uj − ū, Tj(uj) 〉 + η2E∥Tj(uj)∥2
≤ E∥uj − ū∥2 − 2ηE 〈 uj − ū, Tj(uj) 〉 + 500η2
(1− γ)2 . (C.8)
To lower bound the middle term, making extensive use of eqs. (C.4) to (C.7) combined with the Cauchy-Schwarz inequality, and the inductive hypothesis to control E∥uj−k − ū∥2,
E 〈 uj − ū, Tj(uj) 〉 ≥ E 〈 uj−k − ū, Tj(uj) 〉 − E∥uj−k − uj∥ · ∥Tj(uj)∥
≥ E 〈 uj−k − ū, Tj(uj−k) 〉 − E ∥∥uj−k − ū∥∥ ·∥∥Tj(uj)− Tj(uj−k)∥∥ − √ E∥uj−k − uj∥2 √ E∥Tj(uj)∥2
≥ E 〈 uj−k − ū, Tj(uj−k) 〉 − √ E ∥∥uj−k − ū∥∥2√E∥∥Tj(uj)− Tj(uj−k)∥∥2
− √
500 · 500k2η2 (1− γ)2
≥ E 〈 uj−k − ū, Tj(uj−k) 〉 −
√ 26 (1− γ)2 √ (1 + γ)2E∥uj − uj−k∥2 − 500kη (1− γ)2
≥ E 〈 uj−k − ū, Tj(uj−k) 〉 − 750kη
(1− γ)2 .
Now comes the key step of the proof, using the tower property and invoking eq. (C.5): continuing with the non-constant term, but also using ETj = Ts under event Ej and the inductive hypothesis,
E 〈 uj−k − ū, Tj(uj−k) 〉 = E 〈 uj−k − ū,E[Tj(uj−k)|xj−k = x] 〉 ≥ E 〈 uj−k − ū, Ts(uj−k) 〉 inf sj−k Pr[Ej |sj−k]
− E 〈 uj−k − ū,E[Tj(uj−k)|¬Ej ] 〉 sup sj−k Pr[¬Ej |sj−k]
≥ 1 2 E 〈 uj−k − ū, Ts(uj−k) 〉 − 1 N √ E∥uj−k − ū∥2 √ E∥Tj(uj−k;¬Ej)∥2,
≥ 1 2 E 〈 uj−k − ū, Ts(uj−k) 〉 − √ 26 · 500 N(1− γ)2
≥ 1 2 E 〈 uj−k − ū, Ts(uj−k) 〉 − 400 N(1− γ)2 .
Again continuing with the non-constant term, and using the general inequality 2ab ≤ a2 + b2 which holds for any reals a, b, letting x ∼ (s, π) and x′ ∼ x and r a random reward (i.e., all the random quantities used to construct Ts , though r will cancel), and lastly introducing Ts(ū) via the fixed
point property in the form Ts(ū) = 0,〈 uj−k − ū, Ts(uj−k) 〉 = 〈 uj−k − ū, Ts(uj−k)− Ts(ū) 〉 = Ex,r,x′ 〈 x, uj−k − ū 〉 〈 x− γx′, uj−k − ū
〉 = Ex,r,x′ 〈 x, uj−k − ū
〉2 − γ 〈x, uj−k − ū〉 〈x′, uj−k − ū〉 ≥ Ex,r,x′ 〈 x, uj−k − ū
〉2 − γ/2(〈x, uj−k − ū〉2 + 〈x, uj−k − ū〉2) = (1− γ)Ex 〈 x, uj−k − ū 〉2 ,
where EEx 〈 x, uj−k − ū 〉2 ≥ EEx 〈x, uj − ū〉2 + 2EEx 〈x, uj − ū〉 〈x, uj−k − uj〉+ EEx 〈x, uj−k − uj〉2 ≥ EEx 〈 x, uj − ū
〉2 − 2√E∥uj − ū∥2√E∥uj−k − uj∥2 ≥ EEx 〈 x, uj − ū 〉2 − 2√26 · 500k2η2 (1− γ)2
≥ EEx 〈 x, uj − ū 〉2 − 800kη (1− γ)2 .
Plugging all of this back in to eq. (C.8) gives E∥uj+1 − ū∥2 ≤ E∥uj − ū∥2 − η(1− γ)EEx 〈 x, uj − ū 〉2 +
1 (1− γ)2 ( 750kη2 + 400N−1η + 800kη2 ) ≤ E∥uj − ū∥2 − η(1− γ)EEx 〈 x, uj − ū 〉2 + 1600kη2 + 400η/N
(1− γ)2 ,
which after summing over all k ≤ j ≤ j′ and telescoping and re-arranging gives
E∥uj′+1 − ū∥2 + j′∑ i=k η(1− γ)EEx ⟨x, ui − ū⟩2 ≤ E∥uk − ū∥2 + j′∑ i=k 1600kη2 + 400η/N (1− γ)2
≤ 25 (1− γ)2 +N
( 1600kη2 + 400η/N
(1− γ)2
)
≤ 26 (1− γ)2 ,
which establishes the inductive hypothesis stated in eq. (C.3).
Final cleanup. To finish the proof, a tiny amount of cleanup is needed. Adding the missing prefix of the sum from the conclusion of the induction gives
E∥uN − ū∥2 + ∑ i<N η(1− γ)EEx 〈 x, uj − ū 〉2 ≤ 26 (1− γ)2 + ∑ i<k η(1− γ)EEx ⟨x, ui − ū⟩2
≤ 26 (1− γ)2 + ∑ i<k 25η(1− γ) (1− γ)2
≤ 27 (1− γ)2 .
The final bound now follows by using Jensen’s inequality to introduce ûN in the summation term, and introducing ûN within the norm term by noting the bound held for all i < N and thus the triangle inequality implies ∥û − ū∥ ≤ ∑ i<N ∥ui − ū∥/N ≤ √ 27/(1 − γ), whose square can be added to both sides to give the final bound.
Lastly, the proof of Lemma 3.3 in the body is a quick consequence of Lemma C.4 and Lemma C.3.
Proof of Lemma 3.3. Lemma 3.3 is a restatement of Lemma C.4, but using a combination of Assumption 1.3 and Lemma C.3 to ensure the TD fixed point ū The proof is via Lemma C.4, which gives a more general statement, but also substitutes in Qi via Lemma C.3.

heading: D PROOF OF THEOREM 1.4
text: Combining the mirror descent and sampling tools, we can finally prove Theorem 1.4.
Proof of Theorem 1.4. Throughout this proof, let δ > 0 denote a unit of failure probability; the final bound will use the choice δ := t−9/8/2, although most of the proof will simply write δ for sake of interpretation.
Define the following KL-bounded subset of policy space: P := ⋂ s∈S Ps, where Ps := { π : Kvsπ (π, π) ≤ ln k +
1
(1− γ)2
} .
By |S| applications of Lemma 3.1 (one for each Ps) and taking maxima/minima of the resulting constants, since sπ is positive for every state, then there exist constants pmin > 0, C1 > 0, and C2 ≥ 1 so that, for any π ∈ P and any state s and any optimal action a ∈ As,
pmin ≤ sπ(s), π(s, a) ≥ π(s, a)
C2 ,
and letting Pπ denote the transition matrix on the induced chain on S, for any time q, max s∈S ∥P qπ(s)− sπ∥TV ≤ C2 exp(−C1q). (D.1)
Lastly, the fully specified parameters N and η are
N := 107t2C42 lnC2
p4minC1 ln
( 107t2C42 lnC2
p4minC1
) , η :=
1
400 √ kN
, where k := ⌈ lnN + lnC2
C1
⌉ ,
which after expanding the choice of θ satisfy N = Θ ( t2 ln t ) , η = Θ ( 1√
N lnN
) ,
1 Nη ≤ p
2 min
4tC22 ,
where the first two match the desired statement, and the last inequality is used below.
The proof establishes the following inequalities inductively: defining εj for convenience as
εj := sup s,a
( Q̂i(s, a)−Qi(s, a) )2 + ηNE(s,a)∼(sπ,π) ( Q̂i(s, a)−Qi(s, a) )2 ,
then with probability at least 1− 2iδ, Kvsπ (π, πi) + θ(1− γ) ∑ j<i ( Vj(s)− Vπ(s) ) ≤ ln k + 1 (1− γ)2 , ∀s, (IH.MD)
EQ̂jεj ≤ 54 (1− γ)2 , ∀j ≤ i, (IH.TD.1)
εj ≤ 54
δ(1− γ)2 , ∀j ≤ i, (IH.TD.2)
where the first implies πi ∈ P directly, and instantiating these inequalities with i = t and δ = t−9/8/2 and rearranging gives the desired statement.
To establish the inductive claim, consider some i > 0 (the base case i = 0 comes for free), and suppose the inductive hypothesis holds for i − 1; namely, discard its 2(i − 1)δ failure probability, and suppose the three inequalities hold. This induction will first handle the mirror descent guarantee in eq. (IH.MD), and then establish the TD guarantees in eqs. (IH.TD.1) and (IH.TD.2) together.
The first inequality, eq. (IH.MD), is established via the simplified mirror descent bound in Lemma 2.1. To start, since Kν(π, π0) ≤ ln k for any measure ν, then instantiating the simplified bound in Lemma 2.1 for the first i iterations for any starting state s gives
Kvsπ (π, πi) + θ(1− γ) ∑ j<i ( Vπ(s)− Vj(s) ) ≤ ln k + θ
∑ j<i 〈 Qj − Q̂j , πj − π 〉 vsπ + θ2 ∑ j<i sup s,a Q̂j(s, a)2. (D.2)
Upper bounding the second two terms will make use of upper bounds on (εj)j<i, but rather than using only eq. (IH.TD.2), here is a more refined approach. For each j < i, define an indicator random variable
Fj := [ εj > 54 √ t
(1− γ)2
] ,
which by eq. (IH.TD.1) and Markov’s inequality (since εj ≥ 0) satisfies
PrQ̂j (Fj) ≤ PrQ̂j [ εj > √ tEQ̂jεj ] ≤ 1√
t .
By Hoeffding’s inequality applied to the i binary random variables (Fj)j<i, with probability at least 1− δ, and plugging in the choice δ = t−9/8/2,
∑ j<i Fj ≤ ∑ j<i Pr(Fj) +
√ i
2 ln
1 δ ≤
√ i ( 1 + √ 9
16 ln 2t
) ≤ √ 3t ln t;
henceforth discard this failure probability, bringing the total failure probability to (2i − 1)δ. Combining this with eq. (IH.TD.2) gives∑
j<i εj ≤ ∑ j<i Fj=1 εj + ∑ j<i Fj=0 εj
≤ ∑ j<i Fj=1
54 δ(1− γ)2 + ∑ j<i Fj=0 54 √ t (1− γ)2
≤ 54 (1− γ)2
(√ 3t ln t
δ + t3/2
)
≤ 270t 13/8
√ ln t
(1− γ)2 ≤ 1 8θ2(1− γ)2 .
Turning back to eq. (D.2), this gives a way to control the middle term: since π(s, b) = 0 for b ̸∈ As,∑ j<i 〈 Qj − Q̂j , πj − π 〉 vsπ ≤ ∑ j<i max s 〈 Qj − Q̂j , πj − π 〉 δs
≤ 1 pmin ∑ j<i 〈 Qj − Q̂j , πj − π 〉 sπj
= 1
pmin ∑ j<i ( E (s,a)∼(sj ,πj) (Qj(s, a)− Q̂j(s, a))
+ E s∼sj ∑ a∈As π(s, a)(Q̂j(s, a)−Qj(s, a)) )
≤ 2C2 pmin ∑ j<i E (s,a)∼(sj ,πj) |Qj(s, a)− Q̂j(s, a)| ≤ 2C2 √ i
pmin √∑ j<i E (s,a)∼(sj ,πj) (Qj(s, a)− Q̂j(s, a))2
≤ 2C2 √ i
pmin √ Nη √∑ j<i εj
≤ 1 2θ(1− γ) .
Meanwhile, for the last term in eq. (D.2), since sups,a Qj(s, a) ≤ 1/(1− γ),∑ j<i sup s,a Q̂j(s, a)2 ≤ 2 ∑ j<i sup s,a [ Qj(s, a)2 + ( Q̂j(s, a)−Qj(s, a) )2] ≤ 2t
(1− γ)2 + 2 ∑ j<i ϵj
≤ 1 2θ2(1− γ)2 .
Plugging all of this back in to eq. (D.2) gives Kvsπ (π, πi) + θ(1− γ) ∑ j<i ( Vπ(s)− Vj(s) ) ≤ ln k + θ
∑ j<i 〈 Qj − Q̂j , πj − π 〉 vsπ + θ2 ∑ j<i sup s,a Q̂j(s, a)2
≤ ln k + 1 (1− γ)2 ,
thus concluding the proof of eq. (IH.MD) and the mirror descent part of the inductive step.
The TD part of the inductive step is now direct: by eq. (IH.MD), then πi ∈ P , and thus eq. (IH.TD.1) follows directly from Lemma 3.3, and eq. (IH.TD.2) follows via Markov’s inequality after discarding another δ failure probability, bringing the total failure probability to 2iδ, and completing the inductive step and overall proof.

Review summaries:
The paper proposes and analyzes the convergence rate and optimality of a natural-actor-critic-like actor critic with linear function approximation in linear MDPs. The most important discovery is that once the policy is within the ball of the maximum entropy optimal policy, it remains there forever provided that the critic is sufficiently accurate. Consequently, one now needs to make ergodicity assumption for only the optimal policy, instead of all policies along the optimization path.

The paper provides a novel analysis to the linear MDP setting through an actor critic setup where the policy is softmax-parameterized. The claim is that we can avoid mixing time and exploration based assumptions by using this analysis. This is attractive since its much simpler/cleaner, but also comes with a slower convergence rate. The main steps include bounding the policy within a KL ball of the maximum entropy optimal policy through a mirror descent style analysis, followed by controlling the critic approximation error given the policy is within the KL ball.

This heavily technical theoretical paper main contribution is to show that Natural Actor-Critic is "philosophically" implicitly biased toward high entropy policies.  More precisely, the key result is to show that Actor-Critic, when set as a batched  mirror descent algorithm applied on a linear finite states and linear finite actions MDP with linear softmax policies, without regularization or explicit exploration, but with properly chosen parameters, maintains its policies in a KL ball of radius 1+ ln(k) + 1/(1-gamma)^2 around the maximum entropy optimal policy (the optimal policy which samples uniformly the optimal actions) with high probability (Theorem 1.4). It is worth noting that this result is obtained without global mixing assumptions on the MDP (only with a mixing assumption on the target policy).  This is an improvement from previous work (Khodadadian 2021) who assumed uniform mixing and provided only expectation bounds.  Dropping these assumption is however costly: with a step size set to 1/sqrt(t), the number of iterations required to obtain and epsilon-optimal policy is epsilon^{-14}.  The core of the paper is in the detailed proof which spans 11 pages of appendix.