Paper deep dive
Hypergradient-based Bilevel Reinforcement Learning with Improved Sample Complexity
Naman Saxena, Mudit Gaur, Vaneet Aggarwal
Intelligence
Status: succeeded | Model: Gemma-4-26B-A4B | Prompt: intel-v1 | Confidence: 94%
Last extracted: 8/3/2026, 2:14:13 AM
Summary
This paper proposes a Hessian-free hypergradient-based bilevel reinforcement learning algorithm called Approximate Hypergradient Optimization (AHO). By leveraging the optimality of the Boltzmann policy for entropy-regularized RL, the method eliminates the need for Hessian computations and the Polyak-Lojasiewicz (PL) condition on the outer-level objective. The proposed algorithm achieves an iteration complexity of O(ε^-1) and a state-of-the-art sample complexity of Õ(ε^-2), improving upon previous methods that suffered from higher sample complexity or scalability issues due to Hessian-based gradients.
Entities (10)
Relation Signals (8)
AHO → achievesiterationcomplexity → O(ε^-1)
confidence 98% · obtains an iteration complexity of O(ε^-1)
AHO → achievessamplecomplexity → Õ(ε^-2)
confidence 98% · obtains ... state-of-the-art sample complexity of Õ(ε^-2)
AHO → usesoptimalityof → Boltzmann Policy
confidence 97% · using the optimality of the Boltzmann policy for the entropy regularized discounted RL objective function
AHO → removesassumption → Polyak-Lojasiewicz (PL) Condition
confidence 96% · remove the assumption of the Polyak-Lojasiewicz (PL) condition on the outer-level objective function
AHO → ishessianfree → Hessian
confidence 95% · Our proposed algorithm is Hessian-free
Gradient Shifted Value Functions → actsassurrogatefor → Gradient of Q-value and Value Function
confidence 94% · act as a surrogate for the gradient of Q-value and value function
Prior Bilevel RL Algorithms → suffersfrom → High Sample Complexity
confidence 90% · suffer high sample complexity because of using penalty-based approximation methods
Prior Bilevel RL Algorithms → suffersfrom → Scalability Issues
confidence 90% · not scalable because of using hypergradient with Hessian
Cypher Suggestions (0)
No Cypher suggestions yet.
Abstract
Abstract:Bilevel reinforcement learning (RL) is an important framework within the literature of RL that can be used to formalize various categories of problems, such as meta-learning, hierarchical task decomposition, and reinforcement learning from human feedback (RL-HF). Most of the bilevel RL algorithms are either not scalable because of using hypergradient with Hessian, or they suffer from high sample complexity because of using penalty-based approximation methods. In this work, we propose a hypergradient-based bilevel RL algorithm using the optimality of the Boltzmann policy for the entropy regularized discounted RL objective function. Our proposed algorithm is Hessian-free and obtains an iteration complexity of $O(\epsilon^{-1})$ and state-of-the-art sample complexity of $\tilde{O}(\epsilon^{-2})$ under mild regularity conditions. Further, in our convergence analysis, we are able to remove the assumption of the Polyak-Lojasiewicz (PL) condition on the outer-level objective function present in the prior state-of-the-art sample complexity work.
Tags
Links
- Source: https://arxiv.org/abs/2607.28849v1
- Canonical: https://arxiv.org/abs/2607.28849v1
Trouble viewing inline? Open PDF directly →
Full Text
99,525 characters extracted from source content.
Expand or collapse full text
Hypergradient-based Bilevel Reinforcement Learning with Improved Sample Complexity Naman Saxena Purdue University West Lafayette, IN 47907 saxen147@purdue.edu Mudit Gaur Purdue University West Lafayette, IN 47907 mgaur@purdue.edu Vaneet Aggarwal Purdue University West Lafayette, IN 47907 vaneet@purdue.edu Abstract Bilevel reinforcement learning (RL) is an important framework within the literature of RL that can be used to formalize various categories of problems, such as meta- learning, hierarchical task decomposition, and reinforcement learning from human feedback (RL-HF). Most of the bilevel RL algorithms are either not scalable because of using hypergradient with Hessian, or they suffer from high sample complexity because of using penalty-based approximation methods. In this work, we propose a hypergradient-based bilevel RL algorithm using the optimality of the Boltzmann policy for the entropy regularized discounted RL objective function. Our proposed algorithm is Hessian-free and obtains an iteration complexity ofO(ε −1 ) and state-of-the-art sample complexity of ̃ O(ε −2 )under mild regularity conditions. Further, in our convergence analysis, we are able to remove the assumption of the Polyak-Łojasiewicz (PL) condition on the outer-level objective function present in the prior state-of-the-art sample complexity work. 1 Introduction The bilevel reinforcement learning (RL) framework has started receiving a lot of attention lately because of its ability to model different types of problems in RL, such as hierarchical task decom- position, meta-learning, hyper-parameter tuning, and reinforcement learning from human feedback (RL-HF). Specifically for RL-HF, the problem can be formulated as a bilevel RL problem where the outer-level problem optimizes the reward parameter and the inner-level problem optimizes the policy parameters. Most of the works in the bilevel optimization literature (Kwon et al., 2023; Sow et al., 2022; Yang et al., 2023) assume convexity for the inner-level objective function and cannot be extended to address the setting of bilevel RL, where the inner-level problem is non-convex. There are very few bilevel optimization works, such as (Kwon et al., 2024; Chen et al., 2024), that have laid the foundation for extending bilevel optimization methods to bilevel RL. Recently, (Gaur et al., 2025; Shen et al., 2025) proposed a penalty method-based bilevel RL algorithm. (Gaur et al., 2025)’s penalty method-based algorithm uses an approximate outer-level objective gradient based on the conclusion of (Kwon et al., 2024; Chen et al., 2024) and also requires the Polyak-Łojasiewicz (PL) condition to hold true for the outer-level objective function (Chen et al., 2024). Because of using an approximate outer-level objective gradient, their penalty method-based bilevel algorithm obtains a sub-optimal sample complexity ofO(ε −3 ). On the other hand, avoiding the assumption of the PL condition on the outer-level objective function, (Chakraborty et al., 2024) uses an exact gradient for the outer-level objective function and obtains a Hessian-based hypergradient bilevel RL algorithm. Bilevel RL algorithm provided by both (Chakraborty et al., 2024) and (Gaur et al., 2025) obtains an iteration complexity ofO(ε −1 ). However, because of using the Hessian-based hypergradient, the algorithm proposed by (Chakraborty et al., 2024) faces scalability issues with function approximators with a large number of parameters. In this work, we provide a scalable Preprint. arXiv:2607.28849v1 [cs.LG] 30 Jul 2026 bilevel RL algorithm that uses Hessian-free hypergradient, avoiding the approximate gradient for the outer-level objective function. At the same time, we remove the assumption of the PL condition on the outer-level objective function. Definition 1.1 (Informal). A policy classΘis called realizable if it can represent all the Boltzmann policies. Our algorithm is motivated by the optimality of the Boltzmann policy for the entropy regularized discounted reward objective function for RL (Nachum et al., 2017). (Yang et al., 2025) also exploited the optimality of the Boltzmann policy for finite spaces. However, we assume a non-realizable policy class and the hypergradient developed for finite space in Yang et al. (2025) doesn’t hold directly for the non-realizable parameterized policy class because of the lack of a feasible expression for the gradient of Q-value and value function (Remark 3.4). In the case of parameterized policy, optimality of the Boltzmann policy holds if the policy class is realizable (Lemma 2.2). Therefore, to obtain a hypergradient for an unrealizable parameterized policy class, we provide conditions (Assumption 3.1) under which the optimality of the Boltzmann policy could be used. Further, we design gradient shifted functions (Section 3.1) to act as a surrogate for the gradient of Q-value and value function to define an approximate hypergradient. This approximate hypergradient allows us to remove the PL condition on the outer-level objective function, present in prior state-of-the-art work (Gaur et al., 2025). The PL condition on the outer level objective function was earlier necessary as it allowed (Gaur et al., 2025) to use their O(σ)−approximate gradient. Further, the use of Boltzmann policy optimality allows us to remove the Hessian inverse term from the hypergradient expression, which is otherwise present in the hypergradient provided by (Chakraborty et al., 2024). We note here that Boltzmann policy optimality helps us by giving a closed-form expression of the optimal policy for the hypergradient expression. However, our inner-level still assumes a generally parameterized non-realizable policy class. Moreoever, theO(σ)approximate outer level gradient used by (Gaur et al., 2025) leads to a tradeoff between gradient approximation errorO(σ 2 )and sampling errorO(1/(σ 2 B)). The use of our hypergradient removes the tradeoff and improves the sample complexity from ̃ O(ε −3 )to ̃ O(ε −2 ). The following are broad contributions of our work: 1.Boltzmann policy optimality with unrealizable policy class: We provide conditions under which Boltzmann policy optimality could be used with an unrealizable policy class (see Definition 2.1) and discuss its impact on convergence of the proposed algorithm (see Remark 4.8). 2.Algorithm proposal: We proposed a Hessian-free scalable bilevel RL algorithm (Algorithm 1) called Approximate Hypergradient Optimization (AHO) based on the optimality of the Boltzmann policy for the entropy regularized discounted reward RL objective function. 3. Improving sample complexity: We obtain an iteration complexity ofO(ε −1 )and a sample complexity of ̃ O(ε −2 ) (Theorem 4.6) for our algorithm AHO by improving the previous state-of- art sample complexity of ̃ O(ε −3 ) (see Table 1). 4. Removing PL/Unique Minimizer Assumption: PARL (Chakraborty et al., 2024) assumes unique minimizer for the inner level. Further, the previous state-of-the-art bilevel RL algorithm (Gaur et al., 2025) assumes PL for the outer level objective. We remove both assumptions of the PL condition on the outer-level objective function and unique minimizer. Table 1: Comparison of Bilevel RL works References PL a /Unique Minimizer b Continuous Space Hessian Free Iteration Complexity Sample Complexity (Hong et al., 2023)- c ✗O(ε −2.5 )✗ (Chakraborty et al., 2024)✓ b ✓✗O(ε −1 )✗ (Thoma et al., 2024)- c ✗✓O(ε −2 )✗ (Yang et al., 2025)- c ✗✓O(ε −1.5 )O(ε −3.5 ) (Shen et al., 2025)- c ✗✓O(ε −1 )- (Gaur et al., 2025)✓ a ✓O(ε −1 ) ̃ O(ε −3 ) Ours✗ a ✓O(ε −1 ) ̃ O(ε −2 ) a Assumes PL on outer level objective. b Assumes a unique minimizer for the inner level problem. c Assumes finite space. 2 2 Problem Formulation Markov Decision Process (MDP). A Markov Decision Process is characterized by the tuple S,A,r,π,γ,P. Here,S ⊆ R n represents continuous state space,A⊆ R m represents continuous actions space. Further,r :S×A×X 7→ [−R max ,R max ]is the reward function parameterized by x∈X,P(·|s,a) :S×A7→ μ 1 (·)is the transition probability function whereμ 1 (·)is a probability measure over the spaceS,π(·|s,θ) :S 7→ μ 2 (·)is the stochastic policy parameterized byθwhere μ 2 (·)is a probability measure over the spaceAandγis the discount factor. For an MDP, we solve for the entropy regularized objective functionJ (θ,x)in Eq.(1)as the Boltzmann policy is optimal for that function. max θ J (θ,x) := 1 1− γ E (s,a)∼d π(θ) h r(s,a,x)− τ logπ(a|s,θ) i (1) Here,d π θ (s,a) = d π θ s (s)π(a|s,θ), whered π θ s is the discounted state occupancy probabil- ity density for parameterized policy with parameterθ.Further,Q-value function, for pa- rameterized policyπwith parameterθand reward function parameterized byx, is defined asQ π (s,a,θ,x) = r(s,a,x) + γE s ′ ∼P (·|s,a) [V π (s ′ ,θ,x)]and value function is defined as V π (s,θ,x) = E a∼π(·|s,θ) [−τ logπ(a|s,θ) + Q π (s,a,θ,x)], whereτis the temperature coeffi- cient that controls the exploratory nature of the policy. Using the definition of value and Q-value function, we now define the Boltzmann policy (π B ) in Eq.(2)for a policyπwith parameterθ. Let V π,B (s,θ,x), defined in Eq.(2), be the Boltzmann value function for policy parameterθand reward parameter x. π B (a|s,θ,x) := exp(Q π (s,a,θ,x)/τ ) exp(V π,B (s,θ,x)/τ ) where V π,B (s,θ,x) = τ log Z exp(Q π (s,a,θ,x)/τ ) da (2) Definition 2.1. A policy classΘis called realizable if∀θ ∈ Θ ∃θ B (x) ∈ Θ π(a|s,θ B (x)) = π B (a|s,θ,x). Lemma 2.2. LetJ (θ,x)(Eq.(1)) be the objective function for RL defined for policy classΘwhere θ ∈ Θis the policy parameter, andxis the reward parameter. If policy classΘis realizable and there existθ ′ (x) ∈ Θsuch thatπ(a|s,θ ′ (x)) = π B (a|s,θ ′ (x),x)thenθ ′ (x)is the optimal policy parameter for J (θ,x). A non-parameterized Boltzmann policy is the optimal policy for Eq.(1)in the case of a finite state and action space (Nachum et al., 2017). In Lemma 2.2, we show that if the Boltzmann policy lies in the class of parameterized policies, it is optimal for the parameterized policy setting as well. A proof for the same is given in the Appendix C.6. Therefore, Lemma 2.2 along with Eq.(2) provides a closed-form solution for the optimal policy and is used to eliminate the Hessian from the hypergradient as discussed in Section 3. Next, we define how the objective function defined in Eq. (1) is used in the context of Bilevel reinforcement learning. Bilevel Reinforcement Learning. The bilevel RL problem consists of an inner-level and an outer- level objective function. Entropy regularized RL objective function (Eq.(1)) is used as the inner level objective function. The objective function at the outer level is optimized at the optimal solution of the inner-level objective function. The bilevel RL problem is described by Eq.(3)whereφ(x,θ ∗ (x)) is the non-convex outer level objective function andθ ∗ (x)is a localized selection map as described in Assumption 4.5 and represents one of the optimal solutions of the inner-level objective function. Please note thatθ ∗ (x)is a single-valued map. Here,J (θ,x)is the non-convex inner level objective function. min x φ(x,θ ∗ (x)) s.t θ ∗ (x)∈ arg min θ −J (θ,x) (3) Here,φ(x,θ) = −E d i ∼P (d i ,θ) [l(d i I−1 0 ,x)],whered i I−1 0 is a collection ofItrajectories and each trajectory is defined asd = s t ,a t H−1 t=0 is state-action trajectory and sampled from the distributionP (d,θ)defined in Eq.(6). For,I = 2,E d i ∼P (d i ,θ) [l(d i 1 0 ,x)]is defined in Eq.(4) using Bradley-Terry model (Bradley and Terry, 1952). We note that our method isn’t limited to the 3 Bradley-Terry model and can handle any preference-based model. Let(d 0 ,l 0 ,d 1 ,l 1 )represents pair of trajectory withl 1 = 1,l 0 = 0denotingd 1 is preferred overd 0 and vice-versa andP (d a ≻ d b )is defined as Eq. (5) with R x (d) = P s t ,a t ∈d r(s t ,a t ,x). E d i ∼P (d i ,θ) [l(d i 1 0 ,x)] =E d 0 ,d 1 ,l 0 ,l 1 ∼π(θ) h l 0 logP (d 0 ≻ d 1 |x) + l 1 logP (d 1 ≻ d 0 |x) i (4) P (d a ≻ d b |x) = exp(R x (d a )) exp(R x (d a )) + exp(R x (d b )) (5) logP (d,θ) = logρ 0 (s 0 ) + H−2 X i=0 (logπ(a i |s i ,θ) + logP (s i+1 |s i ,a i )) + logπ(a H−1 |s H−1 ,θ) (6) Here,J (θ,x)is defined as in Eq.(1), which is an entropy regularized discounted reward performance metric. In the next section, we will discuss our approach for optimizing the outer level objective function−E d i ∼P (d i ,θ ∗ (x)) [l(d i I−1 0 ,x)] for the optimal policy parameter θ ∗ (x). 3 Proposed Approach In this section, we will first define gradient shifted value functions and then provide the hypergradient theorem for the outer objective function, followed by a discussion on the proposed bilevel RL algorithm. We note that for the rest of the paper,∇and∇ x refer to the full derivative and partial derivative w.r.t. the reward parameter x, respectively. 3.1 Gradient Shifted Value functions We defineU π (s,θ,x)as the gradient shifted value function andW π (s,a,θ,x)is defined as the gradient shifted Q-value function for the policy parameterθand the reward parameterxin Eq. (7).U π (s,θ(x),x)represents the long-term discounted summation of the gradient of the reward (∇r(s,a,x)) starting from state s under the policy π B (·|s t ,θ,x). On the other hand, W π (s,a,θ,x) denotes long term discounted summation of reward gradient (∇r(s,a,x)) starting from statesand actionaunder the policyπ B (·|s,θ,x).U π (s,θ ∗ (x),x)andW π (s,a,θ ∗ (x),x)are designed to act as surrogate for∇V π,B (s,θ ∗ (x),x)and∇Q π (s,a,θ ∗ (x),x)and help in defining hypergradient theorem in the next subsection. U π (s,θ,x) = E π B h ∞ X t=0 γ t ∇r(s t ,a t ,x) s 0 = s,a t ∼ π B (·|s t ,θ,x) i W π (s,a,θ,x) = E π B h ∞ X t=0 γ t ∇r(s t ,a t ,x) s 0 = s,a 0 = a,a t ∼ π B (·|s t ,θ,x) i (7) Assumption 3.1. LetΘbe the class of parameterized policy andπ(·|s,θ ∗ (x))be the optimal policy w.r.t. the objective function−J (θ,x). Further,π B (a|s,θ ∗ (x),x)be the Boltzmann policy. Because of the limited representational capacity of the policy class, we make the following assumption: 1. R π(a|s,θ ∗ (x))| logπ B (a|s,θ ∗ (x),x)− logπ(a|s,θ ∗ (x))| da≤ ε kl 2. R π(a|s,θ ∗ (x))∥∇ x logπ B (a|s,θ ∗ (x),x)−∇ x logπ(a|s,θ ∗ (x))∥ da≤ ε fd Assumption 3.1 arises because of the limited capacity of the policy classΘ. If we can ensure a sufficiently rich policy class such that all Boltzmann policies can be represented by someθ ∈ Θ, then ε kl and ε fd can be driven to zero. Lemma 3.2. LetU π (s,θ,x)be the gradient shifted value function andW π (s,a,θ,x)be the gradient shifted Q-value function. Letθ ∗ (x)be the optimal policy parameter for the entropy regularized RL objective function (Eq. (1)). 1. The following recurrence relation is satisfied by the functions U π and W π : U π (s,θ ∗ (x),x) = Z π B (a|s,θ ∗ (x),x) ∇r(s,a,x) + γE s ′ ∼P (·|s,a) [U π (s ′ ,θ ∗ (x),x)] da W π (s,a,θ ∗ (x),x) =∇r(s,a,x) + γE s ′ ∼P (·|s,a) [U π (s ′ ,θ ∗ (x),x)] (8) 4 2. U π (s,θ ∗ (x),x)andW π (s,a,θ ∗ (x),x)act as surrogate for∇V π,B (s,θ ∗ (x),x)and ∇Q π (s,a,θ ∗ (x),x) with the following error bound: ∥U π (s,θ ∗ (x),x)−∇V π,B (s,θ ∗ (x),x)∥≤ O(τ (ε kl + ε fd )) ∥W π (s,a,θ ∗ (x),x)−∇Q π (s,a,θ ∗ (x),x)∥≤ O(τ (ε kl + ε fd )) (9) Here,ε kl andε fd are errors due to unrealizable policy class as defined in Assumption3.1andτis the temperature parameter defined for the Boltzmann policy. A proof of Lemma 3.2 is provided in the Appendix C.5. The recurrence relations provided for the gradient shifted value functions help us in obtaining their estimate using a Q-learning type algorithm by considering the gradient of the reward function (∇r(s,a,x)) as reward. Moreover,U π (s,θ ∗ (x),x) andW π (s,a,θ ∗ (x),x)becomes exactly equal to∇V π,B (s,θ ∗ (x),x)and∇Q π (s,a,θ ∗ (x),x)re- spectively when the policy class is realizable andε kl ,ε fd = 0(Assumption 3.1). In the next subsection, we will discuss our hypergradient theorem. 3.2 Approximate Hypergradient Theorem The hypergradient of the outer level objective function (φ(x,θ ∗ (x)) ) w.r.t. the reward parameterx provided by (Chakraborty et al., 2024) involves the gradient of the optimal solution of the inner level optimization problem (∇θ ∗ (x)). The expression for∇θ ∗ (x)obtained using the Implicit Function Theorem (Lorraine et al., 2020) introduces a Hessian-based term in the hypergradient. However, we exploit the optimality of the Boltzmann policy (Eq.(2)) for the entropy regularized discounted performance metric (Eq.(1)) to remove the Hessian in the expression. We provide the expression of the hypergradient in Theorem 3.3. Further, we provide the expression of approximate hypergradient in Eq. (10) using gradient shifted value functions defined in Section 3.1. ∇ ̃ φ(x,θ ∗ (x)) = E d i ∼P (d i ,θ ∗ (x)) [∇ x l(d i I−1 0 ,x)] + τ −1 E d i ∼P (d i ,θ ∗ (x)) h l(d i I−1 0 ,x) X i X t (W π (s i t ,a i t ,θ ∗ (x),x)− U π (s i t ,θ ∗ (x),x)) i (10) Theorem 3.3. The hypergradient (∇φ(x,θ ∗ (x))) for the outer objective functionφ(x,θ ∗ (x))is expressed as ∇φ(x,θ ∗ (x)) =E d i ∼P (d i ,θ ∗ (x)) [∇ x l(d i I−1 0 ,x)] + E d i ∼P (d i ,θ ∗ (x)) h l(d i I−1 0 ,x) X i X h ∇ logπ(a i h |s i h ,θ ∗ (x)) i (11) Let the approximate hypergradient be defined in Eq. 10, then the approximation error is given by Ψ(x,θ ∗ (x))) = ∇φ(x,θ ∗ (x))−∇ ̃ φ(x,θ ∗ (x))and∥Ψ(x,θ ∗ (x)))∥ = O(ε fd ) + O(ε kl ). Further, Iis the number of trajectories,His the length of each trajectories,ε fd andε kl are errors due to unrealizable policy class as defined in Assumption 3.1,τis the temperature coefficient from Eq.(2) and|l(d i I−1 0 ,x)| ≤ C l (Lemma C.2). Further,W π (s,a,θ ∗ (x),x)andU π (s,θ ∗ (x),x)are the gradient-shifted Q-value function and the gradient-shifted value function defined in Eq. (7). Proof. A detailed proof of the theorem is presented in Appendix C.8. Remark 3.4. We obtain an approximate hypergradient for the outer level objective because the policy class is not guaranteed to be realizable. The hypergradient approximation error is of the order ofO(ε fd ) + O(ε kl ). If the policy class is realizable, the error would disappear. Fur- ther, the expression for the hypergradient defined by (Yang et al., 2025) for finite spaces using optimality of Boltzmann policy includes the gradient of Q-value (∇Q π ) and the value function (∇V π ). Because of non-realizability, the exact hypergradient contains the gradient of the Boltz- mann value function (∇V π,B ). The Boltzmann value function is related to value function as V π (s,θ,x) = V π,B (s,θ,x)− τD KL (π(·|s,θ)||π B (·|s,θ,x))(Lemma C.4), and therefore, doesn’t yield feasible recursive definition in conjunction with gradient of Q-value function because of theD KL (π(·|s,θ)||π B (·|s,θ,x))term. Hence, the approximate hypergradient was defined using gradient shifted value functions (U π and W π ), which act as a surrogate for∇V π,B and∇Q π . 5 3.3 Approximate Hypergradient Optimization (AHO) Algorithm Algorithm 1 describes our proposed bilevel RL algorithm called Approximate Hypergradient Opti- mization (AHO). A more detailed description of AHO is provided in Appendix B. The update rule for the inner level problem uses the policy gradient theorem (Sutton et al., 1999) and is provided as Eq. (12). ∇ θ J (θ k t ,x t ,B) = 1 B B−1 X j=0 ∇ θ logπ(a j |s j ,θ k t ) ˆ Q π y (s j ,a j ,θ k t ,x t )(12) In Eq.(12), we considerBsamples of a state-action pair for the first term of the gradient andB trajectories of lengthHfor the second term of the gradient. Further, ˆ Q π y is an estimator of Q-value functionQ π with parameteryconsidering reward asr(s,a,x t )− τ logπ(a|s,θ k t ). Parametery is updated using the Q-learning type Algorithm 4 given in Appendix B. The update rule for the outer level objective is based on Theorem 3.3 and is provided as Eq.(13). Also, the definition of ∇ ̃ φ (i) (x t ,θ K t ,B) and∇ ̃ φ (i) (x t ,θ K t ,B) is provided in Eq. (14). ∇ ̃ φ(x t ,θ K t ,B) =∇ ̃ φ (i) (x t ,θ K t ,B) + 1 τ ∇ ̃ φ (i) (x t ,θ K t ,B) (13) ∇ ̃ φ (i) (x t ,θ K t ,B) := 1 B B−1 X j=0 ∇ x l(d i,j I−1 0 ,x) ∇ ̃ φ (i) (x t ,θ K t ,B) := 1 B B−1 X j=0 l(d i,j I−1 0 ,x t ) X i X h c W π off,w (s i,j h ,a i,j h ,θ K t ,x t ) − b U π off,z (s i,j h ,θ K t ,x t ) (14) In Eq.(14), we considerBsamples of trajectory of horizon lengthHwithj-th trajectory denoted as d i,j =s i,j t ,a i,j t H−1 h=0 . Further, c W π off,w is an estimator ofW π off with parameterw. The parameter wis updated using the Bellman error based on recursion forW π off in Eq.(15). Also, b U π off,w is an estimator ofU π off with parameterzandzis also updated in the same manner aswusing the recursion for U π in Eq. (15). U π off (s,θ ∗ (x),x) = Z π(a|s,θ ∗ (x)) ∇r(s,a,x) + γE s ′ ∼P (·|s,a) [U π off (s ′ ,θ ∗ (x),x)] da W π off (s,a,θ ∗ (x),x) =∇r(s,a,x) + γE s ′ ∼P (·|s,a) [U π off (s ′ ,θ ∗ (x),x)] (15) Remark 3.5. We have defined quantitiesU π off (s,θ,x)andW π off (s,a,θ,x)in Eq.(15)based on U π (s,θ,x)andW π (s,a,θ,x)from Lemma 3.2 because the former dependsπ(a|s,θ ∗ (x))which can be obtained from the Algorithm 1 while the latter depends onπ B (a|s,θ ∗ (x),x)which cannot be obtained for unrealizable policy class. Algorithm 1 Approximate Hypergradient Opti- mization (AHO) Algorithm Input: State spaceS, Action spaceA, Num- ber of outer level updatesT, Number of inner level updatesK, Batch sizeB, Horizon length H. Initial policy parametersθ 0 0 . Initial reward parameter x 0 . for t∈0,...,T − 1 do for k ∈0,...,K− 1 do θ k+1 t = θ k t + α t ∇ θ J (θ k t ,x t ,B) end for x t+1 = x t − β t ∇ ̃ φ(x t ,θ K t ,B) end for Output: x T In the next section, we show through our theo- retical analysis that even with an approximate hypergradient, the first-order stationary conver- gence guarantee still holds for our proposed al- gorithm. 4 Theoretical Analysis In this section, first, we will discuss the assumptions taken by us to provide the iteration and sample complexity bounds. Subsequently, we will provide a proof sketch for our main theorem (Theorem 4.6) for the convergence rates. 6 Assumption 4.1. Letπ(a|s,θ)be the parameterized policy,V π (s,θ,x)andQ π (s,a,θ,x)be the corresponding value function and Q-value function, andr(s,a,x)be the reward function for the reward parameter x. These functions satisfy the following Lipschitz continuity condition: 1. ∥V π (s,θ 1 ,x 1 )− V π (s,θ 2 ,x 2 )∥≤ L x,V ∥x 1 − x 2 ∥ + L θ,V ∥θ 1 − θ 2 ∥ 2. ∥Q π (s,a,θ 1 ,x 1 )− Q π (s,a,θ 2 ,x 2 )∥≤ L x,Q ∥x 1 − x 2 ∥ + L θ,Q ∥θ 1 − θ 2 ∥ 3. ∥π(a|s,θ 1 )− π(a|s,θ 2 )∥≤ L π ∥θ 1 − θ 2 ∥ 4. ∥ logπ(a|s,θ 1 )− logπ(a|s,θ 2 )∥≤ L π,log ∥θ 1 − θ 2 ∥ 5. |r(s,a,x 1 )− r(s,a,x 2 )|≤ L r ∥x 1 − x 2 ∥ Assumption 4.1 is a common regularity assumption for convergence in the bilevel optimization literature (Gaur et al., 2025; Grazzi et al., 2023; Chen et al., 2024). Assumption 4.2. There exist constantsR max > 0andC log > 0such that, for alls ∈ S,a ∈ A, θ ∈ Θ, and x∈X such that|r(s,a,x)|≤ R max and| logπ(a|s,θ)|≤ C log . The boundedness of rewards and log-probabilities is imposed to ensure that the regularized return, value functions, and preference-based objectives appearing in the bilevel formulation are well-defined and uniformly bounded. The reward boundedness assumption is standard in discounted RL (Ganesh et al., 2025; Liu et al., 2020; Chen and Zhao, 2023) and prevents the cumulative reward from diverging. The log-probability boundedness assumption prevents degeneracy due to actions receiving zero or arbitrarily small probability, which would make log-policy terms infinite or unbounded. Together, these assumptions imply that the per-step regularized reward is bounded, and hence the discounted return is finite for every policy in the considered class. Assumption 4.3. Letθbe the policy parameter andxbe the reward function parameter. Let the estimated Q-value function be parameterized byy. Because of the limitation of the parameterization used, the following approximation error exists between the estimated and actual Q-value function min y E s,a ˆ Q π y (s,a,θ,x)− Q π (s,a,θ,x) 2 ≤ ε approx (16) Assumption 4.3 is a standard assumption in RL literature (Fu et al., 2021; Wang et al., 2020; Gaur et al., 2024). It is not possible to ensure that the function approximator class used to learn the actual Q-value function will be able to learn the Q-value function with zero errors. Assumption 4.4. Let the Polyak-Lojasiewicz (PL) condition for a differentiable function f be defined as: 1 2 ∥∇f (x)∥ 2 ≥ μ(f (x)− f ∗ )(17) Here,μ > 0is a constant andf ∗ = min x f (x). We assume that−J (θ,x)satisfies PL condition w.r.t. parameter θ. PL-type conditions are widely used in nonconvex bilevel optimization (Kwon et al., 2024; Chen et al., 2024). In parameterized bilevel RL, Gaur et al. (2025) also relies on a PL-type condition. More precisely, prior penalty-based methods impose PL on an auxiliary objective that combines the upper- and lower-level functions. In contrast, we remove any PL-type requirement involving the upper-level objective and assume PL only for the original lower-level loss. This condition relates the lower-level gradient norm to its global optimality gap and enables geometric convergence of the inner optimization; it does not require uniqueness of the lower-level solution. Assumption 4.5. For eachx 0 ∈ Xvisited by the outer-level algorithm, there existsθ 0 ∈ arg min θ∈Θ −J (x 0 ,θ)such that∇ θ J (x 0 ,θ 0 ) = 0and∇ 2 θ J (x 0 ,θ 0 )is nonsingular. Consequently, by the implicit function theorem (Lorraine et al., 2020), there exist neighborhoodsU x 0 ⊆Xofx 0 andV θ 0 ⊆ Θofθ 0 , and a continuously differentiable local selectionθ ⋆ : U x 0 → V θ 0 satisfying θ ⋆ (x 0 ) = θ 0 and∇ θ J (x,θ ⋆ (x)) = 0for allx∈ U x 0 . Moreover, we assume that this local selection has uniformly bounded sensitivity on the visited neighborhood, i.e., there existsC θ > 0such that ∥∇ x θ ⋆ (x)∥≤ C θ , ∀x∈ U x 0 We define the outer-level objective locally byΦ(x) := φ(x,θ ⋆ (x)) for x∈ U x 0 . 7 This assumption is substantially weaker than requiring the inner-level problem to have a globally unique minimizer (Chakraborty et al., 2024). We do not assume that the response mapΘ ∗ (x) = arg min θ −J (θ,x)is single-valued on the whole domain. Instead, we only require that the minimizer selected by the algorithm is locally isolated and nondegenerate. Hence, the inner-level problem may still admit multiple global minimizers, possibly corresponding to different branches. The assumption merely ensures that the selected branch is stable under small perturbations of the upper-level variable and can therefore be locally represented as a differentiable function of x. This is a standard local regularity condition (Lorraine et al., 2020; Mackay et al., 2019) needed for implicit-differentiation- based analysis; without such stability, the inner-level response may jump or bifurcate, and the outer objective along a selected solution would not admit a meaningful gradient characterization. Theorem 4.6. Suppose Assumption 3.1 and Assumption 4.1 to 4.5 hold true. Then, Algorithm 1 obtains the following convergence rate : 1 T T−1 X t=0 ∥∇Φ(x t )∥ 2 ≤O 1 T + O(ε 2 kl ) + O(ε 2 fd ) + O 1 B + O(ε 2 approx ) + O(exp −K ) + O γ 2H B + O(γ 2H ) + O(ε approx ) + O(ε kl ) (18) By choosing,T = Θ(ε −1 ),B = Θ(ε −1 ),K = Θ(log(ε −1 )), andH = Θ(log(ε −1 )/ log(γ −1 )), we obtain the iteration complexity ofT = O(ε −1 )and the sample complexity ofT.K.B.H = ̃ O(ε −2 ). Therefore, we have: 1 T T−1 X t=0 ∥∇Φ(x t )∥ 2 ≤ O(ε) + O(ε approx ) + O(ε fd ) + O(ε kl ) (19) Here,ε approx is the Q-value function approximation error defined in Assumption 4.3. Further,ε fd andε kl are errors introduced because of the limited policy class as defined in Assumption 3.1.Bis the batch size used for empirical expectation,His the horizon length used for estimation of infinite horizon quantities,Kis the number of gradient updates for inner level objective optimization,Tis the number of gradient updates for outer level objective, andτis the temperature coefficient defined in Boltzmann policy (Eq. (2)). Remark 4.7. We obtain a sample complexity of ̃ O(ε −2 )for the Algorithm 1, which is an improvement over the state-of-the-art sample complexity for the bilevel RL algorithms, whereas (Gaur et al., 2025)’s penalty-based bilevel RL algorithm obtains a sample complexity of ̃ O(ε −3 ). The algorithm proposed by (Gaur et al., 2025) used an outer level gradient withO(σ)approximation error, and the gradient approximation error is controlled by anO(σ 2 )term, and sampling error is controlled by an O(1/(σ 2 B)). The tradeoff between gradient approximation error and sampling error drives up the sample complexity for their method. In our case, we use an approximate hypergradient withO(ε fd ) error, which can be removed with a rich enough policy class as explained in Remark 4.8. Hence, our algorithm’s sample complexity bound has two dominant error terms:O(1/B)sampling error and O(1/T ) outer level optimization error. This allows us to obtain a better sample complexity. Remark 4.8. In Theorem 4.6, the norm of the gradient of the outer level objective function depends on term error terms likeO(ε 2 kl ),O(ε 2 fd ), andO(ε approx ). WhileO(ε approx )is a standard term in the literature of RL, the other two terms appear because the policy class cannot be guaranteed to be realizable and contain all Boltzmann policies. If the policy class is realizable, then error terms O(ε 2 kl ), O(ε 2 fd ) would be zero. A detailed proof of the Theorem 4.6 is provided in the Appendix D.10. The rest of the section gives a proof sketch of Theorem 4.6. Using theL-smoothness of the outer level objective function(Φ(x), we obtain the following error decomposition: Φ(x t+1 )≤ Φ(x t )− β 2 − β 2 L ∥∇Φ(x t )∥ 2 + β 2 + β 2 L ∥∇ ̃ φ(x t ,θ K t ,B)−∇Φ(x t )∥ 2 (20) Subsequently, we decompose the hypergradient estimation error∥∇ ̃ φ(x t ,θ K t ,B) − ∇Φ(x t )∥ 2 into gradient estimation error∥∇ ̃ φ(x t ,θ K t ) − ∇Φ(x t )∥ and sampling error∥∇ ̃ φ(x t ,θ K t ,B) − ∇ ̃ φ(x t ,θ K t )∥ as given in Eq. (21). ∥∇ ̃ φ(x t ,θ K t ,B)−∇Φ(x t )∥≤∥∇ ̃ φ(x t ,θ K t )−∇Φ(x t )∥ +∥∇ ̃ φ(x t ,θ K t ,B)−∇ ̃ φ(x t ,θ K t )∥ (21) 8 Here, the gradient estimation error expands into approximate gradient estimation term∥∇ ̃ φ(x t ,θ K t )− ∇ ̃ φ(x t ,θ ∗ (x t ))∥and hypergradient approximation error∥∇ ̃ φ(x t ,θ ∗ (x t )−∇Φ(x t )∥as given in Eq. (22). ∥∇ ̃ φ(x t ,θ K t )−∇Φ(x t )∥≤∥∇ ̃ φ(x t ,θ K t )−∇ ̃ φ(x t ,θ ∗ (x t ))∥ +∥∇ ̃ φ(x t ,θ ∗ (x t )−∇Φ(x t )∥ (22) Lemma 4.9. Letθ K t be the value of the policy parameter aftertiterations of outer loop of Algorithm 1 and θ ∗ (x t ) = arg min θ −J (θ,x t ). Then, the following bound holds for∥θ K t − θ ∗ (x t )∥: ∥θ K t − θ ∗ (x t )∥ 2 ≤ O(exp −K ) + O 1 B + O γ 2H B + O(γ 2H ) + O(ε approx )(23) Here,ε approx is defined in Assumption 4.3.Bis the batch size used for empirical expectation,His the horizon length used for estimation of infinite horizon quantities,Kis the number of gradient updates for inner level objective optimization, and γ is the discount factor for the MDP. Using Lemma D.5, we show that the approximate gradient estimation error depends on the inner level iterate sub-optimality gap∥θ K t − θ ∗ (x t )∥. The inner level iterate sub-optimality gap is proven in Lemma 4.9. A detailed proof of the Lemma 4.9 is given in the Appendix D.6. Lemma 4.9 uses the Quadratic Growth condition (see Definition 4.10) to connect iterate suboptimality gap to value suboptimality gapJ (θ K t ,x t )− J (θ ∗ (x t ),x t ). Further, the value suboptimality gap expands into gradient estimation error ofO(exp −K )because of the PL assumption (Assumption 4.4) on the inner level objective and sampling error of O(1/B). Definition 4.10. (Quadratic Growth) Letfbe proper, lower semicontinuous, and bounded below with unique minimizerx ∗ .fis said to satisfy the Quadratic Growth condition iff (x)− f (x ∗ ) ≥ μ 2 ∥x− x ∗ ∥ 2 holds true with μ > 0. One of departures from the analysis of (Gaur et al., 2025) comes from our hypergradient approxima- tion error (∥∇ ̃ φ(x t ,θ ∗ (x t )−∇Φ(x t )∥) ofO(ε kl ) + O(ε fd )(Theorem 3.3). This error disappears in the case of sufficient rich policy class. In the analysis of Gaur et al. (2025), a similar term relies on the gradient approximation error ofO(σ 2 ), which, combined with their sampling error ofO(1/(σ 2 B)), leads to a tradeoff and drives up the sample complexity. Our algorithm doesn’t suffer from such a tradeoff and thus obtains better sample complexity. Finally, the samplping error term (∥∇ ̃ φ(x t ,θ K t ,B)−∇ ̃ φ(x t ,θ K t )∥ ) from Eq.(21)is present because of using the estimators b U π off,z (s,θ K t ,x t )and c W π off,z (s,a,θ K t ,x t )instead of using gradient shifted value functionsU π (s,θ K t ,x t ) andW π (s,a,θ K t ,x t ) . The rationale for using the estimators is ex- plained in Remark 3.5. Here, the error introduced by using estimator b U π off,z ((s,θ K t ,x t ))instead of U π off,z ((s,θ K t ,x t )) is handled by Q-value convergence result from (Gaur et al., 2024) as parameterz is updated using Bellman error. Further, we prove using Lemma D.9 that the error introduced because of usingU π off (s,θ K t ,x t ) instead ofU π (s,θ K t ,x t ) is a function of∥θ K t − θ ∗ (x t )∥ and is handled using Lemma 4.9. In a similar fashion, the error introduced by using c W π off,z (s,a,θ K t ,x t )instead of W π (s,a,θ K t ,x t )is handled. All the errors discussed above allow us to find a bound on the sampling error∥∇ ̃ φ(x t ,θ K t ,B)−∇ ̃ φ(x t ,θ K t )∥. This completes the analysis. 5 Conclusion In this work, we provide a scalable bilevel RL algorithm using the optimality of the Boltzmann policy for the entropy regularized discounted reward objective function. We provide conditions under which the optimality of the Boltzmann policy could be used in the parameterized policy setting. Our proposed AHO algorithm uses an approximate hypergradient of the outer-level objective function. This allowed us to improve the previous best sample complexity of ̃ O(ε −3 )(Gaur et al., 2025) to obtain a state-of-the-art sample complexity of ̃ O(ε −2 ) . Further, by using a hypergradient-based approach instead of a penalty-based formulation, we were able to remove the assumption of the PL condition on the outer-level objective function as used by the prior state-of-the-art bilevel RL algorithm. 9 References Bradley, R. A. and Terry, M. E. (1952). Rank analysis of incomplete block designs: I. the method of paired comparisons. Biometrika, 39(3/4):324–345. Chakraborty, S., Bedi, A., Koppel, A., Wang, H., Manocha, D., Wang, M., and Huang, F. (2024). PARL: A unified framework for policy alignment in reinforcement learning from human feedback. In The Twelfth International Conference on Learning Representations. Chen, L., Xu, J., and Zhang, J. (2024). On finding small hyper-gradients in bilevel optimization: Hardness results and improved analysis. In The Thirty Seventh Annual Conference on Learning Theory, pages 947–980. PMLR. Chen, T., Sun, Y., Xiao, Q., and Yin, W. (2022). A single-timescale method for stochastic bilevel optimization. In International Conference on Artificial Intelligence and Statistics, pages 2466–2488. PMLR. Chen, T., Sun, Y., and Yin, W. (2021). Closing the gap: Tighter analysis of alternating stochastic gradient methods for bilevel problems. Advances in Neural Information Processing Systems, 34:25294–25307. Chen, X. and Zhao, L. (2023). Finite-time analysis of single-timescale actor-critic. Advances in Neural Information Processing Systems, 36:7017–7049. Christiano, P. F., Leike, J., Brown, T., Martic, M., Legg, S., and Amodei, D. (2017). Deep rein- forcement learning from human preferences. Advances in neural information processing systems, 30. Fu, Z., Yang, Z., and Wang, Z. (2021). Single-timescale actor-critic provably finds globally optimal policy. In International Conference on Learning Representations. Ganesh, S., Chen, J., Mondal, W. U., and Aggarwal, V. (2025). Order-optimal global convergence for actor-critic with general policy and neural critic parametrization. In The 41st Conference on Uncertainty in Artificial Intelligence. Gaur, M., Bedi, A., Wang, D., and Aggarwal, V. (2024). Closing the gap: Achieving global conver- gence (last iterate) of actor-critic under markovian sampling with neural network parametrization. In International Conference on Machine Learning, pages 15153–15179. PMLR. Gaur, M., Singh, U., Bedi, A. S., Pasupathy, R., and Aggarwal, V. (2025). On the sample complexity bounds of bilevel reinforcement learning. In The Thirty-ninth Annual Conference on Neural Information Processing Systems. Ghadimi, S. and Wang, M. (2018). Approximation methods for bilevel programming. arXiv preprint arXiv:1802.02246. Grazzi, R., Pontil, M., and Salzo, S. (2023). Bilevel optimization with a lower-level contraction: Optimal sample complexity without warm-start. Journal of Machine Learning Research, 24(167):1– 37. Hong, M., Wai, H.-T., Wang, Z., and Yang, Z. (2023). A two-timescale stochastic algorithm framework for bilevel optimization: Complexity analysis and application to actor-critic. SIAM Journal on Optimization, 33(1):147–180. Khanduri, P., Zeng, S., Hong, M., Wai, H.-T., Wang, Z., and Yang, Z. (2021). A near-optimal algo- rithm for stochastic bilevel optimization via double-momentum. Advances in neural information processing systems, 34:30271–30283. Kwon, J., Kwon, D., Wright, S., and Nowak, R. D. (2023). A fully first-order method for stochastic bilevel optimization. In International Conference on Machine Learning, pages 18083–18113. PMLR. Kwon, J., Kwon, D., Wright, S., and Nowak, R. D. (2024). On penalty methods for nonconvex bilevel optimization and first-order stochastic approximation. In The Twelfth International Conference on Learning Representations. 10 Li, J., Gu, B., and Huang, H. (2022). A fully single loop algorithm for bilevel optimization without hessian inverse. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 36, pages 7426–7434. Liu, B., Ye, M., Wright, S., Stone, P., and Liu, Q. (2022). Bome! bilevel optimization made easy: A simple first-order approach. Advances in neural information processing systems, 35:17248–17262. Liu, R., Liu, X., Yuan, X., Zeng, S., and Zhang, J. (2021). A value-function-based interior-point method for non-convex bi-level optimization. In International conference on machine learning, pages 6882–6892. PMLR. Liu, Y., Zhang, K., Basar, T., and Yin, W. (2020). An improved analysis of (variance-reduced) policy gradient and natural policy gradient methods. Advances in Neural Information Processing Systems, 33:7624–7636. Lorraine, J., Vicol, P., and Duvenaud, D. (2020). Optimizing millions of hyperparameters by implicit differentiation. In International conference on artificial intelligence and statistics, pages 1540–1552. PMLR. Mackay, M., Vicol, P., Lorraine, J., Duvenaud, D., and Grosse, R. (2019). Self-tuning networks: Bilevel optimization of hyperparameters using structured best-response functions. In International Conference on Learning Representations. Nachum, O., Norouzi, M., Xu, K., and Schuurmans, D. (2017). Bridging the gap between value and policy based reinforcement learning. Advances in neural information processing systems, 30. Shen, H. and Chen, T. (2023). On penalty-based bilevel gradient descent method. In International conference on machine learning, pages 30992–31015. PMLR. Shen, H., Yang, Z., and Chen, T. (2025). Principled penalty-based methods for bilevel reinforcement learning and rlhf. Journal of Machine Learning Research, 26(114):1–49. Sow, D., Ji, K., and Liang, Y. (2022). On the convergence theory for hessian-free bilevel algorithms. Advances in Neural Information Processing Systems, 35:4136–4149. Sutton, R. S., McAllester, D., Singh, S., and Mansour, Y. (1999). Policy gradient methods for reinforcement learning with function approximation. Advances in neural information processing systems, 12. Tassa, Y., Doron, Y., Muldal, A., Erez, T., Li, Y., Casas, D. d. L., Budden, D., Abdolmaleki, A., Merel, J., Lefrancq, A., et al. (2018). Deepmind control suite. arXiv preprint arXiv:1801.00690. Thoma, V., Pásztor, B., Krause, A., Ramponi, G., and Hu, Y. (2024). Contextual bilevel reinforcement learning for incentive alignment. Advances in Neural Information Processing Systems, 37:127369– 127435. Wang, L., Cai, Q., Yang, Z., and Wang, Z. (2020). Neural policy gradient methods: Global optimality and rates of convergence. In International Conference on Learning Representations. Yang, J., Ji, K., and Liang, Y. (2021). Provably faster algorithms for bilevel optimization. Advances in Neural Information Processing Systems, 34:13670–13682. Yang, Y., Gao, B., and Yuan, Y.-x. (2025). Bilevel reinforcement learning via the development of hyper-gradient without lower-level convexity. In International Conference on Artificial Intelligence and Statistics, pages 4780–4788. PMLR. Yang, Y., Xiao, P., and Ji, K. (2023). AchievingO(ε −1.5 )complexity in hessian/jacobian-free stochastic bilevel optimization. Advances in Neural Information Processing Systems, 36:39491– 39503. 11 A Related Work A.1 Bilevel optimization Bilevel optimization has been extensively studied for hyperparameter optimization, meta-learning, and hierarchical decision-making. Early work, such as (Ghadimi and Wang, 2018), established sample-complexity guarantees for hypergradient-based methods under convex inner-level assump- tions, while (Chen et al., 2021, 2022) developed general stochastic and single-timescale bilevel frameworks. Iteration complexity was further improved using momentum-based methods (Yang et al., 2021; Khanduri et al., 2021), though these approaches rely on Hessian-based updates and are computationally expensive. To address this, several Hessian-free and fully first-order methods have been proposed (Li et al., 2022; Sow et al., 2022; Kwon et al., 2023; Liu et al., 2022), along with penalty-based formulations that simplify algorithm design (Shen and Chen, 2023; Kwon et al., 2024) and value-function reformulations (Liu et al., 2021). These advances lay the foundation for the algorithm development in bilevel RL. A.2 Bilevel RL Bilevel RL has emerged as a natural framework for hierarchical decision-making in meta-RL, incentive design, and RL-HF. Early work established stochastic approximation and two-timescale bilevel frameworks for RL, with finite-time guarantees and applications to actor–critic methods (Hong et al., 2023). Penalty-based formulations tailored to RL and RL-HF were later proposed in (Shen et al., 2025), providing convergence guarantees under smoothness and regularity assumptions. Subsequent studies analyzed statistical and modeling challenges in bilevel RL. (Gaur et al., 2025) derived state-of-the-art sample-complexity bounds for bilevel RL, while contextual and hypergradient- based extensions were explored in (Thoma et al., 2024). More recent works relax inner-level convexity assumptions (Yang et al., 2025; Chakraborty et al., 2024). (Chakraborty et al., 2024) provides a bilevel RL algorithm with Hessian-based hypergradient with iteration complexity ofO(ε −1 ). Later, (Yang et al., 2025) provides a scalable Hessian-free hypergradient-based algorithm for finite state and action space and obtains a slightly worse iteration complexity ofO(ε −1.5 ). The optimality of the Boltzmann policy for the regularized RL objective function helped (Yang et al., 2025) to make the algorithm Hessian-free for finite state and action space with a non-parameterized policy. In our work, we propose a Hessian-free algorithm for continuous state and action spaces with a parameterized policy. The usage of parameterized policy leads to issues, and we discuss the conditions under which we can resolve those issues and utilize the optimality of the Boltzmann policy for parameterized policy settings. B Full AHO Algorithm Implementation B.1 Pseudo code for AHO Algorithm 2 provides a full description of the Approximate Hypergradient Optimzation (AHO) algorithm. 12 Algorithm 2 Approximate Hypergradient Optimization (AHO) Algorithm 1:Input: State spaceS, Action spaceA, Reward functionr, Number of outer level updatesT, Number of inner level updatesK, Batch sizeB, Horizon lengthH. Initial policy parametersθ 0 0 . Initial reward parameter x 0 . 2: for t∈0,...,T − 1 do 3:for k ∈0,...,K− 1 do 4:Collect B episodesξ(θ k t ) B−1 i=0 using policy parameter θ k t 5:Obtain ˆ Q π y from Algorithm 3 with policy parameter θ k t 6:θ k+1 t = θ k t + α t ∇ θ J (θ k t ,x t ,B) 7:end for 8:Obtain c W π off,w and b U π off,z from Algorithm 4 with policy parameter θ K t andξ(θ K t ) B−1 i=0 9:Collect B episodesξ ′ (θ k t ) B−1 i=0 using policy 10: x t+1 = x t − β t ∇ ̃ φ(x t ,θ K t ,B)//Using ξ ′ (θ k t ) B−1 i=0 11: end for 12: Output: x T Algorithm 2 uses Algorithm 3 to obtain an estimator of the Q-value function. The Q-value estimator obtained is then used in Eq.(24)to update the policy parameter for the inner level optimization problem (Eq. (1)). Algorithm 3 Q-learning Algorithm 1:Input: State spaceS, Action spaceA, Reward functionr, Number of iterationsJ, Batch sizeB, Number of iterationsL,Bepisodesξ B−1 i=0 using policy parameterθ. Initial Q-value function Q 11 . 2: Sample B tuples (s,a,r,s ′ ) fromξ B−1 i=0 and store in bufferB. 3: for j ∈1,...,J do 4:Initialize Q-value function parameter y 0 5:for l∈1,...,L do 6:Sample (s,a,r,s ′ ) from bufferB 7:Sample a ′ ∼ π(·|s ′ ,θ) 8:Q tar = r− τ logπ(a|s,θ) + γQ jl (s ′ ,a ′ ) 9:y ′ l = y l−1 + β(Q tar − Q y l−1 (s,a))∇ y Q y l−1 (s,a) 10:y l = Γ y 0 ,(1−γ) −1 (y ′ l ) 11:end for 12:Let y = 1 L P L−1 l=0 y l and Q jL = Q y 13: end for 14: Output: Q JL ∇ θ J (θ k t ,x t ,B) = 1 B B−1 X j=0 ∇ θ π(a j |s j ,θ k t ) ˆ Q π y (s j ,a j ,θ k t ,x t )(24) Further, Algorithm 2 uses Algorithm 4 to obtain estimators for the off-policy gradient shifted value function b U π off,z (s,θ K t ,x t ) and off-policy gradient shifted Q-value function c W π off,w (s,a,θ K t ,x t ) . Later, those estimates are used in Eq.(27)to update the reward parameter for the outer level optimization problem (Eq. (3)). 13 Algorithm 4 Q-learning Algorithm for Gradient Shifted function W π and U π 1:Input: State spaceS, Action spaceA, Reward functionr, Number of iterationsJ, Batch sizeB, Number of iterationsL,Bepisodesξ B−1 i=0 using policy parameterθand reward parameterx, Initial gradient shifted value function U 11 . 2: Sample B tuples (s,a,s ′ ) fromξ B−1 i=0 and store in bufferB. 3: for j ∈1,...,J do 4:Initialize gradient shifted value function parameter and Q-value function parameterz 0 and w 0 respectively. 5:for l∈1,...,L do 6:Sample (s,a,s ′ ) from bufferB 7:Sample a ′ ∼ π(·|s ′ ,θ) 8:U tar =∇ x r(s,a,x) + γU jl (s ′ ) 9:z ′ l = z l−1 + β(U tar − U z l−1 (s))∇ z U z l−1 (s) 10:z l = Γ z 0 ,(1−γ) −1 (Z ′ l ) 11:w ′ l = w l−1 + β(U tar − W w l−1 (s,a))∇ w W w l−1 (s,a) 12:w l = Γ w 0 ,(1−γ) −1 (w ′ l ) 13:end for 14:Let z = 1 L P L l=1 z l and U jL = U z 15:Let w = 1 L P L l=1 w l 16: end for 17: Output: W w and U JL ∇ ̃ φ(x t ,θ K t ,B) =∇ ̃ φ (i) (x t ,θ K t ,B) + 1 τ ∇ ̃ φ (i) (x t ,θ K t ,B)(25) ∇ ̃ φ (i) (x t ,θ K t ,B) := 1 B B−1 X j=0 ∇ x l(d ij I−1 0 ,x)(26) ∇ ̃ φ (i) (x t ,θ K t ,B) := 1 B B−1 X j=0 l(d i,j I−1 0 ,x t ) X i X t c W π off,w (s i,j t ,a i,j t ,θ K t ,x t ) − b U π off,z (s i,j t ,θ K t ,x t ) (27) Please note that Algorithm 3 and 4 are based on the Algorithm 1 from (Gaur et al., 2024). B.2 Empirical Results for AHO B.2.1 Bilevel Formulation of the Preference-Based RL Tasks We evaluate our method on walker-walk and cheetah-run from the DM Control suite (Tassa et al., 2018). Although these benchmarks are commonly studied as single-level RL tasks, we instantiate them as preference-based bilevel RL problems using the formulation in Section 2. Outer-level parameter. The outer-level parameterxdenotes the parameters of the learned reward functionr(s,a,x). We representr(s,a,x)using an ensemble of3fully-connected MLPs, where each MLP has3hidden layers of width256and atanhoutput activation. Each ensemble member contains approximately 1.3× 10 5 parameters. Inner-level policy optimization. For a fixed reward parameterx, the inner-level problem trains an entropy-regularized RL policy by optimizingJ (θ,x), as defined in Eq.(1). The resulting policy parameter is denoted by the single-valued localized selectionθ ∗ (x), as described in Assumption 4.5. Thus, the policy used for collecting trajectory segments and evaluating preferences is π θ ∗ (x) . Outer-level preference objective. The outer level optimizes the reward parameterxusing pairwise preference feedback over trajectory segments sampled fromP (d,θ ∗ (x)). In our experiments, we use the pairwise settingI = 2. For a labeled preference pair(d 0 ,l 0 ,d 1 ,l 1 ), wherel 1 = 1,l 0 = 0 indicates thatd 1 is preferred overd 0 , andl 0 = 1,l 1 = 0indicates thatd 0 is preferred overd 1 , the 14 outer-level loss is the negative Bradley–Terry log-likelihood: φ(x,θ ∗ (x)) =−E d 0 ,d 1 ,l 0 ,l 1 ∼P (·,θ ∗ (x)) h l 0 logP (d 0 ≻ d 1 | x) + l 1 logP (d 1 ≻ d 0 | x) i ,(28) where P (d a ≻ d b | x) = exp(R x (d a )) exp(R x (d a )) + exp(R x (d b )) , R x (d) = X (s t ,a t )∈d r(s t ,a t ,x).(29) Thus, the reward network is trained so that trajectory segments with larger preference labels receive larger learned cumulative reward. Preference feedback. Preference labels are generated by a scripted teacher that selects the trajectory segment with larger ground-truth return. Segment pairs are selected using a disagreement-based active-query strategy (Christiano et al., 2017), which chooses pairs with high variance across the reward ensemble. Each run uses a total feedback budget of500preference queries, with new feedback solicited every 20,000 environment steps after an initial unsupervised exploration phase. B.2.2 Experimental Setup We compare our proposed algorithm (AHO) against the bilevel RL algorithm of Gaur et al. (2025) on two continuous-control tasks from the DM Control suite (Tassa et al., 2018): walker-walk and cheetah-run. Walker-walk trains a planar bipedal robot to walk via joint torques; cheetah-run trains a planar cheetah to run via joint torques. Both algorithms are trained for500,000environment steps and evaluated every10,000steps over5random seeds. Hyperparameters that differ between the two methods are held identical wherever applicable, and shared values follow the implementation of (Gaur et al., 2025); the full list is given in Table 2. Table 2: Hyperparameters used in both walker-walk and cheetah-run. Values not listed in the upper block are AHO-specific; the upper block is shared with the baseline of Gaur et al. (2025). GroupHyperparameterValue Inner level Actor / critic learning rate α t 5× 10 −4 Hidden layers (actor / critic)2× 1024 Inner batch size1024 Inner updates per env step (K per outer iter implicit) 1 Outer level (reward) Reward learning rate β t 5× 10 −4 Reward optimizerAdam (β 1 =0.9,β 2 =0.999) Reward batch size B128 pairs Reward update steps per session up to 200 (early stop at 0.97 acc) Reward ensemble size3 Reward MLP3× 256, tanh output Preference data Segment / horizon length H50 Total feedback budget500 pairs Feedback intervalevery 20,000 env steps Active sampling disagreement (feed_type=1) Schedule Total env steps5× 10 5 Seed steps (random actions)1,000 Unsupervised exploration steps9,000 Discount factor (RL)0.99 AHO-specific Temperature τ100.0 Advantage discount γ AHO 0.99 All experiments were run on a single workstation equipped with an NVIDIA GeForce RTX 2080 Ti GPU (11 GB VRAM) and 64 GB of system memory. All seeds of each algorithm completes in approximately7hours of wall-clock time. Our implementation can be found at the URL:https: //anonymous.4open.science/r/AHO-Bilevel-RL-DBE2/ 15 Figure 1: Total episode reward during evaluation for walker-walk (left) and cheetah-run (right). Solid lines show the mean across5random seeds and shaded regions denote 95% confidence interval around mean. B.2.3 Results AHO obtains higher total evaluation reward than the bilevel baseline of Gaur et al. (2025) on both walker-walk and cheetah-run (Figure 1). This empirically supports the sample-complexity improvement predicted by our theoretical analysis. On the choice of baseline. We do not include PARL (Chakraborty et al., 2024) as a learning-curve baseline because PARL’s hypergradient computation requires forming and inverting the inner-loop Hessian of the policy objective. For the inner level policy used here (two MLPs of2× 1024hidden units, totaling∼ 2.6× 10 6 parameters per network), the Hessian has∼ 7× 10 12 entries and cannot be stored in the11GB of VRAM available on the RTX 2080 Ti, let alone inverted. Even with truncated Neumann or conjugate-gradient approximations, a single PARL outer step requires multiple Hessian-vector products through the full inner level actor–critic graph, whereas AHO’s outer step only requires a backward pass through the reward network (∼ 1.3×10 5 parameters). We therefore consider the Hessian-free design of AHO an empirical as well as a theoretical prerequisite for the network sizes used in modern preference-based RL, and report the comparison against the next-most-relevant baseline (Gaur et al., 2025), which is also Hessian-free. C Proof of Theorem 3.3 C.1 Lemmas for the Proof of Theorem 3.3 Lemma C.1 (Smoothness of the outer-level objective). Let Φ(x) = φ x,θ ⋆ (x) ,(30) whereθ ⋆ (x)is the localized selection map from Assumption 4.5, defined on a convex neighborhood U . Suppose that, for all relevant x i and θ i , ||∇ x φ(x 1 ,θ 1 )−∇ x φ(x 2 ,θ 2 )||≤ L φ,x ||x 1 − x 2 || + L φ,xθ ||θ 1 − θ 2 ||,(31) and ||∇ θ φ(x 1 ,θ 1 )−∇ θ φ(x 2 ,θ 2 )||≤ L φ,θx ||x 1 − x 2 || + L φ,θ ||θ 1 − θ 2 ||.(32) Suppose also that ||∇ θ φ(x,θ)||≤ C φ,θ .(33) Let F denote the lower-level loss and define H(x) :=∇ 2 θ F x,θ ⋆ (x) , B(x) :=∇ 2 θx F x,θ ⋆ (x) .(34) Suppose that there exist constants μ H ,C B ,L H ,L B > 0 such that σ min H(x) ≥ μ H , ||B(x)||≤ C B ,(35) 16 and ||H(x 1 )− H(x 2 )||≤ L H ||x 1 − x 2 ||, ||B(x 1 )− B(x 2 )||≤ L B ||x 1 − x 2 ||.(36) If ||∇θ ⋆ (x)||≤ C θ ,(37) then Φ is L Φ -smooth onU , where L Φ = L φ,x + L φ,xθ C θ + C φ,θ L ∇θ ⋆ + C θ (L φ,θx + L φ,θ C θ ),(38) with L ∇θ ⋆ = C B L H μ 2 H + L B μ H .(39) Proof. SinceU is convex and||∇θ ⋆ (x)||≤ C θ , the mean-value inequality gives ||θ ⋆ (x 1 )− θ ⋆ (x 2 )||≤ C θ ||x 1 − x 2 ||.(40) The lower-level stationarity condition satisfies ∇ θ F x,θ ⋆ (x) = 0.(41) Implicit differentiation therefore gives ∇θ ⋆ (x) =−H(x) −1 B(x).(42) Adding and subtracting H(x 2 ) −1 B(x 1 ) yields ||∇θ ⋆ (x 1 )−∇θ ⋆ (x 2 )||≤||H(x 1 ) −1 −H(x 2 ) −1 ||||B(x 1 )||+||H(x 2 ) −1 ||||B(x 1 )−B(x 2 )||. (43) Using H(x 1 ) −1 − H(x 2 ) −1 = H(x 1 ) −1 H(x 2 )− H(x 1 ) H(x 2 ) −1 (44) and||H(x) −1 ||≤ 1/μ H , we obtain ||∇θ ⋆ (x 1 )−∇θ ⋆ (x 2 )||≤ L ∇θ ⋆ ||x 1 − x 2 ||.(45) By the chain rule, ∇Φ(x) =∇ x φ x,θ ⋆ (x) +∇θ ⋆ (x) ⊤ ∇ θ φ x,θ ⋆ (x) .(46) Adding and subtracting the corresponding cross terms and applying the preceding bounds gives ||∇Φ(x 1 )−∇Φ(x 2 )||≤ L Φ ||x 1 − x 2 ||.(47) Hence, Φ is L Φ -smooth onU . Lemma C.2. Letd i I−1 i=0 be a collection ofItrajectories, where each trajectory is denoted by d = s t ,a t H−1 t=0 . Letl i ∈ 0, 1be a one-hot preference label satisfying P I−1 i=0 l i = 1 . Consider the multinomial Bradley–Terry preference model P (d i is preferred amongd j I−1 j=0 | x) = exp(R x (d i )) P I−1 j=0 exp(R x (d j )) , where R x (d) = P s t ,a t ∈d r(s t ,a t ,x). Define the preference log-likelihood l(d i I−1 i=0 ,x) := I−1 X i=0 l i logP (d i is preferred amongd j I−1 j=0 | x). Then, for every collectiond i I−1 i=0 and every x, |l(d i I−1 i=0 ,x)|≤ 2HR max + logI = C l Here, R max is the bound on the reward given in Assumption 4.2. 17 Proof. For notational simplicity, define p i (x) := P (d i is preferred amongd j I−1 j=0 | x) = exp(R x (d i )) P I−1 j=0 exp(R x (d j )) . Then l(d i I−1 i=0 ,x) = I−1 X i=0 l i logp i (x). Sincel i ∈0, 1and P I−1 i=0 l i = 1, there exists an indexi ⋆ ∈0,...,I − 1such thatl i ⋆ = 1and l i = 0 for all i̸= i ⋆ . Hence, l(d i I−1 i=0 ,x) = logp i ⋆ (x). Using the definition of p i ⋆ (x), logp i ⋆ (x) = R x (d i ⋆ )− log I−1 X j=0 exp(R x (d j )) . Using Assumption 4.2 for the boundedness of the reward function, we have|R x (d)|≤ HR max for all trajectories d, we have −HR max ≤ R x (d j )≤ HR max for all j. Therefore, I−1 X j=0 exp(R x (d j ))≤ I exp(HR max ), which implies log I−1 X j=0 exp(R x (d j )) ≤ logI + HR max . Also, I−1 X j=0 exp(R x (d j ))≥ exp(R x (d i ⋆ )), and therefore log I−1 X j=0 exp(R x (d j )) ≥ R x (d i ⋆ ). Thus, logp i ⋆ (x) = R x (d i ⋆ )− log I−1 X j=0 exp(R x (d j )) ≤ 0. Hence, |l(d i I−1 i=0 ,x)| =| logp i ⋆ (x)| =− logp i ⋆ (x). Using the previous upper bound on the log-sum-exp term, |l(d i I−1 i=0 ,x)| = log I−1 X j=0 exp(R x (d j )) − R x (d i ⋆ ) ≤ (logI + HR max ) + HR max = 2HR max + logI. The proof is complete. 18 Lemma C.3. LetΨ(x,θ ∗ (x))be the difference between the exact hypergradient (∇φ(x,θ ∗ (x))) and approximate hypergradient (∇ ̃ φ(x,θ ∗ (x))) of the outer level objective function (φ(x,θ)) as given in Eq.(48). The difference is bounded as∥Ψ(x,θ ∗ (x))∥≤ C l IHε fd . Here,∥l(d i I−1 0 ,x)∥≤ C l (Lemma C.2),Iis the number of trajectory,His the length of each trajectory,ε fd is the approximation error from Assumption 3.1. Ψ 1 (x,θ ∗ (x)) := E d i ∼P (d i ,θ ∗ (x)) h l(d i I−1 0 ,x) X i X t ∇ logπ(a i t |s i t ,θ ∗ (x))−∇ logπ B (a i t |s i t ,θ ∗ (x),x) i (48) Ψ 2 (x,θ ∗ (x)) := τ −1 E d i ∼P (d i ,θ ∗ (x)) h l(d i I−1 0 ,x) X i X t (∇Q π (s i t ,a i t ,θ ∗ (x),x)− W π (s i t ,a i t ,θ ∗ (x),x)) i + τ −1 E d i ∼P (d i ,θ ∗ (x)) h l(d i I−1 0 ,x) X i X t (U π (s i t ,θ ∗ (x),x)−∇V π,B (s i t ,θ ∗ (x),x)) i (49) Proof. First we will first bound on∥Ψ 1 (x,θ ∗ (x))∥: ∥Ψ 1 (x,θ ∗ (x))∥ ≤E d i ∼P (d i ,θ ∗ (x)) h ∥l(d i I−1 0 ,x) X i X t ∇ logπ(a i t |s i t ,θ ∗ (x))−∇ logπ B (a i t |s i t ,θ ∗ (x),x) ∥ i ≤C l X i X t E d i ∼P (d i ,θ ∗ (x)) h ∥∇ logπ(a i t |s i t ,θ ∗ (x))−∇ logπ B (a i t |s i t ,θ ∗ (x),x)∥ i ≤C l X i X t E s t ∼P (d i ,θ ∗ (x)) h Z π(a i t |s i t ,θ ∗ (x))∥∇ logπ(a i t |s i t ,θ ∗ (x)) −∇ logπ B (a i t |s i t ,θ ∗ (x),x)∥ da i t i ≤C l IHε fd (Using Assumption 3.1) (50) We will now find bound on∥Ψ 2 (x,θ ∗ (x))∥: ∥Ψ 2 (x,θ ∗ (x))∥ ≤τ −1 E d i ∼P (d i ,θ ∗ (x)) h l(d i I−1 0 ,x) X i X t ∥∇Q π (s i t ,a i t ,θ ∗ (x),x)− W π (s i t ,a i t ,θ ∗ (x),x)∥ i + τ −1 E d i ∼P (d i ,θ ∗ (x)) h l(d i I−1 0 ,x) X i X t ∥U π (s i t ,θ ∗ (x),x)−∇V π,B (s i t ,θ ∗ (x),x)∥ i ≤ 1 + γ 1− γ C l HI(L π,log C θ ε kl + ε fd ) (Using Lemma C.5) (51) Therefore, using Eq. (50) and Eq. (51): ∥Ψ(x,θ ∗ (x))∥≤∥Ψ 1 (x,θ ∗ (x))∥ +∥Ψ 2 (x,θ ∗ (x))∥ ≤ 1 + γ 1− γ C l HI(L π,log C θ ε kl + ε fd ) + C l IHε fd ∥Ψ(x,θ ∗ (x))∥ =O(ε kl ) + O(ε fd ) (52) Lemma C.4. LetV π (s,θ,x)be the value function andV π,B (s,θ,x)be the Boltzmann value function (Eq.(2)) for the policy parameterθand reward parameterx. The following relation is satisfied by these functions: V π (s,θ,x) = V π,B (s,θ,x)− τD KL (π(·|s,θ)||π B (·|s,θ,x))(53) 19 Here, π B (·|s,θ,x) is the Boltzmann policy. Proof. Using definition of V π (s,θ,x) and π B (a|s,θ,x): V π (s,θ,x) =E a∼π(·|s,θ) [−τ logπ(a|s,θ) + Q π (s,a,θ,x)] =E a∼π(·|s,θ) [−τ logπ(a|s,θ) + V π,B (s,θ,x) + τ logπ B (a|s,θ,x)] =V π,B (s,θ,x)− τD KL (π(·|s,θ)||π B (·|s,θ,x)) (54) Lemma C.5. LetU π (s,θ,x)be the gradient shifted value function andW π (s,a,θ,x)be the gradient shifted Q-value function. Letθ ∗ (x)be the optimal policy parameter for the entropy regularized RL objective function (Eq. (1)). 1. The following recurrence relation is satisfied by the functions U π and W π : U π (s,θ ∗ (x),x) = Z π B (a|s,θ ∗ (x),x) ∇r(s,a,x) + γE s ′ ∼P (·|s,a) [U π (s ′ ,θ ∗ (x),x)] da W π (s,a,θ ∗ (x),x) =∇r(s,a,x) + γE s ′ ∼P (·|s,a) [U π (s ′ ,θ ∗ (x),x)] (55) 2. U π (s,θ ∗ (x),x) andW π (s,a,θ ∗ (x),x)act as surrogate for∇V π,B (s,θ ∗ (x),x)and ∇Q π (s,a,θ ∗ (x),x) with the following error bound: ∥U π (s,θ ∗ (x),x)−∇V π,B (s,θ ∗ (x),x)∥≤ O(τ (ε kl + ε fd ) ∥W π (s,a,θ ∗ (x),x)−∇Q π (s,a,θ ∗ (x),x)∥≤ O(τ (ε kl + ε fd )) (56) Here,ε kl andε fd are errors due to unrealizable policy class as defined in Assumption3.1andτis the temperature parameter defined for the Boltzmann policy. Proof. We have, exp V π,B (s,θ ∗ (x),x) τ = Z exp Q π (s,a,θ ∗ (x),x) τ da(57) Taking the derivative of the equation: ∇ exp V π,B (s,θ ∗ (x),x) τ = Z ∇ exp Q π (s,a,θ ∗ (x),x) τ da =⇒ exp V π,B (s,θ ∗ (x),x) τ ∇V π,B (s,θ ∗ (x),x) τ = Z exp Q π (s,a,θ ∗ (x),x) τ ∇Q π (s,a,θ ∗ (x),x) τ da =⇒ ∇V π,B (s,θ ∗ (x),x) τ = Z exp Q π (s,a,θ ∗ (x),x) τ − V π,B (s,θ ∗ (x),x) τ ∇Q π (s,a,θ ∗ (x),x) τ da =⇒∇V π,B (s,θ ∗ (x),x) = Z π B (a|s,θ ∗ (x),x)∇Q π (s,a,θ ∗ (x),x) da (58) Using definition of Q π (s,a,θ ∗ (x),x): ∇V π,B (s,θ ∗ (x),x) = Z π B (a|s,θ ∗ (x),x) ∇r(s,a,x) + γE s ′ ∼P (·|s,a) [∇V π (s ′ ,θ ∗ (x),x)] da (59) 20 Using definition of V π (s,θ ∗ (x),x) and π B (a|s,θ ∗ (x),x): V π (s,θ ∗ (x),x) =E a∼π(·|s,θ ∗ (x)) [−τ logπ(a|s,θ ∗ (x)) + Q π (s,a,θ ∗ (x),x)] =E a∼π(·|s,θ ∗ (x)) [−τ logπ(a|s,θ ∗ (x)) + V π,B (s,θ ∗ (x),x) + τ logπ B (a|s,θ ∗ (x),x)] =V π,B (s,θ ∗ (x),x)− τD KL (π(·|s,θ ∗ (x))||π B (·|s,θ ∗ (x),x)) =⇒∇V π (s,θ ∗ (x),x) =∇V π,B (s,θ ∗ (x),x)− τ∇D KL (π(·|s,θ ∗ (x))||π B (·|s,θ ∗ (x),x)) (60) Let ∆(s,θ ∗ (x)) = τ∇D KL (π(·|s,θ ∗ (x))||π B (·|s,θ ∗ (x),x)). Using Eq. (60) in Eq. (59) we get: ∇V π,B (s,θ ∗ (x),x) = Z π B (a|s,θ ∗ (x),x) ∇r(s,a,x)− γE s ′ ∼P (·|s,a) [∆(s ′ ,θ ∗ (x)] + γE s ′ ∼P (·|s,a) [∇V π,B (s ′ ,θ ∗ (x),x)] da (61) ∇V π,B (s,θ ∗ (x),x) =E π ∞ X t=0 γ t (∇r(s t ,a t ,x)− γE s ′ ∼P (·|s,a) [∆(s ′ ,θ ∗ (x)]) s 0 = s,a t ∼ π B (·|s t ,θ ∗ (x))] (62) Let us define a new recursion based on Eq. (61) and introduce a new quantity U π (s,θ ∗ (x),x): U π (s,θ ∗ (x),x) = Z π B (a|s,θ ∗ (x),x) ∇r(s,a,x) + γE s ′ ∼P (·|s,a) [U π (s ′ ,θ ∗ (x),x)] da (63) U π (s,θ ∗ (x),x) = E π ∞ X t=0 γ t ∇r(s t ,a t ,x) s 0 = s,a t ∼ π B (·|s t ,θ ∗ (x))] (64) Using Eq. (62) and Eq. (64), let us find an upper bound on∥U π (s,θ ∗ (x),x)−∇V π (s,θ ∗ (x),x)∥: ∥U π (s,θ ∗ (x),x)−∇V π,B (s,θ ∗ (x),x)∥ ≤E π h ∞ X t=0 γ t (E s ′ ∼P (·|s,a) [∥∆(s ′ ,θ ∗ (x))∥] s 0 = s,a t ∼ π B (·|s t ,θ ∗ (x)) i (65) Let us find a bound on∥∆(s ′ ,θ ∗ (x))∥: ∥∆(s ′ ,θ ∗ (x))∥ (1) ≤τ∥∇D KL (π(·|s,θ ∗ (x))||π B (·|s,θ ∗ (x),x))∥ (2) ≤τ Z ∥∇π(a|s,θ ∗ (x))∥| logπ(a|s,θ ∗ (x))− logπ B (a|s,θ ∗ (x),x)| da + τ Z π(a|s,θ ∗ (x))∥∇ logπ(a|s,θ ∗ (x))−∇ logπ B (a|s,θ ∗ (x),x)∥ da (3) ≤τ Z π(a|s,θ ∗ (x))∥∇ logπ(a|s,θ ∗ (x))∥| logπ(a|s,θ ∗ (x))− logπ B (a|s,θ ∗ (x),x)| da + τε fd (4) ≤τL π,log C θ Z π(a|s,θ ∗ (x))| logπ(a|s,θ ∗ (x))− logπ B (a|s,θ ∗ (x),x)| da + τε fd (5) ≤τL π,log C θ ε kl + τε fd (66) 21 Here, in (3) we obtainε fd in the expression by using Assumption 3.1.2. In (4), we use As- sumption 4.1.4 and Assumption 4.5 to bound∥∇ logπ(a|s,θ ∗ (x))∥as∥∇ logπ(a|s,θ ∗ (x))∥ ≤ ∥∇ θ logπ(a|s,θ ∗ (x))∥∇θ ∗ (x)∥≤ L π,log C θ . Further, we obtain (5) by using Assumption 3.1.1 for ε kl . Using Eq. (65) and Eq. (66) we obtain: ∥U π (s,θ ∗ (x),x)−∇V π,B (s,θ ∗ (x),x)∥≤ τL π,log C θ ε kl + τε fd 1− γ (67) Let us obtain an expression for∇Q π (s,a,θ ∗ (x),x): ∇Q π (s,a,θ ∗ (x),x) =∇r(s,a,x) + γE s ′ ∼P (·|s,a) [∇V π,B (s ′ ,θ ∗ (x),x)− ∆(s ′ ,θ ∗ (x))] (68) Let us obtain a new recursion using the above equation by substituting∇V π,B (s ′ ,θ ∗ (x),x)with U (s,θ ∗ (x),x) and introducing a new quantity W π (s,a,θ ∗ (x),x) as: W π (s,a,θ ∗ (x),x) =∇r(s,a,x) + γE s ′ ∼P (·|s,a) [U π (s ′ ,θ ∗ (x),x)] (69) Using Eq. (69) and Eq. (67) we obtain bound for∥∇Q π (s,a,θ ∗ (x),x)− W π (s,a,θ ∗ (x),x)∥ as: ∥∇Q π (s,a,θ ∗ (x),x)− W π (s,a,θ ∗ (x),x)∥ ≤γE s ′ ∼P (·|s,a) [∥U π (s ′ ,θ ∗ (x),x)−∇V π,B (s,θ ∗ (x),x)∥ +∥∆(s ′ ,θ ∗ (x))∥] ≤ τγ(2− γ)(L π,log C θ ε kl + ε fd ) 1− γ (Using Eq. (66)) (70) Let us define U π off and W π off as the following: U π off (s,θ,x) = Z π(a|s,θ) ∇r(s,a,x) + γE s ′ ∼P (·|s,a) [U π off (s ′ ,θ,x)] da(71) W π off (s,a,θ,x) =∇r(s,a,x) + γE s ′ ∼P (·|s,a) [U π off (s ′ ,θ,x)] (72) Lemma C.6. LetJ (θ,x)(Eq.(1)) be the objective function for RL defined for policy classΘwhere θ ∈ Θis the policy parameter, andxis the reward parameter. If policy classΘis realizable and there existθ ′ (x) ∈ Θsuch thatπ(a|s,θ ′ (x)) = π B (a|s,θ ′ (x),x)thenθ ′ (x)is the optimal policy parameter for J (θ,x). Proof. Let us fix x and write π ′ (a|s) := π(a|s,θ ′ (x)).(73) LetQ π ′ andV π ′ denote the entropy-regularized state-action value function and value function corresponding to π ′ . Since θ ′ (x) satisfies π(a|s,θ ′ (x)) = π B (a|s,θ ′ (x),x), we have π ′ (a|s) = exp(Q π ′ (s,a,x)/τ ) R A exp(Q π ′ (s, ̄a,x)/τ )d ̄a .(74) Define the partition function Z π ′ (s) := Z A exp(Q π ′ (s, ̄a,x)/τ )d ̄a.(75) Then Eq. (74) implies logπ ′ (a|s) = 1 τ Q π ′ (s,a,x)− logZ π ′ (s).(76) 22 By the definition of the entropy-regularized value function, V π ′ (s,x) = Z A π ′ (a|s) h Q π ′ (s,a,x)− τ logπ ′ (a|s) i da.(77) Substituting Eq. (76) into Eq. (77), we obtain V π ′ (s,x) = Z A π ′ (a|s) Q π ′ (s,a,x)− τ 1 τ Q π ′ (s,a,x)− logZ π ′ (s) da = Z A π ′ (a|s) h τ logZ π ′ (s) i da = τ logZ π ′ (s). (78) Using the definition of Z π ′ (s) from Eq. (75), this gives V π ′ (s,x) = τ log Z A exp(Q π ′ (s,a,x)/τ )da.(79) Now, by the soft Bellman equation for the fixed policy π ′ , Q π ′ (s,a,x) = r(s,a,x) + γE s ′ ∼P (·|s,a) h V π ′ (s ′ ,x) i .(80) Substituting Eq. (80) into Eq. (79), we obtain V π ′ (s,x) = τ log Z A exp r(s,a,x) + γE s ′ ∼P (·|s,a) [V π ′ (s ′ ,x)] τ ! da.(81) The right-hand side is exactly the soft Bellman optimality operator applied to V π ′ . Therefore, V π ′ =T V π ′ .(82) By Lemma C.7, the soft Bellman optimality operatorTis aγ-contraction and has a unique fixed point, denoted by V ∗ . Since V π ′ is a fixed point ofT , uniqueness implies V π ′ (s,x) = V ∗ (s,x), ∀s∈S.(83) Thus π ′ is an optimal entropy-regularized policy. Finally, for any θ ∈ Θ, let π θ (a|s) = π(a|s,θ). Since V ∗ is the optimal soft value function, V π θ (s,x)≤ V ∗ (s,x) = V π ′ (s,x), ∀s∈S.(84) Taking expectation with respect to the initial state distribution used in the definition of J , we obtain J (θ,x)≤ J (θ ′ (x),x), ∀θ ∈ Θ.(85) Therefore, θ ′ (x)∈ arg max θ∈Θ J (θ,x).(86) Hence, θ ′ (x) is an optimal policy parameter for J (θ,x). Lemma C.7. Fix a reward parameterxand let0 < γ < 1andτ > 0. LetB(S)denote the space of bounded real-valued functions onS equipped with the sup norm ∥V∥ ∞ := sup s∈S |V (s)|.(87) Define the soft Bellman optimality operatorT by (T V )(s) = τ log Z A exp r(s,a,x) + γE s ′ ∼P (·|s,a) [V (s ′ )] τ da.(88) Assume thatT Vis well-defined and bounded for everyV ∈B(S). ThenTis aγ-contraction in the sup norm; that is, for all V,W ∈B(S), ∥T V −T W∥ ∞ ≤ γ∥V − W∥ ∞ .(89) Consequently,T has a unique fixed point V ∗ ∈B(S). 23 Proof. Let V,W ∈B(S) and define δ :=∥V − W∥ ∞ .(90) Then for every s ′ ∈S , W (s ′ )− δ ≤ V (s ′ )≤ W (s ′ ) + δ.(91) Taking expectation with respect to s ′ ∼ P (·|s,a) gives, for every (s,a)∈S×A, E s ′ ∼P (·|s,a) [W (s ′ )]− δ ≤ E s ′ ∼P (·|s,a) [V (s ′ )]≤ E s ′ ∼P (·|s,a) [W (s ′ )] + δ.(92) Multiplying by γ and adding r(s,a,x), we obtain r(s,a,x) + γE s ′ ∼P (·|s,a) [V (s ′ )]≤ r(s,a,x) + γE s ′ ∼P (·|s,a) [W (s ′ )] + γδ.(93) Therefore, exp r(s,a,x) + γE s ′ ∼P (·|s,a) [V (s ′ )] τ ≤ exp γδ τ exp r(s,a,x) + γE s ′ ∼P (·|s,a) [W (s ′ )] τ . (94) Integrating both sides overA gives Z A exp r(s,a,x) + γE s ′ ∼P (·|s,a) [V (s ′ )] τ da ≤ exp γδ τ Z A exp r(s,a,x) + γE s ′ ∼P (·|s,a) [W (s ′ )] τ da. (95) Applying τ log(·) to both sides yields (T V )(s)≤ (T W )(s) + γδ.(96) By the same argument with V and W interchanged, (T W )(s)≤ (T V )(s) + γδ.(97) Hence, for every s∈S , |(T V )(s)− (T W )(s)|≤ γδ.(98) Taking the supremum over s gives ∥T V −T W∥ ∞ ≤ γδ = γ∥V − W∥ ∞ .(99) ThusT is a γ-contraction. SinceB(S)equipped with the sup norm is a complete metric space and0 < γ < 1, Banach’s fixed-point theorem implies thatT has a unique fixed point V ∗ ∈B(S). C.2 Proof of Theorem 3.3 Theorem C.8. The hypergradient (∇φ(x,θ ∗ (x))) for the outer objective functionφ(x,θ ∗ (x))is expressed as ∇φ(x,θ ∗ (x)) =E d i ∼P (d i ,θ ∗ (x)) [∇ x l(d i I−1 0 ,x)] + E d i ∼P (d i ,θ ∗ (x)) h l(d i I−1 0 ,x) X i X h ∇ logπ(a i h |s i h ,θ ∗ (x)) i (100) Let the approximate hypergradient be defined in Eq. 10, then the approximation error is given by Ψ(x,θ ∗ (x))) = ∇φ(x,θ ∗ (x))−∇ ̃ φ(x,θ ∗ (x))and∥Ψ(x,θ ∗ (x)))∥ = O(ε fd ) + O(ε kl ). Further, Iis the number of trajectories,His the length of each trajectories,ε fd andε kl are errors due to unrealizable policy class as defined in Assumption 3.1,τis the temperature coefficient from Eq.(2) and|l(d i I−1 0 ,x)| ≤ C l (Lemma C.2). Further,W π (s,a,θ ∗ (x),x)andU π (s,θ ∗ (x),x)are the gradient-shifted Q-value function and the gradient-shifted value function defined in Eq. (7). 24 Proof. We have: ∇φ(x,θ ∗ (x)) =∇E d i ∼P (d i ,θ ∗ (x)) [l(d i I−1 0 ,x)] =E d i ∼P (d i ,θ ∗ (x)) [∇l(d i I−1 0 ,x)] + Z ∇Π I−1 i=0 P (d i ,θ ∗ (x))[l(d i I−1 0 ,x)]Π I−1 i=0 d i =E d i ∼P (d i ,θ ∗ (x)) [∇l(d i I−1 0 ,x)] + Z Π I−1 i=0 P (d i ,θ ∗ (x))∇ log Π I−1 i=0 P (d i ,θ ∗ (x)) [l(d i I−1 0 ,x)]Π I−1 i=0 d i (101) We know that for a trajectory d i , logP (d i ,θ) is given as: logP (d i ,θ) = logρ 0 (s i 0 ) + H−2 X h=0 (logπ(a i h |s i h ,θ) + logP (s i h+1 |s i h ,a i h )) + logπ(a i H−1 |s i H−1 ,θ) (102) Using Eq. (101) and Eq. (102), we obtain the following hypergradient: ∇E d i ∼P (d i ,θ ∗ (x)) [l(d i I−1 0 ,x)] = E d i ∼P (d i ,θ ∗ (x)) [∇ x l(d i I−1 0 ,x)] + E d i ∼P (d i ,θ ∗ (x)) h l(d i I−1 0 ,x) X i X h ∇ logπ(a i h |s i h ,θ ∗ (x)) i (103) By adding and subtracting∇ logπ B (a i t |s i t ,θ ∗ (x),x) we get: ∇E d i ∼P (d i ,θ ∗ (x)) [l(d i I−1 0 ,x)] = E d i ∼P (d i ,θ ∗ (x)) [∇ x l(d i I−1 0 ,x)] + E d i ∼P (d i ,θ ∗ (x)) h l(d i I−1 0 ,x) X i X t ∇ logπ B (a i t |s i t ,θ ∗ (x)) i + E d i ∼P (d i ,θ ∗ (x)) h l(d i I−1 0 ,x) X i X t ∇ logπ(a i t |s i t ,θ ∗ (x))−∇ logπ B (a i t |s i t ,θ ∗ (x),x) i (104) Let us define: Ψ 1 (x,θ ∗ (x)) := E d i ∼P (d i ,θ ∗ (x)) h l(d i I−1 0 ,x) X i X t ∇ logπ(a i t |s i t ,θ ∗ (x))−∇ logπ B (a i t |s i t ,θ ∗ (x),x) i (105) 25 Using the definition of π B (a i t |s i t ,θ ∗ (x),x) we get: ∇E d i ∼P (d i ,θ ∗ (x)) [l(d i I−1 0 ,x)] = E d i ∼P (d i ,θ ∗ (x)) [∇ x l(d i I−1 0 ,x)] + τ −1 E d i ∼P (d i ,θ ∗ (x)) h l(d i I−1 0 ,x) X i X t (∇Q π (s i t ,a i t ,θ ∗ (x),x)−∇V π,B (s i t ,θ ∗ (x),x)) i + Ψ 1 (x,θ ∗ (x)) = E d i ∼P (d i ,θ ∗ (x)) [∇ x l(d i I−1 0 ,x)] + τ −1 E d i ∼P (d i ,θ ∗ (x)) h l(d i I−1 0 ,x) X i X t (W π (s i t ,a i t ,θ ∗ (x),x)− U π (s i t ,θ ∗ (x),x)) i + τ −1 E d i ∼P (d i ,θ ∗ (x)) h l(d i I−1 0 ,x) X i X t (∇Q π (s i t ,a i t ,θ ∗ (x),x)− W π (s i t ,a i t ,θ ∗ (x),x)) i + τ −1 E d i ∼P (d i ,θ ∗ (x)) h l(d i I−1 0 ,x) X i X t (U π (s i t ,θ ∗ (x),x)−∇V π,B (s i t ,θ ∗ (x),x)) i + Ψ 1 (x,θ ∗ (x)) (106) Let us define Ψ 2 (x,θ ∗ (x)) as: Ψ 2 (x,θ ∗ (x)) =τ −1 E d i ∼P (d i ,θ ∗ (x)) h l(d i I−1 0 ,x) X i X t (∇Q π (s i t ,a i t ,θ ∗ (x),x)− W π (s i t ,a i t ,θ ∗ (x),x)) i + τ −1 E d i ∼P (d i ,θ ∗ (x)) h l(d i I−1 0 ,x) X i X t (U π (s i t ,θ ∗ (x),x)−∇V π,B (s i t ,θ ∗ (x),x)) i (107) Therefore, we have: ∇E d i ∼P (d i ,θ ∗ (x)) [l(d i I−1 0 ,x)] = E d i ∼P (d i ,θ ∗ (x)) [∇ x l(d i I−1 0 ,x)] + τ −1 E d i ∼P (d i ,θ ∗ (x)) h l(d i I−1 0 ,x) X i X t (W π (s i t ,a i t ,θ ∗ (x),x)− U π (s i t ,θ ∗ (x),x)) i + Ψ 1 (x,θ ∗ (x)) + Ψ 2 (x,θ ∗ (x)) (108) We define∇ ̃ φ(x,θ ∗ (x)) as: ∇ ̃ φ(x,θ ∗ (x)) = E d i ∼P (d i ,θ ∗ (x)) [∇ x l(d i I−1 0 ,x)] + τ −1 E d i ∼P (d i ,θ ∗ (x)) h l(d i I−1 0 ,x) X i X t (W π (s i t ,a i t ,θ ∗ (x),x)− U π (s i t ,θ ∗ (x),x)) i (109) Therefore, we have: ∇φ(x,θ ∗ (x))−∇ ̃ φ(x,θ ∗ (x)) = Ψ 1 (x,θ ∗ (x)) + Ψ 2 (x,θ ∗ (x)) = Ψ(x,θ ∗ (x))(110) Further, using Lemma C.3 we obtain that∥Ψ(x,θ ∗ (x)))∥ = O(ε kl ) + O(ε fd ). 26 D Proof of Theorem 4.6 D.1 Lemmas for the Proof of Theorem 4.6 Lemma D.1. Letd i I−1 i=0 be a collection ofItrajectories, where each trajectory is denoted by d = s t ,a t H−1 t=0 . Letl i ∈ 0, 1be a one-hot preference label satisfying P I−1 i=0 l i = 1 . Consider the multinomial Bradley–Terry preference model P (d i is preferred amongd j I−1 j=0 | x) = exp(R x (d i )) P I−1 j=0 exp(R x (d j )) ,(111) where R x (d) = P s t ,a t ∈d r(s t ,a t ,x). Define the preference log-likelihood l(d i I−1 i=0 ,x) := I−1 X i=0 l i logP (d i is preferred amongd j I−1 j=0 | x).(112) Then, for every collectiond i I−1 i=0 and every x, ∥∇ x l(d i I−1 i=0 ,x)∥≤ 2HL r = C lx (113) Here, L r is Lipchitz coefficient from Assumption 4.1.5. Proof. For notational simplicity, define p i (x) := P (d i is preferred amongd j I−1 j=0 | x) = exp(R x (d i )) P I−1 j=0 exp(R x (d j )) .(114) Then l(d i I−1 i=0 ,x) = I−1 X i=0 l i logp i (x).(115) Since P I−1 i=0 l i = 1andl i ∈0, 1, there exists an indexi ⋆ ∈0,...,I − 1such thatl i ⋆ = 1and l i = 0 for all i̸= i ⋆ . Therefore, l(d i I−1 i=0 ,x) = logp i ⋆ (x).(116) Using the definition of p i ⋆ (x), we get logp i ⋆ (x) = R x (d i ⋆ )− log I−1 X j=0 exp(R x (d j )) .(117) Differentiating with respect to x gives ∇ x l(d i I−1 i=0 ,x) =∇ x R x (d i ⋆ )−∇ x log I−1 X j=0 exp(R x (d j )) .(118) By the chain rule, ∇ x log I−1 X j=0 exp(R x (d j )) = P I−1 j=0 exp(R x (d j ))∇ x R x (d j ) P I−1 j=0 exp(R x (d j )) .(119) Using the definition of p j (x), this can be written as ∇ x log I−1 X j=0 exp(R x (d j )) = I−1 X j=0 p j (x)∇ x R x (d j ).(120) Hence, ∇ x l(d i I−1 i=0 ,x) =∇ x R x (d i ⋆ )− I−1 X j=0 p j (x)∇ x R x (d j ).(121) 27 Taking norms and using the triangle inequality, ∥∇ x l(d i I−1 i=0 ,x)∥≤∥∇ x R x (d i ⋆ )∥ + I−1 X j=0 p j (x)∇ x R x (d j ) ≤∥∇ x R x (d i ⋆ )∥ + I−1 X j=0 p j (x)∥∇ x R x (d j )∥.(122) By Assumption 4.1.5, we have∥∇ x R x (d i ⋆ )∥≤ HL r and∥∇ x R x (d j )∥≤ HL r for allj. Therefore, ∥∇ x l(d i I−1 i=0 ,x)∥≤ HL r + I−1 X j=0 p j (x)HL r = HL r + G R I−1 X j=0 p j (x).(123) Sincep j (x) I−1 j=0 is a probability distribution over the I trajectories, P I−1 j=0 p j (x) = 1. Thus, ∥∇ x l(d i I−1 i=0 ,x)∥≤ 2HL r = C lx .(124) This proves the pointwise gradient bound. Lemma D.2. LetU π (s,θ,x)be the gradient shifted value function defined in Lemma 3.2.U π (s,θ,x) satisfies Lipchitz continuity i.e.,∥U π (s,θ 1 ,x)− U π (s,θ 2 ,x)∥≤ V ol(A) L B L r τ (1−γ) 2 ∥θ 1 − θ 2 ∥. Here, V ol(A)is the volume of the action spaceA,L B is the Lipchitz coefficient of the Boltzmann policy π B (a|s,θ,x)defined in Lemma D.8.L r is defined in Assumptions 4.1,τis the temperature coefficient of the Boltzmann policy, and γ is the discount factor of the MDP. Proof. Using Lemma 3.2 for the definition of U π (s,θ,x) we have: U π (s,θ,x) = Z π B (a|s,θ) ∇r(s,a,x) + γE s ′ ∼P (·|s,a) [U π (s ′ ,θ,x)] da(125) 28 ∥U π (s,θ 1 ,x)− U π (s,θ 2 ,x)∥ (1) ≤∥ Z π B (a|s,θ 1 ,x) ∇r(s,a,x) + γE s ′ ∼P (·|s,a) [U π (s ′ ,θ 1 ,x)] da − Z π B (a|s,θ 2 ,x) ∇r(s,a,x) + γE s ′ ∼P (·|s,a) [U π (s ′ ,θ 2 ,x)] da∥ (2) ≤∥ Z (π B (a|s,θ 1 ,x)− π B (a|s,θ 2 ,x))∇r(s,a,x) da∥ + γ∥ Z π B (a|s,θ 1 ,x)E s ′ ∼P (·|s,a) [U π (s ′ ,θ 1 ,x)− U π (s ′ ,θ 2 ,x)] da∥ + γ∥ Z (π B (a|s,θ 1 ,x)− π B (a|s,θ 2 ,x))E s ′ ∼P (·|s,a) [U π (s ′ ,θ 2 ,x)] da∥ (3) ≤ V ol(A) L B L r τ (1− γ) ∥θ 1 − θ 2 ∥ + γ∥ Z π B (a|s,θ 1 ,x)E s ′ ∼P (·|s,a) [U π (s ′ ,θ 1 ,x)− U π (s ′ ,θ 2 ,x)] da∥ (4) ≤ V ol(A) L B L r τ (1− γ) ∥θ 1 − θ 2 ∥ + γV ol(A) L B L r τ (1− γ) ∥θ 1 − θ 2 ∥ + γ 2 Z π B (a|s,θ 1 ,x) E s ′ ∼P (·|s,a) h Z π B (a ′ |s ′ ,θ 1 )E s ′ ∼P (·|s ′ ,a ′ ) [U π (s ′ ,θ 1 ,x)− U π (s ′ ,θ 2 ,x)] da i da (5) ≤ V ol(A) L B L r τ (1− γ) 2 ∥θ 1 − θ 2 ∥ (126) We obtain (3) from (2) by using Assumption 4.1.5 for bounding∇r(s,a,x)and Lemma D.8. We obtain (4) from (3) by expanding the recursion. ∥U π (s,θ 1 ,x)− U π (s,θ 2 ,x)∥≤ V ol(A) L B L r τ (1− γ) 2 ∥θ 1 − θ 2 ∥(127) Lemma D.3. LetW π (s,a,θ,x)be the gradient shifted Q-value function defined in Lemma 3.2.W π (s,a,θ,x)satisfies Lipchitz continuity i.e.,∥W π (s,a,θ 1 ,x) − W π (s,a,θ 2 ,x)∥ ≤ γV ol(A) L B L r τ (1−γ) 2 ∥θ 1 − θ 2 ∥. Here,V ol(A)is the volume of the action spaceA,L B is the Lip- chitz coefficient of the Boltzmann policyπ B (a|s,θ,x)defined in Lemma D.8.L r is defined in Assumptions 4.1,τis the temperature coefficient of the Boltzmann policy andγis the discount factor of the MDP. Proof. Using recursion for W π (s,a,θ 1 ,x) defined in Eq. (69) from Lemma C.5: ∥W (s,a,θ 1 ,x)− W π (s,a,θ 2 ,x)∥ ≤∥∇r(s,a,x) + γE s ′ ∼P (·|s,a) [U π (s ′ ,θ 1 ,x)]−∇r(s,a,x)− γE s ′ ∼P (·|s,a) [U π (s ′ ,θ 2 ,x)]∥ ≤γ∥E s ′ ∼P (·|s,a) [U π (s ′ ,θ 1 ,x)]− E s ′ ∼P (·|s,a) [U π (s ′ ,θ 2 ,x)]∥ ≤γE s ′ ∼P (·|s,a) [∥U π (s ′ ,θ 1 ,x)− U π (s ′ ,θ 2 ,x)∥] (128) Using Lemma D.2 we get: ∥W π (s,a,θ 1 ,x)− W π (s,a,θ 2 ,x)∥≤ γV ol(A) L B L r τ (1− γ) 2 ∥θ 1 − θ 2 ∥(129) 29 Lemma D.4. LetE d i ∼P (d i ,θ) [∇ x l(d i I−1 i=0 ,x)]be the partial derivative of the objective func- tion defined in Eq.(4)w.r.t.reward parameterx.E d i ∼P (d i ,θ) [∇ x l(d i I−1 i=0 ,x)]is Lip- chitz continuous w.r.t. to the policy parameterθsuch that∥E d i ∼P (d i ,θ 1 ) [∇ x l(d i I−1 i=0 ,x)] − E d i ∼P (d i ,θ 2 ) [∇ x l(d i I−1 i=0 ,x)]∥ ≤ C lx HIV ol(A)L π ∥θ 1 − θ 2 ∥ . Here,∥∇ x l(d i I−1 i=0 ,x)∥ ≤ C lx (Lemma D.1),V ol(A)is the volume of the action spaceA,His the length of the trajectory,Iis the number of trajectories and L π is a Lipchitz coefficient defined in Assumption 4.1.3. Proof. Using the Integral Probability Metric (IPM), we have: sup ∥f∥ ∞ ≤C |E d∼P (d,θ 1 ) [f (d)]− E d∼P (d,θ 2 ) [f (d)]|≤ 2CD TV (P (d,θ 1 ),P (d,θ 2 ))(130) Let us find a bound on D TV (P (d,θ 1 ),P (d,θ 2 )). Here F (x) = 1 2 |x− 1|. D TV (P (d,θ 1 ),P (d,θ 2 ))≤ D TV (P (d,θ 1 ),P (d,p)) + D TV (P (d,p),P (d,θ 2 ))(131) Let us consider first D TV (P (d,θ 1 ),P (d,p)): D TV (P (d,θ 1 ),P (d,p)) = Z P (d,p)F ( P (d,θ 1 ) P (d,p) ) d = Z P (d,p) × F ρ 0 (s 0 )π(a 0 |s 0 ,θ 1 )P (s 1 |s 0 ,a 0 )Π H−2 i=1 π(a i |s i ,θ 1 )P (s i+1 |s i ,a i )π(a H−1 |s H−1 ,θ 1 ) ρ 0 (s 0 )π(a 0 |s 0 ,θ 2 )P (s 1 |s 0 ,a 0 )Π H−2 i=1 π(a i |s i ,θ 1 )P (s i+1 |s i ,a i )π(a H−1 |s H−1 ,θ 1 ) d = Z P (d,p)F π(a 0 |s 0 ,θ 1 ) π(a 0 |s 0 ,θ 2 ) d = Z ρ 0 (s 0 ) Z π(a 0 |s 0 ,θ 2 )F π(a 0 |s 0 ,θ 1 ) π(a 0 |s 0 ,θ 2 ) da 0 ds 0 = Z ρ 0 (s 0 )D TV (π(·|s 0 ,θ 1 ),π(·|s 0 ,θ 2 )) ds 0 (132) Now, let us consider D TV (P (d,p),P (d,θ 2 )): D TV (P (d,p),P (d,θ 2 )) = Z P (d,θ 2 )F P (d,p) P (d,θ 2 ) d = Z P (d,θ 2 ) × F ρ 0 (s 0 )π(a 0 |s 0 ,θ 2 )P (s 1 |s 0 ,a 0 )Π H−2 i=1 π(a i |s i ,θ 1 )P (s i+1 |s i ,a i )π(a H−1 |s H−1 ,θ 1 ) ρ 0 (s 0 )π(a 0 |s 0 ,θ 2 )P (s 1 |s 0 ,a 0 )Π H−2 i=1 π(a i |s i ,θ 2 )P (s i+1 |s i ,a i )π(a H−1 |s H−1 ,θ 2 ) d = Z ρ 0 (s 0 ) Z π(a 0 |s 0 ,θ 2 ) Z P (d H−1 1 ,θ 1 |s 0 ,a 0 ) × F P (s 1 |s 0 ,a 0 )Π H−2 i=1 π(a i |s i ,θ 1 )P (s i+1 |s i ,a i )π(a H−1 |s H−1 ,θ 1 ) P (s 1 |s 0 ,a 0 )Π H−2 i=1 π(a i |s i ,θ 2 )P (s i+1 |s i ,a i )π(a H−1 |s H−1 ,θ 2 ) d da 0 ds 0 = Z ρ 0 (s 0 ) Z π(a 0 |s 0 ,θ 2 ) Z P (d H−1 1 ,θ 1 |s 0 ,a 0 )F P (d H−1 1 ,θ 1 |s 0 ,a 0 ) P (d H−1 1 ,θ 2 |s 0 ,a 0 ) d da 0 ds 0 = Z ρ 0 (s 0 ) Z π(a 0 |s 0 ,θ 2 )D TV (P (d H−1 1 ,θ 1 |s 0 ,a 0 ),P (d H−1 1 ,θ 2 |s 0 ,a 0 )) da 0 ds 0 (133) 30 We can again break D TV (P (d H−1 1 ,θ 1 |s 0 ,a 0 ),P (d H−1 1 ,θ 2 |s 0 ,a 0 )) into two terms: D TV (P (d H−1 1 ,θ 1 |s 0 ,a 0 ),P (d H−1 1 ,θ 2 |s 0 ,a 0 )) ≤D TV (P (d H−1 1 ,θ 1 |s 0 ,a 0 ),P (d H−1 1 ,p ′ |s 0 ,a 0 )) + D TV (P (d H−1 1 ,p ′ |s 0 ,a 0 ),P (d H−1 1 ,θ 2 |s 0 ,a 0 )) (134) Using the decomposition in (134) we obtain the following: D TV (P (d,θ 1 ),P (d,θ 2 ))≤ H−1 X h=0 E s h D TV (π(·|s h ,θ 1 ),π(·|s h ,θ 2 )) ≤ H max s D TV (π(·|s,θ 1 ),π(·|s,θ 2 )) ≤ HD TV (π(·|s ∗ ,θ 1 ),π(·|s ∗ ,θ 2 )) ≤ H Z π(a|s ∗ ,θ 2 )T π(a|s ∗ ,θ 1 ) π(a|s ∗ ,θ 2 ) da ≤ H 2 Z |π(a|s ∗ ,θ 1 )− π(a|s ∗ ,θ 2 )| da ≤ H 2 V ol(A)L π ∥θ 1 − θ 2 ∥ (135) For I trajectoriesd i H−1 j=0 I−1 i=0 we have D TV (P (d i H−1 j=0 I−1 i=0 ,θ 1 ),P (d i H−1 j=0 I−1 i=0 ,θ 2 ))≤ HI 2 V ol(A)L π ∥θ 1 − θ 2 ∥(136) We have, sup ∥f∥ ∞ ≤C l |E d i ∼P (d i ,θ 1 ) [f (d i I−1 i=0 )]− E d i ∼P (d i ,θ 2 ) [f (d i I−1 i=0 )]|≤ C l HIV ol(A)L π ∥θ 1 − θ 2 ∥ (137) We have∥∇ x l(d i I−1 i=0 ,x)∥≤ C lx , therefore: |E d i ∼P (d i ,θ 1 ) [∇ x l(d i I−1 i=0 ,x)]− E d i ∼P (d i ,θ 2 ) [∇ x l(d i I−1 i=0 ,x)]|≤ C lx HIV ol(A)L π ∥θ 1 − θ 2 ∥ (138) Lemma D.5. Let∇ ̃ φ(x,θ)be the approximate hypergradient defined in Theorem 3.3.∇ ̃ φ(x,θ) satisfies Lipchitz continuity w.r.t. to parameterθ, i.e., Bound∥∇ ̃ φ(x,θ 1 )−∇ ̃ φ(x,θ 2 )∥≤ L φ ∥θ 1 − θ 2 ∥≤ O(∥θ 1 − θ 2 ∥) + O(∥θ 1 − θ 2 ∥/τ ) + O(∥θ 1 − θ 2 ∥/τ 2 ). Here,τis the temperature coefficient defined for the Boltzmann policy π B (Eq. (2)). Proof. ∇ ̃ φ(x,θ) = E d i ∼P (d i ,θ) [∇ x l(d i I−1 i=0 ,x)] + τ −1 E d i ∼P (d i ,θ) h l(d i I−1 i=0 ,x) X i X h W π (s i h ,a i h ,θ,x)− U π (s i h ,θ,x) i (139) Using Lemma D.4, we have: ∥E d i ∼P (d i ,θ 1 ) [∇ x l(d i I−1 i=0 ,x)]− E d i ∼P (d i ,θ 2 ) [∇ x l(d i I−1 i=0 ,x)]∥≤ C l HIV ol(A)L π ∥θ 1 − θ 2 ∥ (140) 31 Let us consider the following term: E d i ∼P (d i ,θ 1 ) h l(d i I−1 i=0 ,x) X i X h W π (s i h ,a i h ,θ 1 ,x)− U π (s i h ,θ 1 ,x) i −E d i ∼P (d i ,θ 1 ) h l(d i I−1 i=0 ,x) X i X h W π (s i h ,a i h ,θ 2 ,x)− U π (s i h ,θ 2 ,x) i (1) ≤ E d i ∼P (d i ,θ 1 ) h l(d i I−1 i=0 ,x) X i X h W π (s i h ,a i h ,θ 1 ,x)− W π (s i h ,a i h ,θ 2 ,x) i + E d i ∼P (d i ,θ 1 ) h l(d i I−1 i=0 ,x) X i X h U π (s i h ,θ 2 ,x)− U π (s i h ,θ 1 ,x) i (2) ≤ (1 + γ)HIC l V ol(A) L B L r τ (1− γ) 2 ∥θ 1 − θ 2 ∥ (141) We obtain (2) from (1) by using Lipchitz continuity of U π (Lemma D.2) and W π (Lemma D.3) . Let us now consider the term : E d i ∼P (d i ,θ 1 ) h l(d i I−1 i=0 ,x) X i X h W π (s i h ,a i h ,θ 2 ,x)− U π (s i h ,θ 2 ,x) i − E d i ∼P (d i ,θ 2 ) h l(d i I−1 i=0 ,x) X i X h W π (s i h ,a i h ,θ 2 ,x)− U π (s i h ,θ 2 ,x) i (142) We have : ∥l(d i I−1 i=0 ,x) X i X h W π (s i h ,a i h ,θ 2 ,x)− U π (s i h ,θ 2 ,x) ∥≤ C l HI 2L r 1− γ (143) Using Lemma D.4 we know that: sup ∥f∥ ∞ ≤C |E d i ∼P (d i ,θ 1 ) [f (d i I−1 i=0 )]− E d i ∼P (d i ,θ 2 ) [f (d i I−1 i=0 )]|≤ CHIV ol(A)L π ∥θ 1 − θ 2 ∥ (144) Therefore we have: E d i ∼P (d i ,θ 1 ) h l(d i I−1 i=0 ,x) X i X h W π (s i h ,a i h ,θ 2 ,x)− U π (s i h ,θ 2 ,x) i −E d i ∼P (d i ,θ 2 ) h l(d i I−1 i=0 ,x) X i X h W π (s i h ,a i h ,θ 2 ,x)− U π (s i h ,θ 2 ,x) i ≤ C l 2L r 1− γ (HI) 2 V ol(A)L π ∥θ 1 − θ 2 ∥ (145) Let us consider the main bound : 32 ∥∇ ̃ φ(x,θ 1 )−∇ ̃ φ(x,θ 2 )∥ ≤∥E d i ∼P (d i ,θ 1 ) [∇ x l(d i I−1 i=0 ,x)]− E d i ∼P (d i ,θ 2 ) [∇ x l(d i I−1 i=0 ,x)]∥ 1 τ E d i ∼P (d i ,θ 1 ) h l(d i I−1 i=0 ,x) X i X h W π (s i h ,a i h ,θ 1 ,x)− U π (s i h ,θ 1 ,x) i − E d i ∼P (d i ,θ 1 ) h l(d i I−1 i=0 ,x) X i X h W π (s i h ,a i h ,θ 2 ,x)− U π (s i h ,θ 2 ,x) i 1 τ E d i ∼P (d i ,θ 1 ) h l(d i I−1 i=0 ,x) X i X h W π (s i h ,a i h ,θ 2 ,x)− U π (s i h ,θ 2 ,x) i − E d i ∼P (d i ,θ 2 ) h l(d i I−1 i=0 ,x) X i X h W π (s i h ,a i h ,θ 2 ,x)− U π (s i h ,θ 2 ,x) i (146) Using Eq. (140), (141) and (145) in Eq. (146) we get: ∥∇ ̃ φ(x,θ 1 )−∇ ̃ φ(x,θ 2 )∥ ≤ L π + 1 + γ (1− γ) 2 L B L r τ 2 + 2L r HIL π τ (1− γ) C l HIV ol(A)∥θ 1 − θ 2 ∥ (147) ∥∇ ̃ φ(x,θ 1 )−∇ ̃ φ(x,θ 2 )∥≤ O(∥θ 1 − θ 2 ∥) + O ∥θ 1 − θ 2 ∥ τ + O ∥θ 1 − θ 2 ∥ τ 2 (148) Lemma D.6. Letθ K t be the value of the policy parameter aftertiterations of outer loop of Algorithm 1 and θ ∗ (x t ) = arg min θ −J (θ,x t ). Then, the following bound holds for∥θ K t − θ ∗ (x t )∥: ∥θ K t − θ ∗ (x t )∥ 2 ≤ O(exp −K ) + O 1 B + O γ 2H B + O(γ 2H ) + O(ε approx )(149) Here,ε approx is defined in Assumption 4.3.Bis the batch size used for empirical expectation,His the horizon length used for estimation of infinite horizon quantities,Kis the number of gradient updates for inner level objective optimization, and γ is the discount factor for the MDP. Proof. Using Quadratic Growth condition we have: ∥θ K t − θ ∗ (x t )∥ 2 ≤ 2 μ ∥J (θ ∗ (x t ),x t )− J (θ K t ,x t )∥ (150) Let us now consider∥J (θ ∗ (x t ),x t )− J (θ K t ,x t )∥ . Using Lemma 1 from (Gaur et al., 2025), we obtain: ∥J (θ ∗ (x t ),x t )− J (θ K t ,x t )∥≤ O(exp −K ) + O(β(B,H)) (151) Here, E[∥∇ θ J (θ k t ,x t )−∇ θ ˆ J (θ k t ,x t )∥ 2 ]≤ β(B,H). We have: ∇ θ ˆ J (θ k t ,x t ) = 1 B B−1 X i=0 ∇ θ log(π θ (a i |s i )) ˆ Q π y (s i ,a i ,θ k t ,x t ) (152) Now, E[∥∇ θ J (θ k t ,x t )−∇ θ ˆ J (θ k t ,x t )∥ 2 ] ≤E E[∇ θ log(π θ (a|s))Q π (s,a,θ k t ,x t )]− 1 B B−1 X i=0 ∇ θ log(π θ (a i |s i )) ˆ Q π y (s i ,a i ,θ k t ,x t ) 2 (153) 33 Using Lemma 3, Eq. 77 and Eq. 81 from (Gaur et al., 2025) we get: E[∥∇ θ J (θ k t ,x t )−∇ θ ˆ J (θ k t ,x t )∥ 2 ]≤ O 1 B + O γ 2H B + O(γ 2H ) + O(ε approx ) (154) Therefore, ∥J (θ ∗ (x t ),x t )− J (θ K t ,x t )∥≤ O(exp −K ) + O 1 B + O γ 2H B + O(γ 2H ) + O(ε approx ) (155) Hence, ∥θ K t − θ ∗ (x t )∥ 2 ≤ O(exp −K ) + O 1 B + O γ 2H B + O(γ 2H ) + O(ε approx )(156) Lemma D.7. The Boltzmann policy density function π B (a|s,θ) is bounded. Proof. We know that: π B (a|s,θ) = exp(Q π (s,a,θ,x)/τ ) exp(V π,B (s,θ,x)/τ ) (157) Further, using Assumption 4.2 we have: Q π (s,a,θ,x) =E π h ∞ X t=0 γ t (r(s t ,a t ,x)− τ logπ(a t |s t ))|s 0 = s,a 0 = a i |Q π (s,a,θ,x)|≤E π h ∞ X t=0 γ t (|r(s t ,a t ,x)| + τ| logπ(a t |s t ))||s 0 = s,a 0 = a i ≤ R max + τC log 1− γ (158) Also, using Assumption 4.2, we have: V π (s,θ,x) =E π h ∞ X t=0 γ t (r(s t ,a t ,x)− τ logπ(a t |s t ))|s 0 = s i |V π (s,θ,x)|≤E π h ∞ X t=0 γ t (|r(s t ,a t ,x)| + τ| logπ(a t |s t )||s 0 = s i ≤ R max + τC log 1− γ (159) From Eq. (60) of Lemma C.5 we know: V π,B (s,θ,x) =V π (s,θ,x) + τD KL (π(·|s,θ)||π B (·|s,θ,x)) =⇒ V π,B (s,θ,x) (1) ≥ − R max + τC log 1− γ (160) Here, (1) is true because the minimum value of D KL (π(·|s,θ)||π B (·|s,θ,x)) is 0. In order to find the upper bound on π B (a|s,θ). We need the maximum value of the numerator term and the minimum value of the denominator term. Therefore, using Eq. (158) and (159) we have: |π B (a|s,θ)|≤ C B = exp 2R max τ (1− γ) + 2C log 1− γ = O exp 2R max τ (1− γ) (161) 34 Lemma D.8. The Boltzmann policyπ B (a|s,θ,x)is Lipchitz continuous w.r.t. parameterθi.e., ∥π B (a|s,θ 1 ,x)− π B (a|s,θ 2 ,x)∥≤ (L B /τ )∥θ 1 − θ 2 ∥. Proof. log(π B (a|s,θ,x)) = Q π (s,a,θ,x) τ − V π,B (s,θ,x) τ ∇ θ log(π B (a|s,θ,x)) = ∇ θ Q π (s,a,θ,x) τ − ∇ θ V π,B (s,θ,x) τ (162) From Assumption 4.1.1 we know that∥∇ θ Q π (s,a,θ,x)∥≤ L θ,Q . For finding bound on∥∇ θ V π (s,θ,x)∥. Let us consider the following: exp V π,B (s,θ,x) τ = Z exp Q π (s,a,θ,x) τ da(163) Taking derivative of the equation w.r.t. θ: ∇ θ exp V π,B (s,θ,x) τ = Z ∇ θ exp Q π (s,a,θ,x) τ da exp V π,B (s,θ,x) τ ∇ θ V π,B (s,θ,x) τ = Z exp Q π (s,a,θ,x) τ ∇ θ Q π (s,a,θ,x) τ da ∇ θ V π,B (s,θ,x) τ = Z exp Q π (s,a,θ,x) τ − V π,B (s,θ,x) τ ∇ θ Q π (s,a,θ,x) τ da ∇ θ V π,B (s,θ,x) = Z π B (a|s,θ,x)∇ θ Q π (s,a,θ,x) da ∥∇ θ V π,B (s,θ,x)∥ = Z π B (a|s,θ,x)∥∇ θ Q π (s,a,θ,x)∥;da≤ L θ,Q (164) Using∥∇ θ V π,B (s,θ,x)∥≤ L θ,Q and∥∇ θ Q π (s,a,θ,x)∥≤ L θ,Q in Eq. (162) we get: ∥∇ θ log(π B (a|s,θ))∥≤ 2L θ,Q τ ∥∇ θ π B (a|s,θ)∥≤ π B (a|s,θ) 2L θ,Q τ (165) From Lemma D.7 we know that Boltzmann probability density π B is bounded. Therefore: ∥∇ θ π B (a|s,θ)∥≤ 2C B L θ,Q τ (166) So,∥∇ θ π B (a|s,θ)∥is bounded. Hence,π B (a|s,θ)is Lipchitz continuous w.r.t. parameterθwith coefficient L B /τ = 2C B L θ,Q /τ . Lemma D.9. LetW π off (s,a,θ,x)be the off-policy gradient shifted Q-value function and U π off (s,θ,x)be the off-policy gradient shifted value function defined in Eq.(15). Also,W π (s,a,θ,x) be the gradient shifted Q-value function andU π (s,θ,x)be the gradient shifted value function defined in Lemma 3.2. These functions satisfy the following bounds: ∥U π off (s,θ,x)− U π (s,θ,x)∥≤ L r ε kl (1− γ) 2 + L π + L B τ V ol(A)L r L π (1− γ) 2 ∥θ− θ ∗ (x)∥ ∥W π off (s,a,θ,x)− W π (s,a,θ,x)∥≤ γL r ε kl (1− γ) 2 + L π + L B τ γV ol(A)L r L π (1− γ) 2 ∥θ− θ ∗ (x)∥ (167) 35 Here,V ol(A)is the volume of the action spaceA,L B is the Lipchitz coefficient of the Boltzmann policyπ B (a|s,θ,x)defined in Lemma D.8.L r andL π are Lipchitz coefficient defined in Assumptions 4.1,τis the temperature coefficient of the Boltzmann policy,γis the discount factor of the MDP, and ε kl is the error due to unrealizable policy class (Assumption 3.1). Proof. Let s ∗ = arg max s ∥U π off (s,θ,x)− U π (s,θ,x)∥ ∥U π off (s ∗ ,θ,x)− U π (s ∗ ,θ,x)∥ (1) ≤ Z π B (a|s ∗ ,θ,x) ∇r(s ∗ ,a,x) + γE s ′ ∼P (·|s ∗ ,a) [U π (s ′ ,θ,x)] da − Z π(a|s ∗ ,θ) ∇r(s ∗ ,a,x) + γE s ′ ∼P (·|s ∗ ,a) [U π off (s ′ ,θ,x)] da (2) ≤∥∇r(s ∗ ,a,x)∥ Z |π B (a|s ∗ ,θ,x)− π(a|s ∗ ,θ)| da + γ Z π B (a|s ∗ ,θ,x)E s ′ ∼P (·|s ∗ ,a) [∥U π off (s ′ ,θ,x)− U π (s ′ ,θ,x)∥] da + γ∥U π off (s ′ ,θ,x)∥ Z |π B (a|s ∗ ,θ,x)− π(a|s ∗ ,θ)| da (3) ≤ L r 1− γ Z |π B (a|s ∗ ,θ,x)− π(a|s ∗ ,θ)| da + γ∥U π off (s ∗ ,θ,x)− U π (s ∗ ,θ,x)∥ =⇒ ∥U π off (s ∗ ,θ,x)− U π (s ∗ ,θ,x)∥ (4) ≤ L r (1− γ) 2 Z |π B (a|s ∗ ,θ,x)− π(a|s ∗ ,θ)| da (168) Let us now consider the term R |π B (a|s ∗ ,θ,x)− π(a|s ∗ ,θ)| da. Z |π B (a|s ∗ ,θ,x)− π(a|s ∗ ,θ)| da (1) ≤ Z |π B (a|s ∗ ,θ,x)− π B (a|s ∗ ,θ ∗ (x),x)| da + Z |π B (a|s ∗ ,θ ∗ (x),x)− π(a|s ∗ ,θ ∗ (x))| da + Z |π(a|s ∗ ,θ ∗ (x))− π(a|s ∗ ,θ)| da (2) ≤ V ol(A)L B τ ∥θ− θ ∗ (x)∥ (Using Lemma D.7) + √ 2ε kl + V ol(A)L π ∥θ− θ ∗ (x)∥ (Using Assumption 4.1.5) (169) Here, we obtained the second term in (2) by using the following inequality: Z |π B (a|s ∗ ,θ ∗ (x),x)− π(a|s ∗ ,θ ∗ (x))| da =2d TV (π B (·|s ∗ ,θ ∗ (x),x),π(·|s ∗ ,θ ∗ (x))) ≤ q 2D KL (π(·|s ∗ ,θ ∗ (x))||π B (·|s ∗ ,θ ∗ (x),x)) ≤ s 2 Z π(a|s,θ ∗ (x))| logπ B (a|s,θ ∗ (x),x)− logπ(a|s,θ ∗ (x))| da ≤ √ 2ε kl (Using Assumption 3.1) (170) 36 Using Eq. (168) and Eq. (169), we have: ∀ s ∥U π off (s,θ,x)− U π (s,θ,x)∥ ≤∥U π off (s ∗ ,θ,x)− U π (s ∗ ,θ,x)∥ ≤ L r √ 2ε kl (1− γ) 2 + V ol(A)L r L π (1− γ) 2 ∥θ− θ ∗ (x)∥ + V ol(A)L r L B τ (1− γ) 2 ∥θ− θ ∗ (x)∥ (171) Let us now consider the bound on∥W π off (s,a,θ,x)− W π (s,a,θ,x)∥. ∥W π off (s,a,θ,x)− W π (s,a,θ,x)∥ ≤∥∇r(s,a,x) + γE s ′ ∼P (·|s,a) [U π off (s ′ ,θ,x)]−∇r(s,a,x)− γE s ′ ∼P (·|s,a) [U π (s ′ ,θ,x)]∥ ≤γE s ′ ∼P (·|s,a) [∥U π off (s ′ ,θ,x)− U π (s ′ ,θ,x)∥] ≤γ∥U π off (s ∗ ,θ,x)− U π (s ∗ ,θ,x)∥ ≤ γL r √ 2ε kl (1− γ) 2 + V ol(A)γL r L π (1− γ) 2 ∥θ− θ ∗ (x)∥ + V ol(A)γL r L B τ (1− γ) 2 ∥θ− θ ∗ (x)∥ (172) D.2 Proof of Theorem 4.6 Theorem D.10. Suppose Assumption 4.1 to 4.5 holds true. Then, Algorithm 1 obtains the following convergence rate : 1 T T−1 X t=0 ∥∇Φ(x t )∥ 2 ≤O 1 T + O(ε 2 kl ) + O(ε 2 fd ) + O 1 B + O(ε 2 approx ) + O(exp −K ) + O γ 2H B + O(γ 2H ) + O(ε approx ) + O(ε kl ) (173) By choosing,T = Θ(ε −1 ),B = Θ(ε −1 ),K = Θ(log(ε −1 )), andH = Θ(log(ε −1 )/ log(γ −1 )), we obtain the iteration complexity ofT = O(ε −1 )and the sample complexity ofT.K.B.H = ̃ O(ε −2 ). Therefore, we have: 1 T T−1 X t=0 ∥∇Φ(x t )∥ 2 ≤ O(ε) + O(ε approx ) + O(ε fd ) + O(ε kl ) (174) Here,ε approx is Q-value function approximation error defined in Assumption 4.3. Further,ε fd and ε kl are errors introduced because of the limited policy class as defined in Assumption 3.1.Bis the batch size used for empirical expectation,His the horizon length used for estimation of infinite horizon quantities,Kis the number of gradient updates for inner level objective optimization,Tis the number of gradient updates for outer level objective, andτis the temperature coefficient defined in Boltzmann policy (Eq. (2)). Proof. Let φ(x) = E d i ∼P (d i ,θ ∗ (x)) [l(d i I−1 i=0 ,x)]. ∇ ̃ φ(x,θ) = E d i ∼P (d i ,θ) [∇ x l(d i I−1 i=0 ,x)] + τ −1 E d i ∼P (d i ,θ) h l(d i I−1 i=0 ,x) X i X h W π (s i h ,a i h ,θ,x)− U π (s i h ,θ,x) i (175) ∇ ̃ φ(x,θ,B) = 1 B B−1 X j=0 ∇ x l(d i,j I−1 0 ,x) + τ −1 1 B B−1 X j=0 l(d i,j I−1 0 ,x) X i X h c W π off,w (s i,j h ,a i,j h ,θ,x)− b U π off,z (s i,j h ,θ,x) (176) 37 Here, c W π off,w (s i,j h ,a i,j h ,θ,x)is as estimator forW π off (s i h ,a i h ,θ,x)with parameterwand b U π off,z (s i,j h ,θ,x)is an estimator forU π off (s i h ,θ,x)with parameterz. The parameterswandz are updated using the Q-learning update rule from Algorithm 1 in (Gaur et al., 2024). We use the following update rule for the reward parameterxusing approximate hypergradient theorem (Theorem 3.3): x t+1 = x t − β t ∇ ̃ φ(x,θ,B)(177) Using L−smoothness we have: φ(x t+1 )≤ φ(x t ) +⟨∇φ(x t ),x t+1 − x t ⟩ + L 2 ∥x t+1 − x t ∥ 2 ≤ φ(x t )− β t ⟨∇φ(x t ),∇ ̃ φ(x t ,θ K t ,B)⟩ + β 2 t L 2 ∥∇ ̃ φ(x t ,θ K t ,B)∥ 2 ≤ φ(x t )− β t ⟨∇φ(x t ),∇ ̃ φ(x t ,θ K t ,B)⟩ + β 2 t L 2 ∥∇ ̃ φ(x t ,θ K t ,B)∥ 2 ≤ φ(x t )− β t ∥∇φ(x t )∥ 2 − β t ⟨∇φ(x t ),∇ ̃ φ(x t ,θ K t ,B)−∇φ(x t )⟩ + β 2 t L 2 ∥∇ ̃ φ(x t ,θ K t ,B)∥ 2 ≤ φ(x t )− β t 2 ∥∇φ(x t )∥ 2 + β t 2 ∥∇ ̃ φ(x t ,θ K t ,B)−∇φ(x t )∥ 2 + β 2 t L 2 ∥∇ ̃ φ(x t ,θ K t ,B)∥ 2 ≤ φ(x t )− ( β t 2 − β 2 t L)∥∇φ(x t )∥ 2 + ( β t 2 + β 2 t L)∥∇ ̃ φ(x t ,θ K t ,B)−∇φ(x t )∥ 2 (178) Let us consider the term∥∇ ̃ φ(x t ,θ K t ,B)−∇φ(x t )∥: ∥∇ ̃ φ(x t ,θ K t ,B)−∇φ(x t )∥ =∥∇ ̃ φ(x t ,θ K t ,B)−∇ ̃ φ(x t ,θ K t ) +∇ ̃ φ(x t ,θ K t )−∇φ(x t )∥ ≤∥∇ ̃ φ(x t ,θ K t ,B)−∇ ̃ φ(x t ,θ K t )∥ +∥∇ ̃ φ(x t ,θ K t )−∇φ(x t )∥ (179) Let us consider the term∥∇ ̃ φ(x t ,θ K t )−∇φ(x t )∥: ∥∇ ̃ φ(x t ,θ K t )−∇φ(x t )∥ =∥∇ ̃ φ(x t ,θ K t )−∇ ̃ φ(x t ,θ ∗ (x t ))− Ψ(x t )∥ ≤∥∇ ̃ φ(x t ,θ K t )−∇ ̃ φ(x t ,θ ∗ (x t ))∥ +∥Ψ(x t )∥ (1) ≤ ∥∇ ̃ φ(x t ,θ K t )−∇ ̃ φ(x t ,θ ∗ (x t ))∥ + O(ε kl ) + O(ε fd ) (180) Here, (1) is obtained by using Lemma C.3 to provide a bound for∥Ψ(x t )∥. Using Lemma D.5, we have: ∥∇ ̃ φ(x t ,θ K t )−∇φ(x t )∥ ≤O(ε kl ) + O(ε fd ) + O(∥θ K t − θ ∗ (x t )∥) + O ∥θ K t − θ ∗ (x t )∥ τ + O ∥θ K t − θ ∗ (x t )∥ τ 2 (181) Let us look at the term∥∇ ̃ φ(x t ,θ K t ,B)−∇ ̃ φ(x t ,θ K t )∥: 38 ∥∇ ̃ φ(x t ,θ K t ,B)−∇ ̃ φ(x t ,θ K t )∥ ≤ E d i ∼P (d i ,θ) [∇ x l(d i I−1 i=0 ,x t )] + τ −1 E d i ∼P (d i ,θ) h l(d i I−1 i=0 ,x t ) X i X h W π (s i h ,a i h ,θ K t ,x t )− U π (s i h ,θ K t ,x t ) i − 1 B B−1 X j=0 ∇ x l(d i,j I−1 0 ,x t ) − τ −1 1 B B−1 X j=0 l(d i,j I−1 0 ,x t ) X i X h c W π off,w (s i,j h ,a i,j h ,θ K t ,x t )− b U π off,z (s i,j h ,θ K t ,x t ) ≤ E d i ∼P (d i ,θ) [∇ x l(d i I−1 i=0 ,x t )]− 1 B B−1 X j=0 ∇ x l(d i,j I−1 0 ,x t ) + 1 τ E d i ∼P (d i ,θ) h l(d i I−1 i=0 ,x t ) X i X h W π (s i h ,a i h ,θ K t ,x t )− U π (s i h ,θ K t ,x t ) i − 1 B B−1 X j=0 l(d i,j I−1 0 ,x t ) X i X h c W π off,w (s i,j h ,a i,j h ,θ K t ,x t )− b U π off,z (s i,j h ,θ K t ,x t ) (182) Let us consider the term∥E d i ∼P (d i ,θ) [∇ x l(d i I−1 i=0 ,x t )]− 1 B P B−1 j=0 ∇ x l(d i,j I−1 0 ,x t )∥ . Using Hoeffding inequality with probability 1− δ we obtain: E d i ∼P (d i ,θ) [∇ x l(d i I−1 i=0 ,x t )]− 1 B B−1 X j=0 ∇ x l(d i,j I−1 0 ,x t ) ≤ 2C lx r log(2/δ) 2B (183) Let us consider the following term: 1 B B−1 X j=0 l(d i,j I−1 0 ,x t ) X i X h c W π off,w (s i,j h ,a i,j h ,θ K t ,x t )− b U π off,z (s i,j h ,θ K t ,x t ) − E d i ∼P (d i ,θ) h l(d i I−1 i=0 ,x t ) X i X h W π (s i h ,a i h ,θ K t ,x t )− U π (s i h ,θ K t ,x t ) i ≤ 1 B B−1 X j=0 l(d i,j I−1 0 ,x t ) X i X h c W π off,w (s i,j h ,a i,j h ,θ K t ,x t )− b U π off,z (s i,j h ,θ K t ,x t ) − E d i ∼P (d i ,θ) h l(d i I−1 i=0 ,x t ) X i X h c W π off,w (s i h ,a i h ,θ K t ,x t )− b U π off,z (s i h ,θ K t ,x t ) i + E d i ∼P (d i ,θ) h l(d i I−1 i=0 ,x t ) X i X h c W π off,w (s i h ,a i h ,θ K t ,x t )− b U π off,z (s i h ,θ K t ,x t ) i − E d i ∼P (d i ,θ) h l(d i I−1 i=0 ,x t ) X i X h W π off (s i h ,a i h ,θ K t ,x t )− U π off (s i h ,θ K t ,x t ) i + E d i ∼P (d i ,θ) h l(d i I−1 i=0 ,x t ) X i X h W π off (s i h ,a i h ,θ K t ,x t )− U π off (s i h ,θ K t ,x t ) i − E d i ∼P (d i ,θ) h l(d i I−1 i=0 ,x t ) X i X h W π (s i h ,a i h ,θ K t ,x t )− U π (s i h ,θ K t ,x t ) i (184) Let us now consider the following term. Using Hoeffding inequality with probability1−δwe obtain: 39 1 B B−1 X j=0 l(d i,j I−1 0 ,x t ) X i X h c W π off,w (s i,j h ,a i,j h ,θ K t ,x t )− b U π off,z (s i,j h ,θ K t ,x t ) − E d i ∼P (d i ,θ) h l(d i I−1 i=0 ,x t ) X i X h c W π off,w (s i h ,a i h ,θ K t ,x t )− b U π off,z (s i h ,θ K t ,x t ) i ≤ 2C z C u HI r log(2/δ) 2B (185) Let us now consider the following term. c W π off,w (s i h ,a i h ,θ K t ,x t )is a sub-optimal estimate of W π (s i h ,a i h ,θ K t ,x t )using neural network with parametery. Further, b U π off,z (s i h ,θ K t ,x t )is a sub- optimal estimate ofU π (s i h ,θ K t ,x t )using neural network with parameterw. Therefore, using the result from (Gaur et al., 2024), we get: E d i ∼P (d i ,θ) h l(d i I−1 i=0 ,x t ) X i X h c W π off,w (s i h ,a i h ,θ K t ,x t )− b U π off,z (s i h ,θ K t ,x t ) i − E d i ∼P (d i ,θ) h l(d i I−1 i=0 ,x t ) X i X h W π off (s i h ,a i h ,θ K t ,x t )− U π off (s i h ,θ K t ,x t ) i ≤ O(ε approx ) + O 1 √ B (186) Let us consider the following term. Using Lemma D.9 we have: E d i ∼P (d i ,θ) h l(d i I−1 i=0 ,x t ) X i X h W π off (s i h ,a i h ,θ K t ,x t )− U π off (s i h ,θ K t ,x t ) i − E d i ∼P (d i ,θ) h l(d i I−1 i=0 ,x t ) X i X h W π (s i h ,a i h ,θ K t ,x t )− U π (s i h ,θ K t ,x t ) i ≤ (1 + γ)C l L r HI √ 2ε kl (1− γ) 2 + (1 + γ)C l HIV ol(A)L r ((L B /τ ) + L π ) (1− γ) 2 ∥θ K t − θ ∗ (x t )∥ (187) Therefore, using Eq. (183) and Eq. (185)–(187), we have: ∥∇ ̃ φ(x t ,θ K t ,B)−∇ ̃ φ(x t ,θ K t )∥≤2C lx r log(2/δ) 2B + 2C z C u HI τ r log(2/δ) 2B + O ε approx τ +O 1 τ √ B + (1 + γ)C l L r HI √ 2ε kl (1− γ) 2 + (1 + γ)C l HIV ol(A)L r ((L B /τ ) + L π ) (1− γ) 2 ∥θ K t − θ ∗ (x t )∥ (188) Using Eq. (188) and Eq. (181) in Eq. (179): 40 ∥∇ ̃ φ(x t ,θ K t ,B)−∇φ(x t )∥ ≤O(ε kl ) + O(ε fd ) + O(∥θ K t − θ ∗ (x t )∥) + 2C lx r log(2/δ) 2B + 2C z C u HI τ r log(2/δ) 2B + O ε approx τ + O 1 τ √ B + (1 + γ)C l L r HI √ 2ε kl τ (1− γ) 2 + (1 + γ)C l HIV ol(A)L r L π τ (1− γ) 2 ∥θ K t − θ ∗ (x t )∥ + O ∥θ K t − θ ∗ (x t )∥ τ 2 + O ∥θ K t − θ ∗ (x t )∥ τ (189) Using Lemma D.6 for O(∥θ K t − θ ∗ (x t )∥) we get: ∥∇ ̃ φ(x t ,θ K t ,B)−∇φ(x t )∥ 2 ≤O(ε kl ) + O(ε 2 kl ) + O(ε 2 fd ) + O 1 B + O 1 τ 2 B + O ε 2 approx τ 2 + O ε 2 kl τ 2 + O(exp −K ) + O 1 B + O γ 2H B + O(γ 2H ) + O(ε approx ) + O exp −K τ 2 + O 1 τ 2 B + O γ 2H τ 2 B + O γ 2H τ 2 + O ε approx τ 2 + O exp −K τ 4 + O 1 τ 4 B + O γ 2H τ 4 B + O γ 2H τ 4 + O ε approx τ 4 (190) Let us recall Eq. (178) and set β t = β.Also, βL < 1/2. φ(x t+1 )≤ φ(x t )− ( β 2 − β 2 L)∥∇φ(x t )∥ 2 + ( β 2 + β 2 L)∥∇ ̃ φ(x t ,θ K t ,B)−∇φ(x t )∥ 2 ⇒∥∇φ(x t )∥ 2 ≤ 2 β− 2β 2 L (φ(x t )− φ(x t+1 )) + 2 1− 2βL ∥∇ ̃ φ(x t ,θ K t ,B)−∇φ(x t )∥ 2 ⇒ 1 T T−1 X t=0 ∥∇φ(x t )∥ 2 ≤ 2 β− 2β 2 L (φ(x 0 )− φ(x T )) T + 2 (1− 2βL)T T−1 X t=0 ∥∇ ̃ φ(x t ,θ K t ,B)−∇φ(x t )∥ 2 (191) Using Eq. (190): ⇒ 1 T T−1 X t=0 ∥∇φ(x t )∥ 2 ≤O 1 T + O(ε 2 kl ) + O(ε 2 fd ) + O 1 B + O 1 τ 2 B + O ε 2 approx τ 2 + O ε 2 kl τ 2 + O(exp −K ) + O 1 B + O γ 2H B + O(γ 2H ) + O(ε approx ) + O(ε kl ) + O exp −K τ 2 + O 1 τ 2 B + O γ 2H τ 2 B + O γ 2H τ 2 + O ε approx τ 2 + O exp −K τ 4 + O 1 τ 4 B + O γ 2H τ 4 B + O γ 2H τ 4 + O ε approx τ 4 (192) Let τ = Θ(1). We obtain: 41 ⇒ 1 T T−1 X t=0 ∥∇φ(x t )∥ 2 ≤O 1 T + O(ε 2 kl ) + O(ε 2 fd ) + O 1 B + O(ε 2 approx ) + O(exp −K ) + O γ 2H B + O(γ 2H ) + O(ε approx ) + O(ε kl ) (193) Let us substitute T = Θ(ε −1 ), B = Θ(ε −1 ), K = Θ(log(ε −1 )), and H = Θ(log(ε −1 )/ log(γ −1 )). ⇒ 1 T T−1 X t=0 ∥∇φ(x t )∥ 2 ≤ O(ε) + O(ε approx ) + O(ε fd ) + O(ε kl ) (194) Therefore, the iteration complexity isT = O(ε −1 )and the sample complexity isT.K.B.H = ̃ O(ε −2 ) 42