Paper deep dive
Beyond State-Wise Mirror Descent: Offline Policy Optimization with Parametric Policies
Xiang Li, Yuheng Zhang, Nan Jiang
Intelligence
Status: succeeded | Model: Gemma-4-26B-A4B | Prompt: intel-v1 | Confidence: 88%
Last extracted: 7/20/2026, 7:32:03 AM
Summary
This paper addresses limitations in offline reinforcement learning (RL) by extending theoretical guarantees to parameterized policies over large or continuous action spaces. It identifies 'contextual coupling' as a core difficulty when applying state-wise mirror descent to standalone policy parameterization, showing that such approaches can suffer constant per-step regret. The authors propose connecting mirror descent to natural policy gradients, leading to novel actor update rules like Least-Square Policy Update (LSPU) and Distributionally Robust Policy Update (DRPU), which provide finite-sample guarantees and unify offline RL with imitation learning under specific conditions.
Entities (8)
Relation Signals (6)
PSPI → uses → Mirror Descent
confidence 90% · these algorithms rely on state-wise mirror descent
Contextual Coupling → causes → Regret
confidence 88% · contextual mirror descent... can suffer a constant per-step regret... due to an underlying challenge we coin contextual coupling.
PSPI → limitedto → Finite Action Spaces
confidence 85% · PSPI, only apply to finite and small action spaces.
Natural Policy Gradient → inspires → DRPU
confidence 82% · an alternative formulation inspired by natural policy gradients... admits a general regret decomposition
LSPU → relatedto → Natural Policy Gradient
confidence 80% · a least-square regression update-rule (LSPU) closely related to NPG
DRPU → unifies → Offline RL
confidence 75% · our DRPU method recovers behavior cloning, providing an interesting unification between offline RL and imitation learning.
Cypher Suggestions (0)
No Cypher suggestions yet.
Abstract
Abstract:We investigate the theoretical aspects of offline reinforcement learning (RL) under general function approximation. While prior works (e.g., Xie et al., 2021) have established the theoretical foundations of learning a good policy from offline data via pessimism, existing algorithms that are computationally tractable (often in an oracle-efficient sense), such as PSPI, only apply to finite and small action spaces. Moreover, these algorithms rely on state-wise mirror descent and require actors to be implicitly induced from the critic functions, failing to accommodate standalone policy parameterization which is ubiquitous in practice. In this work, we address these limitations and extend the theoretical guarantees to parameterized policy classes over large or continuous action spaces. When extending mirror descent to parameterized policies, we identify contextual coupling as the core difficulty, and show how connecting mirror descent to natural policy gradient leads to novel analyses, guarantees, and algorithmic insights, including a surprising unification between offline RL and imitation learning.
Tags
Links
- Source: https://arxiv.org/abs/2602.23811v4
- Canonical: https://arxiv.org/abs/2602.23811v4
Trouble viewing inline? Open PDF directly →
Full Text
210,203 characters extracted from source content.
Expand or collapse full text
Beyond State-Wise Mirror Descent: Offline Policy Optimization with Parametric Policies Xiang Li Nanjing University lllllimited306@gmail.com &Yuheng Zhang UIUC yuhengz2@illinois.edu &Nan Jiang UIUC nanjiang@illinois.edu Abstract We investigate the theoretical aspects of offline reinforcement learning (RL) under general function approximation. While prior works (e.g., Xie et al., 2021) have established the theoretical foundations of learning a good policy from offline data via pessimism, existing algorithms that are computationally tractable (often in an oracle-efficient sense), such as PSPI, only apply to finite and small action spaces. Moreover, these algorithms rely on state-wise mirror descent and require actors to be implicitly induced from the critic functions, failing to accommodate standalone policy parameterization which is ubiquitous in practice. In this work, we address these limitations and extend the theoretical guarantees to parameterized policy classes over large or continuous action spaces. When extending mirror descent to parameterized policies, we identify contextual coupling as the core difficulty, and show how connecting mirror descent to natural policy gradient leads to novel analyses, guarantees, and algorithmic insights, including a surprising unification between offline RL and imitation learning. 1 Introduction Learning a good policy from historical data, a.k.a. offline reinforcement learning (RL), is an important paradigm for bringing RL to real-life domains (Levine et al., 2020; Prudencio et al., 2023). While the statistical aspects of offline RL theory are relatively well-understood (Jiang and Xie, 2025), the information-theoretic algorithms that achieve strong statistical guarantees under general conditions are often not immediately computationally tractable, and addressing the computational challenge typically requires additional assumptions or sacrificing some of the statistical generality. In particular, while the analyses often make mild assumptions on the critic, strong restrictions are often imposed on the actor, limiting the theory’s applicability scope and practical relevance (Xie et al., 2021; Cheng et al., 2022). As a canonical example, consider PSPI by Xie et al. (2021) (Section 3), an actor-critic style algorithm that achieves strong guarantees when critics are modeled via general function approximation. PSPI assumes an oracle that computes a pessimistic critic fkf_k for policy πk _k, and employs mirror descent (MD) in the actor update: πk+1(a∣s)∝πk(a∣s)exp(ηfk(s,a)). _k+1(a s) _k(a s) (η f_k(s,a) ). (1) This brings two issues. First, the guarantee of PSPI depends on the log-cardinality of the action space and thus does not apply to arbitrarily large (including continuous) action spaces that are ubiquitous in control problems (e.g., Gaussian policies in robotics). Secondly, MD update in Eq.(1) is state-wise, i.e., the action distribution in each state is updated independently. This means that the actor (policy) is implicitly induced from the critics (fkf_k) and cannot have its own standalone parameterization (e.g., an actor network that is separate from the critic network). These limitations not only create a disconnection between theory and practice, but also indicate a gap in theory itself: standalone policy parameterization over continuous actions is not an issue at all when we only pursue statistical guarantees and ignore computational feasibility (Xie et al., 2021, Section 3), but difficulties arise when we aim for computational efficiency. In this work, we address this gap by systematically studying variants of policy optimization methods and their statistical/computational properties, under the assumption that a standard pessimistic critic oracle is given (Assumption 2). Our contributions are 3-fold: • PSPI with general action spaces. In Section 3, we revisit the PSPI algorithm to disentangle critic- and actor-side errors, and present a mild extension of the analysis to arbitrarily large (and even continuous) action spaces. • Contextual coupling: hardness and a guiding principle. In Section 4, we consider standalone policy parameterization. Perhaps surprisingly, we show that contextual mirror descent in Eq. (4), the natural generalization of state-wise mirror descent to parametric policy class, can suffer a constant per-step regret even with an accurate critic, due to an underlying challenge we coin contextual coupling. Instead, an alternative formulation inspired by natural policy gradients (NPG) (Kakade, 2001) and compatible function approximation (CFA) (Sutton et al., 1999) admits a general regret decomposition, which can serve as the guiding principle for designing effective actor updates. • Actor updates with finite-sample guarantees. Building on the earlier regret decomposition, we develop and analyze two statistically and computationally efficient actor updates in Section 5: a least-square regression update-rule (LSPU) closely related to NPG, and a distributionally robust update-rule (DRPU) that leverages importance weighting and can be more robust to actor-critic incompatibility. Surprisingly, when the offline distribution coincides with that of the comparator policy, our DRPU method recovers behavior cloning, providing an interesting unification between offline RL and imitation learning. 2 Preliminary Markov Decision Processes. We formulate RL in infinite-horizon discounted Markov Decision Processes (MDPs), specified by (,,P,R,γ,d0)(S,A,P,R,γ,d_0), where S is the state space, A is the action space, P:×→Δ()P:S×A→ (S) is the transition kernel, R:×→[0,Rmax]R:S×A→[0,R_ max] is the reward function, γ∈[0,1)γ∈[0,1) is the discount factor, and d0∈Δ()d_0∈ (S) is the initial state distribution. We mostly consider finite and discrete S and A with possibly arbitrarily large cardinalities, and our results can be easily extended to continuous action spaces as exemplified in Appendix B.2. A (stochastic) policy π:→Δ()π:S→ (A) specifies a decision-making strategy. Its expected discounted return is denoted by J(π)=π[∑t=0∞γtrt]J(π)=E_π[ _t=0^∞γ^tr_t], with s0∼d0s_0 d_0, at∼π(⋅|st)a_t π(·|s_t), rt=R(st,at)r_t=R(s_t,a_t), and st+1∼P(⋅|st,at)s_t+1 P(·|s_t,a_t). The Q-function of π is defined by Qπ(s,a)=π[∑t=0∞γtrt|s0=s,a0=a]Q^π(s,a)=E_π[ _t=0^∞γ^tr_t|s_0=s,a_0=a], which is the unique fixed point of its Bellman operator πT^π: ∀f∈ℝ×∀ f ^S×A, (πf)(s,a)=R(s,a)+γs′∼P(⋅|s,a)[f(s′,π)](T^πf)(s,a)=R(s,a)+ _s P(·|s,a)[f(s ,π)], where f(s′,π)=a′∼π(⋅|s′)[f(s′,a′)]f(s ,π)=E_a π(·|s )[f(s ,a )]. Vπ(s)=Qπ(s,π)V^π(s)=Q^π(s,π) is the (state-)value function and Aπ(s,a)=Qπ(s,a)−Vπ(s)A^π(s,a)=Q^π(s,a)-V^π(s) is the advantage function. Let dπd^π denote the discounted state-action occupancy distribution of policy π, i.e., dπ(s,a)=(1−γ)∑t=0∞γtdtπ(s,a)d^π(s,a)=(1-γ) _t=0^∞γ^td_t^π(s,a), where dtπd_t^π is the marginal distribution of (st,at)(s_t,a_t).111With a slight abuse of notation, we also use dπd^π to denote the discounted state occupancy of policy π (after marginalizing out the actions). That is, dπ(s)=∑a∈dπ(s,a)d^π(s)= _a d^π(s,a). Offline RL. In offline RL, we learn from pre-collected data without environment interaction. For conceptual clarity, we assume access to two datasets: a critic dataset with transition tuples (s,a,r,s′)(s,a,r,s ) for fitting the critic, and an actor dataset consisting of only (s,a)(s,a) pairs for actor updates. As our focus is on the actor, we do not explicitly characterize the critic dataset, since its properties will later be encapsulated in an oracle assumption (Assumption 2). For the actor dataset, we assume access to N i.i.d. (s,a)(s,a) pairs drawn from a data distribution dDd^D. In practice, they may be extracted from the critic dataset, but our formulation also allows additional data sources, such as expert annotations, which are considered in hybrid setting of imitation learning and offline RL (Mao, 2023; Yang et al., 2023). We adopt the following standard assumption on data coverage, known as density coverage (Jiang and Xie, 2025). The theoretical guarantees in offline RL typically state that we can compete with any comparator policy πcp _ cp that is well-covered by data (i.e., C is small). Assumption 1 (Actor-Side Data Coverage). Assume sups,a|dπcp(s,a)/dD(s,a)|≤<∞ _s,a|d _ cp(s,a)/d^D(s,a)|≤ C<∞. To deal with large state and action spaces, we are in the function approximation regime, modeling Q-functions using a function class ℱ=f:×→[0,Vmax]F=\f:S×A→[0,V_ max]\, where Vmax=Rmax/(1−γ)V_ max=R_ max/(1-γ). Typical choices of ℱF include linear classes or deep neural networks. In the literature, ℱF generally needs to satisfy expressivity conditions such as realizability or Bellman completeness (Chen and Jiang, 2019), which will also be implicitly captured in Assumption 2. Math notation. We use A≲BA B or A=(B)A=O(B) to denote A≤cBA≤ cB for some constant c>0c>0; A=Ω(B)A= (B) is equivalent to B=(A)B=O(A). For a function f:→ℝf:X where X is finite, its supremum norm is ‖f‖∞=maxx∈|f(x)|\|f\|_∞= _x |f(x)|. The KL divergence is DKL(p∥q)=∑x∈p(x)logp(x)q(x)D_ KL(p\|q)= _x p(x) p(x)q(x) for two distributions with probability mass functions p and q. 3 Pessimistic Soft Policy Iteration as State-wise Mirror Descent Xie et al. (2021) proposed Pessimistic Soft Policy Iteration (PSPI), an actor-critic method for offline policy optimization (see Algorithm 1). At a high level, PSPI proceeds iteratively: at each iteration k, the critic produces a pessimistic estimate fkf_k of the value QπkQ _k, and the actor performs a soft improvement step based on fkf_k. The final output is a (trajectory-level) uniform mixture of the intermediate policies π1,…,πK _1,…, _K. Algorithm 1 Pessimistic Soft Policy Iteration (PSPI) (Xie et al., 2021) Input: number of iterations K, learning rate η Initialize policy π1 _1 as an arbitrary policy (e.g., uniform over A) for k=1,2,…,Kk=1,2,…,K do Critic: compute πk _k’s pessimistic Q-function fkf_k using oracle O satisfying Assumption 2 Actor: update policy by Eq. (1), i.e., πk+1(a∣s)∝πk(a∣s)exp(ηfk(s,a)) _k+1(a s) _k(a s) (η f_k(s,a) ) end for Output: π^=Unif[π1:K] π=Unif[ _1:K] Since our ultimate goal is to bound the suboptimality gap J(πcp)−J(π^)J( _ cp)-J( π) between some comparator policy πcp _ cp and the output policy π π, a key component in the analysis is to decompose it via the generalized performance difference lemma (Lemma 25): J(πcp)−J(π^)=J( _ cp)-J( π)= 11−γ(1K∑k=1Ks∼dπcp[fk(s,πcp)−fk(s,πk)]⏟actor-side error (Eq. (2)), focus of this paper+1K∑k=1K(dπcp[πkfk−fk]+dπk[fk−πkfk])⏟critic-side Bellman error, handled by Assumption 2). 11-γ ( 1K _k=1^KE_s d _ cp[f_k(s, _ cp)-f_k(s, _k)]_actor-side error (Eq.~ eq:regret), focus of this paper+ 1K _k=1^K (E_d _ cp[T _kf_k-f_k]+E_d _k[f_k-T _kf_k] )_critic-side Bellman error, handled by Assumption~ ass:oracle ). The first term corresponds to actor-side optimization error, capturing how well π1,…,πK _1,…, _K optimizes against πcp _ cp measured by the pessimistic Q-function; the remaining terms are critic-side errors that measure the violation of the Bellman equations. Such decomposition cleanly separates the difficulty of policy optimization (i.e., actor update) from that of value estimation. To isolate the actor-side difficulty, we abstract the critic as a pessimistic oracle O, as reflected in Assumption 2, which directly controls the latter two Bellman error terms. Such control is central to offline RL theory and essentially an intermediate guarantee achieved in many existing works under standard assumptions (Jin et al., 2020; Xie et al., 2021; Cheng et al., 2022). More detailed discussions and algorithmic realizations of this oracle, e.g., via Bellman error minimization or marginalized importance sampling, are provided in Appendix B.1. Assumption 2 (Pessimistic Oracle). We have an efficient oracle O that, given any policy π as input, it outputs a function f that satisfies the following two conditions: 1. (Pessimism) The function f is a pessimistic estimation of QπQ^π (up to some tolerance ϵr≥0 _r≥ 0), i.e., Jf(π)−J(π)≤ϵr/(1−γ)J_f(π)-J(π)≤ _r/(1-γ) with high probability, where Jf(π)=s∼d0[f(s,π)]J_f(π)=E_s d_0[f(s,π)]. 2. (Bounded “Transferred" Bellman error) The Bellman error under dπcpd _ cp is bounded by some ϵb>0 _b>0. That is, dπcp[πf−f]≤ϵbE_d _ cp[T^πf-f]≤ _b with high probability. Under Assumption 2, ϵr+ϵb _r+ _b naturally controls the latter two terms in the suboptimality decomposition. Thus, bounding J(πcp)−J(π^)J( _ cp)-J( π) reduces to controlling the actor-side error, i.e., the first term in the decomposition, which is a notion of regret we focus on throughout the remainder of the paper: RegKK:=1K∑k=1Ks∼dπcp[fk(s,πcp)−fk(s,πk)]. Reg_KK:= 1K _k=1^KE_s d _ cp [f_k(s, _ cp)-f_k(s, _k) ]. (2) State-wise regret control. Note that in Eq. (2), the regret is measured under an unknown and often inaccessible state distribution dπcpd _ cp. A natural workaround is to solve this online optimization problem in a state-wise manner: If the regret can be controlled uniformly for each state s∈s , then the overall regret bound holds for any dπcp∈Δ()d _ cp∈ (S). Also, it is worth noting that the computational complexity of doing so does not depend on the size of S, since we only need to lazily run the algorithm on states observed in the data. Leveraging this observation, the actor update in PSPI can be interpreted as a multiplicative-weights update from online learning (Hazan and others, 2016). In particular, for each state, the policy update in Eq. (1) corresponds to performing mirror descent (MD) with KL regularizer: πk+1(⋅|s)=argmaxπ(⋅∣s)∈Δ()fk(s,π)−1ηDKL(π(⋅|s)∥πk(⋅|s)). _k+1(·|s)= π(· s)∈ (A) \f_k(s,π)- 1ηD_ KL(π(·|s)\| _k(·|s)) \. (3) This perspective leads to the regret guarantee established for PSPI in (Xie et al., 2021), which, however, depends on |||A|, the cardinality of A.222Apart from the regret’s dependence on |||A|, the computation required by PSPI might also seem to require enumeration over A since we need to sample from the softmax policy in Eq.(1). This is, however, not always the case, as one can use techniques such as rejection sampling to avoid enumeration, and structured settings such as LQRs admit closed-form expressions for the policy that can be efficiently sampled from; see Appendix B.3 for details. Thus, the PSPI algorithm is also computationally viable for large or even continuous A. We next show that their result can be directly extended to remove the explicit |||A| dependence and thus handle arbitrarily large action spaces; we state the result below for finite and discrete A to be consistent with the setup of the rest of the paper. Theorem 1 (Regret Bound of Algorithm 1). Assume that for each iteration k, the critic fkf_k is bounded in [0,Vmax][0,V_ max], and that DKL(πcp∥π1)<∞D_ KL( _ cp\| _1)<∞. Then by choosing η=8DKL(πcp∥π1)/(KVmax2)η= 8D_ KL( _ cp\| _1)/(KV_ max^2), PSPI iterates satisfy RegKK≤VmaxDKL(πcp∥π1)2K, Reg_KK≤ V_ max D_ KL( _ cp\| _1)2K, where DKL(πcp∥π)=s∼dπcp[DKL(πcp(⋅|s)∥π(⋅|s))]D_ KL( _ cp\|π)=E_s d _ cp[D_ KL( _ cp(·|s)\|π(·|s))] is the expected KL divergence under dπcpd _ cp. The result is a mild extension of Xie et al. (2021, Theorem 4.1), where we keep DKL(πcp∥π1)D_ KL( _ cp\| _1) instead of upper-bounding it with log|| |A| as in Xie et al. (2021). This allows the term to be well bounded for some structured policies, even when A is unbounded in cardinality or even continuous. In Appendix B.2, we show that Theorem 1 can be extended straightforwardly to continuous action space,333Results in subsequent sections can also be extended to continuous action spaces in a similar manner, which we omit and stick to the discrete setup for readability. and for standard forms of continuous policies such as Gaussian policies, or structural action space like convex action space, the KL term remains well bounded; see Appendix B.3 for details. 4 Contextual Coupling in Parameterized Policy Optimization The state-wise mirror descent of PSPI in Section 3 does not have its own policy parameterization; rather, it is performing policy optimization within a softmax policy class implicitly induced from ℱF: π(⋅|s)∝π1(⋅|s)exp(∑i=1nfi(s,⋅)):k∈[K],f1:k∈ℱ\π(·|s) _1(·|s) ( _i=1^nf_i(s,·) ):k∈[K],f_1:k \. In this section, we move beyond this setting and consider policy optimization over a standalone policy class parameterized by some θ∈ℝθ d, which is ubiquitous in practice: Πθ:=πθ:θ∈ℝ. _θ:=\ _θ:θ d\. As standard, we consider gradient-type updates to the actor, which requires the following assumption on policy differentiability and smoothness assumptions in theoretical analyses (Agarwal et al., 2021). Such an assumption is widely adopted in the policy-gradient literature, and holds for many popular policy classes under appropriate norms, including the canonical softmax policies, log-linear policies, neural policies, and even Gaussian policies under mild conditions. Assumption 3 (Policy Class). Let πθ _θ be a differentiable policy parameterized by θ∈ℝθ d. For all (s,a)∈×(s,a) ×A, the log-probability is G-Lipschitz and β-smooth with respect to a chosen norm ∥⋅∥\|·\| (and its dual norm ∥⋅∥∗\|·\|_*). |logπθ(a|s)−logπθ′(a|s)|≤G∥θ−θ′∥,∥∇logπθ(a|s)−∇logπθ′(a|s)∥∗≤β∥θ−θ′∥.| _θ(a|s)- _θ (a|s)|≤ G\|θ-θ \|, \|∇ _θ(a|s)-∇ _θ (a|s)\|_*≤β\|θ-θ \|. Algorithm 2 Template for Actor-Critic Policy Optimization Input: number of iterations K, learning rate η Initialize policy π1=πθ1 _1= _ _1 as any policy in Πθ _θ for k=1,2,…,Kk=1,2,…,K do Critic: compute fkf_k using oracle O Actor: update policy by θk+1=θk+ηvk _k+1= _k+η v_k end for Output: π^=Unif[π1:K] π=Unif[ _1:K] 4.1 Why Contextual Mirror Descent Breaks In Section 3, we explained that PSPI admits a state-wise mirror descent interpretation: each state runs mirror descent and enjoys regret guarantee independently. To deal with the standalone policy class Πθ _θ, a natural attempt is to contextualize mirror descent by coupling these state-wise updates in Eq. (3) through the shared parameter θ and aggregating them across states via some state distribution: πk+1=argmaxπ∈Πθs∼dD[fk(s,π)−1ηDKL(π(⋅|s)∥πk(⋅|s))], _k+1= π∈ _θ \ E_s d^D [f_k(s,π)- 1ηD_ KL(π(·|s)\| _k(·|s)) ], (4) where πk _k denotes πθk _ _k. The above form of contextual mirror descent is defined under the state-marginal of the data distribution dDd^D, which is the only state distribution directly accessible in the offline setting. In contrast, the regret in Eq. (2) is evaluated under the comparator distribution dπcpd _ cp. As a consequence, the challenge of distribution mismatch arises between Eq. (2) and Eq. (4). Notice that the integrand fk(s,πcp)−fk(s,πk)f_k(s, _ cp)-f_k(s, _k) in Eq. (2) is not one-sided and may be positive in some states while negative in others. As a result, errors controlled under dDd^D do not necessarily translate to dπcpd _ cp even with the coverage condition (Assumption 1).444This sharply contrasts with the squared loss in Fitted-Q or Bellman residual minimization (Munos, 2007; Munos and Szepesvári, 2008; Antos et al., 2008), where the non-negative loss allows for error transfer under coverage conditions. Therefore, regret bound under dDd^D does not, in general, imply guarantee under dπcpd _ cp. Indeed, we show via the following hardness result that contextual mirror descent indeed fails (even if we do not account for finite-sample errors and effectively assume infinite data), and the construction is deferred to Appendix C.1. Proposition 2 (Failure for Contextual Mirror Descent). There exist an MDP ℳM, a policy class Πθ _θ satisfying Assumption 3, a comparator policy πcp∈Πθ _ cp∈ _θ, and offline data satisfying Assumption 1, such that the policies πk\ _k\ produced by contextual MD in Eq. (4) incur constant per-step regret: s∼dπcp[fk(s,πcp)−fk(s,πk)]≥14,∀k≥2.E_s d _ cp [f_k(s, _ cp)-f_k(s, _k) ]≥ 14, ∀ k≥ 2. Consequently, it follows that RegK/K=Ω(1) Reg_K/K= (1). Proposition 2 shows that contextual MD can fail to minimize the regret against πcp _ cp, even if it satisfies Assumption 3 and is well covered by data. We attribute the failure to a concept we call contextual coupling, where aggregating state-wise updates under a mismatched state distribution induces systematic deviation across states through the shared parameterization. This contrasts with the positive results we establish later (Theorems 4 and 5): while those latter bounds may also admit constant per-step regret (e.g., when ϵCFA≠0 _ CFA≠ 0 in Theorem 4), they do so solely under actor-critic incompatibility (see Section 5.1), which is not the source of the hardness in Proposition 2. 4.2 Regret Decomposition via Compatible Function Approximation The negative result in Section 4.1 rules out a direct extension of PSPI via contextual mirror descent. Nevertheless, this does not preclude first-order methods altogether. In this section, we provide a regret decomposition lemma—which will give a guiding principle for algorithm design in Section 5—for general first-order updates in the form of (see Algorithm 2 for the algorithm template): θk+1=θk+ηvk, _k+1= _k+η v_k, (5) where vk∈ℝv_k d is an update vector at round k∈[K]k∈[K]. For instance, policy gradient (PG) corresponds to taking vkv_k as an estimate of the on-policy gradient (which yields monotonic improvement under the on-policy occupancy dπkd _k), while natural policy gradient (NPG) corresponds to a preconditioned version of this direction. In our setting, in each round the oracle O computes fkf_k for the current policy πk=πθk _k= _ _k, and we need to design the actor update rule (i.e., how vkv_k is chosen) accordingly. For now, we do not specify how vkv_k is constructed and allow it to be arbitrary, and our regret decomposition will hold for any sequence of update vectors vk\v_k\. Under Assumption 3, the update rule (5) induces a first-order approximation of the regret integrand fk(s,πcp)−fk(s,πk)f_k(s, _ cp)-f_k(s, _k) around the current policy, yielding a leading linear term and a higher-order optimization error controlled by smoothness. Crucially, the leading term can be expressed through the error of compatible function approximation (CFA) (Sutton et al., 1999; Kakade, 2001), which represents how policy gradients ∇logπθ∇ _θ approximates the advantage function AπθA _θ of the policy. Similar analysis in the on-policy case can be found in (Even-Dar et al., 2009; Agarwal et al., 2021). Lemma 3 (Regret Decomposition Lemma). Define the CFA error as errk=(s,a)∼dπcp[Ak(s,a)−vk⊤∇θlogπk(a∣s)], err_k=E_(s,a) d _ cp [A_k(s,a)-v_k _θ _k(a s) ], (6) where Ak(s,a)=fk(s,a)−fk(s,πk)A_k(s,a)=f_k(s,a)-f_k(s, _k) denotes the advantage function at round k. Then, under Assumption 3, consider Algorithm 2 with update sequence vk\v_k\ satisfying ‖vk‖≤BL\|v_k\|≤ B_L for all k. Then, with step size η=2DKL(πcp∥π1)/(βKBL2)η= 2D_ KL( _ cp\| _1)/(β KB_L^2), the following regret bound holds: RegKK≤BL2β⋅DKL(πcp∥π1)K+1K∑k=1Kerrk. Reg_KK≤ B_L 2β· D_ KL( _ cp\| _1)K+ 1K _k=1^K err_k. Lemma 3 shows that, as long as the size of the updates is bounded (‖v‖≤BL\|v\|≤ B_L), controlling the regret reduces to controlling the error of CFA, errk err_k, at each round. 5 Constructing Unified Policy Updates in Parameter Space We now apply the decomposition in Section 4.2 to construct policy updates vk\v_k\ that control the CFA error, i.e., errk err_k in Lemma 3. We present two principled approaches of this update, based on least-square regression and distributionally robust optimization, respectively. 5.1 Least Square Policy Update Recall that the error of CFA, errk err_k, quantifies how well the policy gradients ∇logπk(a∣s)∇ _k(a s) can linearly approximate the advantage function Ak(s,a)A_k(s,a) under dπcpd _ cp. Viewing ∇logπk(a∣s)∇ _k(a s) as features and Ak(s,a)A_k(s,a) as the regression target, this observation naturally leads to a noiseless linear regression formulation for constructing the update vkv_k, which we term least square policy update (LSPU). Specifically, we define the least-square loss at round k as Lk(v):=(s,a)∼dD[(Ak(s,a)−v⊤∇logπk(a∣s))2],L_k(v):=E_(s,a) d^D [(A_k(s,a)-v ∇ _k(a s))^2 ], where the expectation is taken on offline data distribution dDd^D. In each round k, the actor first computes the advantage function AkA_k, and then obtains the update vkv_k by minimizing LkL_k using samples, within the norm constraint ‖vk‖≤BL\|v_k\|≤ B_L. In particular, given (s(i),a(i))i=1N∼i.i.d.dD\(s^(i),a^(i))\_i=1^N i.i.d. d^D from the actor dataset, the constrained regression problem is given by: vk=argminv:‖v‖≤BL1N∑i=1N(Ak(s(i),a(i))−v⊤∇logπk(a(i)|s(i)))2.v_k= v:\|v\|≤ B_L 1N _i=1^N (A_k(s^(i),a^(i))-v ∇ _k(a^(i)|s^(i)) )^2. (7) Error transfer through the coverage condition. A key question is why the regression objective can be formed under the data distribution dDd^D, even though the error of CFA are defined under dπcpd _ cp. The reason is that the squared loss LkL_k is always non-negative (c.f. Section 4.1), allowing us to do distribution transfer via the coverage condition: dπcp[(Ak−v⊤∇logπk)2]≤⋅dD[(Ak−v⊤∇logπk)2].E_d _ cp [(A_k-v ∇ _k)^2 ]≤ C·E_d^D [(A_k-v ∇ _k)^2 ]. Moreover, since this is a linear regression problem, this density coverage (known as concentrability coefficient) can be further improved in the compatible case, i.e., when Ak=w⊤∇logπkA_k=w ∇ _k for some w∈ℝw d. Let the covariance matrix be ΣDπ=dD[∇logπ∇logπ⊤] _D^π=E_d^D[∇ π∇ π ]. In this case, we can sharpen the density coverage C (Assumption 1) with the notion of feature coverage (Jiang and Xie, 2025), though we omit such an improvement in our main theorems for readability (see Appendix E.4 for details): feat=maxk∈[K]dπcp[∇logπk]⊤(ΣDπk)−1dπcp[∇logπk] C_ feat= _k∈[K]\ E_d _ cp[∇ _k] ( _D _k)^-1E_d _ cp[∇ _k]. Relation to NPG. This least-square interpretation of policy update can be viewed as a form of the natural policy gradient (NPG) method under function approximation, which is well-studied in the on-policy setting (Kakade, 2001; Peters and Schaal, 2008; Agarwal et al., 2021). That said, our formulation differs from canonical on-policy (or off-policy) NPG since LSPU is computed on the offline data distribution dDd^D without any importance-weight correction. Such design choice follows directly from the decomposition in Lemma 3 and tailors specifically to offline RL. Actor-critic incompatibility. Even with an accurate critic fkf_k, the linear regression formulation above need not be well-specified. In general, the target AkA_k does not necessarily lie in the linear span of the features ∇logπk∇ _k. Hence we are in the agnostic learning setting and any regression-based update may inevitably incur an approximation error, even with infinite data. We capture such misspecification via a quantity ϵCFA _ CFA defined below. Assumption 4 (LSPU Approximation Error). Define vk∗v_k^* as the best linear approximator of the least-square loss LkL_k. Assume that vk∗v_k^* satisfies the norm constraint ‖vk∗‖≤BL\|v_k^*\|≤ B_L555Assumption 4 requires that the global minimizer vk∗v_k^*, which admits a closed-form solution, must satisfy ‖vk∗‖≤BL\|v_k^*\|≤ B_L. This can be achieved by setting BLB_L as a uniform upper bound GVmax/λminGV_ max/ _ min, where λmin _ min denotes the smallest eigenvalue of the feature covariance matrices ΣDπkk=1K\ _D _k\_k=1^K., and its loss is uniformly bounded by some ϵCFA≥0 _ CFA≥ 0, i.e., L(vk∗)=minv∈ℝLk(v)≤ϵCFAL(v_k^*)= _v dL_k(v)≤ _ CFA. The quantity ϵCFA _ CFA uniformly measures the extent to which ∇logπk∇ _k can compatibly express AkA_k at each round. To ensure that ϵCFA _ CFA is small, the actor and critic must align with each other. Thus we refer to ϵCFA _ CFA as actor-critic incompatibility, which vanishes in the compatible case, i.e. when Ak=w⊤∇logπkA_k=w ∇ _k for some w∈ℝw d. For instance, the canonical softmax policy class is fully representative, so ϵCFA=0 _ CFA=0 for any critic class ℱF. In linear function approximation, ϵCFA=0 _ CFA=0 when both Πθ _θ and ℱF share the same feature representation (see Appendix D.1). Now we can present the regret guarantee for LSPU in the following theorem; the proof can be found in Appendix D. Theorem 4 (Main Theorem for LSPU). Let λmin _ min denote the smallest eigenvalue of ΣDπkk=1K\ _D _k\_k=1^K. Under Assumptions 1, 3, 4, and regularity conditions for linear regression (Assumption 6), Algorithm 2 with policy updates vk\v_k\ computed in Eq. (7) achieves the following regret bound with probability at least 1−δ1-δ: RegKK≲BLβDKL(πcp∥π1)K⏟optimization error+ϵCFA⏟intrinsic bias+GϵCFA⋅Comp(ℱ,Πθ,δ)Nλmin⏟statistical estimation error, Reg_KK B_L β D_ KL( _ cp\| _1)K_ optimization error+ C _ CFA_ intrinsic bias+ G C _ CFA· Comp(F, _θ,δ)N _ min_ statistical estimation error, where Comp(ℱ,Πθ,δ) Comp(F, _θ,δ) is some complexity measure of the function class ℱF and the policy class Πθ _θ.666We emphasize that a naïve union bound in analysis leading to log(|ℱ||Πθ|/δ) (|F|| _θ|/δ) is inappropriate due to continuity of Πθ _θ; instead, Comp(ℱ,Πθ,δ) Comp(F, _θ,δ) as an abstract complexity measure can be instantiated via metric entropy (i.e., log-covering numbers). See Appendix D.4 and Eq. (16) for the formal definition. Theorem 4 shows that the regret bound of LSPU admits a 3-fold decomposition: an optimization term due to the update in Eq. (5), a bias (approximation error) term determined by the actor-critic incompatibility , and a statistical estimation term that decays at a rate of (/N)O( C/N). In particular, consider the well-specified setting where ϵCFA=0 _ CFA=0. Since this least-square regression problem is noiseless, the last statistical error term also vanishes. Consequently, as long as the sample size N satisfies N≥N≥ d (the dimension of parameter θ), it suffices to run K=(1/ε2)K=O(1/ ^2) rounds to guarantee RegK/K≤ε Reg_K/K≤ . In contrast, the hardness result of contextual mirror descent (Proposition 2) indicates that constant per-step regret arises even in the well-specified case (see Proposition 8). 5.2 Distributionally Robust Policy Update In Section 5.1, we use a squared surrogate to control the error of CFA, which enjoys favorable statistical and computational properties of linear regression. However, it is inherently a relaxation: the squared loss does not directly correspond to the linear form of errk err_k, and may be loose when the approximation error is highly heterogeneous across the state-action space. This naturally raises a question: can we control the linear error of CFA directly without squaring it? Related ideas have been explored in marginalized importance sampling (Liu et al., 2018; Uehara et al., 2020; Xie and Jiang, 2020). The main obstacle is that errk err_k is defined under the unknown distribution dπcpd _ cp, hence distribution shift remains. To address this issue, we adopt a distributionally robust optimization (DRO) perspective. The key idea is to express the error under dπcpd _ cp as an importance-weighted expectation under dDd^D: |dπcp[Ak−vk⊤∇logπk]|=|dD[w∗(s,a)(Ak−vk⊤∇logπk)]|, |E_d _ cp[A_k-v_k ∇ _k] |= |E_d^D [w^*(s,a)(A_k-v_k ∇ _k) ] |, (8) where w∗w^* is some correction weight that allows distribution transfer between dπcpd _ cp and dDd^D, such as w∗(s,a)=dπcp(s,a)/dD(s,a)w^*(s,a)=d _ cp(s,a)/d^D(s,a), though alternative forms exist which we will discuss later. Since w∗w^* is unknown, we introduce a robust loss that considers the worst-case weight over a weight class W: ℓk(v):=maxw∈|dD[w(Ak−v⊤∇logπk)]|. _k(v):= _w |E_d^D [w(A_k-v ∇ _k) ] |. The weight class W may be specified explicitly or induced implicitly as a nonparametric space. As long as it satisfies realizability (i.e., w∗∈w^* ), we have errk≤ℓk(vk) err_k≤ _k(v_k), and minimizing ℓk _k suffices. We refer to the update that leverages DRO as the distributionally robust policy update (DRPU). The ∞W_∞ class and computation. A natural instantiation of the correction weight w∗w^* is the density ratio dπcp/dDd _ cp/d^D which directly allows the distribution transfer in Eq. (8), i.e., w∗(s,a)=dπcp(s,a)/dD(s,a)w^*(s,a)=d _ cp(s,a)/d^D(s,a). Correspondingly, we can consider the following bounded-density-ratio class: ∞=w:×→[0,]:(s,a)∼dD[w(s,a)]=1.W_∞= \w:S×A→[0, C]:E_(s,a) d^D[w(s,a)]=1 \. (9) which includes all valid density ratios due to the normalization constraint. This choice aligns with the density coverage condition (Assumption 1). In particular, realizability holds since ‖w∗‖∞=‖dπcp/dD‖∞≤\|w^*\|_∞=\|d _ cp/d^D\|_∞≤ C. From now on we instantiate =∞W=W_∞ and keep the notation ℓk _k for simplicity. One key advantage of using ∞W_∞ lies in its computational properties. Under ∞W_∞ class, the robust loss ℓk _k admits an equivalent dual representation (Proposition 17), which is a version of Conditional Value-at-Risk (CVaR) objective: ℓk(v)=max∈±1minτ∈ℝτ+dD[((Ak−v⊤∇logπk)−τ)+] _k(v)= _ s∈\± 1\ _τ \τ+ C\ E_d^D [( s(A_k-v ∇ _k)-τ)_+ ] \\, where ∈±1 s∈\± 1\ denotes the sign and (Z)+=max0,Z(Z)_+= \0,Z\. The algorithm solves for the empirical counterpart of ℓk _k using samples (s(i),a(i))i=1N∼i.i.d.dD\(s^(i),a^(i))\_i=1^N i.i.d. d^D: ℓ^k(v)=max∈±1minτ∈ℝτ+N∑i=1N((Ak(i)−v⊤∇logπk(a(i)|s(i)))−τ)+. _k(v)= _ s∈\± 1\ _τ \τ+ CN _i=1^N ( s(A_k^(i)-v ∇ _k(a^(i)|s^(i)))-τ )_+ \. (10) Note that ℓ^k _k is convex in v. This optimization problem can be reformulated as a d-dimensional linear program (or as a SOCP), thus admitting efficient numerical algorithms; see Appendix E.3. Guarantee. As in Section 5.1, we allow for actor-critic incompatibility in the actor update and characterize it through the following assumption. The norm bound is set as BL=VmaxB_L=V_ max in this section. Assumption 5 (DRPU Approximation Error). Define v~k∗ v_k^* as the best linear approximator of the robust loss ℓk _k (within the norm constraint ‖v~k∗‖≤Vmax\| v_k^*\|≤ V_ max). Assume its loss is uniformly bounded by some ϵ~CFA≥0 ε_ CFA≥ 0 for all k, i.e., ℓk(v~k∗)=minv:‖v‖≤Vmaxℓk(v)≤ϵ~CFA _k( v_k^*)= _v:\|v\|≤ V_ max _k(v)≤ ε_ CFA. It is worth noting that ϵ~CFA ε_ CFA is closely related to the bias term ϵCFA _ CFA associated with LSPU in Assumption 4. In particular, by the Cauchy-Schwarz inequality, one can show that ϵ~CFA≤⋅ϵCFA ε_ CFA≤ C· _ CFA, a relationship that we will explore further in Section 5.3. As a consequence, DRPU is more robust to actor-critic incompatibility; but running the algorithm also relies on a reasonably tight knowledge of the coverage constant C, as also discussed in Xie and Jiang (2020, Section 7). We now present the regret bound for this DRPU method under ∞W_∞ class given in Eq. (9). The guarantee exhibits a similar 3-fold structure of Theorem 4, showing that errk err_k scales as (/N)O( C/N), up to an additional bias term. Theorem 5 (Main Theorem for DRPU under ∞W_∞ Class). Under Assumptions 1, 3 and 5, vk\v_k\ minimizing ℓ^k\ _k\ in Eq. (10) achieves the following regret bound with probability at least 1−δ1-δ: RegKK≲VmaxβDKL(πcp∥π1)K+ϵ~CFA+Vmax(G+1)⋅Comp(ℱ,Πθ,δ)N. Reg_KK V_ max β D_ KL( _ cp\| _1)K+ ε_ CFA+V_ max(G+1) C· Comp(F, _θ,δ)N. The proof of Theorem 5 leverages the structure of CVaR optimization to eliminate the dependency on ∞W_∞, and employs the “tail-peeling” technique to reduce the variance of the active fraction of CVaR, improving the bound from C to C; see Appendix E.2 for details. Alternative weight classes. ∞W_∞ in Eq. (9) is one instantiation of the weight class. More generally, the DRO framework allows for alternative characterizations of W, as long as it satisfies the transfer in Eq. (8). Different choices of W correspond to different structural assumptions on the distribution shift between dπcpd _ cp and dDd^D. For instance, in the compatible case, one can leverage the improved coverage notion of feature coverage in Section 5.1 to define the following chi-square weight class: χ2=w:(s,a)∼dD[w(s,a)2]≤feat.W_χ^2= \w:E_(s,a) d^D[w(s,a)^2]≤ C_ feat \. It suffices to show that such a weight class contains solution to Eq. (8). Indeed, at round k consider w∗(s,a)=dπcp[∇logπk]⊤(ΣDπk)−1∇logπk(a|s)w^*(s,a)=E_d _ cp[∇ _k] ( _D _k)^-1∇ _k(a|s), which satisfies both Eq.(8) and w∗∈χ2w^* _χ^2; see Appendix E.4 for details. 5.3 Bias Comparison between LSPU and DRPU As shown in Theorems 4 and 5, the regret bounds are mainly driven by the intrinsic bias terms when optimization and statistical errors vanish (that is, when sample size N and optimization iterations K are sufficiently large). Such terms are defined differently for LSPU (Assumption 4) and DRPU (Assumption 5). As quantified in Section 5.2, DRPU has potential advantage in terms of robustness to actor-critic incompatibility than LSPU. In this section, we use a case study to illustrate this behavior when dD=dπcpd^D=d _ cp. In fact, perhaps surprisingly, DRPU can be viewed as behavior cloning in this setting, providing an interesting unification between offline RL and imitation learning. Figure 1: Comparison between LSPU and DRPU under no-shift setting (dD=dπcpd^D=d _ cp). Left: performance J(πk)J( _k) over iterations, where DRPU converges to the comparator policy πcp _ cp (not optimal), while LSPU plateaus at a worse policy. Right: the error of CFA, errk err_k, at iteration k=80k=80 on a log scale, showing that DRPU drives the error close to zero, whereas LSPU incurs a larger bias. No-shift case. To isolate the effect of actor-critic incompatibility, we consider the case where dD=dπcpd^D=d _ cp. This rules out the difficulty of distribution shift and naturally arises in hybrid settings of imitation learning and offline RL, where we have access to additional expert annotations (i.e., data from πcp _ cp). In this case, we can choose the weight class as realizable =W=\1\ since dπcp/dD≡1d _ cp/d^D≡ 1. The DRPU then reduces to the following mean-matching problem: minv:‖v‖≤Vmax|dπcp[Ak]−v⊤dπcp[∇logπk]|. _v:\|v\|≤ V_ max |E_d _ cp[A_k]-v E_d _ cp[∇ _k] |. (11) This formulation highlights a fundamental difference between LSPU and DRPU. While LSPU enforces pointwise control by minimizing a squared loss, DRPU only requires agreement in expectation under a certain distribution dπcpd _ cp. Therefore, Eq. (11) can be driven to exactly zero under mild conditions, even when the actor and the critic are incompatible. We empirically illustrate this phenomenon using a simple MDP (details in Appendix F.2), as shown in Figure 1. The mean-matching update also admits a natural interpretation. Consider the policy update θk+1=θk+ηvk _k+1= _k+η v_k, where vkv_k solves Eq. (11). This update can be viewed as performing a steepest descent step777This holds when dπcp[Ak]>0E_d _ cp[A_k]>0. Roughly speaking, this is the typical situation as it is equivalent to J(πk)≤J(πcp)J( _k)≤ J( _ cp) when the critic is accurate; see Appendix F.1. within [−Vmax,Vmax][-V_ max,V_ max] on the expected KL divergence under dπcpd _ cp, DKL(πcp∥πθ)D_ KL( _ cp\| _θ), which is exactly the objective of behavior cloning (BC). Iterating over Eq. (11) will lead to a policy πθ∗∈Πθ _θ^*∈ _θ closest to πcp _ cp in terms of expected KL divergence. More related discussion can be found in Appendix F.3. 6 Conclusion In this paper, we study the policy optimization in offline RL. With standalone policy class, previous mirror-descent-based methods such as PSPI fail due to a challenge we coin contextual coupling. To address this, we propose a unifying framework based on compatible function approximation, encompassing a regression-based policy update (LSPU) and a distributionally robust alternative (DRPU), both enjoying provable statistical and computational efficiency. One limitation is that our analysis primarily focuses on explicit stochastic policy classes, such as log-linear policy or Gaussian policy, where log-density-based requirements (e.g., Assumption 3) is well-defined. Extending the theory to deterministic or implicit generative policies (e.g., diffusion policy) remains an important open problem and may require fundamentally different analytical tools, as suggested by recent work on continuous-control learning (Ren et al., 2024; Simchowitz et al., 2025). We view bridging this gap a promising direction for future research. References A. Agarwal, S. M. Kakade, J. D. Lee, and G. Mahajan (2021) On the theory of policy gradient methods: optimality, approximation, and distribution shift. Journal of Machine Learning Research 22 (98), p. 1–76. Cited by: Appendix A, §4.2, §4, §5.1. A. Antos, C. Szepesvári, and R. Munos (2008) Learning near-optimal policies with bellman-residual minimization based fitted policy iteration and a single sample path. Machine Learning 71 (1), p. 89–129. Cited by: Appendix A, Appendix A, §B.1, §B.1, footnote 4. P. L. Bartlett and S. Mendelson (2002) Rademacher and gaussian complexities: risk bounds and structural results. Journal of machine learning research 3 (Nov), p. 463–482. Cited by: §E.2. A. Bennett, N. Kallus, and M. Oprescu (2023) Low-rank mdps with continuous action spaces. arXiv preprint arXiv:2311.03564. Cited by: Appendix A. O. Bousquet (2002) A bennett concentration inequality and its application to suprema of empirical processes. Comptes Rendus Mathematique 334 (6), p. 495–500. Cited by: Lemma 31. J. Chen and N. Jiang (2019) Information-theoretic considerations in batch reinforcement learning. In International conference on machine learning, p. 1042–1051. Cited by: Appendix A, §2. C. Cheng, T. Xie, N. Jiang, and A. Agarwal (2022) Adversarially trained actor critic for offline reinforcement learning. In International Conference on Machine Learning, p. 3852–3878. Cited by: Appendix A, Appendix A, §1, §3. D. Ernst, P. Geurts, and L. Wehenkel (2005) Tree-based batch mode reinforcement learning. Journal of Machine Learning Research 6. Cited by: Appendix A. E. Even-Dar, Sham. M. Kakade, and Y. Mansour (2009) Online markov decision processes. Mathematics of Operations Research 34 (3), p. 726–736. Cited by: §4.2. A. Farahmand, C. Szepesvári, and R. Munos (2010) Error propagation for approximate policy and value iteration. Advances in neural information processing systems 23. Cited by: Appendix A. A. Faust, P. Ruymgaart, M. Salman, R. Fierro, and L. Tapia (2014) Continuous action reinforcement learning for control-affine systems with unknown dynamics. IEEE/CAA Journal of automatica Sinica 1 (3), p. 323–336. Cited by: Appendix A. M. Fazel, R. Ge, S. Kakade, and M. Mesbahi (2018) Global convergence of policy gradient methods for the linear quadratic regulator. In International conference on machine learning, p. 1467–1476. Cited by: Appendix A. S. Fujimoto, D. Meger, and D. Precup (2019) Off-policy deep reinforcement learning without exploration. In International conference on machine learning, p. 2052–2062. Cited by: Appendix A. T. Haarnoja, A. Zhou, P. Abbeel, and S. Levine (2018) Soft actor-critic: off-policy maximum entropy deep reinforcement learning with a stochastic actor. In International conference on machine learning, p. 1861–1870. Cited by: Appendix A, §B.3. E. Hazan et al. (2016) Introduction to online convex optimization. Foundations and Trends® in Optimization 2 (3-4), p. 157–325. Cited by: §B.2, §3. D. Hsu, S. M. Kakade, and T. Zhang (2012) Random design analysis of ridge regression. In Conference on learning theory, p. 9–1. Cited by: §D.3, Appendix D, Lemma 27, Lemma 28. N. Jiang, A. Krishnamurthy, A. Agarwal, J. Langford, and R. E. Schapire (2017) Contextual decision processes with low bellman rank are pac-learnable. In International Conference on Machine Learning, p. 1704–1713. Cited by: §D.1. N. Jiang and T. Xie (2025) Offline reinforcement learning in large state spaces: algorithms and guarantees. arXiv preprint arXiv:2510.04088. Cited by: Appendix A, §E.4, §1, §2, §5.1, Lemma 25. C. Jin, Z. Yang, Z. Wang, and M. I. Jordan (2020) Provably efficient reinforcement learning with linear function approximation. In Conference on learning theory, p. 2137–2143. Cited by: Appendix A, §D.1, §3. S. M. Kakade (2001) A natural policy gradient. Advances in neural information processing systems 14. Cited by: Appendix A, 2nd item, §4.2, §5.1. N. Kallus and M. Uehara (2020) Statistically efficient off-policy policy gradients. In International Conference on Machine Learning, p. 5089–5100. Cited by: Appendix A. W. Krichene, M. Balandat, C. Tomlin, and A. Bayen (2015) The hedge algorithm on a continuum. In International Conference on Machine Learning, p. 824–832. Cited by: §B.3. D. Kuhn, S. Shafiee, and W. Wiesemann (2025) Distributionally robust optimization. Acta Numerica 34, p. 579–804. Cited by: §E.1, §E.4. A. Kumar, A. Zhou, G. Tucker, and S. Levine (2020) Conservative q-learning for offline reinforcement learning. Advances in neural information processing systems 33, p. 1179–1191. Cited by: Appendix A. S. Levine, A. Kumar, G. Tucker, and J. Fu (2020) Offline reinforcement learning: tutorial, review, and perspectives on open problems. arXiv preprint arXiv:2005.01643. Cited by: Appendix A, §1. Q. Liu, L. Li, Z. Tang, and D. Zhou (2018) Breaking the curse of horizon: infinite-horizon off-policy estimation. Advances in neural information processing systems 31. Cited by: §E.4, §5.2. Y. Liu, A. Swaminathan, A. Agarwal, and E. Brunskill (2019) Off-policy policy gradient with state distribution correction. arXiv preprint arXiv:1904.08473. Cited by: Appendix A. C. Mao (2023) Offline reinforcement learning with additional covering distributions. arXiv preprint arXiv:2305.12679. Cited by: §2. J. Mei, C. Xiao, C. Szepesvari, and D. Schuurmans (2020) On the global convergence rates of softmax policy gradient methods. In International conference on machine learning, p. 6820–6829. Cited by: Appendix A. V. Mnih, K. Kavukcuoglu, D. Silver, A. Graves, I. Antonoglou, D. Wierstra, and M. Riedmiller (2013) Playing atari with deep reinforcement learning. arXiv preprint arXiv:1312.5602. Cited by: Appendix A. M. Mohri, A. Rostamizadeh, and A. Talwalkar (2018) Foundations of machine learning. MIT press. Cited by: §D.4. R. Munos and C. Szepesvári (2008) Finite-time bounds for fitted value iteration.. Journal of Machine Learning Research 9 (5). Cited by: Appendix A, footnote 4. R. Munos (2007) Performance bounds in l_p-norm for approximate value iteration. SIAM journal on control and optimization 46 (2), p. 541–561. Cited by: Appendix A, footnote 4. O. Nachum, Y. Chow, B. Dai, and L. Li (2019) Dualdice: behavior-agnostic estimation of discounted stationary distribution corrections. Advances in Neural Information Processing Systems 32. Cited by: §E.4. F. Orabona (2019) A modern introduction to online learning. arXiv preprint arXiv:1912.13213. Cited by: §B.2. J. Peters and S. Schaal (2008) Natural actor-critic. Neurocomputing 71 (7-9), p. 1180–1190. Cited by: §5.1. R. F. Prudencio, M. R. Maximo, and E. L. Colombini (2023) A survey on offline reinforcement learning: taxonomy, review, and open problems. IEEE Transactions on Neural Networks and Learning Systems 35 (8), p. 10237–10257. Cited by: §1. H. Rahimian and S. Mehrotra (2019) Distributionally robust optimization: a review. arXiv preprint arXiv:1908.05659. Cited by: §E.4. P. Rashidinejad, B. Zhu, C. Ma, J. Jiao, and S. Russell (2021) Bridging offline reinforcement learning and imitation learning: a tale of pessimism. Advances in Neural Information Processing Systems 34, p. 11702–11716. Cited by: Appendix A. A. Z. Ren, J. Lidard, L. L. Ankile, A. Simeonov, P. Agrawal, A. Majumdar, B. Burchfiel, H. Dai, and M. Simchowitz (2024) Diffusion policy policy optimization. arXiv preprint arXiv:2409.00588. Cited by: §6. M. Simchowitz, D. Pfrommer, and A. Jadbabaie (2025) The pitfalls of imitation learning when actions are continuous. arXiv preprint arXiv:2503.09722. Cited by: §6. R. S. Sutton, D. McAllester, S. Singh, and Y. Mansour (1999) Policy gradient methods for reinforcement learning with function approximation. Advances in neural information processing systems 12. Cited by: Appendix A, 2nd item, §4.2. M. Uehara, J. Huang, and N. Jiang (2020) Minimax weight and q-function learning for off-policy evaluation. In International Conference on Machine Learning, p. 9659–9668. Cited by: §B.1, §5.2. H. Van Hasselt and M. A. Wiering (2007) Reinforcement learning in continuous action spaces. In 2007 IEEE International Symposium on Approximate Dynamic Programming and Reinforcement Learning, p. 272–279. Cited by: Appendix A. R. J. Williams (1992) Simple statistical gradient-following algorithms for connectionist reinforcement learning. Machine learning 8 (3), p. 229–256. Cited by: Appendix A. T. Xie, C. Cheng, N. Jiang, P. Mineiro, and A. Agarwal (2021) Bellman-consistent pessimism for offline reinforcement learning. Advances in neural information processing systems 34, p. 6683–6694. Cited by: Appendix A, Appendix A, §B.1, §B.1, §1, §1, §1, §3, §3, §3, §3, Algorithm 1. T. Xie and N. Jiang (2020) Q* approximation schemes for batch reinforcement learning: a theoretical comparison. In Conference on Uncertainty in Artificial Intelligence, p. 550–559. Cited by: Appendix A, §5.2, §5.2. L. Yang and M. Wang (2019) Sample-optimal parametric q-learning using linearly additive features. In International conference on machine learning, p. 6995–7004. Cited by: §D.1. Q. Yang, S. Wang, Q. Zhang, G. Huang, and S. Song (2023) Hundreds guide millions: adaptive offline reinforcement learning with expert guidance. IEEE Transactions on Neural Networks and Learning Systems 35 (11), p. 16288–16300. Cited by: §2. R. Yuan, S. S. Du, R. M. Gower, A. Lazaric, and L. Xiao (2022) Linear convergence of natural policy gradient methods with log-linear policies. arXiv preprint arXiv:2210.01400. Cited by: Appendix A. Y. Zhou, A. Sekhari, Y. Song, and W. Sun (2023) Offline data enhanced on-policy policy gradient with provable guarantees. arXiv preprint arXiv:2311.08384. Cited by: Appendix A. Appendix A Related Work Offline RL studies learning policies from a fixed dataset without further environment interaction [Levine et al., 2020]. With function approximation, a dominant line of work builds on value-function estimation and approximate dynamic programming [Ernst et al., 2005, Munos, 2007, Antos et al., 2008, Munos and Szepesvári, 2008, Farahmand et al., 2010, Chen and Jiang, 2019, Xie and Jiang, 2020]. This value-centric paradigm underlies many practical algorithms [Mnih et al., 2013] as well as much of the accompanying theory, and provides the standard backdrop for understanding statistical and computational aspects in offline RL. See [Jiang and Xie, 2025] for a comprehensive survey of offline RL theory. A central difficulty in offline RL is data coverage. Existing guarantees typically impose some form of coverage assumption, which can be broadly categorized into (i) all-policy coverage, requiring that the dataset sufficiently covers dπd^π for all policies in a class, and (i) single-policy coverage, which only requires coverage of a particular comparator distribution such as dπcpd _ cp. Algorithmically, two common principles are used to cope with single-policy coverage: behavior regularization, which constrains learned policies to remain close to the behavior distribution [Fujimoto et al., 2019]; and pessimism (or uncertainty-aware optimization), which seeks a policy with the best guaranteed performance over models or value functions consistent with the data [Kumar et al., 2020, Jin et al., 2020, Rashidinejad et al., 2021, Xie et al., 2021, Cheng et al., 2022]. Most prior theoretical treatments of offline RL emphasize critic-side learning and treat the actor as an induced object, for example via greedy or soft-greedy policies with respect to learned value functions. In contrast, a smaller but growing literature studies offline RL from an explicit actor–critic or policy-search perspective. The work most closely related to ours is Xie et al. [2021], which induces a soft-greedy policy class with respect to pessimistic value estimates (see Section 3). This structure enables an elegant state-wise mirror-descent interpretation of the actor update, but does not extend to standalone policy classes with arbitrary parameterizations. Subsequent work [Cheng et al., 2022] further develops this actor–critic viewpoint under stronger oracle assumptions on the actor (see Definition 4 of Cheng et al. [2022]) and trains the actor using policy-gradient-style updates based on empirical demonstrations. As we show in this paper, such oracle assumptions are strong, and this formulation can obscure the precise source of actor-side error as well as the role of distribution mismatch. From a policy-based reinforcement learning perspective, our work also connects to the broader literature on policy gradient (PG) [Williams, 1992] and natural policy gradient (NPG) [Kakade, 2001] methods. On-policy analyses of (natural) policy gradient establish convergence and sample complexity guarantees under smooth parametric policy classes [Fazel et al., 2018, Agarwal et al., 2021, Mei et al., 2020, Yuan et al., 2022], and highlight the importance of distribution shift. In particular, Agarwal et al. [2021] elucidates the connection between NPG, compatible function approximation [Sutton et al., 1999], and least-squares regression, yielding a regret decomposition into estimation and approximation errors. We build on this policy-optimization viewpoint, but focus on the offline setting, where the distribution mismatch between the data distribution and the visitation distribution of the updated policies fundamentally alters what can be guaranteed. There is also a line of work on off-policy policy gradient methods [Liu et al., 2019, Kallus and Uehara, 2020], including extensions to offline data [Zhou et al., 2023]. These approaches are largely rooted in analyses of on-policy policy gradient with importance weighting, whereas our work studies policy optimization directly in the offline setting and explicitly addresses distribution shift through data coverage. Finally, continuous action spaces further amplify these challenges. Early work such as Antos et al. [2008] extends fitted Q-iteration to continuous actions by explicitly searching over a policy class rather than computing argmaxaQ(s,a) _aQ(s,a). Much of the offline RL theory for continuous actions relies on strong structural assumptions, including linear-quadratic regulators, linear MDPs, Gaussian policies, or other restricted dynamics and policy families [Van Hasselt and Wiering, 2007, Faust et al., 2014, Haarnoja et al., 2018, Bennett et al., 2023]. In contrast, modern practice often employs flexible standalone policy classes, such as deep neural networks, optimized directly via policy-based methods. This is particularly pronounced in large-scale post-training of language models, where policies are represented by deep networks and updated using PG-type algorithms such as PPO or GRPO. These developments further motivate a principled understanding of policy optimization under distribution shift and function approximation. Our results contribute to this direction by characterizing a fundamental obstruction to naive contextual policy optimization in offline RL and by proposing actor updates with provable guarantees under standalone policy classes. Appendix B Omitted Details for Section 3 B.1 Discussion on the Critic Oracle in Assumption 2 In Assumption 2, we propose a critic oracle O such that given any policy π, it finds a function f∈ℱf such that f satisfies the following two conditions: 1. (Pessimism) The function f is a pessimistic estimation of QπQ^π (up to some tolerance ϵr≥0 _r≥ 0), i.e., Jf(π)−J(π)≤ϵr/(1−γ)J_f(π)-J(π)≤ _r/(1-γ) with high probability, where Jf(π)=s∼d0[f(s,π)]J_f(π)=E_s d_0[f(s,π)]. 2. (Bounded Bellman error) The Bellman error under dπcpd _ cp (comparator policy’s occupancy) is bounded by some ϵb>0 _b>0. That is, dπcp[πf−f]≤ϵbE_d _ cp[T^πf-f]≤ _b with high probability. The Bellman error telescoping (Lemma 24) translates the pessimism condition to dπ[f−πf]=(1−γ)(Jf(π)−J(π))≤ϵrE_d^π[f-T^πf]=(1-γ)(J_f(π)-J(π))≤ _r. This means the oracle can control the Bellman error (f−πf)(f-T^πf) under both dπcpd _ cp and dπd^π, which corresponds to latter two terms in the generalized performance-difference lemma (Lemma 25). Now we discuss how to realize both of these two conditions if the function class ℱF satisfies certain structural conditions. Two classical methods include BRM-type (e.g., Xie et al. [2021]) and MQL-type (e.g., Uehara et al. [2020]). BRM-type critic oracle. The BRM-type oracle leverages classical Bellman residual minimization (BRM) algorithm [Antos et al., 2008] with version-space pessimism. For a policy π and a value function proxy f, define the squared Bellman error (under dcriticDd^D_critic, which is the state-action distribution of the critic-side data) as ℰ(f;π)=dcriticD[(f−πf)2].E(f;π)=E_d^D_critic [(f-T^πf)^2 ]. By Bellman residual minimization [Antos et al., 2008], this can be written as ℰ(f;π)=ℒ(f;f,π)−ℒ(πf;f,π),E(f;π)=L(f;f,π)-L(T^πf;f,π), where ℒ(f′;f,π):=(s,a)∼dcriticD,r=R(s,a),s′∼P(⋅∣s,a)[(f′(s,a)−r−γf(s′,π))2].L(f ;f,π):=E_(s,a) d^D_critic,r=R(s,a),s P(· s,a) [(f (s,a)-r-γ f(s ,π))^2 ]. Let ℒ L denote the empirical version of ℒL estimated from the offline dataset D. Under Bellman completeness, i.e., πf∈ℱT^πf for all f∈ℱf , we have that ℒ(πf;f,π)=ming∈ℱℒ(g;f,π)L(T^πf;f,π)= _g L(g;f,π). Hence, we can provide an unbiased estimate of the squared Bellman error as ℰ^(f;π)=maxg∈ℱℒ^(f;f,π)−ℒ^(g;f,π). E(f;π)= _g L(f;f,π)- L(g;f,π). Therefore, the oracle can be given by the following pessimistic estimation of the Bellman error: fminπ=argminf∈ℱϵ0πJf(π).f_ min^π= f _ _0^π J_f(π). (12) The pessimism is taken inside the feasible set ℱϵ0πF_ _0^π, referred as the version space, which contains all function f∈ℱf with small (empirical) squared Bellman error under dDd^D: ℱϵ0π=f∈ℱ:ℰ^(f;π)≤ϵ0:=Vmax2Nlog|ℱ||Πθ|δ.F_ _0^π= \f : E(f;π)≤ _0:= V_ max^2N |F|| _θ|δ \. Since QπQ^π is the unique fixed point of πT^π, by standard concentration argument, we have Qπ∈ℱϵ0πQ^π _ _0^π with probability at least 1−δ1-δ. Therefore, this oracle (Eq. (12)) satisfies the first condition of pessimism (ϵr=0 _r=0) with high probability: Jf(π)=Jfminπ(π)=minf∈ℱϵ0πJf(π)≤JQπ(π)=J(π).J_f(π)=J_f_ min^π(π)= _f _ _0^πJ_f(π)≤ J_Q^π(π)=J(π). To see that the oracle (Eq. (12)) also satisfies the second argument of bounded Bellman error under dπcpd _ cp, we need to assume the same coverage condition (Assumption 1) also holds for critic-side data, i.e., ‖dπcp/dcriticD‖≤\|d _ cp/d^D_critic\|≤ C for some finite C. By applying coverage condition (Assumption 1), we can transfer the distribution from dπcpd _ cp to dcriticDd^D_critic (in addition to some concentration argument to relate ℰ(f;π)E(f;π) with ℰ^(f;π) E(f;π)): for all f∈ℱϵ0πf _ _0^π, dπcp[πf−f]≤dπcp[(f−πf)2]≤⋅dcriticD[(f−πf)2]=⋅ℰ(f;π)≲ϵ0:=ϵb.E_d _ cp[T^πf-f]≤ E_d _ cp[(f-T^πf)^2]≤ C·E_d^D_critic[(f-T^πf)^2]= C·E(f;π) C _0:= _b. Therefore, the BRM-type oracle in Eq. (12) is a valid oracle that satisfies both conditions in Assumption 2. For computational consideration, we write this as a constrained optimization problem: minf∈ℱJf(π)+λℰ^(f;π), _f J_f(π)+λ E(f;π), which results in a minimax optimization problem due to the maxg _g in the estimation of ℰ^(f;π) E(f;π). When ℱF is a linear function class with respect to some feature ϕs,a\ _s,a\, this optimization problem reduces to a quadratic program which can be efficiently solved, as discussed in [Xie et al., 2021]. MQL-type critic oracle. Another implementation of the critic oracle is based on minimax Q-function learning (MQL), a marginalized importance sampling method. It only requires the realizability of function class ℱF (i.e., Qπ∈ℱQ^π for all π∈Πθπ∈ _θ) instead of Bellman completeness. The oracle is still given by Eq. (12) but with a different version space ℱϵ0πF_ _0^π defined as ℱϵ0π=f∈ℱ:maxw∈ℓ^(f;w,π)≤ϵ0′:=Vmax1Nlog|ℱ||Πθ|δ,F_ _0^π= \f : _w (f;w,π)≤ _0 :=V_ max 1N |F|| _θ|δ \, where W is a weight class similar to what is defined in Section 5.2. And ℓ^(f;w,π) (f;w,π) is the empirical version of ℓ(f;w,π) (f;w,π), the average Bellman error of f under weighted distribution w⋅dcriticDw· d^D_critic: ℓ(f;w,π)=|dcriticD[w⋅(f−πf)]|. (f;w,π)= |E_d^D_critic[w·(f-T^πf)] |. Since QπQ^π is the unique fixed point of πT^π, ℓ(Qπ;w,π)=0 (Q^π;w,π)=0 for all w∈w . By concentration argument, we have Qπ∈ℱϵ0πQ^π _ _0^π with probability at least 1−δ1-δ. This indicates the pessimism is satisfied when we are taking minf∈ℱϵ0π _f _ _0^π in Eq. (12), validating the first condition (ϵr=0 _r=0). Similarly, the second condition of bounded Bellman error under dπcpd _ cp can be analyzed since ‖dπcp/dcriticD‖∞≤C\|d _ cp/d^D_critic\|_∞≤ C by coverage condition (Assumption 1): for all f∈ℱϵ0πf _ _0^π, dπcp[πf−f]≤|dcriticD[w∗(f−πf)]|≤maxw∈|dcriticD[w(f−πf)]|=maxw∈ℓ(f;w)≲ϵ0′:=ϵb,E_d _ cp[T^πf-f]≤ |E_d^D_critic[w^*(f-T^πf)] |≤ _w |E_d^D_critic[w(f-T^πf)] |= _w (f;w) _0 := _b, where w∗(s,a)=dπcp(s,a)/dcriticD(s,a)w^*(s,a)=d _ cp(s,a)/d^D_critic(s,a) and w∗∈w^* (realizability of the weight class). Therefore, this MQL-type oracle in Eq. (12) also satisfies both conditions in Assumption 2. For computational consideration, it requires an additional weight class W. And this can also be treated as a minimax optimization problem: minf∈ℱmaxw∈Jf(π)+λℓ^(f;w,π). _f _w J_f(π)+λ (f;w,π). In special cases like linear function approximation, it can be transformed to some mean-matching problem which can be efficiently solved. B.2 Settings in Continuous Action Space For readability, the main text states Section 3 under a finite action space and writes action-wise expectations using sums. In this appendix, we record the corresponding continuous-action formulation of the state-wise mirror-descent argument underlying Theorem 1. This appendix only extends the PSPI analysis in Section 3, the rest of the paper remains stated in the finite-action setting. Setting. We keep the state space unchanged (since the contextual analysis does not depend on the size of state space) and only generalize the action space. Let A be a measurable action space equipped with a σ-finite reference measure ν. A policy π is a Markov kernel from states to actions such that, for every state s, the conditional action law π(⋅∣s)π(· s) is absolutely continuous with respect to ν. We write its Radon-Nikodym derivative as π(a∣s)π(a s), so that ∫π(a∣s)ν(da)=1 _Aπ(a s)ν(da)=1, ∀s∈∀ s . Accordingly, whenever a function g:×→ℝg:S×A is measurable, we write g(s,π):=∫g(s,a)π(a∣s)ν(da)g(s,π):= _Ag(s,a)π(a s)ν(da). With this notation, the definition of Bellman operator (πf)(s,a)=R(s,a)+γs′∼P(⋅∣s,a)[f(s′,π)](T^πf)(s,a)=R(s,a)+ _s P(· s,a)[f(s ,π)] immediately extends to continuous action spaces as-is. To avoid ambiguity, it is helpful to distinguish the discounted state occupancy from the discounted state-action occupancy. Denote dπd_S^π the discounted state occupancy measure of π: dπ(s)=(1−γ)∑t=0∞γtPrπ[st=s]d_S^π(s)=(1-γ) _t=0^∞γ^t _π[s_t=s] (recall that we still treat states as finite and discrete), and denote by dπd^π the discounted state-action occupancy measure on ×S×A: dπ(B)=(1−γ)∑t=0∞γtPrπ[(st,at)∈B]d^π(B)=(1-γ) _t=0^∞γ^t _π[(s_t,a_t)∈ B] for measurable sets B⊆×B ×A. In particular, the regret quantity in Eq. (2) should be interpreted as an expectation over the state marginal dπcpd_S _ cp, namely RegKK=1K∑k=1Ks∼dπcp[fk(s,πcp)−fk(s,πk)]. Reg_KK= 1K _k=1^KE_s d_S _ cp[f_k(s, _ cp)-f_k(s, _k)]. This is the same quantity as in the main text, just written with the state occupancy explicitly separated from the state-action occupancy. For any two action distributions μ and λ on A such that μ absolutely continuous with respect to λ, we define their KL-divergence as DKL(μ∥λ)=∫log(dμ/dλ)dμD_ KL(μ\|λ)= _A (dμ/dλ)dμ. Furthermore, if both μ and λ admit densities p and q, respectively, with respect to ν, the KL reduces to DKL(p∥q)=∫p(a)log(p(a)/q(a))ν(da)D_ KL(p\|q)= _Ap(a) (p(a)/q(a))ν(da). Similar to the main text, we define the expected KL divergence under dπcpd_S _ cp between policy πcp _ cp and π1 _1 as: DKL(πcp∥π1)=s∼dπcp[DKL(πcp(⋅∣s)∥π1(⋅∣s))].D_ KL( _ cp\| _1)=E_s d_S _ cp[D_ KL( _ cp(· s)\| _1(· s))]. Algorithm and guarantee. Under this setup, the PSPI update has the density form πk+1(a∣s)=πk(a∣s)exp(ηfk(s,a))∫πk(a′∣s)exp(ηfk(s,a′))ν(da′). _k+1(a s)= _k(a s) (η f_k(s,a)) _A _k(a s) (η f_k(s,a ))ν(da ). (13) This is exactly the continuous analogue of the state-wise multiplicative weights update used in PSPI. The reason this extension is clean is that Section 3 is purely state-wise: once one fixes a state s, the proof is just an online learning argument over the action distribution at that state. We now state the continuous-action extension of Theorem 1, which exhibits the same structure as that in finite action space. In fact, it strictly subsumes Theorem 1, since the latter can be instantiated by simply choosing the base measure ν as the counting measure over a finite A. Therefore, below we only prove Theorem 6, as Theorem 1 is a direct corollary of it.888To see that, by choosing the base measure ν as the counting measure in A. Then, all continuous notions defined in this section reduce back to the finite and discrete notions in the main text. Theorem 6 (Theorem 1 with continuous action space). Assume that for each iteration k, the critic fkf_k is bounded in [0,Vmax][0,V_ max], and that DKL(πcp∥π1)<∞D_ KL( _ cp\| _1)<∞. Then the PSPI iterates satisfy RegKK≤DKL(πcp∥π1)ηK+ηVmax28. Reg_KK≤ D_ KL( _ cp\| _1)η K+ η V_ max^28. By choosing the step size as η=8DKL(πcp∥π1)/(KVmax2)η= 8D_ KL( _ cp\| _1)/(KV_ max^2), we have the exactly same regret bound as in Theorem 1 (except here the KL divergence is defined in a continuous manner), i.e., RegK/K≤VmaxDKL(πcp∥π1)/(2K) Reg_K/K≤ V_ max D_ KL( _ cp\| _1)/(2K). We now give a potential-based proof that utilizes classical online learning tools in the analysis of expert problem [Hazan and others, 2016, Orabona, 2019]. Proof of PSPI regret bound. Let ξ:L∞()→ℝξ:L^∞(A) be the negative potential function defined as ξ(f)=−1ηlog∫π1(a∣s)exp(ηf(a))ν(da).ξ(f)=- 1η _A _1(a s) (η f(a))ν(da). Let Fk(s,a)=∑j=1kfj(s,a)F_k(s,a)= _j=1^kf_j(s,a) denote the cumulative value function (at each fixed state s) up to round k. We can first bound the difference of the negative potential function as ξ(Fk+1(s,⋅))−ξ(Fk(s,⋅)) ξ(F_k+1(s,·))-ξ(F_k(s,·)) =−1ηlog∫π1(a∣s)exp(η∑j=1k+1fk(s,a))ν(da)∫π1(a∣s)exp(η∑j=1kfk(s,a))ν(da) =- 1η _A _1(a s) (η _j=1^k+1f_k(s,a))ν(da) _A _1(a s) (η _j=1^kf_k(s,a))ν(da) =−1ηlog∫πk+1(a∣s)exp(ηfk+1(s,a))ν(da) =- 1η _A _k+1(a s) (η f_k+1(s,a))ν(da) =−1ηloga∼πk+1(⋅∣s)[exp(ηfk+1(s,a))] =- 1η _a _k+1(· s)[ (η f_k+1(s,a))] ≥−a∼πk+1(⋅∣s)[fk+1(s,a)]−ηVmax28, ≥-E_a _k+1(· s)[f_k+1(s,a)]- η V_ max^28, where the last step we use the Hoeffding’s lemma with random variable fk+1(s,a)f_k+1(s,a) (the randomness comes from a∼πk+1(⋅∣s)a _k+1(· s)) and the range of fk+1(s,a)f_k+1(s,a) is [0,Vmax][0,V_ max]. Therefore, by telescoping, we have ∑k=1K(ξ(Fk(s,⋅))−ξ(Fk−1(s,⋅)))≥−∑k=1Ka∼πk(⋅∣s)[fk(s,a)]−ηVmax28K. _k=1^K (ξ(F_k(s,·))-ξ(F_k-1(s,·)) )≥- _k=1^KE_a _k(· s)[f_k(s,a)]- η V_ max^28K. Rearranging the terms we have −∑k=1Ka∼πk(⋅∣s)[fk(s,a)]≤ηVmax28K+ξ(FK(s,⋅)),- _k=1^KE_a _k(· s)[f_k(s,a)]≤ η V_ max^28K+ξ(F_K(s,·)), since ξ(F0(s,⋅))=ξ(0)=−1ηlog∫π1(a∣s)ν(da)=−1ηlog1=0ξ(F_0(s,·))=ξ(0)=- 1η _A _1(a s)ν(da)=- 1η 1=0 (by setting π0≡π1 _0≡ _1 as the initial policy). By adding FK(s,πcp)=∑k=1Kfk(s,πcp)F_K(s, _ cp)= _k=1^Kf_k(s, _ cp) at both sides, we can therefore obtain the regret bound ∑k=1K(fk(s,πcp)−fk(s,πk))≤FK(s,πcp)+ηVmax28K+ξ(FK(s,⋅)). _k=1^K (f_k(s, _ cp)-f_k(s, _k) )≤ F_K(s, _ cp)+ η V_ max^28K+ξ(F_K(s,·)). This means we only need to bound the negative log-partition function at round K, i.e., ξ(Fk(s,⋅))ξ(F_k(s,·)). This follows directly via the Gibbs variational principle (Lemma 23) with base measure ν: ξ(FK(s,⋅))=infu∈Δν()1ηDKL(u∥π1(⋅∣s))−a∼u[FK(s,a)].ξ(F_K(s,·))= _u∈ _ν(A) \ 1ηD_ KL(u\| _1(· s))-E_a u[F_K(s,a)] \. Taking u=πcp(⋅∣s)u= _ cp(· s) and using the fact that a∼πcp(⋅∣s)[FK(s,a)]=∑k=1Ka∼πcp(⋅∣s)[fk(s,a)]E_a _ cp(· s)[F_K(s,a)]= _k=1^KE_a _ cp(· s)[f_k(s,a)], we obtain ∑k=1K(fk(s,πcp)−fk(s,πk))≤ηVmax28K+1ηDKL(πcp(⋅∣s)∥π1(⋅∣s))]). _k=1^K (f_k(s, _ cp)-f_k(s, _k) )≤ η V_ max^28K+ 1ηD_ KL( _ cp(· s)\| _1(· s))]). By taking the outer expectation over the designated state distribution s∼dπcps d_S _ cp and tuning the step size as η=(8DKL(πcp∥π1))/(KVmax2)η= (8D_ KL( _ cp\| _1))/(KV_ max^2), we achieve the regret bound in Theorem 1. ∎ B.3 Examples of Bounded KL Term in Theorem 6 We deliberately keep the KL term in Theorem 1 and Theorem 6, rather than replacing it by a crude worse-case upper bound. In the discrete setting, one often upper-bounds this term by log|| |A|, but such a reduction is neither natural nor informative in general continuous action spaces. More importantly, the KL term itself admits elegant and interpretable instantiations for many standard continuous policy classes. Below we provide two examples to further illustrate this point. Gaussian policies. We first consider Gaussian policies, under which the KL term DKL(πcp∥π1)D_ KL( _ cp\| _1) admits explicit closed-form expressions and can be further bounded under mild regularity conditions. For the sake of simplicity, we focus on the isotropic Gaussian case, which is widely used in continuous-control reinforcement learning due to its simplicity, numerical stability, and compatibility with policy-gradient methods. In particular, isotropic Gaussian policies arise naturally when actions are modeled as affine functions of the state with additive exploration noise, and they are commonly adopted in practical algorithms (e.g., actor-critic methods with fixed variance) [Haarnoja et al., 2018]. Concretely, we assume that for each state s, πi(⋅∣s)=(μi(s),σ2I),i∈1,cp. _i(· s)=N( _i(s),σ^2I), i∈\1, cp\. Then, for any fixed s, the KL divergence reduces to a quadratic form in the mean difference: DKL( D_ KL ( πcp(⋅∣s)∥π1(⋅∣s))=a∼πcp(⋅∣s)[logπcp(a∣s)π1(a∣s)] _ cp(· s)\| _1(· s) )=E_a _ cp(· s) [ _ cp(a s) _1(a s) ] =a[−12(a−μcp(s))⊤(σ2I)−1(a−μcp(s))+12(a−μ1(s))⊤(σ2I)−1(a−μ1(s))] =E_a [- 12(a- _ cp(s)) (σ^2I)^-1(a- _ cp(s))+ 12(a- _1(s)) (σ^2I)^-1(a- _1(s)) ] =12σ2a[‖a−μ1(s)‖22−‖a−μcp(s)‖22] = 12σ^2E_a [\|a- _1(s)\|_2^2-\|a- _ cp(s)\|_2^2 ] =12σ2‖μcp(s)−μ1(s)‖22. = 12σ^2\| _ cp(s)- _1(s)\|_2^2. Therefore, DKL(πcp∥π1)=s∼dπcp[DKL(πcp(⋅∣s)∥π1(⋅∣s))]=12σ2s∼dπcp[∥μcp(s)−μ1(s)∥22].D_ KL( _ cp\| _1)=E_s d _ cp [D_ KL ( _ cp(· s) \| _1(· s) ) ]= 12σ^2E_s d _ cp [\| _ cp(s)- _1(s)\|_2^2 ]. Moreover, if the mean difference is uniformly bounded, i.e., ‖μcp(s)−μ1(s)‖2≤B\| _ cp(s)- _1(s)\|_2≤ B for all s, then DKL(πcp∥π1)≤B22σ2.D_ KL( _ cp\| _1)≤ B^22σ^2. One important advantage of Gaussian policies is that they admit efficient computation. That is, the update does not involve integrating the whole (continuous) action space, but only updates the sufficient statistics.999This is not restricted to Gaussian policies. In general, for policies that can be expressed as a distribution in exponential family, we can all update them via sufficient statistics. To be specific, we can consider the function class ℱF as a class of quadratic functions (which is typical in settings like linear quadratic regulators, LQR). Suppose the pessimistic Q-function at round k can be written as (with respect to a) fk(s,a)=−12(a−uk)⊤Qk(a−uk)+ck,f_k(s,a)=- 12(a-u_k) Q_k(a-u_k)+c_k, with state-dependent parameters uk,Qk,cku_k,Q_k,c_k with Qk≻0Q_k 0. In this case the multiplicative-weight update in Eq. (1) preserves the Gaussian family: the density πk(a∣s) _k(a s) remains a multivariate Gaussian (μk,Σk)N( _k, _k) after the update. Its sufficient statistics are the mean μk _k and covariance Σk _k, which can be equivalently represented by the precision matrix Λk=Σk−1 _k= _k^-1 and the natural parameter hk=Σk−1μkh_k= _k^-1 _k. The Hedge update then reduces to Λk+1=Λk+ηQk,hk+1=hk+ηQkuk, _k+1= _k+η Q_k, h_k+1=h_k+η Q_ku_k, so that the updated Gaussian is given by (μk+1,Σk+1)N( _k+1, _k+1) with μk+1=Λk+1−1hk+1 _k+1= _k+1^-1h_k+1 and Σk+1=Λk+1−1 _k+1= _k+1^-1. Convex action space. As claimed in Section 3, under additional structural assumptions on the action space (i.e., convexity) and the function class (i.e., Lipschitzness), we can obtain unified bound that does not depend on the KL divergence of any specific policies. The key idea is to leverage the convexity of the action space A, which allows us to construct a sequence of subsets k⊂A_k that progressively approximate the deterministic action chosen by πcp _ cp. Such a structure can also be extended to notions of uniform-fatness, where every action is guaranteed to have sufficient volume in its neighborhood (see Krichene et al. [2015] for more discussion). Theorem 7 (Unified KL Bound with Convex Action Space for Theorem 6). Suppose the action space A has finite measure with respect to the Lebesgue measure ν, i.e., ν()<∞ν(A)<∞. Furthermore, assume that the action space ⊂ℝA d_A is convex and compact with diameter B in the d_A-dimensional Euclidean space ℝR d_A, and that fk(s,⋅)f_k(s,·) is L-Lipschitz for all k, then the PSPI update with initial distribution π1(⋅∣s) _1(· s) being Lebesgue uniform for all s∈s , i.e., π1(a∣s)≡1/ν() _1(a s)≡ 1/ν(A) for all a∈a , and step size η=(8logK)/(KVmax2)η= (8 d_A K)/(KV_ max^2) achieves RegKK≤VmaxlogK2K+LBK. Reg_KK≤ V_ max d_A K2K+ LBK. Note that the additional logK d_A K factor in Theorem 7 (compared to regular log||/K |A|/K regret for Hedge algorithm) can be viewed as the log|| |A| term in the discrete case: the algorithm is effectively learning from a finite cover of A. For a d_A-dimensional set S, its log-covering number (see Definition 1 for formal definition) scales as log(S,ϵ)≍log(1/ϵ) (S,ε) d_A (1/ε); choosing ϵ=1/Kε=1/ K (which is the rate of the no-regret algorithm) yields the logK d_A K term. This is why the dimension d_A can be viewed as some effective dimension of A, as actions in A can be embedded as the d_A-dimensional vector in ℝR d_A. Proof of Theorem 7. Fix an arbitrary state s. Let FK(s,a)=∑k=1Kfk(s,a)F_K(s,a)= _k=1^Kf_k(s,a) denote the cumulative value function. Since each fk(s,⋅)f_k(s,·) is Lipschitz and A is compact, FK(s,⋅)F_K(s,·) attains its maximum on A. Let a∗∈argmaxa∈FK(s,a)a^*∈ _a F_K(s,a). Then, for any comparator policy πcp(⋅∣s) _ cp(· s), possibly deterministic, we have ∑k=1K(fk(s,πcp)−fk(s,πk)) _k=1^K (f_k(s, _ cp)-f_k(s, _k) ) =FK(s,πcp)−∑k=1Kfk(s,πk) =F_K(s, _ cp)- _k=1^Kf_k(s, _k) ≤FK(s,a∗)−∑k=1Kfk(s,πk), ≤ F_K(s,a^*)- _k=1^Kf_k(s, _k), where the inequality follows because the expectation of FK(s,⋅)F_K(s,·) under any probability measure is upper bounded by its maximum over A. The convexity of the action space makes it possible to construct a sequence of action subsets k⊂A_k such that k=a∗+dk(a−a∗):a∈,A_k= \a^*+d_k(a-a^*):a \, where dk>0d_k>0 is called the decay rate (will be specified later). This is because the diameter of kA_k will decay according to dkd_k, i.e., supa,a′∈k‖a−a′‖=dksupa,a′∈‖a−a′‖=dkB _a,a _k\|a-a \|=d_k _a,a \|a-a \|=d_kB, where B is the diameter of the action space A. Notice that all of the kA_k satisfy realizability, i.e., a∗∈ka^* _k for all k∈[K]k∈[K]. Specifically we consider kA_k, the action subset at the last round. By Lipschitzness of fk(s,⋅)f_k(s,·), for all a∈ka _k, we have |fk(s,a)−fk(s,a∗)|≤L‖a∗−a‖=dKLB.|f_k(s,a)-f_k(s,a^*)|≤ L\|a^*-a\|=d_KLB. This means fk(s,a)≥fk(s,a∗)−dKLBf_k(s,a)≥ f_k(s,a^*)-d_KLB. Summing over k∈[K]k∈[K], we have the cumulative bound FK(s,a)=∑k=1Kfk(s,a)≥∑k=1Kfk(s,a∗)−KdKLB=FK(s,a∗)−KdKLB.F_K(s,a)= _k=1^Kf_k(s,a)≥ _k=1^Kf_k(s,a^*)-Kd_KLB=F_K(s,a^*)-Kd_KLB. Recall that in the proof of Theorem 1, we need to control the last-iterate potential function ξ(FK(s,⋅))ξ(F_K(s,·)): ξ(FKs) ξ(F_K^s) =−1ηlog∫π1(a∣s)exp(ηFKs(a))ν(da) =- 1η _A _1(a s) (η F_K^s(a))ν(da) ≤−1ηlog∫kπ1(a∣s)exp(ηFK(s,a))ν(da) ≤- 1η _A_k _1(a s) (η F_K(s,a))ν(da) ≤−1ηlog∫kπ1(a∣s)exp(η(FK(s,a∗)−KdKLB))ν(da) ≤- 1η _A_k _1(a s) (η(F_K(s,a^*)-Kd_KLB))ν(da) =(KdKLB−FK(s,a∗))−1ηlog∫kπ1(a∣s)ν(da). = (Kd_KLB-F_K(s,a^*) )- 1η _A_k _1(a s)ν(da). Therefore, we can get the regret RegKs≤FK(s,a∗)+ηVmax28K+ξ(FK(s,⋅))≤ηVmax28K+KdKLB−1ηlog∫kπ1(a∣s)ν(da). Reg_K^s≤ F_K(s,a^*)+ η V_ max^28K+ξ(F_K(s,·))≤ η V_ max^28K+Kd_KLB- 1η _A_k _1(a s)ν(da). We only need to control the last term, which is actually the generalized volume of kA_k. For a set 0⊂A_0 , its generalized volume with respect to distribution π1(⋅∣s)∈Δν() _1(· s)∈ _ν(A) is defined as π1(⋅∣s)(0)=∫0π1(a∣s)ν(da)=1ν()∫kν(da)=ν(k)ν()V_ _1(· s)(A_0)= _A_0 _1(a s)ν(da)= 1ν(A) _A_kν(da)= ν(A_k)ν(A) where the last equality is due to π1(a∣s)=1/ν() _1(a s)=1/ν(A) is the Lebesgue uniform measure on A. According to our construction of kA_k, using change of variables, ν(k) ν(A_k) =∫kν(da)=∫dν(a∗+dK(a−a∗))=∫|det(dKI)|ν(da) = _A_kν(da)= _Adν(a^*+d_K(a-a^*))= _A| (d_KI_ d_A)|ν(da) =(dK)∫Aν(da)=(dK)ν(). =(d_K) d_A _Aν(da)=(d_K) d_Aν(A). This means the generalized volume of kA_k is (dK)(d_K) d_A. Hence, by setting the decay rate dK=1/Kd_K=1/K, we have ∑k=1K(fk(s,πcp)−fk(s,πk))≤ηVmax28K+LB+ηlogK. _k=1^K (f_k(s, _ cp)-f_k(s, _k) )≤ η V_ max^28K+LB+ d_Aη K. Taking the expectation over the designated state distribution s∼dπcps d_S _ cp with optimally tuned step size η to be η=8logK/(KVmax2)η= 8 d_A K/(KV_ max^2). This leads to the argument in Theorem 7. ∎ Appendix C Omitted Details for Section 4 C.1 Proof of Proposition 2 We construct a two-state contextual bandit (i.e., a one-step MDP with γ=0γ=0), together with a smooth log-linear policy class and a data-weighted contextual mirror descent update, such that the resulting iterates incur constant per-step comparator regret under dπcpd _ cp. Proof of Proposition 2. We construct the MDP first. For simplicity, we consider the following contextual bandit problem. Let =s1,s2S=\s_1,s_2\ and =0,1A=\0,1\. Since γ=0γ=0, the return equals the immediate reward. Define the reward function R(s,1)=1,R(s,0)=0,∀s∈.R(s,1)=1, R(s,0)=0, ∀ s . Then for any policy π, the Q-function equals the reward, and we set the oracle outputs to be exact: fk(s,a)≡Qπk(s,a)=R(s,a)∈[0,1],∀k≥1.f_k(s,a)≡ Q _k(s,a)=R(s,a)∈[0,1], ∀ k≥ 1. Consequently, fk(s,π)=a∼π(⋅∣s)[fk(s,a)]=π(1∣s),∀s∈,∀k≥1.f_k(s,π)=E_a π(· s)[f_k(s,a)]=π(1 s), ∀ s ,\ ∀ k≥ 1. Let the comparator state distribution be concentrated on s2s_2: dπcp(s1)=0,dπcp(s2)=1.d _ cp(s_1)=0, d _ cp(s_2)=1. Let the offline data state-marginal distribution be dD(s1)=1−ε,dD(s2)=ε,d^D(s_1)=1- , d^D(s_2)= , for some ε∈(0,12) ∈(0, 12). Then the density coverage condition holds with constant ‖dπcpdD‖∞=1ε<∞, \| d _ cpd^D \|_∞= 1 <∞, so coverage condition (Assumption 1) is satisfied by setting ε=1/ =1/ C. We consider the one-dimensional log-linear (a.k.a., linear softmax) policy class Πθ=πθ:θ∈ℝ _θ=\ _θ:θ \ defined by πθ(1∣s)=exp(θx(s))exp(θx(s))+exp(0)=σ(θx(s)),πθ(0∣s)=1−πθ(1∣s), _θ(1 s)= (θ x(s)) (θ x(s))+ (0)=σ(θ x(s)), _θ(0 s)=1- _θ(1 s), where x(s1)=+1x(s_1)=+1, x(s2)=−1x(s_2)=-1, and σ(u)=11+e−uσ(u)= 11+e^-u is the logistic function. Note that this parameterization induces the coupling identity πθ(1∣s2)=σ(−θ)=1−σ(θ)=1−πθ(1∣s1). _θ(1 s_2)=σ(-θ)=1-σ(θ)=1- _θ(1 s_1). Moreover, for any (s,a)(s,a), logπθ(a∣s) _θ(a s) is differentiable with |∂θlogπθ(a∣s)|≤1,|∂θ2logπθ(a∣s)|≤14, | _θ _θ(a s) |≤ 1, | _θ^2 _θ(a s) |≤ 14, so Πθ _θ satisfies Assumption 3 (e.g., with ∥⋅∥=∥⋅∥2\|·\|=\|·\|_2, G=1G=1, and β=1/4β=1/4). Initialize π1 _1 to be uniform over A, i.e., π1(1∣s)=12 _1(1 s)= 12 for both states, which corresponds to θ1=0 _1=0. At each round k, consider the data-weighted contextual mirror descent update obtained by replacing dπcpd _ cp with dDd^D both in the linear term and in the context-weighted KL regularizer: πk+1∈argmaxπ∈Πθs∼dD[fk(s,π)]−1ηs∼dD[DKL(π(⋅∣s)∥πk(⋅∣s))]. _k+1∈ _π∈ _θ \E_s d^D [f_k(s,π) ]- 1ηE_s d^D [D_ KL (π(· s)\| _k(· s) ) ] \. (14) Now we are going to give the regret lower bound. Let p(θ):=πθ(1∣s1)=σ(θ),πθ(1∣s2)=1−p(θ).p(θ):= _θ(1 s_1)=σ(θ), _θ(1 s_2)=1-p(θ). Denote pk:=p(θk)p_k:=p( _k). Because DKL(Ber(1−p)∥Ber(1−q))=DKL(Ber(p)∥Ber(q))D_ KL( Ber(1-p)\| Ber(1-q))=D_ KL( Ber(p)\| Ber(q)), the objective in Eq. (14) can be written as a concave function of p∈(0,1)p∈(0,1): s∼dD[fk(s,πθ)]−1ηs∼dD[DKL(πθ(⋅∣s)∥πθk(⋅∣s))]=ε+(1−2ε)p−1ηDKL(Ber(p)∥Ber(pk)),E_s d^D[f_k(s, _θ)]- 1ηE_s d^D [D_ KL ( _θ(· s)\| _ _k(· s) ) ]= +(1-2 )p- 1ηD_ KL ( Ber(p)\| Ber(p_k) ), where DKL(Ber(p)∥Ber(q))=plogpq+(1−p)log1−p1−qD_ KL( Ber(p)\| Ber(q))=p pq+(1-p) 1-p1-q. Since −DKL(Ber(p)∥Ber(pk))-D_ KL( Ber(p)\| Ber(p_k)) is concave in p and the first term is linear, the maximizer is characterized by the first-order condition: 0=(1−2ε)−1η(logppk−log1−p1−pk)⟺logp1−p=logpk1−pk+η(1−2ε).0=(1-2 )- 1η ( pp_k- 1-p1-p_k ) p1-p= p_k1-p_k+η(1-2 ). Therefore, writing logit(p)=logp1−plogit(p)= p1-p, the update satisfies logit(pk+1)=logit(pk)+η(1−2ε),hencepk+1=σ(logit(pk)+η(1−2ε)).logit(p_k+1)=logit(p_k)+η(1-2 ), p_k+1=σ (logit(p_k)+η(1-2 ) ). (15) Since ε∈(0,12) ∈(0, 12) implies 1−2ε>01-2 >0 and p1=1/2p_1=1/2, Eq. (15) yields pk≥12∀k≥1,andpk>12∀k≥2.p_k≥ 12\ \ ∀ k≥ 1, p_k> 12\ \ ∀ k≥ 2. Let the comparator policy πcp∈Πθ _ cp∈ _θ be θ=−log3θ=- 3. This means πcp(1∣s1)=1/4 _ cp(1 s_1)=1/4 and πcp(1∣s2)=3/4 _ cp(1 s_2)=3/4. Since the comparator occupancy puts all its mass to the state s2s_2, we have s∼dπcp[fk(s,πcp)]=fk(s2,πcp)=πcp(1∣s2)=3/4E_s d _ cp[f_k(s, _ cp)]=f_k(s_2, _ cp)= _ cp(1 s_2)=3/4. While on the other hand, s∼dπcp[fk(s,πk)]=fk(s2,πk)=πk(1∣s2)=1−pkE_s d _ cp[f_k(s, _k)]=f_k(s_2, _k)= _k(1 s_2)=1-p_k. This indicates that s∼dπcp[fk(s,πcp)−fk(s,πk)]=34−(1−pk)=pk−14≥14.E_s d _ cp [f_k(s, _ cp)-f_k(s, _k) ]= 34-(1-p_k)=p_k- 14≥ 14. Thus the per-step regret is bounded below by 1/41/4 for all k≥2k≥ 2, and consequently RegKK=1K∑k=1Ks∼dπcp[fk(s,πcp)−fk(s,πk)]≥Ω(1), Reg_KK= 1K _k=1^KE_s d _ cp [f_k(s, _ cp)-f_k(s, _k) ]≥ (1), which proves the proposition. ∎ As a preview, the simple MDP (contextual bandit) constructed in Proposition 2 is exactly compatible from the perspective of actor-critic incompatibility, formalized in Proposition 8. This shows that the failure of directly applying contextual mirror descent in Eq. (1) arises from a more fundamental source (i.e., distribution shift) rather than from actor-critic incompatibility induced by function approximation in the policy or value class. Consequently, this phenomenon is fundamentally different from the bias term introduced in Section 5. Proposition 8 (No actor-critic incompatibility in the hardness construction). Consider the construction in the proof of Proposition 2. Let Ak(s,a)A_k(s,a) denote the advantage function of πk _k and define the error of CFA errk=(s,a)∼dπcp[Ak(s,a)−v⊤∇θlogπk(a∣s)], err_k=E_(s,a) d _ cp [A_k(s,a)-v _θ _k(a s) ], where θ∈ℝθ is the (one-dimensional) parameter of the log-linear policy class Πθ _θ used in the construction. Then there exists a fixed vector v∈ℝv (in fact v=−1v=-1) such that errk=0 err_k=0 for all k≥1k≥ 1. In particular, the constructed instance has no model misspecification in the sense of compatible function approximation. Proof. In the constructed contextual bandit, the reward is R(s,1)=1R(s,1)=1 and R(s,0)=0R(s,0)=0 for all s and γ=0γ=0. Hence for any policy πk _k we have Qπk(s,a)=R(s,a)Q _k(s,a)=R(s,a) and Vπk(s)=a∼πk(⋅∣s)[R(s,a)]=πk(1∣s)V _k(s)=E_a _k(· s)[R(s,a)]= _k(1 s). Therefore the advantage satisfies, for any s∈s and a∈a , Ak(s,a)=Qπk(s,a)−Vπk(s)=R(s,a)−πk(1∣s)=a=1−πk(1∣s).A_k(s,a)=Q _k(s,a)-V _k(s)=R(s,a)- _k(1 s)=1\a=1\- _k(1 s). Next, consider the log-linear policy class in the construction. It is easy to show that the score function satisfies ∇θlogπθ(a∣s)=x(s)(a=1−πθ(1∣s)). _θ _θ(a s)=x(s) (I\a=1\- _θ(1 s) ). Specializing to s2s_2 (the only state in the support of dπcpd _ cp), we have x(s2)=−1x(s_2)=-1 and thus ∇θlogπk(a∣s2)=−(a=1−πk(1∣s2))=−Ak(s2,a). _θ _k(a s_2)=- (1\a=1\- _k(1 s_2) )=-A_k(s_2,a). Choosing the fixed scalar v=−1v=-1 yields the pointwise identity v∇θlogπk(a∣s2)=Ak(s2,a),∀a∈,∀k≥1v _θ _k(a s_2)=A_k(s_2,a), ∀ a ,\ ∀ k≥ 1. Since dπcpd _ cp is concentrated on s2s_2, it follows that for all k≥1k≥ 1, errk err_k =(s,a)∼dπcp[Ak(s,a)−v∇θlogπk(a∣s)] =E_(s,a) d _ cp [A_k(s,a)-v _θ _k(a s) ] =a∼πk(⋅∣s2)[Ak(s2,a)−v∇θlogπk(a∣s2)] =E_a _k(· s_2) [A_k(s_2,a)-v _θ _k(a s_2) ] =0. =0. This proves the claim. ∎ C.2 Proof of Lemma 3 Proof of Lemma 3. With Assumption 3, logπθ(a∣s) _θ(a s) is β-smooth in θ with respect to some norm ∥⋅∥\|·\|. That is, for all (s,a)∈×(s,a) ×A, we can bound the first-order approximation error between arbitrary θ,θ′∈ℝθ,θ d as −β2‖θ′−θ‖2≤logπθ′(a∣s)−logπθ(a∣s)−⟨∇logπθ(a∣s),θ′−θ⟩≤β2‖θ′−θ‖2.- β2\|θ -θ\|^2≤ _θ (a s)- _θ(a s)- ∇ _θ(a s),θ -θ ≤ β2\|θ -θ\|^2. Applying the update rule θk+1=θk+ηvk _k+1= _k+η v_k and substituting θ′=θk+1θ = _k+1, θ=θkθ= _k, we obtain (by taking the negative side): logπk+1(a∣s)πk(a∣s) _k+1(a s) _k(a s) ≥(∇θlogπk(a∣s))⊤(θk+1−θk)−β2‖θk+1−θk‖2 ≥ ( _θ _k(a s) ) ( _k+1- _k)- β2\| _k+1- _k\|^2 ≥η(∇θlogπk(a∣s))⊤vk−β2η2‖vk‖2. ≥η ( _θ _k(a s) ) v_k- β2η^2\|v_k\|^2. Recall the definition of errk=(s,a)∼dπcp[Ak(s,a)−(∇θlogπk(a∣s))⊤vk] err_k=E_(s,a) d _ cp [A_k(s,a)- ( _θ _k(a s) ) v_k ], we have (s,a)∼dπcp[(∇θlogπk(a∣s))⊤vk]=(s,a)∼dπcp[Ak(s,a)]−errk.E_(s,a) d _ cp [ ( _θ _k(a s) ) v_k ]=E_(s,a) d _ cp [A_k(s,a) ]- err_k. Hence, by the definition of KL divergence DKL(p∥q)=p[log(p/q)]D_ KL(p\|q)=E_p[ (p/q)], we have s∼dπcp[DKL(πcp(⋅∣s)∥πk(⋅∣s))−DKL(πcp(⋅∣s)∥πk+1(⋅∣s))] _s d _ cp [D_ KL( _ cp(· s)\| _k(· s))-D_ KL( _ cp(· s)\| _k+1(· s)) ] =s∼dπcp[a∼πcp(⋅∣s)[logπk+1(a∣s)πk(a∣s)]] =E_s d _ cp [E_a _ cp(· s) [ _k+1(a s) _k(a s) ] ] ≥(s,a)∼dπcp[η(∇θlogπk(a∣s))⊤vk−β2η2‖vk‖2] _(s,a) d _ cp [η ( _θ _k(a s) ) v_k- β2η^2\|v_k\|^2 ] ≥η(s,a)∼dπcp[Ak(s,a)]−η⋅errk−β2η2‖vk‖2, ≥ _(s,a) d _ cp [A_k(s,a) ]-η· err_k- β2η^2\|v_k\|^2, where the first inequality is due to the previous display of the smoothness, and the second inequality is due to the rewrite of errk err_k. Since Ak(s,a)=fk(s,a)−fk(s,πk)A_k(s,a)=f_k(s,a)-f_k(s, _k), rearranging the terms, we get s∼dπcp[fk(s,πcp)− _s d _ cp [f_k(s, _ cp)- fk(s,πk)]=(s,a)∼dπcp[Ak(s,a)]≤errk+β2η∥vk∥2 f_k(s, _k) ]=E_(s,a) d _ cp[A_k(s,a)]≤ err_k+ β2η\|v_k\|^2 +1ηs∼dπcp[DKL(πcp(⋅∣s)∥πk(⋅∣s))−DKL(πcp(⋅∣s)∥πk+1(⋅∣s))]. + 1ηE_s d _ cp [D_ KL( _ cp(· s)\| _k(· s))-D_ KL( _ cp(· s)\| _k+1(· s)) ]. Telescoping the last term of KL divergence, we get RegK≤∑k=1Kerrk+η⋅β2∑k=1K∥vk∥2+1η⋅s∼dπcp[DKL(πcp(⋅∣s)∥π1(⋅∣s))]. Reg_K≤ _k=1^K err_k+η· β2 _k=1^K\|v_k\|^2+ 1η·E_s d _ cp [D_ KL( _ cp(· s)\| _1(· s)) ]. Since the update direction vkv_k satisfies ‖vk‖≤BL\|v_k\|≤ B_L for all k∈[K]k∈[K], choosing the step size optimally as η=2DKL(πcp∥π1)βKBL2η= 2D_ KL( _ cp\| _1)β KB_L^2, yields the regret bound RegKK≤1K∑k=1Kerrk+BL2β⋅DKL(πcp∥π1)K, Reg_KK≤ 1K _k=1^K err_k+B_L 2β· D_ KL( _ cp\| _1)K, where DKL(πcp∥π1)=s∼dπcp[DKL(πcp(⋅∣s)∥π1(⋅∣s))]D_ KL( _ cp\| _1)=E_s d _ cp[D_ KL( _ cp(· s)\| _1(· s))] is the expected KL divergence under dπcpd _ cp. ∎ Appendix D Omitted Details for Section 5.1 In this section, we establish the performance guarantee of Algorithm 2 along with LSPU update. We will decompose the error of compatible function approximation (CFA) into the bias term ϵCFA _ CFA and the estimation error term ϵstat _ stat. And then we utilize results from Hsu et al. [2012] to give a sharp analysis on linear regression, which controls the estimation error ϵstat _ stat. Finally, we will give a more rigorous analysis that is based on log-covering number (i.e., metric entropy) rather than log-cardinality of the function or policy class. D.1 Two Cases with Zero Actor-Critic Incompatibility Taking a detour, we first show that the intrinsic bias term ϵCFA _ CFA vanishes in two special cases: (i) under the canonical softmax policy class with any function class ℱF, and (i) in the linear function approximation setting [Jin et al., 2020, Yang and Wang, 2019, Jiang et al., 2017] under the log-linear policy class. In general, if we achieves “compatible” function approximation (i.e., the actor and the critic aligns compatibly), then ϵCFA=0 _ CFA=0. Proposition 9 (No Bias under Canonical Softmax Policy). Consider the softmax policy class πθ(a∣s)=exp(θ(s,a))∑a′∈exp(θ(s,a′)), _θ(a s)= (θ(s,a)) _a (θ(s,a )), where θ(s,a)θ(s,a) denotes the (s,a)(s,a)-th component of the parameter θ∈ℝ×θ ^S×A. Then, for any advantage function Ak(s,a)A_k(s,a), there exists a parameter update direction vknv_k n such that Ak(s,a)=(vkn)⊤∇θlogπk(a∣s)for all (s,a)∈×.A_k(s,a)=(v_k n) _θ _k(a s) all (s,a) ×A. Consequently, the function approximation is well-specified, and the intrinsic bias term in Assumption 4 satisfies ϵCFA=0 _ CFA=0. Proof. Under the softmax parameterization, the log-policy gradient takes the form ∇θlogπk(a∣s)=∇θ(s,a)−a′∼πk(⋅∣s)[∇θ(s,a′)]. _θ _k(a s)= _θ(s,a)-E_a _k(· s)[ _θ(s,a )]. Since θ(s,a)θ(s,a) can be any real-valued function over (s,a)(s,a), the gradient basis ∇θlogπk(a∣s) _θ _k(a s) spans all zero-mean functions with respect to πk(⋅∣s) _k(· s). The advantage function Ak(s,a)A_k(s,a) also satisfies a∼πk(⋅∣s)[Ak(s,a)]=0E_a _k(· s)[A_k(s,a)]=0 by definition. Therefore, AkA_k lies exactly in the span of ∇θlogπk(a∣s) _θ _k(a s), implying that there exists a vector vknv_k^n achieving zero regression error. Moreover, any function of the form Ak(s,a)+ckA_k(s,a)+c_k, where ckc_k is a state-dependent constant, is also a minimizer, since a∼πk(⋅∣s)[∇θlogπk(a∣s)]=∑a∈πk(a∣s)∇θlogπk(a∣s)=∇θ∑a∈πk(a∣s)=∇θ1=0.E_a _k(· s)[ _θ _k(a s)]= _a _k(a s) _θ _k(a s)= _θ _a _k(a s)= _θ1=0. Hence, under the canonical softmax policy class, we have ϵCFA=0 _ CFA=0. ∎ Proposition 10 (No Bias under Compatible Log-Linear Policy). Assume a log-linear policy πθ(a∣s)=exp(θ⊤ϕ(s,a))∑a′∈exp(θ⊤ϕ(s,a′)), _θ(a s)= (θ φ(s,a)) _a (θ φ(s,a )), and a linear function class ℱ=fw(s,a)=ϕ(s,a)⊤w:w∈ℝF=\f_w(s,a)=φ(s,a) w:w d\ with the same feature map ϕ:×→ℝφ:S×A d. At iteration k, let fk∈ℱf_k and define Ak(s,a)A_k(s,a). Then there exists a parameter update direction vkn∈ℝv_k n d such that Ak(s,a)=vkn⊤∇θlogπk(a∣s)for all (s,a)∈×,A_k(s,a)=v_k n _θ _k(a s) all (s,a) ×A, and hence the function approximation is realizable with ϵCFA=0 _ CFA=0 in Assumption 4. Proof. Fix an iteration k and a state s. Define Z(s,θ)=∑a′∈exp(θ⊤ϕ(s,a′))Z(s,θ)= _a (θ φ(s,a )). Then logπθ(a∣s)=θ⊤ϕ(s,a)−logZ(s,θ) _θ(a s)=θ φ(s,a)- Z(s,θ), whose gradient is ∇θlogπθ(a∣s)=ϕ(s,a)−a′∼πθ(⋅∣s)[ϕ(s,a′)]. _θ _θ(a s)=φ(s,a)-E_a _θ(· s)[φ(s,a )]. Substituting θ=θkθ= _k gives ∇θlogπk(a∣s) _θ _k(a s). On the critic side, fk(s,a)=ϕ(s,a)⊤wkf_k(s,a)=φ(s,a) w_k for some wk∈ℝw_k d, so the advantage Ak(s,a)=fk(s,a)−fk(s,πk)=wk⊤(ϕ(s,a)−a′∼πk(⋅∣s)[ϕ(s,a′)]).A_k(s,a)=f_k(s,a)-f_k(s, _k)=w_k (φ(s,a)-E_a _k(· s)[φ(s,a )] ). Comparing both expressions shows Ak(s,a)=wk⊤∇θlogπk(a∣s)A_k(s,a)=w_k _θ _k(a s) for all (s,a)(s,a). Hence the regression model is exactly realizable with vkn=wkv_k n=w_k, producing zero residual and ϵCFA=0 _ CFA=0. ∎ D.2 Decomposed Regret Bound We can decompose the error of CFA into a bias term ϵCFA _ CFA (in Assumption 4) and an estimation error term ϵstat _ stat, multiplied by some coverage constant. Recall that the least-square loss LkL_k at round k is given by Lk(v)=(s,a)∼dD[(Ak(s,a)−v⊤∇logπk(a∣s))2].L_k(v)=E_(s,a) d^D [(A_k(s,a)-v ∇ _k(a s))^2 ]. And the bias term and the estimation error term in Section 5.1 are respectively defined as Lk(vk∗)=minv:‖v‖≤BLLk(v)≤ϵCFA,Lk(vk)−Lk(vk∗)≤ϵstat,∀k∈[K].L_k(v_k^*)= _v:\|v\|≤ B_LL_k(v)≤ _ CFA, L_k(v_k)-L_k(v_k^*)≤ _ stat, ∀ k∈[K]. The following lemma formalizes this fact of decomposition. Lemma 11 (Decomposed Regret Bound for LSPU). Under Assumptions 1, 3, and 4, the update in Eq. (5) with step size η=2DKL(πcp∥π1)/(βKBL2)η= 2D_ KL( _ cp\| _1)/(β KB_L^2) achieves the following regret bound: RegKK≤BL2βDKL(πcp∥π1)K+(ϵCFA+ϵstat). Reg_KK≤ B_L 2β D_ KL( _ cp\| _1)K+ C ( _ CFA+ _ stat ). Proof. Using the regret decomposition lemma (Lemma 3), we have RegKK≤BL2βDKL(πcp∥π1)K+1K∑k=1Kerrk. Reg_KK≤ B_L 2β D_ KL( _ cp\| _1)K+ 1K _k=1^K err_k. We make the following decomposition of errk err_k: errk=(s,a)∼dπcp[Ak(s,a)−(vk∗)⊤∇θlogπk(a∣s)]+(s,a)∼dπcp[(vk∗−vk)⊤∇θlogπk(a∣s)]. err_k=E_(s,a) d _ cp [A_k(s,a)-(v_k^*) _θ _k(a s) ]+E_(s,a) d _ cp [(v_k^*-v_k) _θ _k(a s) ]. By the coverage assumption that ‖dπcp/dD‖∞≤\|d _ cp/d^D\|_∞≤ C, we can translate the error to the offline data distribution dDd^D and bound the first term with (s,a)∼dπcp[Ak(s,a)−(vk∗)⊤∇θlogπk(a∣s)] _(s,a) d _ cp [A_k(s,a)-(v_k^*) _θ _k(a s) ] ≤(s,a)∼dπcp[(Ak(s,a)−(vk∗)⊤∇θlogπk(a∣s))2] ≤ E_(s,a) d _ cp [ (A_k(s,a)-(v_k^*) _θ _k(a s) )^2 ] ≤⋅(s,a)∼dD[(Ak(s,a)−(vk∗)⊤∇θlogπk(a∣s))2] ≤ C·E_(s,a) d^D [ (A_k(s,a)-(v_k^*) _θ _k(a s) )^2 ] =⋅Lk(vk∗)≤⋅ϵCFA. = C· L_k(v_k^*)≤ C· _ CFA. For the second term, we note that vk∗v_k^* is the minimizer of Lk(v)L_k(v) over the set =v:‖v‖≤BLV=\v:\|v\|≤ B_L\ (since we assume ‖vk∗‖≤BL\|v_k^*\|≤ B_L in Assumption 4). Hence for any v such that ‖v‖≤BL\|v\|≤ B_L, the first-order optimality condition for vk∗v_k^* imply that (v−vk∗)⊤∇vLk(vk∗)≥0. (v-v_k^* ) _vL_k(v_k^*)≥ 0. Therefore, for any v such that ‖v‖≤BL\|v\|≤ B_L, we have Lk(v)−Lk(vk∗) L_k(v)-L_k(v_k^*) =dD[(Ak−ϕk⊤v)2]−dD[(Ak−ϕk⊤vk∗)2] =E_d^D [(A_k- _k v)^2 ]-E_d^D [(A_k- _k v_k^*)^2 ] =dD[(Ak−ϕk⊤vk∗+ϕk⊤vk∗−ϕk⊤v)2]−dD[(Ak−ϕk⊤vk∗)2] =E_d^D [(A_k- _k v_k^*+ _k v_k^*- _k v)^2 ]-E_d^D [(A_k- _k v_k^*)^2 ] =dD[(ϕk⊤(vk∗−v))2]−2dD[ϕk⊤(vk∗−v)(Ak−ϕk⊤vk∗)] =E_d^D [ ( _k (v_k^*-v) )^2 ]-2E_d^D [ _k (v_k^*-v)(A_k- _k v_k^*) ] =‖vk∗−vk‖ΣD2+2(v−vk∗)⊤∇vLk(vk∗) =\|v_k^*-v_k\|_ _D^2+2(v-v_k^*) _vL_k(v_k^*) ≥‖vk∗−vk‖ΣD2, ≥\|v_k^*-v_k\|_ _D^2, where we use ϕk _k to denote the feature ∇θlogπk _θ _k, and ΣD=dD[ϕkϕk⊤] _D=E_d^D[ _k _k ]. The last inequality is due to the first-order optimality condition stated before. By taking v=vkv=v_k and the coverage condition, we have (s,a)∼dπcp[(vk∗−vk)⊤∇θlogπk(a∣s)] _(s,a) d _ cp [(v_k^*-v_k) _θ _k(a s) ] ≤(s,a)∼dπcp[((vk∗−vk)⊤∇θlogπk(a∣s))2] ≤ E_(s,a) d _ cp [ ((v_k^*-v_k) _θ _k(a s) )^2 ] ≤⋅(s,a)∼dD[((vk∗−vk)⊤∇θlogπk(a∣s))2] ≤ C·E_(s,a) d^D [ ((v_k^*-v_k) _θ _k(a s) )^2 ] =⋅‖vk∗−vk‖ΣD2 = C·\|v_k^*-v_k\|_ _D^2 ≤⋅(Lk(vk)−Lk(vk∗))≤⋅ϵstat. ≤ C· (L_k(v_k)-L_k(v_k^*) )≤ C· _ stat. Combining those two terms, we get that errk≤(ϵCFA+ϵstat) err_k≤ C( _ CFA+ _ stat). Substituting into the regret bound, we get Lemma 11: RegKK≤BL2βDKL(πcp∥π1)K+(ϵCFA+ϵstat). Reg_KK≤ B_L 2β D_ KL( _ cp\| _1)K+ C ( _ CFA+ _ stat ). ∎ D.3 Bounding the Estimation Error As we see from Lemma 11, the error of CFA decomposes into an intrinsic bias term ϵCFA _ CFA and an estimation error term ϵstat _ stat. Now we proceed to bound this statistical error ϵstat _ stat. Recall that at each iteration k, the estimator vkv_k is obtained by solving a linear regression problem defined over samples from the offline dataset D. Formally, for any (s,a)∼dD(s,a) d^D, the regression model is given by Ak(s,a)∼v⊤ϕk(s,a)+ϵk(s,a),A_k(s,a) v _k(s,a)+ _k(s,a), where ϕk(s,a)=∇θlogπk(a∣s) _k(s,a)= _θ _k(a s) is the feature vector, and ϵk(s,a) _k(s,a) represents the model misspecification bias (not a stochastic noise term, since each AkA_k is deterministically computable). This corresponds to the random design, noiseless, and misspecified model setting in linear regression. Before we proceed the analysis, we first provide an assumption that is crucial for the linear regression analysis. Such assumptions are standard in giving a sharper statistical bound of linear regression [Hsu et al., 2012], compared to naïve SGD-based algorithm (see Appendix D.5). Assumption 6 (Data Model for Linear Regression). Assume the feature covariance matrix ΣD=dD[ϕkϕk⊤] _D=E_d^D[ _k _k ] is invertible. Then, suppose uniformly for all k∈[K]k∈[K]: 1. (Bounded pointwise bias) There exists a finite Bbias≥0B_ bias≥ 0 such that for all (s,a)(s,a) almost surely: ‖ΣD−1/2ϕk(s,a)ϵk(s,a)‖≤Bbias⋅.\| _D^-1/2 _k(s,a) _k(s,a)\|≤ B_ bias· d. Note that BbiasB_ bias is a pointwise bound that only appear in lower order terms. It is actually possible to relax this condition to moment bounds like ϵCFA _ CFA by using a differential exponential tail inequality in the analysis. We do not consider this relaxation for the sake of simplicity. 2. (Bounded statistical leverage) There exists a finite ρ≥1ρ≥ 1 such that for all (s,a)(s,a) almost surely: ‖ΣD−1/2ϕk(s,a)‖=‖ΣD−1/2ϕk(s,a)‖[‖ΣD−1/2ϕk(s,a)‖2]≤ρ. \| _D^-1/2 _k(s,a)\| d= \| _D^-1/2 _k(s,a)\| E[\| _D^-1/2 _k(s,a)\|^2]≤ρ. The bounded statistical leverage means that the squared length (after whitening) is never more than a constant factor greater than its expectation. Following Assumption 6, since the feature covariance matrix ΣD _D is invertible, the closed-form solutions of the population and empirical minimizers are respectively vk∗=ΣD−1[ϕkAk],vk=argminv:‖v‖≤BL^[(Ak−v⊤ϕk)2],v_k^*= _D^-1E[ _kA_k], v_k= v:\|v\|≤ B_L \ E [(A_k-v _k)^2 ], where E denotes the empirical average. To proceed, we first express the estimation error in a form that separates the randomness arising from the empirical covariance Σ^D _D and the model misspecification term ϵk(s,a) _k(s,a). Lemma 12 (Estimation Error “Decomposition”). If the empirical covariance matrix Σ^D=^[ϕkϕk⊤]≻0 _D= E[ _k _k ] 0 (which is a high-probability consequence under Assumption 6), then the estimation error can be bounded by ϵstat≤4‖ΣD1/2Σ^D−1ΣD1/2‖2⏟(I)⋅‖^[ΣD−1/2ϕkϵk]‖2⏟(I). _ stat≤ 4 \| _D^1/2 _D^-1 _D^1/2 \|^2_ (I)· \| E [ _D^-1/2 _k _k ] \|^2_ (I). Proof. By the definition of ϵstat _ stat, we are actually going to bound the excess risk Lk(vk)−Lk(vk∗)L_k(v_k)-L_k(v_k^*). Since vk∗v_k^* is the minimizer of Lk(vk)L_k(v_k), by the same procedure in the proof of Lemma 11, we can express this excess risk as Lk(vk)−Lk(vk∗)=‖vk−vk∗‖ΣD2:=‖Δv‖ΣD2.L_k(v_k)-L_k(v_k^*)=\|v_k-v_k^*\|_ _D^2:=\| _v\|_ _D^2. Since for each (s,a)∼ℝ×(s,a) ^S×A, Ak(s,a)−(vk∗)⊤ϕk(s,a)=ϵk(s,a)A_k(s,a)-(v_k^*) _k(s,a)= _k(s,a), we have vk⊤ϕk−Ak=(vk∗+Δv)⊤ϕk−(vk∗)⊤ϕk−ϵk=Δv⊤ϕk−ϵk.v_k _k-A_k=(v_k^*+ _v) _k-(v_k^*) _k- _k= _v _k- _k. Recall that vkv_k minimizes for the empirical loss, we have ^[(vk⊤ϕk−Ak)2]≤^[((vk∗)⊤ϕk−Ak)2]=^[ϵk2] E[(v_k _k-A_k)^2]≤ E[((v_k^*) _k-A_k)^2]= E[ _k^2]. Substituting the above equation into this inequality and cancelling ϵk2 _k^2, we have ‖Δv‖Σ^D2=^[(Δv⊤ϕk)2]≤2^[Δv⊤ϕkϵk]=2⟨^[ϕkϵk],Δv⟩≤2‖Δv‖Σ^D‖^[ϕkϵk]‖Σ^D−1,\| _v\|_ _D^2= E[( _v _k)^2]≤ 2 E[ _v _k _k]=2 E[ _k _k], _v ≤ 2\| _v\|_ _D\| E[ _k _k]\|_ _D^-1, where the last inequality is due to Cauchy-Schwarz. This leads to ‖Δv‖Σ^D≤2∥^[Σ^D−1/2ϕkϵk]\| _v\|_ _D≤ 2\| E[ _D^-1/2 _k _k]. To finish the proof, we only need to do two geometry transfer from Σ^D _D to ΣD _D. First, since ‖Σ^D−1/2ΣDΣ^D−1/2‖=‖ΣD1/2Σ^D−1ΣD1/2‖\| _D^-1/2 _D _D^-1/2\|=\| _D^1/2 _D^-1 _D^1/2\|, we have ‖Δv‖ΣD2 \| _v\|_ _D^2 =Δv⊤Σ^D1/2(Σ^D−1/2ΣDΣ^D−1/2)Σ^D1/2Δv = _v _D^1/2 ( _D^-1/2 _D _D^-1/2 ) _D^1/2 _v ≤‖ΣD1/2Σ^D−1ΣD1/2‖⋅‖Δv‖Σ^D2 ≤\| _D^1/2 _D^-1 _D^1/2\|·\| _v\|_ _D^2 ≤4∥ΣD1/2Σ^D−1ΣD1/2∥⋅∥^[Σ^D−1/2ϕkϵk∥2. ≤ 4\| _D^1/2 _D^-1 _D^1/2\|·\| E[ _D^-1/2 _k _k\|^2. Similarly, we can transfer the last term by ‖^[Σ^D−1/2ϕkϵk]‖2 \| E[ _D^-1/2 _k _k]\|^2 =^[ϕkϵk]⊤ΣD−1/2(ΣD1/2Σ^D−1ΣD1/2)ΣD−1/2^[ϕkϵk] = E[ _k _k] _D^-1/2 ( _D^1/2 _D^-1 _D^1/2 ) _D^-1/2 E[ _k _k] ≤‖ΣD1/2Σ^D−1ΣD1/2‖⋅‖^[ΣD−1/2ϕkϵk]‖2. ≤\| _D^1/2 _D^-1 _D^1/2\|·\| E[ _D^-1/2 _k _k]\|^2. Combining the above two leads to the error bound of ϵstat _ stat, i.e., ‖Δv‖ΣD2≤4‖ΣD1/2Σ^D−1ΣD1/2‖2⋅‖^[ΣD−1/2ϕkϵk]‖2.\| _v\|_ _D^2≤ 4\| _D^1/2 _D^-1 _D^1/2\|^2·\| E[ _D^-1/2 _k _k]\|^2. ∎ Therefore, term (I) quantifies the concentration between the population covariance ΣD _D and its empirical counterpart Σ^D _D, while term (I) accounts for the model misspecification through ϵk _k. The key of bounding the estimation error proceeds by bounding these two terms separately, using appropriate matrix concentration inequalities for each. Lemma 13 (LSPU Estimation Error Bound). Under Assumptions 3, 4, and 6, for any given πk∈Πθ _k∈ _θ and fk∈ℱf_k , with probability at least 1−δ1-δ, Lk(vk)−Lk(vk∗)≲ρ2ϵCFANlog1δ+Bbias2N2log1δ.L_k(v_k)-L_k(v_k^*) ρ^2 d _ CFAN 1δ+ B_ bias^2 dN^2 1δ. Proof of Lemma 13. We first analyze term (I). Let ϕ~k(i)=ΣD−1/2ϕk(i) φ_k^(i)= _D^-1/2 _k^(i) denote the whitened feature for sample i∈[N]i∈[N], and define the corresponding covariance matrix as Σ~D=1N∑i=1Nϕ~k(i)(ϕ~k(i))⊤ _D= 1N _i=1^N φ_k^(i)( φ_k^(i)) . By applying the matrix Chernoff bound (Lemma 27), we obtain that, with probability at least 1−δ/21-δ/2, λmin(Σ~D)≥1−2ρ2nlog2δ, _ min ( _D )≥ 1- 2ρ^2 dn 2 dδ, since ϕ~k(s,a)=‖ΣD−1/2ϕk(s,a)‖≤ρ φ_k(s,a)=\| _D^-1/2 _k(s,a)\|≤ρ d by Assumption 6. The lower bound on n guarantees that λmin(Σ~D)>0 _ ( _D)>0, which in turn implies that Σ^D=ΣD1/2Σ~DΣD1/2≻0 _D= _D^1/2 _D _D^1/2 0. This indicates that it suffices to assume the positive definiteness of ΣD _D rather than Σ^D _D. Moreover, since ΣD1/2Σ^DΣD1/2=Σ~D−1 _D^1/2 _D _D^1/2= _D^-1, we can bound term (I) as ‖ΣD1/2(Σ^D)−1ΣD1/2‖=‖Σ~−1‖≤1λmin(Σ~)≤11−2ρ2Nlogδ:=Kδ,N. \| _D^1/2( _D)^-1 _D^1/2 \|= \| ^-1 \|≤ 1 _ min( )≤ 11- 2ρ^2 dN dδ:=K_δ,N. For N≥Nδ:=4ρ2log(/δ)N≥ N_δ:=4ρ^2 d ( d/δ), we have Kδ,N≤5K_δ,N≤ 5; and we also have that limN→∞Kδ,N=1 _N→∞K_δ,N=1. Therefore, we can regard Kδ,NK_δ,N as a constant without loss of generality and term (I) do not change the convergence rate with respect to N. Now we are going to handle term (I). The optimality of vk∗v_k^* means that [ϕk(i)ϵk(i)]=[ϕkϵk]=0E[ _k^(i) _k^(i)]=E[ _k _k]=0 for all i∈[N]i∈[N]. Using this fact and that‖Σ−1/2ϕk(s,a)ϵk(s,a)‖≤Bbias\| ^-1/2 _k(s,a) _k(s,a)\|≤ B_ bias d (Assumption 6), we can apply the matrix Bernstein inequality (Lemma 28) and obtain that with probability at least 1−δ/21-δ/2, ‖^[ΣD−1/2ϕkϵk]‖≤[‖Σ−1/2ϕkϵk‖2]N(1+8log2δ)2+4Bbias3Nlog2δ. \| E [ _D^-1/2 _k _k ] \|≤ E [\| ^-1/2 _k _k\|^2 ]N (1+ 8 2δ )^2+ 4B_ bias d3N 2δ. By squaring both sides and applying the inequality (a+b)2≤2(a2+b2)(a+b)^2≤ 2(a^2+b^2), we have ‖^[ΣD−1/2ϕkϵk]‖2≤4[‖Σ−1/2ϕkϵk‖2]N(1+8log2δ)+3Bbias2N2log2δ. \| E [ _D^-1/2 _k _k ] \|^2≤ 4E [\| ^-1/2 _k _k\|^2 ]N (1+8 2δ )+ 3B_ bias^2 dN^2 2δ. Since we assume that ‖ΣD−1/2ϕk‖≤ρ\| _D^-1/2 _k\|≤ρ d, we can further bound [‖Σ−1/2ϕkϵk‖2]E [\| ^-1/2 _k _k\|^2 ] as [‖Σ−1/2ϕkϵk‖2]≤ρ2⋅(s,a)∼dD[ϵk(s,a)2]=ρ2⋅ϵCFA,E [\| ^-1/2 _k _k\|^2 ]≤ρ^2 d·E_(s,a) d^D[ _k(s,a)^2]=ρ^2 d· _ CFA, where the last inequality is due the definition of ϵCFA _ CFA in Assumption 4 and the pointwise bias term ϵk _k. Combining these two results and substituting it into Lemma 12, we get the bound of estimation error in Lemma 13: Lk(vk)−Lk(vk∗)≲ρ2ϵCFANlog1δ+Bbias2N2log1δ.L_k(v_k)-L_k(v_k^*) ρ^2 d _ CFAN 1δ+ B_ bias^2 dN^2 1δ. ∎ Note that this does not directly lead to a bound for ϵstat _ stat since Lemma 13 holds for only fixed policy πk∈Πθ _k∈ _θ (hence ϕk=∇logπk _k=∇ _k) and function fk∈ℱf_k (hence Ak=fk−f¯kA_k=f_k- f_k). Therefore there should be a workaround to union over all π∈Πθπ∈ _θ and f∈ℱf , which is provided next. D.4 Proof of Theorem 4 As established in Lemma 13, the estimation error exhibits an elegant bound for fixed πk∈Πθ _k∈ _θ and fk∈ℱf_k , ∀k∈[K]∀ k∈[K]. To work with arbitrary π∈Πθπ∈ _θ amd f∈ℱf , a natural approach is to apply union bound over all Πθ _θ and ℱF, leading to Lk(vk)−Lk(vk∗)≲ρ2ϵCFANlog|ℱ||Πθ|δ+Bbias2N2log|ℱ||Πθ|δ.L_k(v_k)-L_k(v_k^*) ρ^2 d _ CFAN |F|| _θ|δ+ B_ bias^2 dN^2 |F|| _θ|δ. While the log(|ℱ||Πθ|/δ) (|F|| _θ|/δ) term allows the function class ℱF and the policy class Πθ _θ to be exponentially large, it does not apply rigorously when Πθ _θ is continuous. In particular, under Assumption 3, the policy class is assumed to satisfy Lipschitzness and smoothness conditions, for which a finite log-cardinality is no longer well-defined. Therefore, in Theorem 4, we employ an abstract complexity measure Comp(ℱ,Πθ,δ) Comp(F, _θ,δ) to capture the statistical complexity of the two classes. Common tools from statistical learning theory (e.g., VC-dimension, Rademacher complexity) can be used to instantiate this measure. Here we adopt the notion of covering numbers [Mohri et al., 2018], which leads to an estimation error bound that depends on the metric entropy of the two classes. Definition 1 (ε -covering number). An ε -cover of a set G with respect to a metric d is a set g1,…,gn⊆\g_1,…,g_n\ , such that for each g∈g , there exists some gi∈g1,…,gng_i∈\g_1,…,g_n\ such that d(g,gi)≤εd(g,g_i)≤ . We define the ε -covering number of a set G under metric d, d(,ε)N_d(G, ) to be the cardinality of the smallest ε -cover. For the function class ℱF, we use the following metric dℱ(f1,f2):=‖f1−f2‖∞=sup(s,a)∈×|f1(s,a)−f2(s,a)|.d_F(f_1,f_2):=\|f_1-f_2\|_∞= _(s,a) ×A|f_1(s,a)-f_2(s,a)|. For the (parametric) policy class Πθ _θ, we define the metric as follows: dΠ(π1,π2):=‖θ1−θ2‖.d_ ( _1, _2):=\| _1- _2\|. Lemma 14 (Covering Version of Lemma 13). Let vkv_k denote the least-squares solution defined in Eq. (7). Under the same assumption of Lemma 13, let (ℱ,ε)N(F, ) and (Πθ,ε)N( _θ, ) to respectively denote the ε -covering number of ℱF and Πθ _θ with respect to metric dℱd_F and dΠd_ , then the estimation error ϵstat _ stat satisfies, with probability at least 1−δ1-δ, ϵstat≲ρ2ϵCFANlog(ℱ,Vmax/N)(Πθ,1/N)δ. _ stat ρ^2 d _ CFAN N(F,V_ max/N)N( _θ,1/N)δ. Proof. Let ℱε1F_ _1 be an ε1 _1-cover of ℱF and Πε2 _ _2 be an ε2 _2 cover of Πθ _θ, so that we know: 1) |ℱε1|=(ℱ,ε1)|F_ _1|=N(F, _1), |Πε2|=(Πθ,ε2)| _ _2|=N( _θ, _2); 2) for all f∈ℱf , πθ∈Πθ _θ∈ _θ, there exists f~∈ℱε1 f _ _1, and πθ~∈Πε2 _ θ∈ _ _2 such that ‖f−f~‖∞≤ε1\|f- f\|_∞≤ _1 and ‖θ−θ~‖≤ε2\|θ- θ\|≤ _2. Therefore, we can decompose the estimation error ϵstat _ stat with |Lk(vk)−Lk(vk∗)|≤|Lk(vk)~−Lk(vk∗)~|⏟optimization error+2supv:‖v‖≤BL|Lk(v)−Lk(v)~|⏟approximation error, |L_k(v_k)-L_k(v_k^*) |≤ | L_k(v_k)- L_k(v_k^*) |_optimization error+ 2 _v:\|v\|≤ B_L |L_k(v)- L_k(v) |_approximation error, where L~k(v;dD) L_k(v;d^D) denote the linear regression with Ak,ϕkA_k, _k replaced by A~k A_k and ϕ~k φ_k in the covering. By the same argument in the proof of Lemma 13, we have that for some f~∈ℱε1 f _ _1 and πθ~∈Πε2 _ θ∈ _ _2, running linear regression on A~(s,a)∼v⊤ϕ~(s,a)+ϵCFA A(s,a) v φ(s,a)+ _ CFA will lead to |Lk(vk)~−Lk(vk∗)~|≲ρ2⋅ϵCFANlog(ℱ,ε1)⋅(Πθ,ε2)δ+Bbias2N2log(ℱ,ε1)⋅(Πθ,ε2)δ. | L_k(v_k)- L_k(v_k^*) | ρ^2 d· _ CFAN N(F, _1)·N( _θ, _2)δ+ B_ bias^2 dN^2 N(F, _1)·N( _θ, _2)δ. Now we need to bound the approximation error. Since ‖f−f~‖∞≤ε1\|f- f\|_∞≤ _1 and ‖θ−θ~‖≤ε2\|θ- θ\|≤ _2, we have ‖A−A~‖∞≤2ε1,‖ϕ−ϕ~‖∞,∗≤βε2,\|A- A\|_∞≤ 2 _1, \|φ- φ\|_∞,*≤β _2, which is due to the smoothness of the policy class (Assumption 3). Therefore, for any v such that ‖v‖≤BL\|v\|≤ B_L, we have |Lk(v)−Lk(v)~| |L_k(v)- L_k(v) | =|dD[(Ak−v⊤ϕk)2−(A~k−v⊤ϕk~)2]| = |E_d^D [(A_k-v _k)^2-( A_k-v _k)^2 ] | =|dD[(Ak+A~k−v⊤(ϕk+ϕk~))(Ak−A~k−v⊤(ϕk−ϕ~k))]| = |E_d^D [ (A_k+ A_k-v ( _k+ _k) ) (A_k- A_k-v ( _k- φ_k) ) ] | ≤(‖Ak+A~k‖∞+‖v‖‖ϕk+ϕ~k‖∗)⋅|dD[Ak−A~k−v⊤(ϕk−ϕ~k)]| ≤ (\|A_k+ A_k\|_∞+\|v\|\| _k+ φ_k\|_* )· |E_d^D [A_k- A_k-v ( _k- φ_k) ] | ≤(2Vmax+Vmax⋅2G)|dD[Ak−A~k]−v⊤dD[ϕk−ϕk~]| ≤(2V_ max+V_ max· 2G) |E_d^D[A_k- A_k]-v E_d^D[ _k- _k] | ≤2Vmax(G+1)|‖Ak−A~k‖∞+‖v‖⋅‖ϕk−ϕk~‖∞,∗| ≤ 2V_ max(G+1) |\|A_k- A_k\|_∞+\|v\|·\| _k- _k\|_∞,* | ≤2Vmax(G+1)(2ε1+BLβε2), ≤ 2V_ max(G+1)(2 _1+B_Lβ _2), where we use the Lipschitzness of the policy class that ‖ϕ‖∗≤G\|φ\|_*≤ G (Assumption 3) and Hölder’s inequality. By setting ε1=(Vmax/N) _1=O(V_ max/N) and ε2=(1/N) _2=O(1/N) (where the constants depend on Lipschitzness, smoothness, etc.), we will lead to the approximation error also be (1/N)O(1/N). Therefore, by combining the approximation error and the optimization error in the covering, we can also get the bound of estimation error as ϵstat≲ρ2ϵCFANlog(ℱ,Vmax/N)(Πθ,1/N)δ. _ stat ρ^2 d _ CFAN N(F,V_ max/N)N( _θ,1/N)δ. ∎ As a consequence of Lemma 14, we can set Comp(ℱ,Πθ,δ)=log(ℱ,Vmax/N)(Πθ,1/N)δ Comp(F, _θ,δ)= N(F,V_ max/N)N( _θ,1/N)δ (16) as the corresponding complexity measure. Now we come to prove Theorem 4, which is a natural result combining the regret decomposition lemma with least-square update (Lemma 11) and the estimation error bound (Lemma 14). Proof of Theorem 4. By Lemma 11, we have the following regret bound: RegKK≤BL2βDKL(πcp∥π1)K+(ϵCFA+ϵstat). Reg_KK≤ B_L 2β D_ KL( _ cp\| _1)K+ C ( _ CFA+ _ stat ). Then, by Lemma 14, we can substitute the upper bound of ϵstat _ stat in the regret bound, yielding RegKK≲BLβDKL(πcp∥π1)K+ϵCFA+ρ2ϵCFAComp(ℱ,Πθ)⋅log(1/δ)N, Reg_KK B_L β D_ KL( _ cp\| _1)K+ C _ CFA+ Cρ^2 d _ CFA Comp(F, _θ)· (1/δ)N, where the complexity measure Comp(ℱ,Πθ,δ)=log((ℱ,Vmax/N)(Πθ,1/N)/δ) Comp(F, _θ,δ)= (N(F,V_ max/N)N( _θ,1/N)/δ). Recall the definition of ρ (as bounded statistical leverage) in Assumption 6. We have set ρ as ‖ΣD−1/2ϕk‖≤Gλmin:=ρ, \| _D^-1/2 _k\| d≤ G d _ min:=ρ, since ‖ϕk‖≤G\| _k\|≤ G by Lipschitzness assumption (Assumption 3) and λmin _ min is the smallest eigenvalue of ΣD _D such that ΣD−1/2 _D^-1/2 rescales the feature ϕk _k. Therefore, we have RegKK≲BLβDKL(πcp∥π1)K+ϵCFA+GϵCFA⋅Comp(ℱ,Πθ,δ)Nλmin. Reg_KK B_L β D_ KL( _ cp\| _1)K+ C _ CFA+G C _ CFA· Comp(F, _θ,δ)N _ min. ∎ D.5 Analysis of the SGD-based Algorithm Another way to solve for the update vkv_k at round k actually utilizes more straightforward stochastic gradient descent (SGD), which treats LkL_k as the objective function and run SGD on the offline dataset with totally N inner updates (N is the sample size). This is because each sample forms an unbiased estimate of the desired quantity. Finally, this procedure outputs the estimator vk=1N∑i=1Nvk(i)v_k= 1N _i=1^Nv_k^(i) as the average-iterate result. The overall algorithm is summarized in Algorithm 3. Algorithm 3 SGD-based Least Square Policy Update (SGD-LSPU) 1: Initialize θ0=0 _0=0. 2: for k=1,2,…,Kk=1,2,…,K do 3: Compute the pessimistic value function fkf_k using an oracle. 4: Initialize v(0)=0v^(0)=0. 5: for i=1,2,…,Ni=1,2,…,N do 6: Using offline data (s(i),a(i))(s^(i),a^(i)), compute Ak(i)=fk(s(i),a(i))−fk(s(i),πk),ϕk(i)=∇θlogπk(a(i)∣s(i)).A_k^(i)=f_k(s^(i),a^(i))-f_k(s^(i), _k), _k^(i)= _θ _k(a^(i) s^(i)). 7: Update the inner iterate: v(i+1)=Proj[v(i)−2α((v(i)⊤ϕk(i)−Ak(i))ϕk(i))],=v:‖v‖2≤BL.v^(i+1)= Proj_V [v^(i)-2α ((v^(i) _k^(i)-A_k^(i)) _k^(i) ) ], =\v:\|v\|_2≤ B_L\. 8: end for 9: Set vk=1N∑i=1Nv(i)v_k= 1N _i=1^Nv^(i). 10: Update the policy parameter via θk+1=θk+ηvk _k+1= _k+η v_k. 11: end for 12: Output: uniform mixture of π1,…,πK _1,…, _K, i.e., π^=Unif[π1:K] π=Unif[ _1:K] The following corollary shows that Algorithm 3 achieves a sample complexity of (1/N1/4)O(1/N^1/4) in expectation. Theorem 15 (Regret Bound of Algorithm 3). Under Assumptions 2, 1, 3, and 4, the SGD-based offline NPG algorithm (Algorithm 3) achieves the following sample complexity. With step sizes η=2DKL(πcp∥π1)/(βKBL2)η= 2D_ KL( _ cp\| _1)/(β KB_L^2) and α=M/(2G(GVmax+BL)N)α=M/(2G(GV_ max+B_L) N), let π π denote the uniform mixture of πθ1,…,πθK _ _1,…, _ _K. Then we have [RegKK]≲BL2βDKL(πcp∥π1)K+GVmax(GVmax+BL)N+CϵCFA.E [ Reg_KK ] B_L 2β D_ KL( _ cp\| _1)K+ CGV_ max(GV_ max+B_L) N+ C _ CFA. Proof. Note that the update vector of v in Step 7 of Algorithm 3 provides an unbiased estimate of the true gradient of the loss function Lk(v)L_k(v): 2(s,a)∼dD[(v⊤∇θlogπk(a∣s)−Ak(s,a))∇θlogπk(a∣s)]=∇vLk(v).2E_(s,a) d^D [ (v _θ _k(a s)-A_k(s,a) ) _θ _k(a s) ]= _vL_k(v). By Assumption 3, we have ∥∇θlogπk(a∣s)∥∗≤G\| _θ _k(a s)\|_*≤ G, and since Ak(s,a)∈[−Vmax,Vmax]A_k(s,a)∈[-V_ max,V_ max] and ‖vk‖≤BL\|v_k\|≤ B_L, the stochastic gradient is uniformly bounded by ρ:=2G(GVmax+BL)ρ:=2G(GV_ max+B_L). Applying Lemma 26, we thus obtain [ϵstat]≤2GVmax(GVmax+BL)N,E[ _ stat]≤ 2GV_ max(GV_ max+B_L) N, where we use vk=1N∑i=1Nv(i)v_k= 1N _i=1^Nv^(i). Substituting this bound into Lemma 11 finishes the proof. ∎ Appendix E Omitted Details for Section 5.2 Using the generic regret decomposition lemma (Lemma 3), we can bound the regret term as (by taking BL=VmaxB_L=V_ max): RegKK=Vmax2βDKL(πcp∥π1)K+ϵ~CFA+ϵ~stat, Reg_KK=V_ max 2β D_ KL( _ cp\| _1)K+ ε_ CFA+ ε_ stat, (17) where ϵ~CFA ε_ CFA and ϵ~stat ε_ stat are similarly the approximation error and the estimation error. Recall: ℓk(v~k∗)=minv:‖v‖≤Vmaxℓk(v)≤ϵ~CFA,ℓk(vk)−ℓk(v~k∗)≤ϵ~stat,∀k∈[K]. _k( v_k^*)= _v:\|v\|≤ V_ max _k(v)≤ ε_ CFA, _k(v_k)- _k( v_k^*)≤ ε_ stat, ∀ k∈[K]. Since ϵ~CFA ε_ CFA is given in Assumption 5, our goal is to give a non-asymptotic control of ϵ~stat ε_ stat. E.1 Analysis of the SGD-based Algorithm We first consider the approach that is based on stochastic gradient descent, which leads to a regret guarantee in expectation. Recall that the robust loss at each round is given by ℓk(v)=maxw∈|(s,a)∼dD[w(s,a)(Ak(s,a)−v⊤ϕk(s,a))]|. _k(v)= _w |E_(s,a) d^D [w(s,a)(A_k(s,a)-v _k(s,a)) ] |. By Danskin’s theorem (Lemma 29), the robust loss ℓk(v) _k(v) is convex in v, and its gradient is given by ∇vℓk(v)=−^⋅(s,a)∼dD[w∗(s,a)ϕ(s,a)], _v _k(v)=- s·E_(s,a) d^D [w^*(s,a)φ(s,a) ], where ^∈±1 s∈\± 1\ denotes the optimal sign achieving the outer absolute value, and the optimal weight w∗∈argmaxw∈|ℓk(v,w)|w^*∈ _w | _k(v,w)|. We first estimate (s^,w∗)( s,w^*) using the offline dataset D (via a suitable DRO oracle, which depends on the specific realization of W), and then run projected SGD for N iterations to minimize ℓk(v) _k(v). The procedure is summarized in Algorithm 4; the proof of which is omitted for the sake of simplicity (similar to the proof of Theorem 15). Algorithm 4 SGD-based Distributionally Robust Policy Update (SGD-DRPU) Input: horizon K, inner iterations N, step sizes (η,α)(η,α) Initialize policy π1=πθ1 _1= _ _1 as uniform over A for k=1,2,…,Kk=1,2,…,K do Critic: compute fkf_k using the pessimistic oracle Initialize v(0)=0v^(0)=0 for i=1,2,…,Ni=1,2,…,N do Sample one data point (s(i),a(i))(s^(i),a^(i)) from D Obtain (s^,w∗)( s,w^*) with some DRO oracle Run projected SGD: v(i+1)=Proj‖v‖≤Vmax(v(i)−αg^(i))v^(i+1)=Proj_\|v\|≤ V_ max (v^(i)-α g^(i) ), where g^(i)=−s^kwk∗(s(i),a(i))ϕk(s(i),a(i)) g^(i)=- s_kw_k^*(s^(i),a^(i)) _k(s^(i),a^(i)) end for Actor: update policy by θk+1=θk+ηvk _k+1= _k+η v_k, where vk=1N∑i=1Nv(i)v_k= 1N _i=1^Nv^(i) end for Output: uniform mixture of π1,…,πK _1,…, _K, i.e., π^=Unif[π1:K] π=Unif[ _1:K] Theorem 16 (Regret Bound of Algorithm 4). Under Assumptions 1, 2, 3 and 5, for realizable weight class W, by tuning step sizes η=2DKL(πcp∥π1)/(βKVmax2)η= 2D_ KL( _cp\| _1)/(β KV_ max^2) and α=Vmax/(GN)α=V_ /( CG N), Algorithm 4 achieves the regret bound [RegKK]≲Vmax2βDKL(πcp∥π1)K+ϵ~CFA+GVmaxNE [ Reg_KK ] V_ max 2β D_ KL( _cp\| _1)K+ ε_ CFA+ CGV_ N Note that unlike Algorithm 3, Algorithm 4 relies on an efficient DRO oracle. It actually depends on the specific realization of the weight class (a.k.a. uncertainty set) W. For instance, for the L∞L_∞ weight class ∞W_∞ defined in Eq. (9), we can adopt the following strategy to compute the optimal weight wk∗w_k^* (and its sign s s): first calculate each sample’s residuals r(i)=A(i)−v⊤ϕ(i)r^(i)=A^(i)-v φ^(i), and then sort the residuals in reversing order and assign the weight wk∗w_k^* uniformly on the top C/NC/N samples, and the sign s s can be accordingly got calculate the optimal weight’s average residual. With other realization of the W like the KL-ball and Wasserstein ball (or in general, a f-divergence ball), there accordingly exists the efficient oracle to solve for that optimization problem in DRO literature [Kuhn et al., 2025]. E.2 Proof of Theorem 5 We first show that under ∞W_∞ class, the robust optimization problem can essentially be transformed as an CVaR problem, which would validate that DRPU under ∞W_∞ in Eq. (9) by setting α=1/α=1/ C. Proposition 17. Let Z be an integrable random variable and α∈(0,1]α∈(0,1] be a tail probability level. Then the following equivalence holds: supw:[w]=10≤w≤1/α[wZ]=infτ∈ℝτ+1α[(Z−τ)+]=:CVaR1−α(Z). _ subarraycw:E[w]=1\\ 0≤ w≤ 1/α subarrayE[wZ]= _τ \τ+ 1αE[(Z-τ)_+] \=: CVaR_1-α(Z). Proof. For any feasible w and τ∈ℝτ , we have wZ=wτ+w(Z−τ)≤wτ+1α(Z−τ)+,wZ=wτ+w(Z-τ)≤ wτ+ 1α(Z-τ)_+, which is due to 0≤w≤1/α0≤ w≤ 1/α. Taking expectations and using [w]=1E[w]=1, [wZ]≤τ+1α[(Z−τ)+].E[wZ]≤τ+ 1αE[(Z-τ)_+]. Since this holds for every feasible w and every τ, supw:[w]=10≤w≤1/α[wZ]≤infτ∈ℝτ+1α[(Z−τ)+]. _ subarraycw:E[w]=1\\ 0≤ w≤ 1/α subarrayE[wZ]≤ _τ \τ+ 1αE[(Z-τ)_+] \. Now we give a construction such that the equality holds. Take τ∗τ^* to be the (1−α)(1-α) quantile of Z such that Pr(Z>τ∗)≤α≤Pr(Z≥τ∗) (Z>τ^*)≤α≤ (Z≥τ^*), and the corresponding w∗w^* is chosen as w∗=1αZ>τ∗+λαZ=τ∗,w^*= 1α1\Z>τ^*\+ λα1\Z=τ^*\, with λ∈[0,1]λ∈[0,1] chosen so that [w∗]=1E[w^*]=1. That is, if we let q1=Pr(Z=τ∗)q_1= (Z=τ^*), q2=Pr(Z>τ∗)q_2= (Z>τ^*), then q2≤α≤q1+q2q_2≤α≤ q_1+q_2. Since q1,q2∈[0,1]q_1,q_2∈[0,1], there must exist some λ∈[0,1]λ∈[0,1] such that λq1+q2=αλ q_1+q_2=α. Using this construction, [w∗Z]=1α[Z⋅Z>τ∗]+λα[Z⋅Z=τ∗].E[w^*Z]= 1αE[Z·1\Z>τ^*\]+ λαE[Z·1\Z=τ^*\]. For the first term, we have Z⋅Z>τ∗=(Z−τ∗)Z>τ∗+τ∗Z>τ∗Z·1\Z>τ^*\=(Z-τ^*)1\Z>τ^*\+τ^*1\Z>τ^*\. Taking expectation, [Z⋅Z>τ∗]=[(Z−τ∗)+]+τ∗Pr(Z>τ∗)=[(Z−τ∗)+]+τ∗q2.E[Z·1\Z>τ^*\]=E[(Z-τ^*)_+]+τ^* (Z>τ^*)=E[(Z-τ^*)_+]+τ^*q_2. For the second term, it’s easy to see that [Z⋅Z=τ∗]=τ∗Pr(Z=τ∗)=τ∗q1E[Z·1\Z=τ^*\]=τ^* (Z=τ^*)=τ^*q_1. Combining the two terms, [w∗Z]=1α(τ∗q2+[(Z−τ∗)+])+λατ∗q1=1α[(Z−τ∗)+]+τ∗α(λq1+q2)=1α[(Z−τ∗)+]+τ∗.E[w^*Z]= 1α (τ^*q_2+E[(Z-τ^*)_+] )+ λατ^*q_1= 1αE[(Z-τ^*)_+]+ τ^*α(λ q_1+q_2)= 1αE[(Z-τ^*)_+]+τ^*. Therefore, the proposition holds with exact equality. ∎ We now proceed to prove Theorem 5. Lemma 18 (DRPU Estimation Error Bound). Let vkv_k denote the minimizer of the empirical robust loss ℓ^k _k in Eq. (10). Under Assumptions 3 and 5, the estimation error term ϵ~stat ε_ stat satisfies, with probability at least 1−δ1-δ, ϵ~stat≲(Vmax(G+1))(⋅Comp(ℱ,Πθ,δ)N+⋅Comp(ℱ,Πθ,δ)N3/4+N), ε_ stat (V_ max(G+1)) ( C· Comp(F, _θ,δ)N+ C· Comp(F, _θ,δ)N^3/4+N ), where Comp(ℱ,Πθ)=log((ℱ,Vmax/N)⋅(Πθ,1/N)/δ) Comp(F, _θ)= (N(F,V_ max/N)·N( _θ,1/N)/δ) is the chosen complexity measure. Recall that v~k∗ v_k^* is the minimizer of the population loss ℓk _k and vkv_k is the minimizer of the empirical loss ℓ^k _k. The estimation error can be decomposed as ℓk(vk)−ℓk(v~k∗) _k(v_k)- _k( v_k^*) =(ℓk(vk)−ℓ^k(vk))+(ℓ^k(vk)−ℓ^k(v~k∗))+(ℓ^k(v~k∗)−ℓk(v~k∗)) = ( _k(v_k)- _k(v_k) )+ ( _k(v_k)- _k( v_k^*) )+ ( _k( v_k^*)- _k( v_k^*) ) ≤2supv:‖v‖≤Vmax|ℓk(v)−ℓ^k(v)|, ≤ 2 _v:\|v\|≤ V_ max | _k(v)- _k(v) |, (18) since vk=argminv:‖v‖≤Vmaxℓ^k(v)v_k= _v:\|v\|≤ V_ max _k(v) so the second term vanishes. This means we only need to bound the generalization gap uniform on v such that ‖v‖≤Vmax\|v\|≤ V_ max. We will first analyze this for a fixed v and then give a uniform bound over v such that ‖v‖≤Vmax\|v\|≤ V_ max. The CVaR expression for ℓk(v) _k(v) is given by ℓk(v)=maxminτ∈ℝτ+⋅dD[(ϵv−τ)+],minτ∈ℝτ+⋅dD[(−ϵv−τ)+]:=maxℓk+(v),ℓk−(v). _k(v)= \ _τ \τ+ C·E_d^D[( _v-τ)_+] \, _τ \τ+ C·E_d^D[(- _v-τ)_+] \ \:= \ _k^+(v), _k^-(v) \. Similarly we can also write ℓ^k(v)=maxℓ^k+(v),ℓ^k−(v) _k(v)= \ _k^+(v), _k^-(v)\. Therefore, |ℓk(v)−ℓ^k(v)|≤max|ℓk+(v)−ℓ^k+(v)|,|ℓk−(v)−ℓ^k−(v)|. | _k(v)- _k(v) |≤ \ | _k^+(v)- _k^+(v) |, | _k^-(v)- _k^-(v) | \. (19) By symmetry, it remains to give a uniform convergence bound for either |ℓk+−ℓ^k+|| _k^+- _k^+| or |ℓk−ℓ^k−|| _k^-- _k^-|. Without loss of generality, we only bound the generalization gap of ℓ0(v):=ℓk+(v)=minττ+⋅dD[(ϵv−τ)+] _0(v):= _k^+(v)= _τ \τ+ C·E_d^D[( _v-τ)_+] \. We first give a quantile characterization of this CVaR loss ℓ0(v) _0(v) and its empirical version ℓ^0(v) _0(v), see the following lemma. Lemma 19 (Quantile Characterization of Tail Probability). Fix any v such that ‖v‖≤Vmax\|v\|≤ V_ max. Any population minimizer τ∗(v)τ^*(v) satisfies Pr(ϵv>τ∗(v))≤1,τ∗(v)∈argminτ∈[−B,B]τ+⋅[(ϵv−τ)+]. ( _v>τ^*(v))≤ 1 C, τ^*(v)∈ τ∈[-B,B] \τ+ C·E[( _v-τ)_+] \. Any empirical minimizer τ^(v) τ(v) can be chosen so that 1N∑i=1Nϵv(i)>τ^(v)≤1,τ^(v)∈argminτ∈[−B,B]τ+N∑i=1N(ϵv(i)−τ)+, 1N _i=1^N1\ _v^(i)> τ(v)\≤ 1 C, τ(v)∈ τ∈[-B,B] \τ+ CN _i=1^N ( _v^(i)-τ )_+ \, where ϵv(i)=Ak(s(i),a(i))−v⊤ϕk(s(i),a(i)) _v^(i)=A_k(s^(i),a^(i))-v _k(s^(i),a^(i)) is the i-th sample formed by the offline dataset. Proof. For a fixed z∈ℝz , gz(τ)=(z−τ)+g_z(τ)=(z-τ)_+ as a convex function of τ, its sub-differential is given by ∂τgz(τ)=−1,z>τ,[−1,0],z=τ,0,z<τ. _τg_z(τ)= cases\-1\,&z>τ,\\ [-1,0],&z=τ,\\ \0\,&z<τ. cases We first analyze the population case. Let Fv(t)=Pr(ϵv≤t)F_v(t)= ( _v≤ t) be the CDF for the random variable ϵv _v (where the randomness comes from (s,a)(s,a) pair). Using linearity of expectation, we have ∂τ+⋅[(ϵv−τ)+]=1+⋅[∂τ(ϵv−τ)+]=[1−⋅Pr(ϵv≥τ(v)),1−⋅Pr(ϵv>τ(v))]. _τ \τ+ C·E[( _v-τ)_+] \=\1\+ C·E[ _τ( _v-τ)_+]= [1- C· ( _v≥τ(v)),1- C· ( _v>τ(v)) ]. Since τ∗τ^* is the population minimizer, by optimality condition, its sub-differential should contain 0. This means 1−⋅Pr(ϵv≥τ∗(v))≤0≤1−Pr(ϵv>τ∗(v)),1- C· ( _v≥τ^*(v))≤ 0≤ 1- C ( _v>τ^*(v)), which implies that Pr(ϵv>τ∗(v))≤1/ ( _v>τ^*(v))≤ 1/ C. For empirical case, similarly we obtain that 1−N∑i=1Nϵv(i)>τ^(v)≤0≤1−N∑i=1Nϵv(i)≥τ^(v),1- CN _i=1^N1\ _v^(i)> τ(v)\≤ 0≤ 1- CN _i=1^N1\ _v^(i)≥ τ(v)\, which implies the second argument in Lemma 19 ∎ Lemma 19 actually implies an explicit formula for the (empirical) CVaR loss ℓ^0(v) _0(v). Let the descending order statistics be ϵv↓,(1)≥ϵv↓,(2)≥⋯≥ϵv↓,(N). _v ,(1)≥ _v ,(2)≥·s≥ _v ,(N). Fix k∈0,1,…,Nk∈\0,1,…,N\ and consider τ inside the open interval (ϵv↓,(k+1),ϵv↓,(k))( _v ,(k+1), _v ,(k)) (with the conventions ϵv↓,(0)=+∞ _v ,(0)=+∞, ϵv↓,(N+1)=−∞ _v ,(N+1)=-∞). Then #i:ϵv(i)>τ=k\#\i: _v^(i)>τ\=k. This means the function τ+⋅[(ϵv−τ)+]τ+ C·E[( _v-τ)_+] is affine with slope 1−/N1- C/N. Its minimum occurs where the slope crosses zero, i.e., at the “knot” between the last interval with positive slope and the first with non-positive slope. That is, k∗=⌈N⌉,τ^(v)∈[ϵv↓,(k∗),ϵv↓,(k∗+1)].k^*= N C , τ(v)∈ [ _v ,(k^*), _v ,(k^*+1) ]. This means with τ(v)=τ^(v)τ(v)= τ(v), there exist at most ⌈N/⌉ N/ C “active” points that would not be obviated by (⋅−τ^)+(·- τ)_+ operation. At the same time, the empirical CVaR loss can be written as ℓ^0(v)=minτ∈[−B,B]τ+N∑i=1N(ϵv(i)−τ)+=N∑j=1k∗ϵv↓,(j). _0(v)= _τ∈[-B,B] \τ+ CN _i=1^N ( _v^(i)-τ )_+ \= CN _j=1^k^* _v ,(j). Now we can proceed the proof of Lemma 18, which uses standard technique in statistical learning theory to give uniform convergence via empirical Rademacher complexity (see Bartlett and Mendelson [2002] for the definition). The key step is to handle the Rademacher term by the tail-peeling that reflects the “about 1/1/ C” active fraction in CVaR (as shown in Lemma 19), giving the C rather than C dependence.101010If we directly bound the |ℓk(v)−ℓ^k(v)|| _k(v)- _k(v)| with their original definition of maxw∈ _w , this would lead to a Rademacher complexity term of the weight class W, which is in general uncontrollable. But using the fact that w has controlled variance, dD[w2]≤⋅dD[w]=E_d^D[w^2]≤ C·E_d^D[w]= C, we can use Bernstein-type concentration to give the bound which will lead to a C dependence. So what we did in Lemma 19 is essentially to control the variance of this CVaR loss to use the Bernstein-type concentration (Lemma 31). Proof of Lemma 18. Let gv,τ(s,a):=(ϵv(s,a)−τ)+g_v,τ(s,a):= C( _v(s,a)-τ)_+. For any fixed v:‖v‖≤Vmaxv:\|v\|≤ V_ max, recall the definition of τ∗(v)τ^*(v) and τ^(v) τ(v) in Lemma 19, we have that ℓ0(v)=τ∗(v)+[gv,τ∗(v)],ℓ^0(v)=τ^(v)+^[gv,τ^(v)]. _0(v)=τ^*(v)+E[g_v,τ^*(v)], _0(v)= τ(v)+ E[g_v, τ(v)]. Therefore, by that τ∗(v)τ^*(v) is the population minimizer, we have ℓ0(v)−ℓ^0(v) _0(v)- _0(v) =τ∗(v)+[gv,τ∗(v)]−τ^(v)−^[gv,τ^(v)] =τ^*(v)+E[g_v,τ^*(v)]- τ(v)- E[g_v, τ(v)] ≤τ^(v)+[gv,τ^(v)]−τ^(v)−^[gv,τ^(v)] ≤ τ(v)+E[g_v, τ(v)]- τ(v)- E[g_v, τ(v)] ≤(−^)[gv,τ^(v)]. ≤(E- E)[g_v, τ(v)]. Similarly we can obtain ℓ^0(v)−ℓ0(v)≤(^−)[gv,τ∗(v)] _0(v)- _0(v)≤( E-E)[g_v,τ^*(v)] by that τ^(v) τ(v) is the empirical minimizer. This means that the uniform generalization gap can be bounded by supv:‖v‖≤Vmax|ℓ0(v)−ℓ^0(v)|≤supv:‖v‖≤Vmaxmaxτ∈τ∗(v),τ^(v)|(−^)[gv,τ]|:=supg∈|(−^)[g]| _v:\|v\|≤ V_ max | _0(v)- _0(v) |≤ _v:\|v\|≤ V_ max _τ∈\τ^*(v), τ(v)\ |(E- E)[g_v,τ] |:= _g |(E- E)[g] | where we use a function class G that expresses all possible functions gv,τg_v,τ we needed. In particular, since |ϵv(s,a)|=|Ak(s,a)−v⊤ϕk(s,a)|≤Vmax(G+1)| _v(s,a)|=|A_k(s,a)-v _k(s,a)|≤ V_ max(G+1), denote B=Vmax(G+1)B=V_ max(G+1) as the uniform upper bound of ϵv _v, we can constrain all possible τ∈[−B,B]τ∈[-B,B] (outside this interval the hinge is 0 or can be pulled back). Hence the function class G is given by =gv,τ(s,a)=(ϵv(s,a)−τ):‖v‖≤Vmax,τ∈τ∗(v),τ^(v)⊆[−B,B].G= \g_v,τ(s,a)= C( _v(s,a)-τ):\|v\|≤ V_ max,τ∈\τ^*(v), τ(v)\ [-B,B] \. For any τ∈[−B,B]τ∈[-B,B] and v:‖v‖≤Vmaxv:\|v\|≤ V_ max, we can express gv,τ(s,a)g_v,τ(s,a) as gv,τ(s,a)=⋅(ϵv(s,a)−τ)+=⋅|ϵv(s,a)−τ|⋅ϵv(s,a)>τ.g_v,τ(s,a)= C·( _v(s,a)-τ)_+= C·| _v(s,a)-τ|·1\ _v(s,a)>τ\. A direct consequence is that 0≤gv,τ(s,a)≤2BC0≤ g_v,τ(s,a)≤ 2BC for all (s,a)(s,a). And we can actually control its variance by Var[gv,τ(s,a)]≤[gv,τ(s,a)2]≤2⋅4B2⋅[ϵv(s,a)>τ]=4B22⋅Pr(ϵv>τ). Var[g_v,τ(s,a)] [g_v,τ(s,a)^2]≤ C^2· 4B^2·E[1\ _v(s,a)>τ\]=4B^2 C^2· ( _v>τ). By Lemma 19, if τ=τ∗(v)τ=τ^*(v) for some v, then this tail probability is actually controlled by 1/1/ C. This means the all gv,τ∗(v)v\g_v,τ^*(v)\_v fall in this low-variance regime: Var[gv,τ∗(v)(s,a)]≤4B22⋅Pr(ϵv(s,a)>τ∗(v))≤4B22⋅1=4B2. Var[g_v,τ^*(v)(s,a)]≤ 4B^2 C^2· ( _v(s,a)>τ^*(v))≤ 4B^2 C^2· 1 C=4B^2 C. For empirical version τ=τ^(v)τ= τ(v), we need to invoke DKW inequality (Lemma 30) to get a high-probability argument: with probability at least 1−δ/21-δ/2, Var[gv,τ^(v)(s,a)] Var[g_v, τ(v)(s,a)] ≤4B22⋅Pr(ϵv(s,a)>τ^(v)) ≤ 4B^2 C^2· ( _v(s,a)> τ(v)) ≤4B22⋅(1N∑i=1Nϵv(i)>τ^+12Nlog4δ) ≤ 4B^2 C^2· ( 1N _i=1^N1\ _v^(i)> τ\+ 12N 4δ ) ≤4B2+4B2212Nlog4δ. ≤ 4B^2 C+4B^2 C^2 12N 4δ. where the first inequality is due to the DKW inequality that concentrates an empirical CDF to a population CDF, and the third inequality is due to Lemma 19. Therefore for all gv,τ∈g_v,τ , we can control its range |gv,τ|≤2B|g_v,τ|≤ 2B C and its variance Var[gv,τ]≤4B2+η Var[g_v,τ]≤ 4B^2 C+η (where η is the error introduced by the DKW inequality). This enables us to leverage Bernstein-type concentration to (−^)g(E- E)g. Notice that this is actually a supremum of some empirical process, so Bousquet’s Bennett inequality (Lemma 31) applies here: with probability at least 1−δ1-δ, supgv,τ∈|(−^)gv,τ| _g_v,τ |(E- E)g_v,τ | ≤[supgv,τ∈|(−^)gv,τ|]+2Var[gv,τ]Nlog2δ+2supgv,τ|gv,τ|3Nlog2δ [ _g_v,τ |(E- E)g_v,τ | ]+ 2 Var[g_v,τ]N 2δ+ 2 _g_v,τ|g_v,τ|3N 2δ ≤[supgv,τ∈|(−^)gv,τ|]+2B2Nlog2δ+22BN3/4log2δ+4B3Nlog2δ, [ _g_v,τ |(E- E)g_v,τ | ]+2B 2 CN 2δ+ 2 2B CN^3/4 2δ+ 4B C3N 2δ, where the second inequality is just replacing the range and variance of gv,τ∈g_v,τ . By a standard symmetrization technique, we can relate the first term (expected uniform convergence) with the Rademacher complexity of the function class G, denoted as ℜN() R_N(G): (s,a)[supgv,τ∈|(− _(s,a) [ _g_v,τ |(E- ^)gv,τ|]=(si,ai),(si′,ai′)[supgv,τ∈∪−1N∑i=1N(gv,τ(si,ai)−gv,τ(si′,ai′))] E)g_v,τ | ]=E_\(s_i,a_i)\,\(s_i ,a_i )\ [ _g_v,τ ∪-G 1N _i=1^N (g_v,τ(s_i,a_i)-g_v,τ(s_i ,a_i ) ) ] =(si,ai),(si′,ai′),σi[supgv,τ∈∪−1N∑i=1Nσi(gv,τ(si,ai)−gv,τ(si′,ai′))] =E_\(s_i,a_i)\,\(s_i ,a_i )\,\ _i\ [ _g_v,τ ∪-G 1N _i=1^N _i (g_v,τ(s_i,a_i)-g_v,τ(s_i ,a_i ) ) ] ≤(si,ai),(si′,ai′),σi[supg1N∑i=1Nσig(si,ai)+supg1N∑i=1N(−σi)g(si,ai)] _\(s_i,a_i)\,\(s_i ,a_i )\,\ _i\ [ _g 1N _i=1^N _ig(s_i,a_i)+ _g 1N _i=1^N(- _i)g(s_i,a_i) ] =2⋅(si,ai),σi[supgv,τ∈∪−1N∑i=1Nσigv,τ(si,ai)] =2·E_\(s_i,a_i)\,\ _i\ [ _g_v,τ ∪-G 1N _i=1^N _ig_v,τ(s_i,a_i) ] =2ℜN(∪−)≤4ℜN(), =2 R_N(G∪-G)≤ 4 R_N(G), where σi∼±1\ _i\ \± 1\ is the Rademacher random variable. So it remains to control the Rademacher complexity ℜN() R_N(G) of the function class G. Instead, we bound the empirical Rademacher complexity ℜ^N() R_N(G) based on N i.i.d. samples (si,ai)(s_i,a_i) due to that ℜN()=[ℜ^N()] R_N(G)=E[ R_N(G)]. A direct contraction would lead to a C dependency (since the Lipschitz constant of gv,τg_v,τ is of the order C). So we use a layer-peeling technique. For any m∈0,1,2,…m∈\0,1,2,…\, define mG_m as m=gv,τ∈:1N∑i=1Nϵv(i)>τ∈(2−(m+1),2−m].G_m= \g_v,τ : 1N _i=1^N1\ _v^(i)>τ\∈ ( 2^-(m+1) C, 2^-m C ] \. We claim that all =⋃m≥0mG= _m≥ 0G_m since the empirical tail-probability is ≤1/≤ 1/ C by Lemma 19. For any gv,τ∈mg_v,τ _m, such configuration indicates that 0≤gv,τ(si,ai)≤2B0≤ g_v,τ(s_i,a_i)≤ 2B C, and ∑i=1Ngv,τ(si,ai)2≤4B22∑i=1Nϵv(si,ai)>τ≤4B22⋅N⋅2−m=4B2CN⋅2−m. _i=1^Ng_v,τ(s_i,a_i)^2≤ 4B^2 C^2 _i=1^N1\ _v(s_i,a_i)>τ\≤ 4B^2 C^2· N· 2^-m C=4B^2CN· 2^-m. This gives a bound for the empirical Rademacher complexity ℜ^N(m) R_N(G_m): ℜ^N(m) R_N(G_m) =σi[supgv,τ∈m1N∑i=1Nσigv,τ(si,ai)]≤1N(σi[supgv,τ∈m(∑i=1Nσigv,τ(si,ai))2])1/2 =E_\ _i\ [ _g_v,τ _m 1N _i=1^N _ig_v,τ(s_i,a_i) ]≤ 1N (E_\ _i\ [ _g_v,τ _m ( _i=1^N _ig_v,τ(s_i,a_i) )^2 ] )^1/2 ≤1N(N⋅supgv,τ∈m∑i=1Ngv,τ(si,ai)2)1/2=1N(supgv,τ∈m∑i=1Ngv,τ(si,ai)2)1/2 ≤ 1N (N· _g_v,τ _m _i=1^Ng_v,τ(s_i,a_i)^2 )^1/2= 1 N ( _g_v,τ _m _i=1^Ng_v,τ(s_i,a_i)^2 )^1/2 ≤1N⋅4B2N⋅2−m=2BN⋅2−m, ≤ 1N· 4B^2 CN· 2^-m=2B CN· 2^-m, where the first inequality is by Jensen, the second inequality is by Cauchy-Schwarz and the property of Rademacher random variable that σi[∑i=1Nσi2]=NE_\ _i\[ _i=1^N _i^2]=N. Therefore, by =⋃m≥0mG= _m≥ 0G_m, we have ℜ^N()≤∑m=0∞ℜ^N(m)≤2BN⋅∑m=0∞2−m/2≤4BN. R_N(G)≤ _m=0^∞ R_N(G_m)≤ 2B CN· _m=0^∞2^-m/2≤ 4B CN. Hence the Rademacher complexity of G is also bounded by 4BC/N4B C/N. Combining, we get supv:‖v‖≤Vmax|ℓ0(v)−ℓ^0(v)|≲BN+BNlog1δ+BN3/4log1δ+BNlog1δ. _v:\|v\|≤ V_ max | _0(v)- _0(v) | B CN+B CN 1δ+ B CN^3/4 1δ+ B CN 1δ. Notice that ℓ0(v)=ℓk+(v)=minττ+[(ϵv−τ)+] _0(v)= _k^+(v)= _τ\τ+E[( _v-τ)_+]\. Similarly, we can reproduce the exact identical proof for ℓk−(v) _k^-(v) since |−ϵv|≤B|- _v|≤ B. Therefore, combine this with Eq. (E.2) (that connects the estimation error and the generalization gap) and Eq. (19) (that connects the ℓk _k gap with ℓk+ _k^+ and ℓk− _k^-), we get the following by B=Vmax(G+1)B=V_ max(G+1): |ℓk(vk)−ℓk(v~k∗)|≲Vmax(G+1)(Nlog1δ+N3/4+Nlog1δ).| _k(v_k)- _k( v_k^*)| V_ max(G+1) ( CN 1δ+ CN^3/4+N 1δ ). Combining the covering argument for ℱF and Πθ _θ, the final component of Comp(ℱ,Πθ,δ) Comp(F, _θ,δ) is determined, yielding the bound for ϵ~stat ε_ stat. This completes the proof of Lemma 18. ∎ Theorem 5 is hence a direct consequence of combining Eq. (17) and Lemma 18. We note a key difference from Theorem 4. In the well-specified setting, i.e., when ϵ~bias=0 ε_bias=0, the estimation error ϵ~stat ε_stat converges to zero asymptotically but does not vanish exactly, in contrast to the linear regression case. This behavior stems from the fact that the first-order loss considered here does not fully explore the parameter space; instead, DRPU effectively enforces a form of “mean matching” over a family of distributions. As a result, the associated concentration bound is derived under a weaker structural assumption on the compatible function space. E.3 Computation In Section 5.2 we mentioned that minimizing the loss ℓ^k(v) _k(v) can be viewed as a linear program (or more generally, a SOCP)111111The specific type of the program depends on the norm constraint of v:‖v‖≤Vmaxv:\|v\|≤ V_ max. That is, if it’s ∥⋅∥∞\|·\|_∞ or ∥⋅∥1\|·\|_1, then it’s a linear program (LP); if it’s ∥⋅∥2\|·\|_2, then it’s a second-order cone program (SOCP), which can be efficiently solved by any convex solver. Now we give the specific realization of this program. Recall the CVaR expression of ℓ^k _k is given by ℓ^k(v)=maxminτ∈ℝτ+N∑i=1N(ϵv(i)−τ)+,minτ∈ℝτ+N∑i=1N(−ϵv(i)−τ)+, _k(v)= \ _τ \τ+ CN _i=1^N ( _v^(i)-τ )_+ \, _τ \τ+ CN _i=1^N (- _v^(i)-τ )_+ \ \, where ϵv(i)=Ak(i)−v⊤∇logπk(a(i)|s(i)) _v^(i)=A_k^(i)-v ∇ _k(a^(i)|s^(i)). Since the outer max of the two CVaRs with an epigraph variable (similarly for the inner τ, we can write down the corresponding d-dimensional convex program of minv∈ℝ:‖v‖≤Vmaxℓ^k(v) _v d:\|v\|≤ V_ max _k(v): minv,z,τ+,τ−,c+(i)i=1N,c−(i)i=1N _ subarraycv,z, _+, _-,\\ \c_+^(i)\_i=1^N,\c_-^(i)\_i=1^N subarray z z s.t. z≥τ++N∑i=1Nc+(i), z≥ _++ CN _i=1^Nc_+^(i), c+(i)≥Ak(i)−v⊤ϕk(i)−τ+,c+(i)≥0,i=1,…,N, c_+^(i)≥ A_k^(i)-v _k^(i)- _+, c_+^(i)≥ 0, i=1,…,N, z≥τ−+N∑i=1Nc−(i), z≥ _-+ CN _i=1^Nc_-^(i), c−(i)≥−Ak(i)+v⊤ϕk(i)−τ−,c−(i)≥0,i=1,…,N, c_-^(i)≥-A_k^(i)+v _k^(i)- _-, c_-^(i)≥ 0, i=1,…,N, ‖v‖≤Vmax. \|v\|≤ V_ . E.4 Feature Coverage and Chi-Square Weight Class In this section, we discuss the feature coverage condition in Section 5.1 and clarify its relation to the chi-square weight class introduced in Section 5.2. Feature coverage condition. Recall that in the compatible case, the advantage function Ak(s,a)A_k(s,a) lies in the linear span of the policy-gradient features, which we denote by ϕk(s,a)=∇logπk(a∣s) _k(s,a)=∇ _k(a s). Let ΣDπ=dD[(∇logπ)(∇logπ)⊤] _D^π=E_d^D[(∇ π)(∇ π) ] denote the feature covariance matrix under the data distribution dDd^D (suppose it’s invertible), and let μcpπ=(s,a)∼dπcp[∇logπ(a∣s)] _ cp^π=E_(s,a) d _ cp[∇ π(a s)] denote the mean feature under dπcpd _ cp. Then the feature coverage condition feat C_ feat can be written as (μcpπk)⊤(ΣDπk)−1μcpπk≤feat,∀k∈[K].( _ cp _k) ( _D _k)^-1 _ cp _k≤ C_ feat, ∀ k∈[K]. Unlike density coverage, which controls distribution shift uniformly over all (s,a)(s,a) pairs, feature coverage only controls transfer on the restricted function class induced by the policy-gradient features. That is, feat C_ feat requires data only to cover a single direction μcpπk _ cp _k, which is the mean feature direction under dπcpd _ cp. Since the error of CFA is exactly a linear error in the feature class, the feature coverage is the known tightest coverage notion under linear function approximation[Jiang and Xie, 2025]. The next proposition shows that feature coverage is always implied by density coverage, and can therefore be viewed as a refined notion of coverage. Proposition 20 (Density Coverage Implies Feature Coverage). Assume Assumption 1 holds, namely ‖w∗‖∞≤\|w^*\|_∞≤ C for w∗=dπcp/dDw^*=d _ cp/d^D. Then for every k∈[K]k∈[K] and every f∈span(ϕk)f∈ span( _k), (dπcp[f])2≤dD[f2]. (E_d _ cp[f] )^2≤ C\,E_d^D[f^2]. Consequently, for invertible ΣDπk _D _k, this is equivalent to (μcpπk)⊤(ΣDπk)−1μcpπk≤( _ cp _k) ( _D _k)^-1 _ cp _k≤ C. In particular, the feature coverage constant always satisfies feat≤ C_ feat≤ C. Proof. Fix any k∈[K]k∈[K] and any f∈span(ϕk)f∈ span( _k). Since w∗=dπcp/dDw^*=d _ cp/d^D, we have dπcp[f]=dD[w∗f]E_d _ cp[f]=E_d^D[w^*f]. Therefore, (dπcp[f])2=(dD[w∗f])2≤dD[(w∗)2]dD[f2]≤dD[f2],∀f∈span(ϕk), (E_d _ cp[f] )^2= (E_d^D[w^*f] )^2 _d^D[(w^*)^2]E_d^D[f^2]≤ C\,E_d^D[f^2], ∀ f∈ span( _k), where the first inequality is by Cauchy-Schwarz, and the second inequality leverages the “low-variance” property of the importance weight. That is, for w∗w^* such that dD[w∗]=1E_d^D[w^*]=1 and ‖w∗‖∞≤\|w^*\|_∞≤ C, we have dD[(w∗)2]≤‖w∗‖∞dD[w∗]≤E_d^D[(w^*)^2]≤\|w^*\|_∞\,E_d^D[w^*]≤ C. Now write any f∈span(ϕk)f∈ span( _k) as fθ(s,a)=θ⊤ϕk(s,a)f_θ(s,a)=θ _k(s,a) for some θ∈ℝdθ ^d. Then dπcp[fθ]=θ⊤μcpπkE_d _ cp[f_θ]=θ _ cp _k and dD[fθ2]=θ⊤ΣDπkθE_d^D[f_θ^2]=θ _D _kθ. Hence, supθ≠0(θ⊤μcpπk)2θ⊤ΣDπkθ≤,∀k∈[K]. _θ≠ 0 (θ _ cp _k)^2θ _D _kθ≤ C, ∀ k∈[K]. Since ΣDπk _D _k is invertible, the left-hand side is the Rayleigh quotient supθ≠0(θ⊤μcpπk)2θ⊤ΣDπkθ=(μcpπk)⊤(ΣDπk)−1μcpπk, _θ≠ 0 (θ _ cp _k)^2θ _D _kθ=( _ cp _k) ( _D _k)^-1 _ cp _k, which implies (μcpπk)⊤(ΣDπk)−1μcpπk≤,∀k∈[K].( _ cp _k) ( _D _k)^-1 _ cp _k≤ C, ∀ k∈[K]. Taking the supremum over k∈[K]k∈[K] gives feat≤ C_ feat≤ C. ∎ Proposition 20 shows that feature coverage is never worse than density coverage. More importantly, it can be substantially smaller. The reason is that density coverage controls the worst-case reweighting error over the entire state-action space, whereas feature coverage only measures mismatch along the specific feature directions relevant to the actor update. Chi-square weight class. We now connect the above discussion to the chi-square weight class in Section 5.2. In the compatible linear case, one need not use the true density ratio for distribution transfer. Instead, it suffices to use a feature-based correction function that is exact on the linear residual class. Define wk∗(s,a):=(μcpπk)⊤(ΣDπk)−1ϕk(s,a),w_k^*(s,a):=( _ cp _k) ( _D _k)^-1 _k(s,a), (20) and consider the chi-square weight class χ2:=w:dD[w2]≤feat.W_χ^2:=\w:E_d^D[w^2]≤ C_ feat\. Proposition 21. Assume the compatible case, so that Ak(s,a)∈span(ϕk)A_k(s,a)∈ span( _k). Then the feature-based correction weight wk∗w_k^* defined above satisfies the following two properties: (i) (Distribution transfer) for any f∈span(ϕk)f∈ span( _k), dπcp[f]=dD[wk∗f]E_d _ cp[f]=E_d^D[w_k^*f]. (i) (Realizability) dD[(wk∗)2]=(μcpπk)⊤(ΣDπk)−1μcpπk≤featE_d^D[(w_k^*)^2]=( _ cp _k) ( _D _k)^-1 _ cp _k≤ C_ feat, and hence wk∗∈χ2w_k^* _χ^2. Proof. For any f∈span(ϕk)f∈ span( _k), there exists θ∈ℝdθ ^d such that f(s,a)=θ⊤ϕk(s,a)f(s,a)=θ _k(s,a). Then dD[wk∗f]=(μcpπk)⊤(ΣDπk)−1dD[ϕkϕk⊤]θ=(μcpπk)⊤θ=dπcp[f],E_d^D[w_k^*f]=( _ cp _k) ( _D _k)^-1E_d^D[ _k _k ]θ=( _ cp _k) θ=E_d _ cp[f], which proves (i). For (i), dD[(wk∗)2]=(μcpπk)⊤(ΣDπk)−1dD[ϕkϕk⊤](ΣDπk)−1μcpπk=(μcpπk)⊤(ΣDπk)−1μcpπk≤feat.E_d^D[(w_k^*)^2]=( _ cp _k) ( _D _k)^-1E_d^D[ _k _k ]( _D _k)^-1 _ cp _k=( _ cp _k) ( _D _k)^-1 _ cp _k≤ C_ feat. Thus wk∗∈χ2w_k^* _χ^2. ∎ Proposition 21 shows that, in the compatible linear case, the chi-square weight class can be instantiated directly by feature coverage: the correction function wk∗w_k^* exactly transfers expectations on the linear residual class, and its second moment under dDd^D is precisely the feature coverage quantity. In this sense, χ2W_χ^2 provides a feature-based analogue of the density-ratio weight class that is tailored to the actor update. Remark: feature correction weight. It is important to note that the feature-based correction weight wk∗w_k^* in Eq. (20) should NOT be interpreted as a density ratio. In general, it need not be nonnegative and need not satisfy the normalization condition dD[wk∗]=1E_d^D[w_k^*]=1. This is not an issue for our purpose, since the role of wk∗w_k^* is only to realize exact transfer on the residual class span(ϕk) span( _k), rather than to represent a valid change of measure. The normalization issue can also be handled by a simple centering trick. Let μDπk=dD[ϕk] _D _k=E_d^D[ _k], μcpπk=dπcp[ϕk] _ cp _k=E_d _ cp[ _k], and Σ¯Dπk=dD[(ϕk−μDπk)(ϕk−μDπk)⊤] _D _k=E_d^D[( _k- _D _k)( _k- _D _k) ]. Define w¯k(s,a)=1+(μcpπk−μDπk)⊤(Σ¯Dπk)−1(ϕk(s,a)−μDπk). w_k(s,a)=1+( _ cp _k- _D _k) ( _D _k)^-1( _k(s,a)- _D _k). Then dD[w¯k]=1E_d^D[ w_k]=1, and the same exact transfer property holds for every f∈span(ϕk)f∈ span( _k). Moreover, dD[(w¯k−1)2]=(μcpπk−μDπk)⊤(Σ¯Dπk)−1(μcpπk−μDπk).E_d^D[( w_k-1)^2]=( _ cp _k- _D _k) ( _D _k)^-1( _ cp _k- _D _k). Thus, normalization can be kept by replacing the uncentered 2nd-moment geometry with a centered covariance geometry. Nonnegativity, however, is a separate requirement and is not needed for restricted transfer over the linear residual class. This observation highlights a broader distinction between our correction-weight perspective and the traditional DRO or importance-weighting literature. In classical DRO [Kuhn et al., 2025, Rahimian and Mehrotra, 2019], the uncertainty set W is typically chosen as an f-divergence ball around the data distribution dDd^D, so its elements correspond to valid probability reweightings. Similarly, importance weighting methods, including marginalized importance sampling (MIS) [Liu et al., 2018, Nachum et al., 2019], use correction weights that are valid density ratios. In contrast, our feature-based correction weights need not define a valid change of measure; they only need to realize the desired transfer over the function class relevant to the actor update. In this sense, correction weights are more general than density ratios. Appendix F Omitted Details for Section 5.3 F.1 Recovery of Behavior Cloning Recall that with known dπcpd _ cp, let mk=(s,a)∼dπcp[Ak(s,a)]m_k=E_(s,a) d _ cp[A_k(s,a)] and μk=(s,a)∼dπcp[∇logπk(a∣s)] _k=E_(s,a) d _ cp[∇ _k(a s)], we solve for minv:‖v‖≤Vmax|mk−v⊤μk| _v:\|v\|≤ V_ max|m_k-v _k| in Eq. (11). There exists a closed-form solution which can be expressed as vk=mk‖μk‖∗uk,if|mk|≤Vmax⋅‖μk‖∗,Vmax⋅uk,ifmk>Vmax⋅‖μk‖∗,−Vmax⋅uk,ifmk<−Vmax⋅‖μk‖∗,v_k= cases m_k\| _k\|_*u_k,&if |m_k|≤ V_ max·\| _k\|_*,\\ V_ max· u_k,&if m_k>V_ max·\| _k\|_*,\\ -V_ max· u_k,&if m_k<-V_ max·\| _k\|_*, cases (21) where uk=argmaxu:‖u‖≤1u⊤μku_k= _u:\|u\|≤ 1u _k aligns with the direction of μk _k. This can be viewed as running steepest descent on Φ(θ) (θ), defined as the expected KL divergence under dπcpd _ cp: Φ(θ)=s∼dπcp[DKL(πcp(⋅∣s)∥πθ(⋅∣s))]. (θ)=E_s d _ cp[D_ KL( _ cp(· s)\| _θ(· s))]. This is because that the negative gradient of Φ corresponds to feature mean (at round k) μk _k: ∇θΦ(θk) _θ ( _k) =∇θs∼dπcp[a∼πcp(⋅∣s)[logπcp(a∣s)πk(a∣s)]] = _θE_s d _ cp [E_a _ cp(· s) [ _ cp(a s) _k(a s) ] ] =∇θ(s,a)∼dπcp[logπcp(a∣s)−logπk(a∣s)] = _θE_(s,a) d _ cp[ _ cp(a s)- _k(a s)] =−(s,a)∼dπcp[∇θlogπk(a∣s)]=−μk. =-E_(s,a) d _ cp[ _θ _k(a s)]=- _k. Sign of advantage. There is a subtlety regarding the sign of the advantage term: we are only updating along the direction of −∇Φ(θk)-∇ ( _k) to minimize the BC objective if mk=dπcp[Ak]≥0m_k=E_d _ cp[A_k]≥ 0; this is the BC regime described in Section 5.3. However, when mk<0m_k<0: the update will increase Φ(θ) (θ) and move away from the comparator. To understand the condition mk≥0m_k≥ 0, consider the case where fkf_k is accurate, i.e., fk=Qπkf_k=Q _k, then mk≥0⟺s∼dπcp[Aπk(s,a)]≥0⟺J(πcp)≥J(πk),m_k≥ 0 _s d _ cp[A _k(s,a)]≥ 0 J( _ cp)≥ J( _k), where the second equivalence is due to the performance-difference lemma (PDL). This means mk≥0m_k≥ 0 corresponds to J(πk)≤J(πcp)J( _k)≤ J( _ cp), whereas mk<0m_k<0 indicates that the current policy is already outperforming the comparator (at least from the critic’s perspective). Therefore the update deliberately moves towards an “improving” direction which depends whether the current policy is better than the comparator πcp _ cp. This means that DRPU is still identical to BC in typical settings when the learned policy is unlikely to exceed the performance of πcp _ cp. Finally, this sign issue does not conflict with our theoretical guarantees. The reason is that the guarantees in the paper are stated in terms of comparator regret, not monotonic decrease of the KL objective. Recall that in Section 3 we introduce the actor-side quantity as RegKK=1K∑k=1Ks∼dπcp[fk(s,πcp)−fk(s,πk)]=1K∑k=1Kmk, Reg_KK= 1K _k=1^KE_s d _ cp[f_k(s, _ cp)-f_k(s, _k)]= 1K _k=1^Km_k, which is precisely the average advantage with respect to the comparator policy. Thus, rounds with mk<0m_k<0 are not harmful for the regret analysis; if anything, they help, because they indicate that the current policy already outperforms the comparator. What matters in the analysis is not the iterates remain close to πcp _ cp, but rather that the mean-matching error is controlled, which is where the norm constraint ‖vk‖≤Vmax\|v_k\|≤ V_ max plays an important stabilizing role here. F.2 Numerical Result Setting We consider a simple discounted MDP with finite state and action spaces. The state space is =1,2,3S=\1,2,3\ and the action space is =a1,a2A=\a_1,a_2\. The discount factor is γ=0.9γ=0.9, and the initial state distribution d0d_0 is uniform over S. The transition dynamics are state-absorbing, so the state does not change over time. As a result, the problem reduces to a contextual bandit with discounted returns, while still admitting a well-defined occupancy measure dπd^π. The reward function is deterministic and state-dependent. For action a1a_1, the reward is given by r(s,a1)=(1,4,4)r(s,a_1)=(1,4,4) for states s=1,2,3s=1,2,3, respectively. For action a2a_2, the reward is constant across states, given by r(s,a2)=(2,2,2)r(s,a_2)=(2,2,2). This construction ensures that the advantage function varies across states and actions, while remaining smooth and bounded. In particular, the policy that always selects a1a_1 is not optimal, since action a2a_2 yields higher reward in state s=1s=1. We consider a one-dimensional softmax policy class Πθ=πθ:θ∈ℝ _θ=\ _θ:θ \ parameterized by πθ(a1∣s)=exp(θcs)exp(θcs)+exp(−θcs),πθ(a2∣s)=1−πθ(a1∣s), _θ(a_1 s)= (θ c_s) (θ c_s)+ (-θ c_s), _θ(a_2 s)=1- _θ(a_1 s), where the state-dependent coefficients are c=(1,2,3)c=(1,2,3). The corresponding score function ∇logπθ(a∣s)∇ _θ(a s) is bounded and one-dimensional, which makes model misspecification effects transparent. The comparator policy πcp _ cp is chosen as the deterministic policy that always selects action a1a_1 in every state. Importantly, πcp _ cp is not an optimal policy for this MDP. In the experiments, πcp _ cp is approximated within the policy class by a large parameter value θcp=100 _ cp=100. The data distribution is set to dD=dπcpd^D=d _ cp, corresponding to the no-shift setting as in imitation learning with expert-generated data. All methods are initialized at θ0=0 _0=0 and run for a fixed number of iterations. Performance is evaluated by tracking the policy value and the CFA error errk err_k under dπcpd _ cp at each iteration. Since dD=dπcpd^D=d _ cp, there is no distribution shift in this experiment, and any observed performance gap reflects model misspecification alone. F.3 Analysis of Mean Matching Algorithm under No-Shift Here we provide the analysis of the mean-matching algorithm, along with some additional assumptions. Under the settings in Appendix F.1, we have already shown that the feature mean μk _k represents the negative gradient on the objective Φ . Actually, the target mean mkm_k can also be related to Φ : mk m_k =(s,a)∼dπcp[fk(s,a)−fk(s,πk)] =E_(s,a) d _ cp[f_k(s,a)-f_k(s, _k)] =s∼dπcp[∑afk(s,a)(πcp(a∣s)−πk(a∣s))] =E_s d _ cp [ _af_k(s,a) ( _ cp(a s)- _k(a s) ) ] ≤s∼dπcp[Vmax⋅∥πcp(⋅∣s)−πk(⋅∣s)∥1] _s d _ cp [V_ max·\| _ cp(· s)- _k(· s)\|_1 ] ≤Vmax⋅s∼dπcp[12DKL(πcp(⋅∣s)∥πk(⋅∣s))] ≤ V_ max·E_s d _ cp [ 12D_ KL( _ cp(· s)\| _k(· s)) ] ≤Vmax⋅12s∼dπcp[DKL(πcp(⋅∣s)∥πk(⋅∣s))]=Vmax12Φ(θk), ≤ V_ max· 12E_s d _ cp [D_ KL( _ cp(· s)\| _k(· s)) ]=V_ max 12 ( _k), where the first inequality follows from Hölder’s inequality, the second from Pinsker’s inequality, and the last from Jensen’s inequality. Therefore, it is natural to assume that Φ(θ) (θ) satisfies the μ-Polyak–Łojasiewicz (PL) condition, such that for all θ, 12‖∇Φ(θ)‖∗2≥μ(Φ(θ)−δ∗),δ∗=infθΦ(θ). 12\|∇ (θ)\|_*^2≥μ( (θ)-δ^*), δ^*= _θ (θ). Hence, we can use the gradient norm ‖∇Φ(θ)‖∗\|∇ (θ)\|_* to control the function value Φ(θ) (θ)—or more precisely, the optimality gap Φ(θ)−δ∗ (θ)-δ^*, since there may exist model mis-specification. Under this PL condition, an approximate stationary point implies an approximate optimal point. Intuitively, this means that if the feature mean ‖μk‖∗\| _k\|_* is small, then the target mean |mk||m_k| is also small, which enables effective mean-matching under the norm constraint ‖v‖≤Vmax\|v\|≤ V_ max. In contrast, for a “bad” policy class, the magnitude of the expected advantage, i.e., |mk||m_k|, would be large, making the mean-matching problem difficult and consequently leading to a non-zero error. Intuitively, if a policy class can achieve zero error at all rounds, which means vk⊤μk=mkv_k _k=m_k for all k∈[K]k∈[K], the telescoping lemma tells that ∑k=1Kmk=∑k=1Kvk⊤μk≤Φ(θ1)η+βη2Vmax2K=(VmaxβΦ(θ1)K). _k=1^Km_k= _k=1^Kv_k _k≤ ( _1)η+ βη2V_ max^2K=O(V_ max β ( _1)K). Since mkm_k represents the expected advantage of policy πcp _ cp compared to policy πk _k, the above bound indicates that the cumulative advantage should be controlled by a sublinear rate 1/K1/ K. This cannot happen for a bad policy class where there might exist some lower bound Δ of the advantage AkA_k, i.e., fk(s,πcp)−fk(s,πk)≥Δf_k(s, _ cp)-f_k(s, _k)≥ . In this case, ∑k=1Kmk≥KΔ _k=1^Km_k≥ K which contradicts to the sublinear rate. Thus, the PL condition essentially characterizes the “gradient domination” property, which allows us to reconstruct the generic regret decomposition lemma (Lemma 3) and extend the analysis in this no-shift setting. Theorem 22 (Regret Bound of Mean-Matching with Known dπcpd _ cp). Suppose we have access to the comparator distribution dπcpd _ cp. We update the policy parameters according to θk+1=θk+ηvk _k+1= _k+η v_k, where vkv_k is defined in Eq. (21). Under Assumption 3, and assuming that Φ(θ) (θ) satisfies the μ-PL condition, by tuning η=Vmax−12(Φ(θ1)−δ∗)/(βK)η=V_ max^-1 2( ( _1)-δ^*)/(β K), we obtain RegKK≤Vmax12δ∗+(1+12μ)Vmax2β(Φ(θ1)−δ∗)K. Reg_KK≤ V_ max 12δ^*+ (1+ 12 μ )V_ max 2β( ( _1)-δ^*)K. Proof of Theorem 22. Recall that in the proof of Lemma 3, we use the β-smoothness of Φ(θ) (θ) to obtain the following “descent lemma”: Φ(θk)−Φ(θk+1)≥ηvk⊤μk−β2η2‖vk‖2. ( _k)- ( _k+1)≥η v_k _k- β2η^2\|v_k\|^2. Define gk=Φ(θk)−δ∗g_k= ( _k)-δ^*. This descent lemma also works: gk+1≤gk−ηvk⊤μk+βη22‖vk‖2g_k+1≤ g_k-η v_k _k+ βη^22\|v_k\|^2. By the definition of vkv_k, we have vk⊤μk=Proj[−Vmax‖μk‖∗,Vmax‖μk‖∗](mk)v_k _k= Proj_[-V_ max\| _k\|_*,V_ max\| _k\|_*](m_k). We then partition the rounds into three sets: S0=k:|mk|≤Vmax‖μk‖∗S_0=\k:|m_k|≤ V_ max\| _k\|_*\, S1=k:mk>Vmax‖μk‖∗S_1=\k:m_k>V_ max\| _k\|_*\, and S2=k:mk<−Vmax∥μk∥∗S_2=\k:m_k<-V_ max\| _k\|_*\. We only analyze the telescoping sum over S0S_0 and S1S_1, since the regret can be rewritten as RegK=∑k=1Ks∼dπcp[fk(s,πcp)−fk(s,πk)]=∑k=1K(s,a)∼dπcp[fk(s,a)−fk(s,πk)]=∑k=1Kmk, Reg_K= _k=1^KE_s d _ cp[f_k(s, _ cp)-f_k(s, _k)]= _k=1^KE_(s,a) d _ cp[f_k(s,a)-f_k(s, _k)]= _k=1^Km_k, and the rounds in S2S_2 necessarily satisfy mk<0m_k<0, which do not contribute positively to the regret. For rounds in S0S_0, we have that vk⊤μk=mkv_k _k=m_k. Substitute this into the descent lemma: gk+1≤gk−ηmk+βη22Vmax2⟹mk≤gk−gk+1η+βη2Vmax2.g_k+1≤ g_k-η m_k+ βη^22V_ max^2 m_k≤ g_k-g_k+1η+ βη2V_ max^2. Therefore, telescoping over k∈S0k∈ S_0, since |S0|≤K|S_0|≤ K, we get ∑k∈S0mk≤1η∑k∈S0(gk−gk+1)+βη2Vmax2|S0|≤Φ(θ1)−δ∗η+βη2Vmax2K. _k∈ S_0m_k≤ 1η _k∈ S_0(g_k-g_k+1)+ βη2V_ max^2|S_0|≤ ( _1)-δ^*η+ βη2V_ max^2K. For rounds in S1S_1, we have that vk⊤μk=Vmax‖μk‖∗v_k _k=V_ max\| _k\|_*. Similarly, we get that gk+1≤gk−ηVmax‖μk‖∗+βη22Vmax2⟹‖μk‖∗≤gk−gk+1ηVmax+βη2Vmax.g_k+1≤ g_k-η V_ max\| _k\|_*+ βη^22V_ max^2 \| _k\|_*≤ g_k-g_k+1η V_ max+ βη2V_ max. We can relate this bounded ‖μk‖∗\| _k\|_* with bounded mkm_k (see in previous discussion using Pinsker’s inequality): mk m_k ≤Vmax12Φ(θk) ≤ V_ max 12 ( _k) ≤Vmax12δ∗+Vmax12gk ≤ V_ max 12δ^*+V_ max 12g_k ≤Vmax12δ∗+Vmax⋅‖μk‖∗2μ ≤ V_ max 12δ^*+V_ max· \| _k\|_*2 μ ≤Vmax12δ∗+12μ(gk−gk+1η+βη2Vmax2), ≤ V_ max 12δ^*+ 12 μ ( g_k-g_k+1η+ βη2V_ max^2 ), where the first inequality is due to a+b≤a+b a+b≤ a+ b, the second inequality is due to the μ-PL condition of Φ(θ) (θ), and the third inequality is due to the one-step descent lemma that bounds ‖μk‖∗\| _k\|_*. Therefore, telescoping over k∈S1k∈ S_1, since |S1|≤K|S_1|≤ K, we get ∑k∈S1mk _k∈ S_1m_k ≤KVmax12δ∗+12μ(1η∑k∈S1(gk−gk+1)+βη2Vmax2|S1|) ≤ KV_ max 12δ^*+ 12 μ ( 1η _k∈ S_1(g_k-g_k+1)+ βη2V_ max^2|S_1| ) ≤KVmax12δ∗+12μ(Φ(θ1)−δ∗η+βη2Vmax2K). ≤ KV_ max 12δ^*+ 12 μ ( ( _1)-δ^*η+ βη2V_ max^2K ). Therefore, combine the results in S0S_0 and S1S_1 and tune η=Vmax−12(Φ(θ1)−δ∗)/(βK)η=V_ max^-1 2( ( _1)-δ^*)/(β K) lead to RegKK≤1K(∑k∈S0mk+∑k∈S1mk)≤Vmax12δ∗+(1+12μ)Vmax2β(Φ(θ1)−δ∗)K. Reg_KK≤ 1K ( _k∈ S_0m_k+ _k∈ S_1m_k )≤ V_ max 12δ^*+ (1+ 12 μ )V_ max 2β ( ( _1)-δ^* )K. ∎ Appendix G Technical Lemmas Lemma 23 (Gibbs Variational Principle). For any measurable function ϕ:→ℝφ:A and any distribution u∈Δν()u∈ _ν(A) that is absolutely continuous w.r.t. the base measure ν, we have −1ηlog∫exp(−ηϕ(a))ν(da)=infu∈Δν()a∼u[ϕ(a)]+1ηDKL(u∥ν).- 1η _A (-ηφ(a))ν(da)= _u∈ _ν(A) \E_a u[φ(a)]+ 1ηD_ KL(u\|ν) \. Moreover, the infimum is attained at the Gibbs (softmax) distribution u⋆(a)=exp(−ηϕ(a))∫exp(−ηϕ(a′))ν(da′).u (a)= (-ηφ(a)) _A (-ηφ(a ))ν(da ). Lemma 24 (Bellman Error Telescoping). For any π:→Δ()π:S→ (A), and any f∈ℝ×f ^S×A, the performance gap using f as an estimate of QπQ^π is given by Jf(π)−J(π)=11−γdπ[f−πf],J_f(π)-J(π)= 11-γE_d^π[f-T^πf], where Jf(π)=s∼d0[f(s,π)]J_f(π)=E_s d_0[f(s,π)], and dπd^π is the discounted state-action occupancy of π. Lemma 25 (Generalized Performance-Difference Lemma [Jiang and Xie, 2025, Lemma 6]). For any f∈ℝ×f ^S×A, and policies π,π′:→Δ()π,π :S→ (A), the difference between there expected return is given by J(π′)−J(π)=11−γ(s∼dπ′[f(s,π′)−f(s,π)]+dπ′[πf−f]+dπ[f−πf]).J(π )-J(π)= 11-γ (E_s d^π [f(s,π )-f(s,π) ]+E_d^π [T^πf-f]+E_d^π[f-T^πf] ). Lemma 26 (Convergence Rate of Stochastic Gradient Descent). Assume =x:‖x‖≤BX=\x:\|x\|≤ B\ for some B≥0B≥ 0. Let f be a convex function and let x∗∈argminx∈f(x)x^*∈ _x f(x). Assume that for all k, ‖gt‖∗≤ρ\|g_t\|_*≤ρ and [gt∣xt]=∇f(xt)E[g_t x_t]=∇ f(x_t), and that projected SGD xt+1=Proj[xt−ηgt]x_t+1= Proj_X [x_t-η g_t ] is run for T iterations with η=B2/(ρ2T)η= B^2/(ρ^2T). Then, [f(1T∑t=1Txt)]−f(x∗)≤BρN.E [f ( 1T _t=1^Tx_t ) ]-f(x^*)≤ Bρ N. Lemma 27 (Matrix Chernoff Bound [Hsu et al., 2012, Lemma 17]). Let X1,…,XnX_1,…,X_n be random vectors in ℝR dsuch that for all i, ∑i=1n[‖Xi‖2∣X1:i−1]≥1,‖Xi‖≤b, _i=1^nE [\|X_i\|^2 X_1:i-1 ]≥ 1, \|X_i\|≤ b, almost surely. Then, for all δ∈(0,1)δ∈(0,1), with probability at least 1−δ1-δ, λmin(1n∑i=1nXiXi⊤)≥1−2b2nlogdδ. _ min ( 1n _i=1^nX_iX_i )≥ 1- 2b^2n dδ. Lemma 28 (Freedman Inequality for Vector-Valued Martingales [Hsu et al., 2012, Lemma 15]). Let X1,…,XnX_1,…,X_n be a martingale difference vector sequence (i.e., [Xi∣X1:i−1]=0E[X_i X_1:i-1]=0 for all i=1,…,ni=1,…,n) such that for all i, ∑i=1n[‖Xi‖2∣X1:i−1]≤v,‖Xi‖≤b, _i=1^nE [\|X_i\|^2 X_1:i-1 ]≤ v, \|X_i\|≤ b, almost surely. Then for any δ∈(0,1)δ∈(0,1), with probability at least 1−δ1-δ, ‖∑i=1nXi‖≤v(1+8log1δ)+43blog1δ. \| _i=1^nX_i \|≤ v (1+ 8 1δ )+ 43b 1δ. Lemma 29 (Danskin’s Theorem). Let ϕ:ℝn×Z→ℝφ:R^n× Z be a continuous function, where Z⊂ℝmZ ^m is a compact set. Define f(x)=maxz∈Zϕ(x,z),Z0(x)=z¯∈Z:ϕ(x,z¯)=maxz∈Zϕ(x,z).f(x)= _z∈ Zφ(x,z), Z_0(x)= \ z∈ Z:\ φ(x, z)= _z∈ Zφ(x,z) \. Then the followings hold: 1. (Convexity) If ϕ(x,z)φ(x,z) is convex in x for every z∈Zz∈ Z, then f(x)f(x) is convex. 2. (Derivative) If ϕ(x,z)φ(x,z) is differentiable in x and Z0(x)Z_0(x) consists of a single element z¯ z, then f(x)f(x) is differentiable at x and ∇f(x)=∂ϕ(x,z¯)∂x.∇ f(x)= ∂φ(x, z)∂ x. Lemma 30 (Dvoretzky-Kiefer-Wolfowitz Inequality). Given a distribution p∈Δp∈ _X. Let X∼pX p be a random variable with CDF F, i.e., F(x)=Prp(X≤x)F(x)= _p(X≤ x). Let X1,…,XNX_1,…,X_N be i.i.d. random variables from distribution p, with associated empirical CDF defined by F^N(x)=1N∑i=1NXi≤x. F_N(x)= 1N _i=1^N1\X_i≤ x\. Then, the following holds with probability at least 1−δ1-δ: supx|F(x)−F^N(x)|≤12nlog2δ. _x|F(x)- F_N(x)|≤ 12n 2δ. Lemma 31 (Bousquet’s Inequality [Bousquet, 2002]). Let ℱF be a class of measurable functions f:→ℝf:X , and let x1,…,xNx_1,…,x_N be i.i.d. samples from some distribution P on X. Define Z=supf∈ℱ(P−PN)f,wherePf=x∼P[f(x)],PNf=1N∑i=1Nf(xi).Z= _f (P-P_N)f, Pf=E_x P[f(x)], P_Nf= 1N _i=1^Nf(x_i). Assume that, for all f∈ℱf , ‖f‖∞≤B\|f\|_∞≤ B and VarP(f)=P[f2]−P[f2]≤v Var_P(f)=E_P[f^2]-E_P[f^2]≤ v. Then, with probability at least 1−δ1-δ, Z≤[Z]+2vlog(1/δ)N+2blog(1/δ)3N.Z [Z]+ 2v (1/δ)N+ 2b (1/δ)3N.