Paper deep dive

Provable Last-Iterate Convergence for Multi-Objective Safe LLM Alignment via Optimistic Primal-Dual

Yining Li, Peizhong Ju, Ness Shroff

Year: 2026Venue: arXiv preprintArea: cs.LGType: PreprintEmbeddings: 213

Intelligence

Status: succeeded | Model: Gemma-4-26B-A4B | Prompt: intel-v1 | Confidence: 93%

Last extracted: 7/20/2026, 11:25:19 AM

Summary

The paper proposes an Optimistic Primal-Dual (OPD) algorithm for safe Reinforcement Learning from Human Feedback (RLHF) to address the instability and lack of last-iterate convergence in standard primal-dual methods. It introduces a universal framework unifying existing safe RLHF approaches and provides theoretical guarantees for last-iterate convergence in both distributional and parameterized policy spaces, showing that optimism mitigates oscillations in constrained alignment objectives.

Entities (6)

Optimistic Primal-Dual · algorithm · 98%LLMs · model · 95%RLHF · method · 95%Last-Iterate Convergence · property · 92%Saddle-point Problem · mathematical-concept · 90%Lagrangian Relaxation · method · 88%

Relation Signals (5)

Optimistic Primal-Dual → appliedto → RLHF

confidence 95% · we introduce an optimistic primal-dual (OPD) algorithm that incorporates predictive updates... for safe RLHF

Optimistic Primal-Dual → improves → Last-Iterate Convergence

confidence 95% · We establish last-iterate convergence guarantees for the proposed method... Our analysis reveals that optimism plays a crucial role in mitigating oscillations

RLHF → usedfor → LLMs

confidence 95% · Reinforcement Learning from Human Feedback (RLHF) plays a significant role in aligning Large Language Models (LLMs)

Optimistic Primal-Dual → mitigates → Oscillations

confidence 92% · optimism plays a crucial role in mitigating oscillations inherent to constrained alignment objectives

Standard Primal-Dual Methods → suffersfrom → instability

confidence 90% · standard primal-dual methods may exhibit instability or divergence in the last iterate

Cypher Suggestions (0)

No Cypher suggestions yet.

Abstract

Abstract:Reinforcement Learning from Human Feedback (RLHF) plays a significant role in aligning Large Language Models (LLMs) with human preferences. While RLHF with expected reward constraints can be formulated as a primal-dual optimization problem, standard primal-dual methods only guarantee convergence with a distributional policy where the saddle-point problem is in convex-concave form. Moreover, standard primal-dual methods may exhibit instability or divergence in the last iterate under policy parameterization in practical applications. In this work, we propose a universal primal-dual framework for safe RLHF that unifies a broad class of existing alignment algorithms, including safe-RLHF, one-shot, and multi-shot based methods. Building on this framework, we introduce an optimistic primal-dual (OPD) algorithm that incorporates predictive updates for both primal and dual variables to stabilize saddle-point dynamics. We establish last-iterate convergence guarantees for the proposed method, covering both exact policy optimization in the distributional space and convergence to a neighborhood of the optimal solution whose gap is related to approximation error and bias under parameterized policies. Our analysis reveals that optimism plays a crucial role in mitigating oscillations inherent to constrained alignment objectives, thereby closing a key theoretical gap between constrained RL and practical RLHF.

PDF

Open source PDF →Open local PDF →

Trouble viewing inline? Open PDF directly →

Full Text

211,835 characters extracted from source content.

Expand or collapse full text

Provable Last-Iterate Convergence for Multi-Objective Safe LLM Alignment via Optimistic Primal-Dual Yining Li The Ohio State University Peizhong Ju University of Kentucky Ness Shroff The Ohio State University Abstract Reinforcement Learning from Human Feedback (RLHF) plays a significant role in aligning Large Language Models (LLMs) with human preferences. While RLHF with expected reward constraints can be formulated as a primal–dual optimization problem, standard primal–dual methods only guarantee the convergence with a distributional policy where the saddle-point problem is in the convex-concave form. Moreover, standard primal-dual methods may exhibit instability or divergence in the last iterations under policy parameterization in practical applications. In this work, we propose a universal primal–dual framework for safe RLHF that unifies a broad class of existing alignment algorithms, including safe-RLHF, one-shot, and multi-shot based methods. Building on the universal primal-dual framework, we introduce an optimistic primal–dual (OPD) algorithm that incorporates predictive updates for both primal and dual variables to stabilize saddle-point dynamics. We establish last-iterate convergence guarantees for the proposed method, covering both exact policy optimization in the distributional space and convergence to the neighborhood of the optimal solution whose gap is related to approximate error and bias with parameterized policies. Our analysis reveals that optimism plays a crucial role in mitigating the oscillations inherent to constrained alignment objectives, thereby closing a key theoretical gap between constrained RL and practical RLHF. 1 Introduction The unsafe behaviors of large language models (LLMs) have raised growing concerns about the need to align safe and useful models. Although LLMs have shown impressive performance across a wide range of language tasks, such as summarization Zhang et al. (2024), translation Elshin et al. (2024), and code generation Wang and Chen (2023), they can also exhibit harmful behaviors, including generating misleading or incorrect information Guerreiro et al. (2023); Zhang et al. (2025b), producing inappropriate or toxic content Wen et al. (2023), and leaking sensitive or private data Feretzakis and Verykios (2024). As a result, aligning LLMs with human preferences that jointly emphasize helpfulness and safety has become a critical challenge. In practice, preferences involve multiple attributes, such as helpfulness, conciseness, factuality, and harmlessness, and these attributes are often not perfectly aligned and can even conflict with one another Sorensen et al. (2024). However, standard Reinforcement Learning from Human Feedback (RLHF) is inherently single-objective and does not fully capture the complexity of human preferences Ziegler et al. (2019); Stiennon et al. (2020). In its typical form, RLHF aligns a language model by collecting pairwise comparisons from human annotators, learning a reward model that reflects these preferences, and then optimizing the model to maximize the learned reward. This observation naturally motivates constrained RLHF, where the model is optimized for helpfulness while explicitly enforcing safety-related constraints. For example, Dai et al. (2024); Huang et al. (2022); Du et al. (2025) study how to maximize the helpfulness reward while requiring the expected safety cost to stay below a predefined threshold. We propose a universal framework that unifies a broad class of constrained RLHF algorithms based on Lagrangian relaxation Dai et al. (2024); Huang et al. (2024); Zhang et al. (2025a). These methods formulate constrained RLHF as a saddle-point problem over a policy and a set of non-negative dual variables. Our framework unifies these approaches by explicitly characterizing how different algorithms (i) approximately solve the primal policy optimization problem induced by the current dual variables, and (i) update the dual variables using feedback from constraint violations. This unified perspective highlights several algorithmic characteristics of existing approaches, including the convergence behavior of primal–dual methods and the computational requirements of one-shot and multi-shot procedures. In practice, naive primal–dual updates Dai et al. (2024) can lead to unstable saddle-point dynamics. Even in simple bilinear saddle-point problems, simultaneous primal–dual updates fail to converge in the last iterate and guarantee only average convergence, meaning that optimality is achieved only when averaging over iterates. This is often insufficient in safe RLHF, where the deployed model corresponds to the last iterate of training. Multi-shot methods can be computationally expensive, as they require repeatedly solving the primal policy optimization problem to near optimality for each dual update Zhang et al. (2025a). Meanwhile, one-shot dualization-based approaches rely on choosing the closed-form solution in the space of distributional policies as the primal optimal policy Huang et al. (2024). While this assumption enables efficient dual optimization, it does not accurately reflect practical alignment settings, where policies are parameterized by large neural networks and the exact distributional optimum may be unattainable. These observations bring up an open question: Is it possible to design an iterative alignment algorithm for constrained RLHF that is both computationally practical and provably stable in the last iterate, without relying on one-shot dualization or inner-loop optimal policy solvers? To address the stability issue, we propose an optimistic primal–dual method for safe RLHF. Optimistic primal–dual methods are known to stabilize saddle-point dynamics and admit last-iterate convergence guarantees Ding et al. (2023). Motivated by this observation, we propose an optimistic safe RLHF algorithm that augments both primal and dual updates with optimistic steps. These steps predict future gradients, and the final updates are obtained by correcting the predicted trajectories, leading to more stable training and improved last-iterate performance. Our main contributions include two parts. First, building on the proposed unified primal–dual framework, we develop an optimistic primal–dual algorithm for safe RLHF. By incorporating optimistic updates for both the policy and the dual variables, the proposed method stabilizes saddle-point dynamics and mitigates the oscillatory behavior in the constrained alignment problems. Second, we establish theoretical guarantees for the proposed optimistic primal–dual algorithm. In the distributional policy space, we show that the optimistic primal–dual method achieves last-iterate convergence to an optimal solution. We further extend the analysis to parameterized policy spaces relevant to practical LLM alignment, where we prove that the last iterate converges to a neighborhood of the optimal solution. The resulting residual error is explicitly characterized in terms of statistical estimation error and parameterization bias. 2 Preliminaries on Constrained RLHF 2.1 Constrained RLHF Problem To align with human preferences that involve multiple, potentially conflicting objectives, multi-objective or constrained variants of RLHF have been widely studied, where alignment is performed with respect to a primary objective while additional preference dimensions are enforced via constraints. These variants largely follow the standard RLHF pipeline, which consists of supervised fine-tuning (SFT) to obtain a reference policy, learning reward models from human preference data, and reinforcement-learning-based policy optimization with KL regularization to the reference model Ziegler et al. (2019); Stiennon et al. (2020). Let X and Y denote the sets of prompts and responses, respectively. A language model is represented as a stochastic policy mapping from the prompt set X to the distribution on the response set Y, denoted as π:→Δ()π:X→ (Y), where Δ() (Y) is the set of all distributions on Y. Denote πref _ref as the reference policy obtained after SFT. We consider multiple preference objectives indexed by =∪ℋK=S , where objectives in S are optimized and those in ℋH are enforced via constraints. To learn a reward model for objective k, we assume access to a human preference dataset (xki,yki,w,yki,l)i=1N\(x_k^i,y_k^i,w,y_k^i,l)\_i=1^N, where xkix_k^i is a prompt and (yki,w,yki,l)(y_k^i,w,y_k^i,l) denotes a preferred (indicated by superscript w) and less preferred (indicated by superscript l) response pair annotated by human annotators. Following standard practice in RLHF, we assume that preferences are generated according to a latent reward function Rk∗(x,y)R_k^*(x,y), and that human comparisons follow the Bradley-Terry model Ouyang et al. (2022): P(yw≻yl|x)=σ(Rk∗(x,yw)−Rk∗(x,yl)),P(y^w y^l|x)=σ (R_k^* (x,y^w )-R_k^* (x,y^l ) ), where σ(⋅)σ(·) denotes the sigmoid function. The reward model is then estimated by maximum likelihood over the preference dataset, Rk=arg⁡maxR∑i=1Nlog⁡σ(R(xki,yki,w)−R(xki,yki,l)).R_k= _R _i=1^N σ (R (x_k^i,y_k^i,w )-R (x_k^i,y_k^i,l ) ). For the constrained objectives indexed by ℋH, we specify a vector of thresholds =(bj)j∈ℋb=(b_j)_j , which define minimum performance requirements. For notational convenience, we absorb the thresholds into the reward definitions by introducing shifted rewards R~j(x,y):=Rj(x,y)−bj R_j(x,y):=R_j(x,y)-b_j, and with a slight abuse of notation, we continue to denote the shifted rewards by RjR_j. The goal of RLHF is to optimize a policy with respect to the learned reward signals while regularizing it to remain close to a reference policy. Given a preference weight vector ∈ℝ+||w _+^|S| such that ∑k∈wk=1 _k w_k=1, encoding the user’s trade-off over the soft objectives in S, the resulting multi-objective RLHF problem is formulated as maxπ _π x∼[y∼π(⋅|x)[∑k∈wkRk(x,y)] _x [E_y π(·|x) [ _k w_kR_k(x,y) ] . −βKL(π(⋅|x)∥πref(⋅|x))] .- (π(·|x)\| _ref(·|x) ) ] s.t. x∼,y∼π(⋅|x)[Rj(x,y)]≥0,∀j∈ℋ, _x ,y π(·|x) [R_j(x,y) ]≥ 0, ∀ j , where D denotes the prompt distribution and β>0β>0 controls the weight of KL regularization to the reference policy πref _ref. 2.2 Lagrangian Method A standard approach to solving constrained RLHF problems is the Lagrangian method. For each constrained objective j∈ℋj , we introduce a nonnegative Lagrange multiplier λj≥0 _j≥ 0. Given the preference weights w over the soft objectives, we define the aggregated reward Sλ(x,y):=∑k∈wkRk(x,y)+∑j∈ℋλjRj(x,y).S_λ(x,y):= _k w_kR_k(x,y)+ _j _jR_j(x,y). (1) The resulting Lagrangian of the constrained multi-objective RLHF problem is ℒ(π,λ)= (π,λ)= x∼,y∼π(⋅|x)[Sλ(x,y)] _x ,\,y π(·|x)\! [S_λ(x,y) ] −βx∼[KL(π(⋅|x)∥πref(⋅|x))]. -β\,E_x [KL\! (π(·|x)\,\|\, _ref(·|x) ) ]. The corresponding saddle-point problem is minλ≥0⁡maxπ⁡ℒ(π,λ). _λ≥ 0\; _π\;L(π,λ). (2) When optimizing over the space of all stochastic policies, the objective is concave in π and linear in λ, and the problem admits a convex–concave structure. In this case, for any fixed λ, the optimal policy has a closed-form solution given by π⋆(y|x)=πref(y|x)exp⁡(Sλ(x,y)/β)/Z(x),π (y|x)= _ref(y|x) (S_λ(x,y)/β )/Z(x), (3) where Z(x)Z(x) is the normalization factor Z(x)=∑yπref(y|x)exp⁡(Sλ(x,y)/β)Z(x)= _y _ref(y|x) (S_λ(x,y)/β ). Detailed derivations are provided in lemma B.7. In practice, however, the policy is restricted to a parameterized family πθ∈Θ\ _θ\_θ∈ , under which the optimization becomes non-concave in θ. As a result, practical constrained RLHF algorithms typically rely on iterative primal–dual updates, alternating between approximate policy optimization for fixed λ and gradient-based updates of the dual variables. The convergence of such methods in the parameterized setting generally requires additional assumptions or specialized algorithmic designs. Fixing the policy π, the Lagrangian is differentiable with respect to the dual variables. The gradient of ℒ(π,λ)L(π,λ) with respect to λj _j is given by ∇λjℒ(π,λ)=x∼,y∼π(⋅|x)[Rj(x,y)]. _ _jL(π,λ)=E_x ,\,y π(·|x) [R_j(x,y) ]. Accordingly, standard constrained RLHF methods update the dual variables by projected gradient descent, i.e., moving λ in the direction of constraint violation and projecting onto ℝ≥0R_≥ 0. 2.3 A universal safe RLHF framework We propose a universal framework that unifies a broad class of constrained RLHF algorithms based on Lagrangian re- laxation. The detailed universal Lagrangian alignment framework is shown in 1. Algorithm 1 Universal Lagrangian Alignment Framework 0: Prompt distribution D; Reward models Rk(x,y)k∈\R_k(x,y)\_k ; soft weights wjj∈\w_j\_j ; reference policy πref _ref; KL coefficient β; initial θ0 _0, λ0≥0 _0≥ 0; 1: for t=0,1,2,…,T−1t=0,1,2,…,T-1 do 2: Primal update: 3: πθt+1←PrimalOracle(πθt,λt,πref,,β) _ _t+1← PrimalOracle( _ _t, _t, _ref,D,β) 4: Dual update: 5: gt←GradEst(θt+1,λt,πref,)g_t← GradEst( _t+1, _t, _ref,D) 6: λt+1←[λt−1ηλgt]+ _t+1← [ _t- 1 _λg_t ]_+ 7: end for 8: Return λT _T and θT _T. For each iteration, the framework alternates between a primal update and a dual update. (1) The primal update is abstracted as a PrimalOracle, which aims to maximize the Lagrangian objective for a given dual variable. Depending on the choice of the oracle, the primal step may correspond to a single-step or multi-step policy gradient update in the parameter space, an approximate inner-iterations to solve the near-optimal policy in the parameterization space, or an exact closed-form solution in the distribution space Huang et al. (2024). (2) The dual update use GradEst estimates the expected rewards of the constrained objectives under the current policy, followed by a projected gradient step on the dual variable. Different existing alignment methods can be recovered by instantiating the primal oracle and the dual gradient estimator differently, as detailed below. • Finite-step primal–dual updates. When the primal oracle performs a finite number of stochastic gradient steps, the algorithm reduces to the class of coupled primal–dual methods used in safe RLHF and constrained DPO Dai et al. (2024); Du et al. (2025); Liu et al. (2024). In this regime, the primal policy is updated by a small number of stochastic gradient steps under a non-stationary objective induced by the evolving dual variable. These methods lack last-iterate convergence guarantees, even when the underlying Lagrangian is convex–concave in the distribution space. • Approximate multi-shot variants. Some recent works decouple the optimization by introducing an outer-loop dual update and an inner-loop primal optimization that approximately maximizes the Lagrangian for a fixed dual variable Zhang et al. (2025a). While this reduces interference between primal and dual updates, the inner-loop problem remains non-convex in the parameter space and is only solved approximately, which prevents these methods from being interpreted as exact primal oracles. • Exact dualization and one-shot alignment. In contrast, one-shot methods are obtained by analytically eliminating the primal variable in the distribution space, which yields an explicit, closed-form, and convex dual objective Huang et al. (2024). They can be viewed as a degenerate instantiation of the universal framework: the primal oracle returns the closed-form optimal distributional policy for a given dual variable, so no iterative primal updates are required during dual optimization. Therefore, each iteration reduces to a pure dual update step. 3 Optimistic Primal–Dual Method Standard primal–dual methods do not guarantee last-iterate convergence in constrained RLHF, and this fundamental limitation motivates the need for alternative primal–dual methods with stronger stability properties. The universal framework in algorithm 1 formulates constrained RLHF as a Lagrangian saddle-point problem, where the primal update optimizes the policy and the dual update adjusts the constraint multipliers. When optimization is carried out over the distributional policy space, the KL regularization induces strong concavity in the primal variable. However, the Lagrangian remains linear in the dual multipliers, and hence the resulting saddle-point problem is generally not strongly-convex-strongly-concave. The gradient descent-ascent methods converge linearly to the unique saddle point only under smooth strongly-convex-strongly-concave conditions with appropriate step sizes Zamani et al. (2024). Once these conditions are violated, such guarantees no longer hold, and last-iterate convergence may fail even when a unique saddle point exists. Example: Failure of Last-Iterate Convergence in a Bilinear Saddle-Point Problem We consider a simple convex–concave bilinear problem min⁡max⁡T _y _xx^TAy, where A is a full-rank matrix whose singular values are [σ1,⋯,σM][ _1,·s, _M]. The standard primal–dual gradient method gives t+1=t+αtx_t+1=x_t+ _t and t+1=t−α⊤ty_t+1=y_t- x_t, where α is the stepsize. Let zt=[t,i]⊤z_t=[x_t,y_i] . Then the update can be written as a linear iteration zt+1=(−α)zt,=[0−⊤0].z_t+1=(I- )z_t, = bmatrix0&-A\\ A &0 bmatrix. The matrix J has imaginary eigenvalues ±iσi± i _i. Hence, (−α)(I- ) has eigenvalues 1±iασi1± iα _i whose magnitudes are larger than 11, implying that the last iterates do not contract toward the saddle point due to the saddle-point problem’s inherently rotational structure Daskalakis and Panageas (2018). The aforementioned example implies that, even in constrained RLHF problems where the primal objective is strongly concave over the distributional policy space, standard primal–dual methods generally admit only average convergence guarantees and may fail to converge in the last iterate. The situation becomes even more challenging in practical RLHF settings with parameterized policies, where the optimization problem is no longer convex in the policy parameters. Motivated by these challenges, we adopt an optimistic primal–dual (OPD) method, which corrects each update using a prediction of the next-step gradient and is known to suppress the rotational dynamics which can cause oscillations. In the following, we first analyze OPD in the distributional policy space and establish last-iterate convergence to the optimal primal–dual solution. We then extend the analysis to parameterized policies, showing that the same guarantees hold up to approximation errors. 3.1 OPD in Distribution Space Algorithm 2 OPD with Primal Distributional Policies 0: Prompt distribution D; Reward models Rk(x,y)k∈\R_k(x,y)\_k ; soft weights wjj∈\w_j\_j ; reference policy πref _ref; KL coefficient β; initial π^0 π_0, λ0≥0 _0≥ 0; 1: for t=0,1,2,…,T−1t=0,1,2,…,T-1 do 2: Primal Optimistic Update: πt=arg _t= maxπ(ℒ(π,λt−1) _π (L(π, _t-1) . (4) −x∼[ηθKL(π(⋅|x)∥π^t(⋅|x))]), .-E_x [ _θKL (π(·|x)\| π_t(·|x) ) ] ), 3: Dual Optimistic Update: λt=arg⁡minλ≥0⁡λx∼,y∼πt−1(⋅|x)[R(x,y)]+ηλ(λ−λ^t)2, _t= _λ≥ 0 aligned & _x ,y _t-1(·|x) [R(x,y) ]\\ &+ _λ(λ- λ_t)^2, aligned (5) 4: Primal Actual Update: π^t+1=arg π_t+1= maxπ⁡ℒ(π,λt) _πL(π, _t) (6) −x∼[ηθKL(π(⋅|x)∥π^t(⋅|x))], -E_x [ _θKL (π(·|x)\| π_t(·|x) ) ], 5: Dual Actual Update: λ^t+1=arg⁡minλ≥0⁡λx∼,y∼πt(⋅|x)[R(x,y)]+ηλ(λ−λ^t)2. λ_t+1= _λ≥ 0 aligned & _x ,y _t(·|x) [R(x,y) ]\\ &+ _λ(λ- λ_t)^2. aligned (7) 6: end for 7: Return λ^T λ_T and π^T π_T. OPD update in distribution space is shown in eqs. 4, 5, 6 and 7 of algorithm 2. OPD introduces predictive iterates (πt,λt)( _t, _t) to approximate the next-step primal and dual variables. The actual updates (π^t+1,λ^t+1)( π_t+1, λ_t+1) are then corrected based on these predictions. We make the following assumptions. 3.1 corresponds to Slater’s condition, which assumes the existence of a strictly feasible policy and guarantees strong duality, i.e., the existence of the optimal saddle point. Slater’s condition is standard in the analysis of constrained optimization and primal–dual methods Huang et al. (2024); Zhang et al. (2025a); Du et al. (2025). 3.2 assumes that all reward models are uniformly bounded, which is a common condition in the RLHF literature Du et al. (2025). 3.3 requires the reference policy to assign nonzero probability to every feasible action. For LLM policies parameterized by softmax distributions, token probabilities are strictly positive over the modeled action set. When action masking or filtering is applied, we equivalently redefine the action space as the accessible set and require the reference policy to have full support on this restricted space. Assumption 3.1 (Slater’s condition). There exists a policy π¯∈Π π∈ and a constant ξ>0ξ>0 such that x∼,y∼π¯[Rj(x,y)]≥ξE_x ,y π [R_j(x,y) ]≥ξ, ∀j∈ℋ∀ j . Assumption 3.2 (Bounded rewards). There exists Rmax>0R_ >0 such that |Rk(x,y)|≤Rmax |R_k(x,y) |≤ R_ for all k∈k , x∈x , and y∈y . Assumption 3.3 (Full support of the reference policy). Assume the reference policy has the full support, i.e., there exists pmin>0p_ >0 such that πref(y|x)≥pmin _ref(y|x)≥ p_ for any (x,y)(x,y) pair. 3.3 ensures that policy supports do not collapse along the OPD iterates and that all KL divergence terms remain well-defined throughout optimization. We initialize π^0=πref π_0= _ref, and all subsequent policy updates are obtained via KL-regularized maximization. Hence, the support of π^t(⋅|x) π_t(·|x) remains contained within that of the reference policy for all t. Moreover, any optimal policy π⋆π satisfying the constraints is covered by the reference support and by the supports of the OPD iterates. This assumption prevents premature elimination of feasible actions and guarantees that OPD operates over a policy class that contains the optimal solution. Theorem 3.4. Under 3.1, 3.2, and 3.3, under suitably chosen hyper-parameters ηθ _θ and ηλ _λ (e.g., ηθ=ηλ=3|ℋ|Rmax _θ= _λ=3 |H|R_ ), then the optimistic primal–dual iterates of eqs. 4, 5, 6 and 7 satisfy x∼[KL(πθ⋆(⋅|x)∥π^t(⋅|x))]+∥⋆−^t∥22 _x [KL( _θ (·|x)\| π_t(·|x)) ]+\| λ - λ_t\|_2^2 ≤ρt−1Φ1min⁡(ηθ+β,74ηλ−34|ℋ|Rmax), ≤ρ^t-1 _1 ( _θ+β, 74 _λ- 34 |H|R_ ), where 0<ρ<10<ρ<1 is defined in eq. 46 and Φ1 _1 is a costant defined as eq. 47. theorem 3.4 establishes a linear last-iterate convergence guarantee for OPD in the policy distribution space. The final iterates (π^t,λ^t)( π_t, λ_t) converge linearly toward the optimal saddle point (π⋆,λ⋆)(π ,λ ) at rate ρ<1ρ<1, as measured by the KL divergence in the primal variable and the squared ℓ2 _2 error in the dual variable. In contrast to standard primal–dual methods that typically only ensure ergodic convergence, this result provides direct control over the final policy iterate, which is particularly important in safe RLHF, where constraint satisfaction and alignment quality are evaluated on the deployed policy rather than on an average of iterates. Moreover, the result holds under a linear dual objective and without strong convexity in the dual variable, highlighting the stabilizing effect of the optimistic primal–dual updates. 3.2 OPD in Parameter Space 3.2.1 OPD Updates in the Parameterized Policy Space In the parameterized policy space, where the policy is represented as πθ _θ with parameters θ∈Θθ∈ , the resulting Lagrangian optimization problem is generally non-convex and the closed-form distributional updates in eqs. 4 and 6 are no longer tractable. We therefore adopt a gradient-based optimistic primal–dual method in the parameter space. We denote the parameterized counterparts of πt _t and π^t π_t by πθt _ _t and πθ^t _ θ_t, respectively. To obtain a tractable update consistent with the distributional formulation shown in eqs. 4 and 6, we approximate the KL divergence by its second-order Taylor expansion around θ^t θ_t. Specifically, when θt _t is sufficiently close to θ^t θ_t, we have x∼[KL(πθt(⋅|x)∥πθ^t(⋅|x))] _x [KL ( _ _t(·|x)\| _ θ_t(·|x) ) ] ≈12(θt−θ^t)⊤F(θ^t)(θt−θ^t), ≈ 12( _t- θ_t) F( θ_t)( _t- θ_t), where F(θ)F(θ) denotes the Fisher information matrix, F(θ)=x∼,y∼πθ(⋅|x)[∇θlog⁡πθ(y|x)∇θlog⁡πθ(y|x)⊤].F(θ)=E_x ,y _θ(·|x) [ _θ _θ(y|x) _θ _θ(y|x) ]. To accommodate possible rank deficiency, we use the Moore-Penrose pseudo-inverse F(θ)†F(θ) . Under this local approximation, the distributional OPD updates reduce to natural policy gradient (NPG) steps in the parameter space. To ensure feasibility in the parameter domain, we project the updated parameters back onto the parameter space Θ after each primal update. Similar to algorithm 2, the proposed method first performs optimistic primal and dual updates to predict the next-step policy parameters and dual variables, as shown in eqs. 8 and 9. The actual primal and dual updates are then carried out using these predictions, as specified in eqs. 10 and 11. The complete OPD procedure in the parameterized policy space is summarized in algorithm 3. The parameterized OPD applies optimism asymmetrically across the primal and dual variables. In particular, the predicted policy iterate πθt _ _t is only used to form the dual updates λt _t and λ^t+1 λ_t+1, whereas the actual policy πθ^t _ θ_t is used for the primal updates θt _t and θ^t+1 θ_t+1. This asymmetric design ensures that policy-gradient computations are performed only for the actual policy updates, while the predicted policy iterate πθt _ _t is used solely for evaluation in the dual updates and does not require gradient computation. In contrast, symmetric extragradient methods Ding et al. (2023) typically require evaluating both primal and dual operators at the predictor iterate, resulting in higher computational cost and variance. Algorithm 3 OPD with Primal Parameterized Policies 0: Prompt distribution D; Reward models Rk(x,y)k∈\R_k(x,y)\_k ; soft weights wjj∈\w_j\_j ; reference policy πref _ref; KL coefficient β; initial θ^0 θ_0, λ0≥0 _0≥ 0; 1: for t=0,1,2,…,T−1t=0,1,2,…,T-1 do 2: Primal Optimistic Update: θt=ProjΘ(θ^t+1ηθ+βF(θ^t)†∇θℒ(πθ^t,λt−1)). _t=Proj_ ( θ_t+ 1 _θ+βF( θ_t) _θL( _ θ_t, _t-1) ). (8) 3: Dual Optimistic Update: λt=[λ^t−1ηλx∼,y∼πθt−1(⋅|x)[R(x,y)]]+. _t= [ λ_t- 1 _λE_x ,\,y _ _t-1(·|x) [R(x,y) ] ]_+. (9) 4: Primal Actual Update: θ^t+1=ProjΘ(θ^t+1ηθ+βF(θ^t)†∇θℒ(πθ^t,λt)). θ_t+1=Proj_ ( θ_t+ 1 _θ+βF( θ_t) _θL( _ θ_t, _t) ). (10) 5: Dual Actual Update: λ^t+1=[λ^t−1ηλx∼,y∼πθt(⋅|x)[R(x,y)]]+. λ_t+1= [ λ_t- 1 _λE_x ,\,y _ _t(·|x) [R(x,y) ] ]_+. (11) 6: end for 7: Return λ^T λ_T and πθ^T _ θ_T. Remark 3.5 (Equivalence between Distribution-Space OPD and NPG Updates). Under tabular softmax parameterization, the distribution-space OPD updates in eqs. 4, 5, 6 and 7 are equivalent to their parameter-space counterparts in eqs. 8, 9, 10 and 11. In particular, for all t, the induced policies satisfy πθt=πt _ _t= _t and πθ^t+1=π^t+1 _ θ_t+1= π_t+1. The key observation is that, under tabular softmax parameterization, policy parameters θ are in one-to-one correspondence with policy distributions. Moreover, KL-regularized optimization in the distribution space is exactly equivalent to mirror descent under the KL geometry, which corresponds to NPG updates in the parameter space. As a result, the distribution-space OPD updates generate exactly the same sequence of policies as the NPG-based OPD updates. Remark 3.6 (Relationship to PPO in Practice). NPG controls policy updates by explicitly constraining the KL divergence between consecutive policies, while proximal policy optimization (PPO) enforces update stability by directly clipping the policy ratio. Although the two approaches differ in their formulations, both can be interpreted as mechanisms for bounding policy updates and preventing overly aggressive policy changes. In practice, PPO is often preferred due to its simplicity and empirical robustness, and the proposed OPD framework can be implemented using PPO-style clipped updates. In this paper, we adopt the NPG formulation for analytical convenience, as it provides a clean connection to KL-regularized optimization and facilitates theoretical analysis. In our experiments, we implement the proposed OPD framework using PPO-style updates. 3.2.2 A Toy RLHF Example Illustrating the Stability of OPD Figure 1: Comparison of OPD and PD under a softmax tabular parameterization in a single-state, two-action RLHF toy problem. OPD (red) converges to the optimal solution in the last iterate, while PD (blue) exhibits persistent oscillations and fails to converge. We consider a minimal RLHF-style constrained optimization problem with a single state (||=1|X|=1) and two actions (||=2|Y|=2), denoted by y0y_0 and y1y_1. Since there is only one state, we omit the dependence on x in the following. We consider two reward models. The first reward RsR_s represents the objective to be maximized, while the second reward RhR_h corresponds to a safety-related constraint. We set Rs(y0)=1R_s(y_0)=1 and Rs(y1)=0R_s(y_1)=0, so that the expected reward under a policy π is simply π(y0)π(y_0). For the constraint reward, we choose Rh(y0)=−0.7R_h(y_0)=-0.7 and Rh(y1)=0.3R_h(y_1)=0.3, which induces the constraint −0.7π(y0)+0.3(1−π(y0))≥0-0.7\,π(y_0)+0.3\,(1-π(y_0))≥ 0, or equivalently π(y0)≤0.3π(y_0)≤ 0.3. We select the reference policy as πref(y0)=0.3 _ref(y_0)=0.3. The resulting optimization problem is to maximize π(y0)−βKL(π(⋅)∥πref(⋅))subject toπ(y0)≤0.3,π(y_0)-β\,KL\! (π(·)\, \|\, _ref(·) ) to π(y_0)≤ 0.3, with β=0.05β=0.05. It is easy to verify that the optimal policy coincides with the reference policy πref _ref. To avoid explicit projection onto the policy simplex, we adopt a softmax parameterization π(y0)=1/(1+exp⁡(θ))π(y_0)=1/(1+ (θ)). We set the effective primal stepsize α=(ηθ+β)−1=0.6α=( _θ+β)^-1=0.6 and the dual stepsize ηλ−1=0.6 _λ^-1=0.6. Figure 1 compares the trajectories of OPD and standard primal–dual updates under this parameterization. As shown in fig. 1, the proposed OPD method converges to the optimal saddle point, with the distance to the optimum decreasing linearly, consistent with the theoretical guarantees in theorem 3.4. In contrast, the standard PD updates fail to converge and exhibit divergent behavior in this simple setting. 3.2.3 Theoretical Results Let ΠΘ _ denote the class of parameterized policies that have full support on the considered action set, i.e., there exists pmin>0p_ >0 such that πθ(y|x)≥pmin _θ(y|x)≥ p_ for all feasible (x,y)(x,y). We further assume that the parameter domain Θ⊂ℝd ^d is closed and convex, so that the projection operator ProjΘ(⋅)Proj_ (·) used in the updates is well-defined. Since our analysis focuses on optimality within the parameterized policy class, we impose a Slater-type condition in the parameterized policy space. Assumption 3.7 (Slater’s condition in the parameterized policy space). There exists a parameter vector θ¯∈Θ θ∈ and a constant ξ>0ξ>0 such that the corresponding policy πθ¯∈ΠΘ _ θ∈ _ satisfies x∼,y∼πθ¯(⋅|x)[Rj(x,y)]≥ξ,∀j∈ℋ.E_x ,y _ θ(·|x) [R_j(x,y) ]≥ξ, ∀ j . 3.8 assumes that the log-policy is Lipschitz continuous with respect to the policy parameters. This condition allows us to translate deviations in the parameter space into controlled changes in the induced policy distributions, and is particularly useful for bounding KL divergence and log-ratio terms that arise in the analysis. Such an assumption is standard in the analysis of policy gradient and mirror descent methods with parameterized policies. Assumption 3.8 (Log-policy Lipschitz continuity). There exists a constant C>0C>0 such that for any θ1,θ2∈Θ _1, _2∈ , x∼,y∼(x)[|logπθ1(y|x)−logπθ2(y|x)|]≤C∥θ1−θ2∥1.E_x ,\,y (x) [ | _ _1(y|x)- _ _2(y|x) | ]≤ C\| _1- _2\|_1. As the primal updates rely on stochastic gradient estimates and empirical Fisher information computed from finite samples, we make the following assumption to quantify the inexactness arises naturally in practice. Assumption 3.9 (Inexact primal updates). Let θt∗ _t^* and θ^t+1∗ θ_t+1^* denote the exact primal updates defined by eqs. 8 and 10 when all expectations are computed exactly. Due to stochastic estimation and numerical approximation, the implemented updates produce θt _t and θ^t+1 θ_t+1 such that, for all t, [‖θt−θt∗‖1]≤ϵapprox,[‖θ^t+1−θ^t+1∗‖1]≤ϵapprox.E [\| _t- _t^*\|_1 ]≤ _approx,\,E [\| θ_t+1- θ_t+1^*\|_1 ]≤ _approx. Such per-iteration errors are standard in the analysis of stochastic mirror descent and natural policy gradient methods. In the tabular setting with exact expectations, this approximation error vanishes, i.e., ϵapprox=0 _approx=0. For parameterized policies, ϵapprox _approx captures the combined effects of sampling noise and numerical approximation, and can be made arbitrarily small with sufficiently large batch sizes. Corollary 3.10. Under 3.2, 3.3, 3.7, 3.8 and 3.9, under suitably chosen hyper-parameters ηθ _θ and ηλ _λ (e.g., ηθ=ηλ=3|ℋ|Rmax _θ= _λ=3 |H|R_ ), then the optimistic primal–dual iterates of eqs. 8, 9, 10 and 11 satisfies x∼[KL(πθ⋆(⋅|x)∥π^t(⋅|x))]+∥⋆−^t∥22 _x [KL( _θ (·|x)\| π_t(·|x)) ]+\| λ - λ_t\|_2^2 ≤ρt−1Φ1min⁡(ηθ+β,74ηλ−34|ℋ|Rmax) ≤ρ^t-1 _1 ( _θ+β, 74 _λ- 34 |H|R_ ) +2(1−ρt)1−ρgap(εapprox,pmin), + 2(1-ρ^t)1-ρgap( _approx,p_ ), where 0<ρ<10<ρ<1 is defined in eq. 46 and Φ1 _1 is defined as eq. 47, and gap(εapprox,pmin)gap( _approx,p_ ) is defined in eq. 28. The additional error term gap(εapprox,pmin)gap( _approx,p_ ) characterizes the error gap induced by function approximation and finite-sample estimation in the policy update, and it determines the radius of a bounded neighborhood around the optimal saddle point (π⋆,λ⋆)(π ,λ ). The geometric contraction factor ρt−1ρ^t-1 with 0<ρ<10<ρ<1 ensures last-iterate convergence. OPD in the parameter space preserves geometric last-iterate convergence, implying that function approximation does not destroy the stabilizing effect of optimism, but only introduces a controlled residual error. As the approximation error vanishes, the neighborhood shrinks accordingly. This result establishes OPD as a robust framework for constrained RLHF under practical policy parameterizations. 4 Computational Experiments In this section, we empirically evaluate the effectiveness and robustness of the proposed OPD-based methods for aligning helpfulness and harmlessness. Specifically, our experiments are designed to answer the following questions: • How robust is the training process of the proposed OPD-based method compared to standard PD-based approaches? • Does improved training stability translate into superior performance at evaluation time? Datasets and Reward Models We adopt the Alpaca-7b-reproduced model as the reference policy throughout our experiments. For model-based alignment, we directly use the beaver-7b-v1.0-reward and beaver-7b-v1.0-cost models released with Safe-RLHF Dai et al. (2024) as the reward model for the target objective and the safety model for the constraint, respectively. Note that the original Safe-RLHF formulation enforces the cost to be smaller than zero; to match our constraint convention, we negate the cost model outputs. We conduct our experiments on the PKU-SafeRLHF-30K preference dataset Dai et al. (2024), which contains approximately 27K training prompts and 3K test prompts, each paired with a preferred and a less-preferred response. In addition to preference labels, the dataset provides safety annotations, where preferences are determined jointly based on helpfulness and harmlessness. OPD implementation On the primal side, we follow the standard PPO-style implementation used in practical RLHF systems. Specifically, the policy update is implemented via a clipped policy gradient objective, which can be viewed as a practical approximation of NPG under a trust-region constraint induced by the KL divergence to the reference policy. This design ensures stable policy updates while remaining compatible with large-scale language model fine-tuning. On the dual side, the dual variable λ is updated using gradient ascent in the logarithmic parameterization log⁡λ λ to enforce non-negativity and improve numerical stability. We store the dual gradient from the previous iteration and construct an extrapolated gradient using an extragradient-style correction. The effective update direction is given by gtOPD=2gt−gt−1,g_t^OPD=2g_t-g_t-1, where gtg_t denotes the gradient of the dual objective at iteration t. This corrected gradient is applied directly to the log-dual variable log⁡λ λ, yielding an optimistic update that anticipates future primal responses. Our OPD implementation explicitly introduces temporal coupling across iterations through gradient reuse. We set both the actor and critic learning rates to 5×10−55× 10^-5, and the stepsize for the dual variable λ to 0.50.5. These relatively aggressive stepsizes intentionally place PD-based methods in an unstable regime, allowing us to test the robustness of the proposed OPD updates. As shown in fig. 2, the OPD method converges to policies that satisfy the safety constraints while maintaining competitive rewards, whereas PD-based methods exhibit degraded safety performance at convergence. Figure 2: Comparison of PD and OPD on reward and constrained reward during the training phase. We conduct model-based evaluations for both helpfulness and safety, as shown in fig. 3. Specifically, the generated responses are evaluated by computing the corresponding average helpfulness and safety scores using the proxy reward and safety models. The evaluation results show that the OPD-based method achieves higher rewards and constraints than PD-based methods, indicating that improved training stability translates into superior evaluation performance. Figure 3: Inference comparison of PD and OPD on reward and cost. 5 Conclusion We develop a universal primal–dual framework that unifies a broad class of Lagrangian approaches to constrained RLHF. Building on this framework, we propose an OPD algorithm that introduces predictive updates for both the primal policy and the dual multipliers to stabilize saddle-point dynamics. We establish last-iterate convergence in both the distributional policy space and the parameterized policy space. In the distributional setting, the iterates converge to the exact saddle point; in the parameterized setting, they converge to a neighborhood of the optimum. We compare standard primal–dual training with our OPD variant. With more aggressive step sizes, OPD exhibits improved training stability relative to PD, and this stability translates into better performance in evaluations. References A. Agnihotri, R. Jain, D. Ramachandran, and Z. Wen (2025) Multi-objective preference optimization: improving human alignment of generative models. arXiv preprint arXiv:2505.10892. Cited by: Appendix A. M. G. Azar, Z. D. Guo, B. Piot, R. Munos, M. Rowland, M. Valko, and D. Calandriello (2024) A general theoretical paradigm to understand learning from human preferences. In International Conference on Artificial Intelligence and Statistics, p. 4447–4455. Cited by: Appendix A. J. Dai, X. Pan, R. Sun, J. Ji, X. Xu, M. Liu, Y. Wang, and Y. Yang (2024) Safe rlhf: safe reinforcement learning from human feedback. In The Twelfth International Conference on Learning Representations, Cited by: Appendix A, §1, §1, §1, 1st item, §4. C. Daskalakis and I. Panageas (2018) The limit points of (optimistic) gradient descent in min-max optimization. Advances in neural information processing systems 31. Cited by: §3. G. S. Dhillon, X. Shi, Y. W. Teh, and A. Smola (2024) L3Ms–lagrange large language models. arXiv preprint arXiv:2410.21533. Cited by: Appendix A. D. Ding, C. Wei, K. Zhang, and A. Ribeiro (2023) Last-iterate convergent policy gradient primal-dual methods for constrained mdps. Advances in Neural Information Processing Systems 36, p. 66138–66200. Cited by: §1, §3.2.1. D. Ding, K. Zhang, J. Duan, T. Basar, and M. R. Jovanovic (2025) Convergence and sample complexity of natural policy gradient primal-dual methods for constrained mdps. Journal of Machine Learning Research 26 (256), p. 1–76. Cited by: Lemma B.5. Y. Du, S. T. Kong, and R. Srikant (2025) Primal-dual direct preference optimization for constrained llm alignment. arXiv preprint arXiv:2510.05703. Cited by: Appendix A, §1, 1st item, §3.1. D. Elshin, N. Karpachev, B. Gruzdev, I. Golovanov, G. Ivanov, A. Antonov, N. Skachkov, E. Latypova, V. Layner, E. Enikeeva, et al. (2024) From general llm to translation: how we dramatically improve translation quality using human evaluation data for llm finetuning. In Proceedings of the Ninth Conference on Machine Translation, p. 247–252. Cited by: §1. K. Ethayarajh, W. Xu, N. Muennighoff, D. Jurafsky, and D. Kiela (2024) Kto: model alignment as prospect theoretic optimization. arXiv preprint arXiv:2402.01306. Cited by: Appendix A. G. Feretzakis and V. S. Verykios (2024) Trustworthy ai: securing sensitive data in large language models. AI 5 (4), p. 2773–2800. Cited by: §1. N. M. Guerreiro, D. M. Alves, J. Waldendorf, B. Haddow, A. Birch, P. Colombo, and A. F. Martins (2023) Hallucinations in large multilingual translation models. Transactions of the Association for Computational Linguistics 11, p. 1500–1517. Cited by: §1. J. Hong, N. Lee, and J. Thorne (2024) Orpo: monolithic preference optimization without reference model. arXiv preprint arXiv:2403.07691. Cited by: Appendix A. S. Huang, A. Abdolmaleki, G. Vezzani, P. Brakel, D. J. Mankowitz, M. Neunert, S. Bohez, Y. Tassa, N. Heess, M. Riedmiller, et al. (2022) A constrained multi-objective reinforcement learning framework. In Conference on Robot Learning, p. 883–893. Cited by: §1. X. Huang, S. Li, E. Dobriban, O. Bastani, H. Hassani, and D. Ding (2024) One-shot safety alignment for large language models via optimal dualization. Advances in Neural Information Processing Systems 37, p. 84350–84383. Cited by: Appendix A, §1, §1, 3rd item, §2.3, §3.1. G. Kim, Y. Jang, Y. J. Kim, B. Kim, H. Lee, K. Bae, and M. Lee (2025) SafeDPO: a simple approach to direct preference optimization with enhanced safety. arXiv preprint arXiv:2505.20065. Cited by: Appendix A. Z. Liu, X. Sun, and Z. Zheng (2024) Enhancing llm safety via constrained direct preference optimization. arXiv preprint arXiv:2403.02475. Cited by: Appendix A, 1st item. L. Ouyang, J. Wu, X. Jiang, D. Almeida, C. Wainwright, P. Mishkin, C. Zhang, S. Agarwal, K. Slama, A. Ray, et al. (2022) Training language models to follow instructions with human feedback. Advances in neural information processing systems 35, p. 27730–27744. Cited by: §2.1. R. Rafailov, A. Sharma, E. Mitchell, C. D. Manning, S. Ermon, and C. Finn (2023) Direct preference optimization: your language model is secretly a reward model. Advances in neural information processing systems 36, p. 53728–53741. Cited by: Appendix A. T. Sorensen, J. Moore, J. Fisher, M. Gordon, N. Mireshghallah, C. M. Rytting, A. Ye, L. Jiang, X. Lu, N. Dziri, et al. (2024) A roadmap to pluralistic alignment. arXiv preprint arXiv:2402.05070. Cited by: §1. N. Stiennon, L. Ouyang, J. Wu, D. Ziegler, R. Lowe, C. Voss, A. Radford, D. Amodei, and P. F. Christiano (2020) Learning to summarize with human feedback. Advances in neural information processing systems 33, p. 3008–3021. Cited by: §1, §2.1. A. Wachi, T. Tran, R. Sato, T. Tanabe, and Y. Akimoto (2024) Stepwise alignment for constrained language model policy optimization. Advances in Neural Information Processing Systems 37, p. 104471–104520. Cited by: Appendix A. J. Wang and Y. Chen (2023) A review on code generation with llms: application and evaluation. In 2023 IEEE International Conference on Medical Artificial Intelligence (MedAI), p. 284–289. Cited by: §1. J. Wen, P. Ke, H. Sun, Z. Zhang, C. Li, J. Bai, and M. Huang (2023) Unveiling the implicit toxicity in large language models. arXiv preprint arXiv:2311.17391. Cited by: §1. R. Yang, X. Pan, F. Luo, S. Qiu, H. Zhong, D. Yu, and J. Chen (2024) Rewards-in-context: multi-objective alignment of foundation models with dynamic preference adjustment. In Proceedings of the 41st International Conference on Machine Learning, p. 56276–56297. Cited by: Appendix A, Appendix A. M. Zamani, H. Abbaszadehpeivasti, and E. de Klerk (2024) Convergence rate analysis of the gradient descent–ascent method for convex–concave saddle-point problems. Optimization Methods and Software 39 (5), p. 967–989. Cited by: §3. B. Zhang, S. Li, I. Hounie, O. Bastani, D. Ding, and A. Ribeiro (2025a) Alignment of large language models with constrained learning. arXiv preprint arXiv:2505.19387. Cited by: Appendix A, §1, §1, 2nd item, §3.1. Y. Zhang, H. Jin, D. Meng, J. Wang, and J. Tan (2024) A comprehensive survey on process-oriented automatic text summarization with exploration of llm-based methods. arXiv preprint arXiv:2403.02901. Cited by: §1. Y. Zhang, Y. Li, L. Cui, D. Cai, L. Liu, T. Fu, X. Huang, E. Zhao, Y. Zhang, Y. Chen, et al. (2025b) Siren’s song in the ai ocean: a survey on hallucination in large language models. Computational Linguistics, p. 1–46. Cited by: §1. Z. Zhou, J. Liu, J. Shao, X. Yue, C. Yang, W. Ouyang, and Y. Qiao (2024) Beyond one-preference-fits-all alignment: multi-objective direct preference optimization. In Findings of the Association for Computational Linguistics: ACL 2024, p. 10586–10613. Cited by: Appendix A. D. M. Ziegler, N. Stiennon, J. Wu, T. B. Brown, A. Radford, D. Amodei, P. Christiano, and G. Irving (2019) Fine-tuning language models from human preferences. arXiv preprint arXiv:1909.08593. Cited by: §1, §2.1. Appendix A Related Works This section summarizes the related work in the LLMs safety alignment. Constrained Alignment for LLMs There is a growing body of work that formulates safe RLHF as a constrained optimization problem, where helpfulness is maximized subject to safety-related constraints Dai et al. (2024); Huang et al. (2024); Zhang et al. (2025a). A representative approach is modeling the safety violations via an expected cost constraint and solving the resulting constrained objective using iterative primal-dual updates Dai et al. (2024). However, the primal-dual methods can be computationally expensive and may suffer from training instability and hyperparameter sensitivity Huang et al. (2024). To mitigate these issues, Huang et al. (2024) leverages the closed-form structure of the optimal distribution induced by fixed dual variables, and optimizes a smooth dual objective to eliminate repeated primal-dual policy iterations. This dualization-based method leads to more stable training in practice. In contrast, Zhang et al. (2025a) studies constrained alignment in the parameterized LLM policy space and develops an iterative dual-based alignment method that alternates between maximizing the Lagrangian over the LLM policy parameters and performing dual descent updates. Dhillon et al. (2024) proposes an interior point method and uses a relaxed log-barrier function to enforce constraints, thereby avoiding the oscillation between primal and dual variables. Existing approaches stabilize training via simplifying the dual problem with the closed-form structure of the optimal policy distribution, solving near-optimal primal subproblems for each dual variable, or enforcing the constraints with the interior-point methods. However, it is still an open question of how to design iterative primal-dual updates with provable last-iterate guarantees for constrained LLM alignment. RL-free Based Safety Alignment In parallel, a line of RL-free methods has been proposed for preference alignment, which bypasses explicit reward model learning and policy optimization via reinforcement learning, and instead directly optimize the policy using preference data Rafailov et al. (2023); Azar et al. (2024); Ethayarajh et al. (2024); Hong et al. (2024); Yang et al. (2024). Building upon these approaches, several recent works propose constrained preference alignment in an RL-free manner Liu et al. (2024); Wachi et al. (2024); Du et al. (2025); Kim et al. (2025). Among them, some methods still adopt a primal-dual perspective and iteratively update both the policy and the dual variables, while using Direct Policy Optimization (DPO)-style objectives as the primal optimizer Liu et al. (2024); Du et al. (2025). To implicitly control the trade-off between reward and safety using only reward and cost preference datasets, existing approaches either reweight or reconstruct preference data according to the current dual variables Liu et al. (2024), or perform separate preference optimization on reward and cost datasets under a Lagrangian formulation Du et al. (2025). In contrast, Wachi et al. (2024) avoids iterative dual updates and instead performs constrained alignment that evaluates multiple fixed dual values. Kim et al. (2025) proposes a heuristic yet lightweight approach that enforces safety by directly reordering preference pairs: responses that violate safety guidelines are automatically relabeled as the worse one, enabling safety-aware alignment without explicit dual optimization. While these RL-free approaches improve efficiency and empirical stability, they either rely on heuristic trade-off control or lack a principled analysis with respect to last-iterate convergence under safety constraints. General Multi-objective Preference Optimization Beyond single-constraint formulations, several works study alignment from a multi-objective perspective. Some approaches aim to approximate Pareto-optimal policies by optimizing scalarization over multiple objectives with respect to a given preference vector Zhou et al. (2024). Other works vary the threshold of constraints to construct a Pareto front, where a primary objective is optimized subject to secondary objectives satisfying varying bounds, enabling flexible trade-offs between helpfulness and safety Agnihotri et al. (2025). In addition, recent work explores context-dependent preference modeling, where alignment objectives dynamically vary with user intent or task context, as exemplified by reward-in-context approaches Yang et al. (2024). While these methods emphasize flexible and expressive preference modeling, they typically do not analyze the optimization dynamics of constrained saddle-point formulations, particularly under expectation-based safety constraints. Appendix B Useful Lemmas Lemma B.1 (Hölder’s inequality). ‖fq‖1≤‖f‖p‖g‖q\|fq\|_1≤\|f\|_p\|g\|_q for 1p+1q=1 1p+ 1q=1. Lemma B.2 (Pinsker’s inequality (discrete form)). Let p=[p1,⋯,pd]⊤p=[p_1,·s,p_d] and q=[q1,⋯,qd]⊤q=[q_1,·s,q_d] be probability vectors on a finite set, and assume KL(p∥q)<∞KL(p\|q)<∞. Then ‖p−q‖1≤2KL(p∥q).\|p-q\|_1≤ 2KL(p\|q). Lemma B.3 (Young’s inequality). For δ>0δ>0 and ,∈ℝdu,v ^d, |⟨,⟩|≤δ2‖22+12δ‖22.| ,v |≤ δ2\|u\|_2^2+ 12δ\|v\|_2^2. Lemma B.4. For any δ,θ>0δ,θ>0, we have ‖++‖2≥(1−δ)‖2+(1−1δ)(1−θ)‖2+(1−1δ)(1−1θ)‖2.\|a+b+c\|^2≥(1-δ)\|a\|^2+(1- 1δ)(1-θ)\|b\|^2+(1- 1δ)(1- 1θ)\|c\|^2. Proof. By Young’s inequality for any δ>0δ>0, ⟨,⟩≥−δ2‖2−12δ‖2 ,\,y ≥- δ2\|x\|^2- 12δ\|y\|^2, we have ‖+‖2=‖2+‖2+2⟨,⟩≥(1−δ)‖2+(1−1δ)‖2\|x+y\|^2=\|x\|^2+\|y\|^2+2 ,\,y ≥(1-δ)\|x\|^2+(1- 1δ)\|y\|^2. For any δ,θ>0δ,θ>0 ‖++‖2=‖2+‖+‖2+2⟨,+⟩ \|a+b+c\|^2=\|a\|^2+\|b+c\|^2+2 ,b+c ≥(1−δ)‖2+(1−1δ)‖+‖2 ≥(1-δ)\|a\|^2+(1- 1δ)\|b+c\|^2 ≥(1−δ)‖2+(1−1δ)((1−θ)‖2+(1−1θ)‖2) ≥(1-δ)\|a\|^2+(1- 1δ)((1-θ)\|b\|^2+(1- 1θ)\|c\|^2) =(1−δ)‖2+(1−1δ)(1−θ)‖2+(1−1δ)(1−1θ)‖2. =(1-δ)\|a\|^2+(1- 1δ)(1-θ)\|b\|^2+(1- 1δ)(1- 1θ)\|c\|^2. ∎ Lemma B.5. (Ding et al. (2025) Lemme 3(b)) Let 3.1 hold, then λ∗>0λ^*>0 and ‖λ∗‖1≤ \|λ^* \|_1≤ 1ξx∼[(y∼π∗(⋅|x)[∑j∈wjRj(x,y)]−βKL(π∗(⋅|x)||πref(⋅|x))) 1ξE_x [ (E_y π^*(·|x) [ _j w_jR_j(x,y) ]- (π^*(·|x)|| _ref(·|x)) ) . −(y∼π¯(⋅|x)[∑j∈wjRj(x,y)]−βKL(π∗(⋅|x)||πref(⋅|x)))]. .- (E_y π(·|x) [ _j w_jR_j(x,y) ]- (π^*(·|x)|| _ref(·|x)) ) ]. Remark B.6. Assume 3.2 and 3.3 hold. By 3.2, we have Rj(x,y)≤RmaxR_j(x,y)≤ R_ for any j∈j and (x,y)(x,y) pairs. By 3.3, there exists pmin>0p_ >0 such that πref(y|x)≥pmin _ref(y|x)≥ p_ for any (x,y)(x,y) pair. By lemma B.5, we have ‖λ∗‖1≤2ξ(Rmax+βlog⁡1pmin).\|λ^*\|_1≤ 2ξ (R_ +β 1p_ ). Define ‖1,max=2ξ(Rmax+βlog⁡1pmin)\| λ\|_1, = 2ξ (R_ +β 1p_ ). If we set Λ=λ|‖λ‖1≤‖1,max =\λ|\|λ\|_1≤\| λ\|_1, \, then the optimality of λ∗λ^* is not affected by projection. Lemma B.7. Given an optimization problem maxπx∼[y∼π(⋅|x)[S(x,y)]−βKL(π(⋅|x)∥πref(⋅|x))] _πE_x [E_y π(·|x)[S(x,y)]- (π(·|x)\| _ref(·|x) )] (12) The solution can be written as π⋆(y|x)=1Z(x)πref(y|x)exp⁡(1βS(x,y)),π (y|x)= 1Z(x) _ref(y|x) ( 1βS(x,y) ), where Z(x)Z(x) is the normalization factor Z(x)=∑yπref(y|x)exp⁡(1βS(x,y))Z(x)= _y _ref(y|x) ( 1βS(x,y) ). Proof. Since the objective decomposes over x, the maximizer can be found pointwise in x. For a fixed x, we can rewrite the optimization problem as maxπ(⋅|x)∈Δ∑yπ(y|x)S(x,y)−β∑yπ(y|x)log⁡π(y|x)πref(y|x), _π(·|x)∈ _yπ(y|x)S(x,y)-β _yπ(y|x) π(y|x) _ref(y|x), (13) where Δ=|‖1=1 and >0 =\x|\|x\|_1=1 and x>0\ Introduce a multiplier η(x)η(x) for the normalization constraint. The Lagrangian for eq. 13 is ℒx(πx,η)=∑yπ(y|x)S(x,y)−β∑yπ(y|x)log⁡π(y|x)πref(y|x)+η(x)(∑yπ(y|x)−1).L_x( _x,η)= _yπ(y|x)S(x,y)-β _yπ(y|x) π(y|x) _ref(y|x)+η(x)( _yπ(y|x)-1). (14) Taking the derivative w.r.t. π(y|x)π(y|x) and setting to zero gives, for every y in the support, 0=∂ℒx∂π(y|x) 0= _x∂π(y|x) =S(x,y)−β(log⁡π(y|x)−log⁡πref(y|x)+1)+η(x). =S(x,y)-β( π(y|x)- _ref(y|x)+1)+η(x). (15) Rearranging eq. 15 yields log⁡π(y|x) π(y|x) =log⁡πref(y|x)+1β(S(x,y)+η(x)−β). = _ref(y|x)+ 1β(S(x,y)+η(x)-β). ⇒π⋆(y|x) π (y|x) =πref(y|x)exp⁡(1β(S(x,y)+η(x)−β)), = _ref(y|x) ( 1β(S(x,y)+η(x)-β) ), (16) Taking the derivative w.r.t. η(x)η(x) and setting to zero gives ∑yπ⋆(y|x)=1 _yπ (y|x)=1. Therefore, we have π⋆(y|x)=1Z(x)πref(y|x)exp⁡(1βS(x,y))π (y|x)= 1Z(x) _ref(y|x) ( 1βS(x,y) ), where Z(x)=∑yπref(y|x)exp⁡(1βS(x,y))Z(x)= _y _ref(y|x) ( 1βS(x,y) ). ∎ Lemma B.8 (Three-point identity for Bregman divergences). Let f:Ω→ℝf: be a function that is: a) strictly convex, b) continuously differentiable, c) defined on a closed convex set Ω . Then the Bregman divergence is defined as Df(u,v)=f(u)−f(v)−⟨∇f(v),u−v⟩,∀x,y∈ΩD_f(u,v)=f(u)-f(v)- ∇ f(v),u-v ,∀ x,y∈ . Then for all x,y,z∈Ωx,y,z∈ Df(x,z)−Df(x,y)−Df(y,z)=⟨∇yDf(y,z),x−y⟩.D_f(x,z)-D_f(x,y)-D_f(y,z)= _yD_f(y,z),x-y . (17) Proof. By the definition of the Bregman divergence, we have Df(x,z) D_f(x,z) =f(x)−f(z)−⟨∇f(z),x−z⟩, =f(x)-f(z)- ∇ f(z),x-z , Df(x,y) D_f(x,y) =h(x)−h(y)−⟨∇f(y),x−y⟩, =h(x)-h(y)- ∇ f(y),x-y , Df(y,z) D_f(y,z) =f(y)−f(z)−⟨∇f(z),y−z⟩. =f(y)-f(z)- ∇ f(z),y-z . Subtracting the latter two from the first gives Df(x,z)−Df(x,y)−Df(y,z) D_f(x,z)-D_f(x,y)-D_f(y,z) =(f(x)−f(z)−⟨∇f(z),x−z⟩)−(f(x)−f(y)−⟨∇f(y),x−y⟩)−(f(y)−f(z)−⟨∇f(z),y−z⟩) =(f(x)-f(z)- ∇ f(z),x-z )-(f(x)-f(y)- ∇ f(y),x-y )-(f(y)-f(z)- ∇ f(z),y-z ) =−⟨∇f(z),x−z⟩+⟨∇f(y),x−y⟩+⟨∇f(z),y−z⟩ =- ∇ f(z),x-z + ∇ f(y),x-y + ∇ f(z),y-z =⟨∇f(y),x−y⟩−⟨∇f(z),x−y⟩ = ∇ f(y),x-y - ∇ f(z),x-y =⟨∇f(y)−∇f(z),x−y⟩. = ∇ f(y)-∇ f(z),x-y . Also we have ⟨∇yDf(y,z),x−y⟩ _yD_f(y,z),x-y =⟨∇y(f(y)−f(z)−⟨∇f(z),y−z⟩),x−y⟩ = _y (f(y)-f(z)- ∇ f(z),y-z ),x-y =⟨∇f(y)−∇f(z),x−y⟩ = ∇ f(y)-∇ f(z),x-y This concludes the proof. ∎ Lemma B.9. Let h:Ω→ℝh: be a function that is: a) strictly convex, b) continuously differentiable, c) defined on a closed convex set Ω , and Dh(u,v),∀u,vD_h(u,v),∀ u,v be the Bregman divergence defined on h. Let f()=⟨g,⟩−ηDh(,old)f(x)= g,x -η D_h(x,x_old). Given step sizes η>0η>0, consider the update new=arg⁡max∈Ω⁡f().x_new= _x∈ f(x). (18) Then for any ′∈Ωx ∈ , ⟨g,new−′⟩≥η(−Dh(′,old)+Dh(′,new)+Dh(new,old)). g,x_new-x ≥η (-D_h(x ,x_old)+D_h(x ,x_new)+D_h(x_new,x_old) ). (19) Proof. Note that f()= f(x)= ⟨g,⟩−ηDh(,old) g,x -η D_h(x,x_old) = = ⟨g,⟩−η(h()−h(old)−⟨∇h(old),−old⟩) g,x -η(h(x)-h(x_old)- ∇ h(x_old),x-x_old ) = = ⟨g−η∇h(old),⟩−ηh()+ηh(old)+η⟨∇h(old),old⟩. g-η∇ h(x_old),x -η h(x)+η h(x_old)+η ∇ h(x_old),x_old . The first term is linear with x, and the second term is strictly concave with x since h(⋅)h(·) is strictly convex, and the last two terms are constants with x. Therefore, f()f(x) is strictly concave with x. As f(⋅)f(·) is differentiable on Ω and new=arg⁡max∈Ω⁡f()x_new= _x∈ f(x), we have ⟨∇f(new),new−′⟩≥0. ∇ f(x_new),x_new-x ≥ 0. Substituting f()=⟨g,⟩−ηDh(,old)f(x)= g,x -η D_h(x,x_old) into the above inequality, we have ⟨g−η∇Dh(new,old),new−′⟩≥0. g-η∇ D_h(x_new,x_old),x_new-x ≥ 0. (20) Let x=′x=x , y=newy=x_new, and z=oldz=x_old and Df(⋅,⋅)=Dh(⋅,⋅)D_f(·,·)=D_h(·,·) in lemma B.8, we have ⟨∇Dh(new,old),′−new⟩=Dh(′,old)−Dh(′,new)−Dh(new,old). ∇ D_h(x_new,x_old),x -x_new =D_h(x ,x_old)-D_h(x ,x_new)-D_h(x_new,x_old). Substituting the above equation to the LHS of eq. 20, we get ⟨g,new−′⟩+η(Dh(′,old)−Dh(′,new)−Dh(new,old))≥0. g,x_new-x +η (D_h(x ,x_old)-D_h(x ,x_new)-D_h(x_new,x_old) )≥ 0. This completes the proof. ∎ Lemma B.10 (Three-point inequality with KL regularization). Let Π be the probability simplex, and πold,πref∈Π _old, _ref∈ . Let f(π)=⟨g,π⟩−ηKL(π∥πold)−βKL(π∥πref)f(π)= g,π - (π\| _old)- (π\| _ref). Define Πeff=π∈Π|supp(π)⊆supp(πold)∩supp(πref) _eff=\π∈ |supp(π) ( _old) ( _ref)\. Given step sizes η>0η>0 and β>0β>0, consider the update πnew=arg⁡maxπ∈Π⁡f(π). _new= _π∈ f(π). (21) Then for any π′∈Πeffπ ∈ _eff, ⟨g,πnew−π′⟩−β(KL(πnew∥πref)−KL(π′∥πref)) g, _new-π -β (KL( _new\| _ref)-KL(π \| _ref) ) (22) ≥η(−KL(π′∥πold)+KL(π′∥πnew)+KL(πnew∥πold))+βKL(π′∥πnew). ≥η (-KL(π \| _old)+KL(π \| _new)+KL( _new\| _old) )+ (π \| _new). Proof. Since η and β are larger than zero, and KL(π∥πold)KL(π\| _old) and KL(π∥πref)KL(π\| _ref) are not defined when supp(π)⊈supp(πold)∩supp(πref)supp(π) ( _old) ( _ref), the domain of definition of f(π)f(π) is Πeff _eff. Moreover, we can rearrange f(π)f(π) as f(π)=⟨g+ηlog⁡πold+βlog⁡πref,π⟩−(η+β)h(π),f(π)= g+η _old+β _ref,π -(η+β)h(π), where h(π)h(π) is the negative entropy of π. Since the first term is linear with π, and h(π)h(π) is strictly convex with π and η+β>0η+β>0, we have f(π)f(π) is a strictly concave function with π. Note that f(π)f(π) is differentiable on Πeff _eff. By the optimality of πnew _new in eq. 21, for every π′∈Πeffπ ∈ _eff, ⟨∇f(πnew),πnew−π′⟩≥0. ∇ f( _new), _new-π ≥ 0. Calculating ∇f(πnew)∇ f( _new) and rearranging the above equation, we have ⟨g−η∇πnewKL(πnew∥πold)−β∇πnewKL(πnew∥πref),πnew−π′⟩≥0. g-η _ _newKL( _new\| _old)-β _ _newKL( _new\| _ref), _new-π ≥ 0. (23) The Bregman divergence generated by h(p)h(p) is Dh(u,v)=KL(u∥v)D_h(u,v)=KL(u\|v). Applying lemma B.8, we have ⟨∇πnewKL(πnew∥πold),π′−πnew⟩= _ _newKL( _new\| _old),π - _new = KL(π′∥πold)−KL(π′∥πnew)−KL(πnew∥πold), (π \| _old)-KL(π \| _new)-KL( _new\| _old), ⟨∇πnewKL(πnew∥πref),π′−πnew⟩= _ _newKL( _new\| _ref),π - _new = KL(π′∥πref)−KL(π′∥πnew)−KL(πnew∥πref), (π \| _ref)-KL(π \| _new)-KL( _new\| _ref), where the first equation is letting x=π′x=π , y=πnewy= _new, z=πoldz= _old, and f(p)=h(p)f(p)=h(p), and the second equation is letting x=π′x=π , y=πnewy= _new, z=πrefz= _ref, and f(p)=h(p)f(p)=h(p). Substituting the above equations into the LHS of eq. 23, we have ⟨g−η∇πnewKL(πnew∥πold)−β∇πnewKL(πnew∥πref),πnew−π′⟩ g-η _ _newKL( _new\| _old)-β _ _newKL( _new\| _ref), _new-π (24) =⟨g,πnew−π′⟩+η(KL(π′∥πold)−KL(π′∥πnew)−KL(πnew∥πold)) = g, _new-π +η (KL(π \| _old)-KL(π \| _new)-KL( _new\| _old) ) +β(KL(π′∥πref)−KL(π′∥πnew)−KL(πnew∥πref)) +β (KL(π \| _ref)-KL(π \| _new)-KL( _new\| _ref) ) ≥0. ≥ 0. Rearranging this equation, we have ⟨g,πnew−π′⟩−β(KL(πnew∥πref)−KL(π′∥πref)) g, _new-π -β (KL( _new\| _ref)-KL(π \| _ref) ) ≥η(−KL(π′∥πold)+KL(π′∥πnew)+KL(πnew∥πold))+βKL(π′∥πnew). ≥η (-KL(π \| _old)+KL(π \| _new)+KL( _new\| _old) )+ (π \| _new). This concludes the proof. ∎ Lemma B.11. Let ΠΘ _ denote the parameterized policy set whose probability for each action is larger than pminp_ and Θ is a convex set. Assume |g(x,y)|≤gmax|g(x,y)|≤ g_ for any (x,y)(x,y) pair. Let f(π)=⟨g,π⟩−ηKL(π∥πθold)−βKL(π∥πref)f(π)= g,π - (π\| _ _old)- (π\| _ref). Given step sizes η>0η>0 and β>0β>0, consider the update πnew=arg⁡maxπ∈ΠΘ⁡f(π). _new= _π∈ _ f(π). Let θnew=θold+1η+βw _new= _old+ 1η+βw, where w= w= (x∼,y∼πθold[∇θoldlog⁡πθ(y|x)log⁡πθold(y|x)T])† (E_x ,y _ _old [ _ _old _θ(y|x) _ _old(y|x)^T ] ) x∼,y∼πθold[(g(x,y)−βlog⁡πθold(y|x)πref(y|x))∇θoldlog⁡πθold(y|x)]. _x ,y _ _old [ (g(x,y)-β _ _old(y|x) _ref(y|x) ) _ _old _ _old(y|x) ]. Under 3.8 and 3.9, for any π′∈Πeffπ ∈ _eff, x∼[⟨g−η∇πθnewKL(πθnew∥πold)−β∇πθnewKL(πθnew∥πref),πθnew−π′⟩]≥−gap(εapprox,pmin).E_x [ g-η _ _ _newKL( _ _new\| _old)-β _ _ _newKL( _ _new\| _ref), _ _new-π ]≥-gap( _approx,p_ ). where gap(εapprox,pmin)gap( _approx,p_ ) is defined in eq. 28. Proof. We first rewrite ⟨g−η∇πθnewKL(πθnew∥πold)−β∇πθnewKL(πθnew∥πref),πθnew−π′⟩ g-η _ _ _newKL( _ _new\| _old)-β _ _ _newKL( _ _new\| _ref), _ _new-π as ⟨g−η∇πθnewKL(πθnew∥πold)−β∇πθnewKL(πθnew∥πref),πθnew−π′⟩ g-η _ _ _newKL( _ _new\| _old)-β _ _ _newKL( _ _new\| _ref), _ _new-π =⟨g−η∇πnewKL(πnew∥πold)−β∇πnewKL(πnew∥πref),πθnew−π′⟩ = g-η _ _newKL( _new\| _old)-β _ _newKL( _new\| _ref), _ _new-π +⟨η(∇πnewKL(πnew∥πold)−∇πθnewKL(πθnew∥πold)),πθnew−π′⟩ + η ( _ _newKL( _new\| _old)- _ _ _newKL( _ _new\| _old) ), _ _new-π +⟨β(∇πnewKL(πnew∥πref)−∇πθnewKL(πθnew∥πref)),πθnew−π′⟩. + β ( _ _newKL( _new\| _ref)- _ _ _newKL( _ _new\| _ref) ), _ _new-π . Since ∇π(y|x)KL(π(⋅|x)||π′(⋅|x))=logπ(y|x)π′(y|x)+1 _π(y|x)KL(π(·|x)||π (·|x))= π(y|x)π (y|x)+1, the LHS of the above equation can be rewritten as LHS= = ⟨g−η∇πnewKL(πnew∥πold)−β∇πnewKL(πnew∥πref),πθnew−π′⟩+⟨(η+β)log⁡πnewπθnew,πθnew−π′⟩ g-η _ _newKL( _new\| _old)-β _ _newKL( _new\| _ref), _ _new-π + (η+β) _new _ _new, _ _new-π = = ⟨g−η∇πnewKL(πnew∥πold)−β∇πnewKL(πnew∥πref),πθnew−πnew⟩ g-η _ _newKL( _new\| _old)-β _ _newKL( _new\| _ref), _ _new- _new +⟨g−η∇πnewKL(πnew∥πold)−β∇πnewKL(πnew∥πref),πnew−π′⟩ + g-η _ _newKL( _new\| _old)-β _ _newKL( _new\| _ref), _new-π +⟨(η+β)log⁡πnewπθnew,πθnew−π′⟩. + (η+β) _new _ _new, _ _new-π . By πnew=arg⁡maxπ∈ΠΘ⁡f(π) _new= _π∈ _ f(π) and ΠΘ _ is the convex set, for any π′∈ΠΘπ ∈ _ we have ⟨g−η∇πnewKL(πnew∥πold)−β∇πnewKL(πnew∥πref),πnew−π′⟩≥0. g-η _ _newKL( _new\| _old)-β _ _newKL( _new\| _ref), _new-π ≥ 0. Substituting the optimality of πnew _new into ⟨g−η∇πθnewKL(πθnew∥πold)−β∇πθnewKL(πθnew∥πref),πθnew−π′⟩ g-η _ _ _newKL( _ _new\| _old)-β _ _ _newKL( _ _new\| _ref), _ _new-π and taking the expectation over x∼x , we have x∼[⟨g−η∇πθnewKL(πθnew∥πold)−β∇πθnewKL(πθnew∥πref),πθnew−π′⟩] _x [ g-η _ _ _newKL( _ _new\| _old)-β _ _ _newKL( _ _new\| _ref), _ _new-π ] (25) ≥x∼[⟨g−η∇πnewKL(πnew∥πold)−β∇πnewKL(πnew∥πref),πθnew−πnew⟩+(η+β)⟨log⁡πnewπθnew,πθnew−π′⟩]. _x [ g-η _ _newKL( _new\| _old)-β _ _newKL( _new\| _ref), _ _new- _new +(η+β) _new _ _new, _ _new-π ]. Since πref,πnew,πold∈ΠΘ _ref, _new, _old∈ _ , we have x∼[|⟨g−η∇πnewKL(πnew∥πold)−β∇πnewKL(πnew∥πref),πθnew−πnew⟩|] _x [ | g-η _ _newKL( _new\| _old)-β _ _newKL( _new\| _ref), _ _new- _new | ] (26) =x∼[|⟨g−ηlog⁡πnewπold−βlog⁡πnewπref,πθnew−πnew⟩|] =E_x [ | g-η _new _old-β _new _ref, _ _new- _new | ] ≤x∼[‖g−ηlog⁡πnewπold−βlog⁡πnewπref‖∞‖πθnew−πnew‖1] _x [ \|g-η _new _old-β _new _ref \|_∞ \| _ _new- _new \|_1 ] ≤x∼[(gmax+(η+β)log⁡1pmin)‖πθnew−πnew‖1] _x [ (g_ +(η+β) 1p_ ) \| _ _new- _new \|_1 ] Substituting eq. 26 into eq. 25 gives x∼[|⟨g−η∇πθnewKL(πθnew∥πold)−β∇πθnewKL(πθnew∥πref),πθnew−π′⟩|] _x [ | g-η _ _ _newKL( _ _new\| _old)-β _ _ _newKL( _ _new\| _ref), _ _new-π | ] (27) ≤x∼[(gmax+(η+β)log⁡1pmin)‖πθnew−πnew‖1+(η+β)|⟨log⁡πnewπθnew,πθnew−π′⟩|] _x [ (g_ +(η+β) 1p_ ) \| _ _new- _new \|_1+(η+β) | _new _ _new, _ _new-π | ] ≤x∼[(gmax+(η+β)log⁡1pmin)2KL(πθnew∥πnew)+(η+β)(1+1pmin)KL(πθnew∥πnew)] _x [ (g_ +(η+β) 1p_ ) 2KL ( _ _new\| _new )+(η+β) (1+ 1p_ )KL ( _ _new\| _new ) ] (by π′(y|x)πθnew(y|x)≤1pmin π (y|x) _ _new(y|x)≤ 1p_ ) ≤(gmax+(η+β)log⁡1pmin)2x∼[KL(πθnew∥πnew)]+(η+β)(1+1pmin)x∼[KL(πθnew∥πnew)]. ≤ (g_ +(η+β) 1p_ ) 2E_x [KL ( _ _new\| _new ) ]+(η+β) (1+ 1p_ )E_x [KL ( _ _new\| _new ) ]. As πnew(y|x) _new(y|x) corresponds to parameter θ∗θ^*, under 3.8 and 3.9, we have x∼[KL(πθnew∥πnew)]≤ _x [KL ( _ _new\| _new ) ]≤ x∼[‖πθnewπθold‖∞y∼πold[log⁡πθnewπnew]] _x [ \| _ _new _ _old \|_∞E_y _old [ _ _new _new ] ] ≤ ≤ x∼[1pmin‖log⁡(πθnew(y|x)πnew(y|x))‖1] _x [ 1p_ \| ( _ _new(y|x) _new(y|x) ) \|_1 ] ≤ ≤ x∼[Cpmin‖θnew−θ∗‖1] _x [ Cp_ \| _new-θ^*\|_1 ] ≤ ≤ Cϵapproxpmin C _approxp_ We have x∼[⟨g−η∇πθnewKL(πθnew∥πold)−β∇πθnewKL(πθnew∥πref),πθnew−π′⟩]≥−gap(εapprox,pmin),E_x [ g-η _ _ _newKL( _ _new\| _old)-β _ _ _newKL( _ _new\| _ref), _ _new-π ]≥-gap( _approx,p_ ), where gap(εapprox,pmin) ( _approx,p_ ) =(gmax+(η+β)log⁡1pmin)2Cϵapproxpmin+(η+β)(1+1pmin)Cϵapproxpmin. = (g_ +(η+β) 1p_ ) 2C _approxp_ +(η+β) (1+ 1p_ ) C _approxp_ . (28) ∎ Corollary B.12. Let ΠΘ _ denote the parameterized policy set whose probability for each action is larger than pminp_ and Θ is a convex set. Assume |g(x,y)|≤gmax|g(x,y)|≤ g_ for any (x,y)(x,y) pair. Let f(π)=⟨g,π⟩−ηKL(π∥πθold)−βKL(π∥πref)f(π)= g,π - (π\| _ _old)- (π\| _ref). Given step sizes η>0η>0 and β>0β>0, consider the update πnew=arg⁡maxπ∈ΠΘ⁡f(π). _new= _π∈ _ f(π). Let θnew=θold+1η+βw _new= _old+ 1η+βw, where w= w= (x∼,y∼πθold[∇θoldlog⁡πθ(y|x)log⁡πθold(y|x)T])† (E_x ,y _ _old [ _ _old _θ(y|x) _ _old(y|x)^T ] ) x∼,y∼πθold[(g(x,y)−βlog⁡πθold(y|x)πref(y|x))∇θoldlog⁡πθold(y|x)]. _x ,y _ _old [ (g(x,y)-β _ _old(y|x) _ref(y|x) ) _ _old _ _old(y|x) ]. Under 3.8 and 3.9, for any π′∈Πeffπ ∈ _eff, we have x∼[⟨g,πθnew−π′⟩−β(KL(πθnew∥πref)−KL(π′∥πref))] _x [ g, _ _new-π -β (KL( _ _new\| _ref)-KL(π \| _ref) ) ] ≥x∼[η(−KL(π′∥πold)+KL(π′∥πθnew)+KL(πθnew∥πold))+βKL(π′∥πθnew)]−gap(εapprox,pmin), _x [η (-KL(π \| _old)+KL(π \| _ _new)+KL( _ _new\| _old) )+ (π \| _ _new) ]-gap( _approx,p_ ), where gap(εapprox,pmin)gap( _approx,p_ ) is defined in eq. 28. Proof. By lemma B.11, we have x∼[⟨g−η∇πθnewKL(πθnew∥πold)−β∇πθnewKL(πθnew∥πref),πθnew−π′⟩]≥−gap(εapprox,pmin)E_x [ g-η _ _ _newKL( _ _new\| _old)-β _ _ _newKL( _ _new\| _ref), _ _new-π ]≥-gap( _approx,p_ ) Applying lemma B.8 and let f be the negative entropy function, we have ⟨∇πθnewKL(πθnew∥πold),π′−πθnew⟩= _ _ _newKL( _ _new\| _old),π - _ _new = KL(π′∥πold)−KL(π′∥πθnew)−KL(πθnew∥πold), (π \| _old)-KL(π \| _ _new)-KL( _ _new\| _old), ⟨∇πθnewKL(πθnew∥πref),π′−πθnew⟩= _ _ _newKL( _ _new\| _ref),π - _ _new = KL(π′∥πref)−KL(π′∥πθnew)−KL(πθnew∥πref), (π \| _ref)-KL(π \| _ _new)-KL( _ _new\| _ref), Substituting the above inequalities into x∼[⟨g−η∇πθnewKL(πθnew∥πold)−β∇πθnewKL(πθnew∥πref),πθnew−π′⟩]E_x [ g-η _ _ _newKL( _ _new\| _old)-β _ _ _newKL( _ _new\| _ref), _ _new-π ] concludes the proof. ∎ Appendix C Proof of theorem 3.4 As defined in eq. 1, the aggregated reward function is the combined the weighted reward objectives and dual-variable weighted constrained reward objectives, shown as Sλ(x,y)=∑k∈wkRk(x,y)+∑j∈ℋλjRj(x,y),S_λ(x,y)= _k w_kR_k(x,y)+ _j _jR_j(x,y), Define the corresponding value function as VSλπ(x) V^π_S_λ(x) :=y∼π(⋅∣x)[Sλ(x,y)]. :=E_y π(· x) [S_λ(x,y) ]. (29) The Lagrangian associated with the constrained MO-RLHF problem can then be written as ℒ(π,λ) (π,λ) =J(π;)+∑j∈ℋλjx∼,y∼π(⋅∣x)[Rj(x,y)] =J(π;w)+ _j _jE_x ,y π(· x) [R_j(x,y) ] =x∼[VSλπ(x)−βKL(π(⋅∣x)∥πref(⋅∣x))]. =E_x [V^π_S_λ(x)- (π(· x)\| _ref(· x) ) ]. The Lagrangian problem is minλ≥0⁡maxπ∈Π⁡ℒ(π,λ). _λ≥ 0 _π∈ L(π,λ). Note that Π is a finite policy set, hence the primal maximization attains an optimum. Moreover, lemma B.5, there exists optimal dual variable λ⋆λ and λmax>0 _ >0 such that 0≤λ⋆≤λmax0≤λ ≤ _ Under 3.1, the strong duality holds and optimal saddle-point (π⋆,λ⋆)(π ,λ ) exists. Since π⋆=argmaxπL(π,⋆)π =argmax_πL(π, λ ), we have L(π⋆,⋆)≥L(π,⋆)L(π , λ )≥ L(π, λ ) for any π∈Ππ∈ . Similarly, since ⋆=argminλL(π⋆,λ) λ =argmin_λL(π ,λ), we have L(π⋆,λ)≥L(π⋆,⋆)L(π ,λ)≥ L(π , λ ) for any λ≥0λ≥ 0. Combining these two inequalities together, for any π∈Ππ∈ and λ≥0λ≥ 0, we have L(π⋆,λ)−L(π,⋆)=L(π⋆,λ)−L(π⋆,⋆)⏟≥0+L(π⋆,⋆)−L(π,⋆)⏟≥0≥0L(π ,λ)-L(π, λ )= L(π ,λ)-L(π , λ )_≥ 0+ L(π , λ )-L(π, λ )_≥ 0≥ 0 (30) Let π=πtπ= _t and λ=tλ= λ_t and substituting the definition of L(π,λ)L(π,λ) into the LHS of the above inequality, we have L(π⋆,t)−L(πt,⋆)= L(π , λ_t)-L( _t, λ )= x∼[VStπ⋆(x)−βKL(π⋆(⋅|x)∥πref(⋅|x))]−x∼[VS⋆π(x)−βKL(π(⋅|x)∥πref(⋅|x))] _x [V^π _S_ λ_t(x)- (π (·|x)\| _ref(·|x)) ]-E_x [V^π_S_ λ (x)- (π(·|x)\| _ref(·|x)) ] (31) = = x∼[VStπ⋆(x)−βKL(π⋆(⋅|x)∥πref(⋅|x))]−x∼[VStπt(x)−βKL(πt(⋅|x)∥πref(⋅|x))]⏟A E_x [V^π _S_ λ_t(x)- (π (·|x)\| _ref(·|x)) ]-E_x [V _t_S_ λ_t(x)- ( _t(·|x)\| _ref(·|x)) ]_A +x∼[VStπt(x)−βKL(πt(⋅|x)∥πref(⋅|x))]−x∼[VS⋆πt(x)−βKL(πt(⋅|x)∥πref(⋅|x))])⏟B + E_x [V _t_S_ λ_t(x)- ( _t(·|x)\| _ref(·|x)) ]-E_x [V _t_S_ λ (x)- ( _t(·|x)\| _ref(·|x)) ])_B C.1 Upper bound of term AA We can rewrite term AA as: A= = x∼[VStπ⋆(x)−βKL(π⋆(⋅|x)∥πref(⋅|x))]−x∼[VStπt(x)−βKL(πt(⋅|x)∥πref(⋅|x))] _x [V^π _S_ λ_t(x)- (π (·|x)\| _ref(·|x)) ]-E_x [V _t_S_ λ_t(x)- ( _t(·|x)\| _ref(·|x)) ] (32) = = x∼[(VStπ⋆(x)−VStπt(x))−β(KL(π⋆(⋅|x)∥πref(⋅|x))−KL(πt(⋅|x)∥πref(⋅|x)))] _x [ (V^π _S_ λ_t(x)-V _t_S_ λ_t(x) )-β (KL(π (·|x)\| _ref(·|x))-KL( _t(·|x)\| _ref(·|x)) ) ] =(a) (a)= x∼[⟨π⋆(⋅|x)−πt(⋅|x),St(x,⋅)⟩−β(KL(π⋆(⋅|x))∥πref(⋅|x)))−KL(πt(⋅|x))∥πref(⋅|x))))] _x [ π (·|x)- _t(·|x),S_ λ_t(x,·) -β (KL(π (·|x))\| _ref(·|x)))-KL( _t(·|x))\| _ref(·|x))) ) ] =(b) (b)= x∼[⟨π⋆(⋅|x)−π^t+1(⋅|x),St(x,⋅)⟩−β(KL(π⋆(⋅|x)∥πref(⋅|x))−KL(π^t+1(⋅|x)∥πref(⋅|x))) _x [ π (·|x)- π_t+1(·|x),S_ λ_t(x,·) -β (KL(π (·|x)\| _ref(·|x))-KL( π_t+1(·|x)\| _ref(·|x)) ) . +⟨π^t+1(⋅|x)−πt(⋅|x),St−1(x,⋅)⟩−β(KL(π^t+1(⋅|x)∥πref(⋅|x))−KL(πt(⋅|x)∥πref(⋅|x))) + π_t+1(·|x)- _t(·|x),S_ λ_t-1(x,·) -β (KL( π_t+1(·|x)\| _ref(·|x))-KL( _t(·|x)\| _ref(·|x)) ) +⟨π^t+1(⋅|x)−πt(⋅|x),St(x,⋅)−St−1(x,⋅)⟩] .+ π_t+1(·|x)- _t(·|x),S_ λ_t(x,·)-S_ λ_t-1(x,·) ] where (a)(a) is because the action space is discrete and VStπ(x)=∑yπ(y|x)St(x,y)=⟨π(⋅|x),St(x,⋅)⟩V^π_S_ λ_t(x)= _yπ(y|x)S_ λ_t(x,y)= π(·|x),S_ λ_t(x,·) for any π∈Ππ∈ , and (b)(b) is because adding and subtracting the same term keeps the equality. Recall the π^t+1 π_t+1 update shown in eq. 6 of the optimistic policy gradient primal-dual method, π^t+1=argmaxπx∼[y∼π(⋅|x)[St(x,y)]−βKL(π(⋅|x)∥πref(⋅|x))−ηθKL(π(⋅|x)∥π^t(⋅|x))], π_t+1= _πE_x [E_y π(·|x) [S_ λ_t(x,y) ]- (π(·|x)\| _ref(·|x) )- _θKL (π(·|x)\| π_t(·|x) ) ], Since the optimality is independent for any x, we can write the for fixed x as: π^t+1(⋅|x)= π_t+1(·|x)= argmaxπy∼π(⋅|x)[St(x,y)]−βKL(π(⋅|x)∥πref(⋅|x))−ηθKL(π(⋅|x)∥π^t(⋅|x)) _πE_y π(·|x) [S_ λ_t(x,y) ]- (π(·|x)\| _ref(·|x) )- _θKL (π(·|x)\| π_t(·|x) ) = = argmaxπ⟨π(⋅|x),St(x,⋅)⟩−βKL(π(⋅|x)∥πref(⋅|x))−ηθKL(π(⋅|x)∥π^t(⋅|x)) _π π(·|x),S_ λ_t(x,·) - (π(·|x)\| _ref(·|x) )- _θKL (π(·|x)\| π_t(·|x) ) Recall that we start with π0 _0 which has the same support as πref _ref, which has the full support by 3.3. We also set π^0=πref π_0= _ref Given the optimistic policy gradient shown in eqs. 4 and 6, πt(y|x)∝π^t(y|x)η+βπref(y|x)βη+βexp⁡(Sλt−1(x,y)) _t(y|x) π_t(y|x) η+βπ_ref(y|x) βη+β (S_ _t-1(x,y)) for any t, πt _t and π^t∝π^t(y|x)η+βπref(y|x)βη+βexp⁡(Sλt(x,y)) π_t π_t(y|x) η+βπ_ref(y|x) βη+β (S_ _t(x,y)) for any t. By iteration, we have π^t π_t and πt _t have the same support as πref _ref for any t. Therefore, supp(πt)∩supp(πref)=supp(π^t)∩supp(πref)=supp(πref)supp( _t) ( _ref)=supp( π_t) ( _ref)=supp( _ref). Since πref _ref spans the action space by 3.3, π⋆π is covered by πref _ref. Therefore supp(π⋆)⊆supp(πt)∩supp(πref)supp (π ) ( _t ) ( _ref ). Using lemma B.10 and letting η=ηθη= _θ, g=St(x,⋅)g=S_ λ_t(x,·), πold=π^t(⋅|x) _old= π_t(·|x), πnew=π^t+1(⋅|x) _new= π_t+1(·|x), and π′=π⋆(⋅|x)π =π (·|x), we have ⟨St(x,⋅),π^t+1(⋅|x)−π⋆(⋅|x)⟩−β(KL(π^t+1(⋅|x)∥πref(⋅|x))−KL(π⋆(⋅|x)∥πref(⋅|x))) S_ λ_t(x,·), π_t+1(·|x)-π (·|x) -β (KL( π_t+1(·|x)\| _ref(·|x))-KL(π (·|x)\| _ref(·|x)) ) ≥ηθ(−KL(π⋆(⋅|x)∥π^t(⋅|x))+KL(π⋆(⋅|x)∥π^t+1(⋅|x))+KL(π^t+1(⋅|x)∥π^t(⋅|x)))+βKL(π⋆(⋅|x)∥π^t+1(⋅|x)). ≥ _θ (-KL(π (·|x)\| π_t(·|x))+KL(π (·|x)\| π_t+1(·|x))+KL( π_t+1(·|x)\| π_t(·|x)) )+ (π (·|x)\| π_t+1(·|x)). Putting a negative sign on both sides, we have ⟨π⋆(⋅|x)−π^t+1(⋅|x),St(x,⋅)⟩−β(KL(π⋆(⋅|x)∥πref(⋅|x))−KL(π^t+1(⋅|x)∥πref(⋅|x))) π (·|x)- π_t+1(·|x),S_ λ_t(x,·) -β (KL(π (·|x)\| _ref(·|x))-KL( π_t+1(·|x)\| _ref(·|x)) ) (33) ≤ηθ(KL(π⋆(⋅|x)∥π^t(⋅|x))−KL(π⋆(⋅|x)∥π^t+1(⋅|x))−KL(π^t+1(⋅|x)∥π^t(⋅|x)))−βKL(π⋆(⋅|x)∥π^t+1(⋅|x)) ≤ _θ (KL(π (·|x)\| π_t(·|x))-KL(π (·|x)\| π_t+1(·|x))-KL( π_t+1(·|x)\| π_t(·|x)) )- (π (·|x)\| π_t+1(·|x)) =ηθKL(π⋆(⋅|x)∥π^t(⋅|x))−(ηθ+β)KL(π⋆(⋅|x)∥π^t+1(⋅|x))−ηθKL(π^t+1(⋅|x)∥π^t(⋅|x)) = _θKL(π (·|x)\| π_t(·|x))-( _θ+β)KL(π (·|x)\| π_t+1(·|x))- _θKL( π_t+1(·|x)\| π_t(·|x)) Similarly, the update of πt _t in the optimistic update is πt=argmaxπx∼[y∼π(⋅|x)[St−1(x,y)]−βKL(π(⋅|x)∥πref(⋅|x))−ηθKL(π(⋅|x)∥π^t(⋅|x))] _t= _πE_x [E_y π(·|x) [S_ λ_t-1(x,y) ]- (π(·|x)\| _ref(·|x) )- _θKL (π(·|x)\| π_t(·|x) ) ] let η=ηθη= _θ, g=St−1(x,⋅)g=S_ λ_t-1(x,·), πold=π^t(⋅|x) _old= π_t(·|x), πnew=πt(⋅|x) _new= _t(·|x), and π′=π^t+1(⋅|x)π = π_t+1(·|x) in lemma B.10, we have ⟨π^t+1(⋅|x)−πt(⋅|x),St−1(x,⋅)⟩−β(KL(π^t+1(⋅|x)∥πref(⋅|x))−KL(πt(⋅|x)∥πref(⋅|x))) π_t+1(·|x)- _t(·|x),S_ λ_t-1(x,·) -β (KL( π_t+1(·|x)\| _ref(·|x))-KL( _t(·|x)\| _ref(·|x)) ) (34) ≤ηθ(KL(π^t+1(⋅|x)∥π^t(⋅|x))−KL(π^t+1(⋅|x)∥πt(⋅|x))−KL(πt(⋅|x)∥π^t(⋅|x)))−βKL(π^t+1(⋅|x)∥πt(⋅|x)) ≤ _θ (KL( π_t+1(·|x)\| π_t(·|x))-KL( π_t+1(·|x)\| _t(·|x))-KL( _t(·|x)\| π_t(·|x)) )- ( π_t+1(·|x)\| _t(·|x)) =ηθKL(π^t+1(⋅|x)∥π^t(⋅|x))−(ηθ+β)KL(π^t+1(⋅|x)∥πt(⋅|x))−ηθKL(πt(⋅|x)∥π^t(⋅|x)). = _θKL( π_t+1(·|x)\| π_t(·|x))-( _θ+β)KL( π_t+1(·|x)\| _t(·|x))- _θKL( _t(·|x)\| π_t(·|x)). Let C>0C>0 be a constant. For the last term in the RHS of eq. 32, we derive the upper bound as ⟨π^t+1(⋅|x)−πt(⋅|x),St(x,⋅)−St−1(x,⋅)⟩ π_t+1(·|x)- _t(·|x),S_ λ_t(x,·)-S_ λ_t-1(x,·) (35) =⟨π^t+1(⋅|x)−πt(⋅|x),∑j∈ℋ(λt,j−λt−1,j)Rj(x,⋅)⟩ = π_t+1(·|x)- _t(·|x), _j ( _t,j- _t-1,j)R_j(x,·) ≤(a)∥π^t+1(⋅|x)−πt(⋅|x)∥1∥∑j∈ℋ(λt,j−λt−1,j)Rj(x,⋅)∥∞ (a)≤\| π_t+1(·|x)- _t(·|x)\|_1 \| _j ( _t,j- _t-1,j)R_j(x,·) \|_∞ ≤(b)∥π^t+1(⋅|x)−πt(⋅|x)∥1∥t−t−1∥1Rmax (b)≤\| π_t+1(·|x)- _t(·|x)\|_1\| λ_t- λ_t-1\|_1R_ ≤2KL(π^t+1(⋅|x)∥πt(⋅|x))‖t−t−1‖1Rmax(By Pinsker’s inequality in lemma B.2) ≤ 2KL( π_t+1(·|x)\| _t(·|x))\| λ_t- λ_t-1\|_1R_ (By Pinsker's inequality in @crefcreftype~refnumlem:pinsker's ineq) ≤CKL(π^t+1(⋅|x)∥πt(⋅|x))+Rmax22C∥t−t−1∥12(By AM-GM inequality x22C+y2C2≥xy with C>0) ≤ CKL( π_t+1(·|x)\| _t(·|x))+ R_ ^22C\| λ_t- λ_t-1\|_1^2 (By AM-GM inequality $ x^22C+ y^2C2≥ xy$ with $C>0$) ≤CKL(π^t+1(⋅|x)∥πt(⋅|x))+|ℋ|Rmax22C∥t−t−1∥22(By ‖12≤d‖22, ∀∈ℝd) ≤ CKL( π_t+1(·|x)\| _t(·|x))+ |H|R_ ^22C\| λ_t- λ_t-1\|_2^2 (By $\| x\|_1^2≤ d\|x\|_2^2$, $ ^d$) ≤(c)CKL(π^t+1(⋅|x)∥πt(⋅|x))+|ℋ|Rmax2C(∥t−^t∥22+∥^t−t−1∥22), (c)≤CKL( π_t+1(·|x)\| _t(·|x))+ |H|R_ ^2C (\| λ_t- λ_t\|_2^2+\| λ_t- λ_t-1\|_2^2 ), where (a)(a) is by Hölder’s inequality shown in lemma B.1 and letting f(⋅)=π^t+1(⋅|x)−πt(⋅|x)f(·)= π_t+1(·|x)- _t(·|x), g(⋅)=∑j∈ℋ(λt,j−λt−1,j)Rj(x,⋅)g(·)= _j ( _t,j- _t-1,j)R_j(x,·), p=1p=1, and q=∞q=∞. (b)(b) is by ‖∑j∈ℋ(λt,j−λt−1,j)Rj(x,⋅)‖∞≤ \| _j ( _t,j- _t-1,j)R_j(x,·) \|_∞≤ ∑j∈ℋ‖(λt,j−λt−1,j)Rj(x,⋅)‖∞(by triangle inequality) _j \|( _t,j- _t-1,j)R_j(x,·) \|_∞ (by triangle inequality) = = ∑j∈ℋ|λt,j−λt−1,j|‖Rj(x,⋅)‖∞ _j | _t,j- _t-1,j| \|R_j(x,·) \|_∞ ≤ ≤ (∑j∈ℋ|λt,j−λt−1,j|)maxj⁡‖Rj(x,⋅)‖∞ ( _j | _t,j- _t-1,j| ) _j \|R_j(x,·) \|_∞ = = ‖t−t−1‖1maxj⁡‖Rj(x,⋅)‖∞(by definition of 1-norm) \| λ_t- λ_t-1\|_1 _j \|R_j(x,·) \|_∞ (by definition of 1-norm) ≤ ≤ ‖t−t−1‖1Rmax \| λ_t- λ_t-1\|_1R_ (by 3.2 that Rj(x,y)≤RmaxR_j(x,y)≤ R_ for any j∈∪ℋj and (x,y)(x,y) pair). (c)(c) is because ‖t−t−1‖22= \| λ_t- λ_t-1\|_2^2= ‖t−^t+^t−t−1‖22 \| λ_t- λ_t+ λ_t- λ_t-1\|_2^2 = = ‖t−^t‖22+‖^t−t−1‖22+2⟨t−^t,^t−t−1⟩ \| λ_t- λ_t\|_2^2+\| λ_t- λ_t-1\|_2^2+2 λ_t- λ_t, λ_t- λ_t-1 ≤ ≤ 2‖t−^t‖22+2‖^t−t−1‖22 2\| λ_t- λ_t\|_2^2+2\| λ_t- λ_t-1\|_2^2 (by Young’s inequality with p=q=2p=q=2, i.e., ⟨,⟩≤12(‖22+‖22) ,y ≤ 12(\|x\|_2^2+\|y\|_2^2)) Substituting eq. 33, eq. 34, and eq. 35 into the RHS of eq. 32, we have A≤ ≤ x∼[ηθKL(π⋆(⋅|x)∥π^t(⋅|x))−(ηθ+β)KL(π⋆(⋅|x)∥π^t+1(⋅|x))−ηθKL(π^t+1(⋅|x)∥π^t(⋅|x)) _x [ _θKL(π (·|x)\| π_t(·|x))-( _θ+β)KL(π (·|x)\| π_t+1(·|x))- _θKL( π_t+1(·|x)\| π_t(·|x)) . (36) +ηθKL(π^t+1(⋅|x)∥π^t(⋅|x))−(ηθ+β)KL(π^t+1(⋅|x)∥πt(⋅|x))−ηθKL(πt(⋅|x)∥π^t(⋅|x)) + _θKL( π_t+1(·|x)\| π_t(·|x))-( _θ+β)KL( π_t+1(·|x)\| _t(·|x))- _θKL( _t(·|x)\| π_t(·|x)) +CKL(π^t+1(⋅|x)∥πt(⋅|x))+|ℋ|Rmax2C(∥t−^t∥22+∥^t−t−1∥22)] .+CKL( π_t+1(·|x)\| _t(·|x))+ |H|R_ ^2C (\| λ_t- λ_t\|_2^2+\| λ_t- λ_t-1\|_2^2 ) ] = = x∼[ηθKL(π⋆(⋅|x)∥π^t(⋅|x))−(ηθ+β)KL(π⋆(⋅|x)∥π^t+1(⋅|x)) _x [ _θKL(π (·|x)\| π_t(·|x))-( _θ+β)KL(π (·|x)\| π_t+1(·|x)) . −(ηθ+β)KL(π^t+1(⋅|x)∥πt(⋅|x))−ηθKL(πt(⋅|x)∥π^t(⋅|x)) -( _θ+β)KL( π_t+1(·|x)\| _t(·|x))- _θKL( _t(·|x)\| π_t(·|x)) +CKL(π^t+1(⋅|x)∥πt(⋅|x))]+|ℋ|Rmax2C(∥t−^t∥22+∥^t−t−1∥22) .+CKL( π_t+1(·|x)\| _t(·|x)) ]+ |H|R_ ^2C (\| λ_t- λ_t\|_2^2+\| λ_t- λ_t-1\|_2^2 ) C.2 Upper bound of term BB Similarly, we rewrite the term BB as B= = x∼[VStπt(x)−βKL(πt(⋅|x)∥πref(⋅|x))]−x∼[VS⋆πt(x)−βKL(πt(⋅|x)∥πref(⋅|x))]) _x [V _t_S_ λ_t(x)- ( _t(·|x)\| _ref(·|x)) ]-E_x [V _t_S_ λ (x)- ( _t(·|x)\| _ref(·|x)) ]) (37) = = x∼[VStπt(x)−VS⋆πt(x)] _x [V_S_ λ_t _t(x)-V_S_ λ _t(x) ] = = x∼[(VStπt(x)−VS^t+1πt(x))+(VS^t+1πt(x)−VS⋆πt(x)) _x [ (V_S_ λ_t _t(x)-V_S_ λ_t+1 _t(x) )+ (V_S_ λ_t+1 _t(x)-V_S_ λ _t(x) ) . −(VStπt−1(x)−VS^t+1πt−1(x))+(VStπt−1(x)−VS^t+1πt−1(x))] .- (V_S_ λ_t _t-1(x)-V_S_ λ_t+1 _t-1(x) )+ (V_S_ λ_t _t-1(x)-V_S_ λ_t+1 _t-1(x) ) ] Define Rℋ=[Rj1,Rj2,⋯,Rj|ℋ|]∈ℝ|ℋ|R_H= [R_j_1,R_j_2,·s,R_j_|H| ] ^|H|, where j1<j2<⋯<j|ℋ|j_1<j_2<·s<j_|H|, and jk∈ℋj_k for any integer 1≤k≤|ℋ|1≤ k≤|H|. Define VRℋπ(x)=y∼π(⋅|x)Rℋ(x,y)∈ℝ|ℋ|V_R_H^π(x)=E_y π(·|x)R_H(x,y) ^|H|. By the definition of VSλπ(x)V_S_λ^π(x), we have VSλπ(x)= V_S_λ^π(x)= y∼π(⋅|x)Sλ(x,y)(by definition of VSλπ(x)) _y π(·|x)S_λ(x,y) (by definition of $V_S_λ^π(x)$) = = y∼π(⋅|x)[∑j∈wjRj(x,y)+∑j∈ℋλjRj(x,y)](by definition of Sλ) _y π(·|x) [ _j w_jR_j(x,y)+ _j _jR_j(x,y) ] (by definition of $S_λ$) = = y∼π(⋅|x)[∑j∈wjRj(x,y))]+∑j∈ℋλjy∼π(⋅|x)[Rj(x,y)] _y π(·|x) [ _j w_jR_j(x,y)) ]+ _j _jE_y π(·|x) [R_j(x,y) ] = = y∼π(⋅|x)[∑j∈wjRj(x,y))]+λTVRℋπ(x)(by definition of VRℋπ) _y π(·|x) [ _j w_jR_j(x,y)) ]+λ^TV_R_H^π(x) (by definition of $V_R_ H^π$) Plugging the above expression of VSλπ(x)V_S_λ^π(x) into term BB, we have B= = x∼[(t−^t+1)TVRℋπt(x)+(^t+1−⋆)TVRℋπt(x)−(t−^t+1)TVRℋπt−1(x)+(t−^t+1)TVRℋπt−1(x)] _x [ ( λ_t- λ_t+1 )^TV_R_H _t(x)+ ( λ_t+1- λ )^TV_R_H _t(x)- ( λ_t- λ_t+1 )^TV_R_H _t-1(x)+ ( λ_t- λ_t+1 )^TV_R_H _t-1(x) ] (38) = = x∼[(^t+1−⋆)TVRℋπt(x)+(t−^t+1)TVRℋπt−1(x)+(t−^t+1)T(VRℋπt(x)−VRℋπt−1(x))] _x [ ( λ_t+1- λ )^TV_R_H _t(x)+ ( λ_t- λ_t+1 )^TV_R_H _t-1(x)+ ( λ_t- λ_t+1 )^T (V_R_H _t(x)-V_R_H _t-1(x) ) ] = = (^t+1−⋆)Tx∼[VRℋπt(x)]+(t−^t+1)Tx∼[VRℋπt−1(x)] ( λ_t+1- λ )^TE_x [V_R_H _t(x) ]+ ( λ_t- λ_t+1 )^TE_x [V_R_H _t-1(x) ] +(t−^t+1)T(x∼[VRℋπt(x)]−x∼[VRℋπt−1(x)]) + ( λ_t- λ_t+1 )^T (E_x [V_R_H _t(x) ]-E_x [V_R_H _t-1(x) ] ) By lemma B.5, λ∗≥0λ^*≥ 0. Without loss of generality, for a vector a, we write ≥0a≥ 0 to indicate that all entries of a are nonnegative. Recall eq. 7 gives the λ^t+1,j λ_t+1,j in the optimistic gradient descent, and we rewrite the update as follows λ^t+1,j=arg⁡minλ≥0⁡λx∼,y∼πt(⋅|x)[Rj(x,y)]+ηλ(λ−λ^t,j)2. λ_t+1,j= _λ≥ 0 _x ,y _t(·|x) [R_j(x,y) ]+ _λ (λ- λ_t,j )^2. Rewrite the above update in the vectorized form as follows ^t+1= λ_t+1= arg⁡min≥0⁡Tx∼[VRℋπt(x)]+ηλ‖−^t‖22 _ λ≥ 0 λ^TE_x [V_R_H _t(x) ]+ _λ\| λ- λ_t\|_2^2 = = arg⁡max≥0−Tx∼[VRℋπt(x)]−ηλ‖−^t‖22. _ λ≥ 0- λ^TE_x [V_R_H _t(x) ]- _λ\| λ- λ_t\|_2^2. Let Ω=ℝ+|ℋ| =R_+^|H|, g=−x∼[VRℋπt(x)]g=-E_x [V_R_H _t(x) ], η=ηλη= _λ, h()=‖22h(x)=\|x\|_2^2, Dh(,)=‖−‖22D_h(x,y)=\|x-y\|_2^2, ′=⋆x = λ , new=^t+1x_new= λ_t+1, old=^tx_old= λ_t in lemma B.9, then we have ⟨−x∼[VRℋπt(x)],^t+1−⋆⟩≥ηλ(−‖⋆−^t‖22+‖⋆−^t+1‖22+‖^t+1−^t‖22). -E_x [V_R_H _t(x) ], λ_t+1- λ ≥ _λ (-\| λ - λ_t\|_2^2+\| λ - λ_t+1\|_2^2+\| λ_t+1- λ_t\|_2^2 ). Putting a negative sign on both sides, we have ⟨^t+1−⋆,x∼[VRℋπt(x)]⟩≤ηλ(‖⋆−^t‖22−‖⋆−^t+1‖22−‖^t+1−^t‖22). λ_t+1- λ ,E_x [V_R_H _t(x) ] ≤ _λ (\| λ - λ_t\|_2^2-\| λ - λ_t+1\|_2^2-\| λ_t+1- λ_t\|_2^2 ). (39) Similarly, since eq. 5 gives the optimistic update of λt,j _t,j as follows, λt,j=arg⁡minλ≥0⁡λx∼,y∼πt−1(⋅|x)[Rj(x,y)]+ηλ(λ−λ^t,j)2, _t,j= _λ≥ 0 _x ,y _t-1(·|x) [R_j(x,y) ]+ _λ (λ- λ_t,j )^2, Applying lemma B.9 by setting g=−x∼[VRℋπt−1(x)]g=-E_x [V_R_H _t-1(x) ], η=ηλη= _λ, h()=‖22h(x)=\|x\|_2^2, Dh(,)=‖−‖22D_h(x,y)=\|x-y\|_2^2, ′=^t+1x = λ_t+1, new=tx_new= λ_t, old=^tx_old= λ_t, we have ⟨t−^t+1,x∼[VRℋπt−1(x)]⟩≤ηλ(‖^t+1−^t‖22−‖^t+1−t‖22−‖t−^t‖22). λ_t- λ_t+1,E_x [V_R_H _t-1(x) ] ≤ _λ (\| λ_t+1- λ_t\|_2^2-\| λ_t+1- λ_t\|_2^2-\| λ_t- λ_t\|_2^2 ). (40) We upper bound the last term of BB as (t−^t+1)T(x∼[VRℋπt(x)]−x∼[VRℋπt−1(x)]) ( λ_t- λ_t+1 )^T (E_x [V_R_H _t(x) ]-E_x [V_R_H _t-1(x) ] ) =x∼[(t−^t+1)T(VRℋπt(x)−VRℋπt−1(x))] =E_x [ ( λ_t- λ_t+1 )^T (V_R_H _t(x)-V_R_H _t-1(x) ) ] =x∼[(t−^t+1)T(⟨πt(⋅|x),Rℋ(x,⋅)⟩−⟨πt−1(⋅|x),Rℋ(x,⋅)⟩)] =E_x [ ( λ_t- λ_t+1 )^T ( _t(·|x),R_H(x,·) - _t-1(·|x),R_H(x,·) ) ] (by VRℋπ(x)=y∼π(⋅|x)[Rℋ(x,y)]=⟨π(⋅|x),Rℋ(x,⋅)⟩V_R_H^π(x)=E_y π(·|x) [R_H(x,y) ]= π(·|x),R_H(x,·) ) =x∼[⟨πt(⋅|x)−πt−1(⋅|x),(t−^t+1)TRℋ(x,⋅)⟩] =E_x [ _t(·|x)- _t-1(·|x), ( λ_t- λ_t+1 )^TR_H(x,·) ] =x∼[⟨πt(⋅|x)−πt−1(⋅|x),∑j∈ℋ(λt,j−λ^t+1,j)Rj(x,⋅)⟩] =E_x [ _t(·|x)- _t-1(·|x), _j ( _t,j- λ_t+1,j)R_j(x,·) ] Define constants C1>0C_1>0 and C2>0C_2>0. Fixing x, we have ⟨πt(⋅|x)−πt−1(⋅|x),∑j∈ℋ(λt,j−λ^t+1,j)Rj(x,⋅)⟩ _t(·|x)- _t-1(·|x), _j ( _t,j- λ_t+1,j)R_j(x,·) =⟨πt(⋅|x)−π^t(⋅|x),∑j∈ℋ(λt,j−λ^t+1,j)Rj(x,⋅)⟩+⟨π^t(⋅|x)−πt−1(⋅|x),∑j∈ℋ(λt,j−λ^t+1,j)Rj(x,⋅)⟩ = _t(·|x)- π_t(·|x), _j ( _t,j- λ_t+1,j)R_j(x,·) + π_t(·|x)- _t-1(·|x), _j ( _t,j- λ_t+1,j)R_j(x,·) ≤C1KL(πt(⋅|x)∥π^t(⋅|x))+|ℋ|Rmax22C1∥t−^t+1∥22+C2KL(π^t(⋅|x)∥πt−1(⋅|x))+|ℋ|Rmax22C2∥t−^t+1∥22 ≤ C_1KL( _t(·|x)\| π_t(·|x))+ |H|R_ ^22C_1\| λ_t- λ_t+1\|_2^2+C_2KL( π_t(·|x)\| _t-1(·|x))+ |H|R_ ^22C_2\| λ_t- λ_t+1\|_2^2 (By derivations of eq. 35) =C1KL(πt(⋅|x)∥π^t(⋅|x))+C2KL(π^t(⋅|x)∥πt−1(⋅|x))+|ℋ|Rmax2(12C1+12C2)∥t−^t+1∥22 =C_1KL( _t(·|x)\| π_t(·|x))+C_2KL( π_t(·|x)\| _t-1(·|x))+|H|R_ ^2 ( 12C_1+ 12C_2 )\| λ_t- λ_t+1\|_2^2 Substituting the above inequality into (t−^t+1)T(x∼[VRℋπt(x)]−x∼[VRℋπt−1(x)]) ( λ_t- λ_t+1 )^T (E_x [V_R_H _t(x) ]-E_x [V_R_H _t-1(x) ] ), we have (t−^t+1)T(x∼[VRℋπt(x)]−x∼[VRℋπt−1(x)]) ( λ_t- λ_t+1 )^T (E_x [V_R_H _t(x) ]-E_x [V_R_H _t-1(x) ] ) (41) =x∼[C1KL(πt(⋅|x)∥π^t(⋅|x))+C2KL(π^t(⋅|x)∥πt−1(⋅|x))]+|ℋ|Rmax2(12C1+12C2)∥t−^t+1∥22 =E_x [C_1KL( _t(·|x)\| π_t(·|x))+C_2KL( π_t(·|x)\| _t-1(·|x)) ]+|H|R_ ^2 ( 12C_1+ 12C_2 )\| λ_t- λ_t+1\|_2^2 Combining eq. 39, eq. 40, and eq. 41, we can upper bound BB as B≤ ≤ ηλ(‖⋆−^t‖22−‖⋆−^t+1‖22−‖^t+1−^t‖22)+ηλ(‖^t+1−^t‖22−‖^t+1−t‖22−‖t−^t‖22) _λ (\| λ - λ_t\|_2^2-\| λ - λ_t+1\|_2^2-\| λ_t+1- λ_t\|_2^2 )+ _λ (\| λ_t+1- λ_t\|_2^2-\| λ_t+1- λ_t\|_2^2-\| λ_t- λ_t\|_2^2 ) (42) +x∼[C1KL(πt(⋅|x)∥π^t(⋅|x))+C2KL(π^t(⋅|x)∥πt−1(⋅|x))]+|ℋ|Rmax2(12C1+12C2)∥t−^t+1∥22 +E_x [C_1KL( _t(·|x)\| π_t(·|x))+C_2KL( π_t(·|x)\| _t-1(·|x)) ]+|H|R_ ^2 ( 12C_1+ 12C_2 )\| λ_t- λ_t+1\|_2^2 = = ηλ(‖⋆−^t‖22−‖⋆−^t+1‖22−‖t−^t+1‖22−‖t−^t‖22) _λ (\| λ - λ_t\|_2^2-\| λ - λ_t+1\|_2^2-\| λ_t- λ_t+1\|_2^2-\| λ_t- λ_t\|_2^2 ) +x∼[C1KL(πt(⋅|x)∥π^t(⋅|x))+C2KL(π^t(⋅|x)∥πt−1(⋅|x))]+|ℋ|Rmax2(12C1+12C2)∥t−^t+1∥22 +E_x [C_1KL( _t(·|x)\| π_t(·|x))+C_2KL( π_t(·|x)\| _t-1(·|x)) ]+|H|R_ ^2 ( 12C_1+ 12C_2 )\| λ_t- λ_t+1\|_2^2 C.3 Combining AA and BB Substituting eq. 36 and eq. 42 into the RHS of eq. 31, we get L(π⋆,t)−L(πt,⋆) L(π , λ_t)-L( _t, λ ) ≤x∼[ηθKL(π⋆(⋅|x)∥π^t(⋅|x))−(ηθ+β)KL(π⋆(⋅|x)∥π^t+1(⋅|x))−(ηθ+β)KL(π^t+1(⋅|x)∥πt(⋅|x)) _x [ _θKL(π (·|x)\| π_t(·|x))-( _θ+β)KL(π (·|x)\| π_t+1(·|x)) [rgb]1,0,0-( _θ+β)KL( π_t+1(·|x)\| _t(·|x)) . −ηθKL(πt(⋅|x)∥π^t(⋅|x))+CKL(π^t+1(⋅|x)∥πt(⋅|x))] . [rgb]0,0,1- _θKL( _t(·|x)\| π_t(·|x)) [rgb]1,0,0+CKL( π_t+1(·|x)\| _t(·|x)) ] +|ℋ|Rmax2C(‖t−^t‖22+‖^t−t−1‖22)+ηλ(‖⋆−^t‖22−‖⋆−^t+1‖22−‖t−^t+1‖22−‖t−^t‖22) + |H|R_ ^2C ( [rgb]1,0,1\| λ_t- λ_t\|_2^2+\| λ_t- λ_t-1\|_2^2 )+ _λ (\| λ - λ_t\|_2^2-\| λ - λ_t+1\|_2^2 [rgb]0,1,1-\| λ_t- λ_t+1\|_2^2- [rgb]1,0,1\| λ_t- λ_t\|_2^2 ) +x∼[C1KL(πt(⋅|x)∥π^t(⋅|x))+C2KL(π^t(⋅|x)∥πt−1(⋅|x))]+|ℋ|Rmax2(12C1+12C2)∥t−^t+1∥22 +E_x [ [rgb]0,0,1C_1KL( _t(·|x)\| π_t(·|x))+C_2KL( π_t(·|x)\| _t-1(·|x)) ]+ [rgb]0,1,1|H|R_ ^2 ( 12C_1+ 12C_2 )\| λ_t- λ_t+1\|_2^2 ≤x∼[ηθKL(π⋆(⋅|x)∥π^t(⋅|x))−(ηθ+β)KL(π⋆(⋅|x)∥π^t+1(⋅|x))−(ηθ+β−C)KL(π^t+1(⋅|x)∥πt(⋅|x)) _x [ _θKL(π (·|x)\| π_t(·|x))-( _θ+β)KL(π (·|x)\| π_t+1(·|x))-( _θ+β-C)KL( π_t+1(·|x)\| _t(·|x)) . −(ηθ−C1)KL(πt(⋅|x)∥π^t(⋅|x))+C2KL(π^t(⋅|x)∥πt−1(⋅|x))] .- ( _θ-C_1 )KL( _t(·|x)\| π_t(·|x))+C_2KL( π_t(·|x)\| _t-1(·|x)) ] −(ηλ−|ℋ|Rmax2C)‖t−^t‖22+|ℋ|Rmax2C‖^t−t−1‖22+ηλ‖⋆−^t‖22−ηλ‖⋆−^t+1‖22 - ( _λ- |H|R_ ^2C )\| λ_t- λ_t\|_2^2+ |H|R_ ^2C\| λ_t- λ_t-1\|_2^2+ _λ\| λ - λ_t\|_2^2- _λ\| λ - λ_t+1\|_2^2 −(ηλ−|ℋ|Rmax2(12C1+12C2))‖t−^t+1‖22, - ( _λ-|H|R_ ^2 ( 12C_1+ 12C_2 ) )\| λ_t- λ_t+1\|_2^2, where terms sharing the same color can be combined. Recall eq. 30 that L(π⋆,t)−L(πt,⋆)≥0L(π , λ_t)-L( _t, λ )≥ 0. Substituting this into the above equation and rearranging the equation, we have (ηθ+β)x∼[KL(π⋆(⋅|x)∥π^t+1(⋅|x))]+(ηθ+β−C)x∼[KL(π^t+1(⋅|x)∥πt(⋅|x))] ( _θ+β)E_x [KL(π (·|x)\| π_t+1(·|x)) ]+( _θ+β-C)E_x [KL( π_t+1(·|x)\| _t(·|x)) ] (43) +ηλ‖⋆−^t+1‖22+(ηλ−|ℋ|Rmax2(12C1+12C2))‖t−^t+1‖22 + _λ\| λ - λ_t+1\|_2^2+ ( _λ-|H|R_ ^2 ( 12C_1+ 12C_2 ) )\| λ_t- λ_t+1\|_2^2 ≤ηθx∼[KL(π⋆(⋅|x)∥π^t(⋅|x))]+C2x∼[KL(π^t(⋅|x)∥πt−1(⋅|x))]+ηλ∥⋆−^t∥22+|ℋ|Rmax2C∥^t−t−1∥22 ≤ _θE_x [KL(π (·|x)\| π_t(·|x)) ]+C_2E_x [KL( π_t(·|x)\| _t-1(·|x)) ]+ _λ\| λ - λ_t\|_2^2+ |H|R_ ^2C\| λ_t- λ_t-1\|_2^2 −(ηθ−C1)x∼[KL(πt(⋅|x)∥π^t(⋅|x))]−(ηλ−|ℋ|Rmax2C)∥t−^t∥22 - ( _θ-C_1 )E_x [KL( _t(·|x)\| π_t(·|x)) ]- ( _λ- |H|R_ ^2C )\| λ_t- λ_t\|_2^2 Note that for any δ,θ>0δ,θ>0, we have ‖t−^t‖2 \| λ_t- λ_t\|^2 =‖(t−^t+1)+(^t+1−⋆)+(⋆−^t)‖2 = \| ( λ_t- λ_t+1 )+ ( λ_t+1- λ )+ ( λ - λ_t ) \|^2 (44) ≥(1−δ)‖^t+1−⋆‖2+(1−1δ)(1−θ)‖t−^t+1‖2+(1−1δ)(1−1θ)‖⋆−^t‖2(by lemma B.4). ≥(1-δ)\| λ_t+1- λ \|^2+(1- 1δ)(1-θ)\| λ_t- λ_t+1\|^2+(1- 1δ)(1- 1θ)\| λ - λ_t\|^2 (by @crefcreftype~refnumlem:||a+b+c||_2^2_lower_bd). Substituting eq. 44 into the last term of the RHS of eq. 43 to get (ηθ+β)x∼[KL(π⋆(⋅|x)∥π^t+1(⋅|x))]+(ηθ+β−C)x∼[KL(π^t+1(⋅|x)∥πt(⋅|x))] ( _θ+β)E_x [KL(π (·|x)\| π_t+1(·|x)) ]+( _θ+β-C)E_x [KL( π_t+1(·|x)\| _t(·|x)) ] +ηλ‖⋆−^t+1‖22+(ηλ−|ℋ|Rmax2(12C1+12C2))‖t−^t+1‖22 [rgb]1,0,0+ _λ\| λ - λ_t+1\|_2^2+ [rgb]0,0,1 ( _λ-|H|R_ ^2 ( 12C_1+ 12C_2 ) )\| λ_t- λ_t+1\|_2^2 ≤ηθx∼[KL(π⋆(⋅|x)∥π^t(⋅|x))]+C2x∼[KL(π^t(⋅|x)∥πt−1(⋅|x))]+ηλ∥⋆−^t∥22+|ℋ|Rmax2C∥^t−t−1∥22 ≤ _θE_x [KL(π (·|x)\| π_t(·|x)) ]+C_2E_x [KL( π_t(·|x)\| _t-1(·|x)) ]+ [rgb]0,1,1 _λ\| λ - λ_t\|_2^2+ |H|R_ ^2C\| λ_t- λ_t-1\|_2^2 −(ηθ−C1)x∼[KL(πt(⋅|x)∥π^t(⋅|x))]−(ηλ−|ℋ|Rmax2C)(1−δ)∥^t+1−⋆∥2 - ( _θ-C_1 )E_x [KL( _t(·|x)\| π_t(·|x)) ] [rgb]1,0,0- ( _λ- |H|R_ ^2C )(1-δ)\| λ_t+1- λ \|^2 −(ηλ−|ℋ|Rmax2C)(1−1δ)(1−θ)‖t−^t+1‖2−(ηλ−|ℋ|Rmax2C)(1−1δ)(1−1θ)‖⋆−^t‖2, [rgb]0,0,1- ( _λ- |H|R_ ^2C )(1- 1δ)(1-θ)\| λ_t- λ_t+1\|^2 [rgb]0,1,1- ( _λ- |H|R_ ^2C )(1- 1δ)(1- 1θ)\| λ - λ_t\|^2, where terms of the same color can be combined. Rearranging the above equation, we have (ηθ+β)x∼[KL(π⋆(⋅|x)∥π^t+1(⋅|x))]+(ηθ+β−C)x∼[KL(π^t+1(⋅|x)∥πt(⋅|x))] ( _θ+β)E_x [KL(π (·|x)\| π_t+1(·|x)) ]+( _θ+β-C)E_x [KL( π_t+1(·|x)\| _t(·|x)) ] (45) +(ηλ+(ηλ−|ℋ|Rmax2C)(1−δ))‖⋆−^t+1‖22 + ( _λ+ ( _λ- |H|R_ ^2C )(1-δ) )\| λ - λ_t+1\|_2^2 +(ηλ−|ℋ|Rmax2(12C1+12C2)+(ηλ−|ℋ|Rmax2C)(1−1δ)(1−θ))‖^t+1−t‖22 + ( _λ-|H|R_ ^2 ( 12C_1+ 12C_2 )+ ( _λ- |H|R_ ^2C )(1- 1δ)(1-θ) )\| λ_t+1- λ_t\|_2^2 ≤ηθx∼[KL(π⋆(⋅|x)∥π^t(⋅|x))]+C2x∼[KL(π^t(⋅|x)∥πt−1(⋅|x))] ≤ _θE_x [KL(π (·|x)\| π_t(·|x)) ]+C_2E_x [KL( π_t(·|x)\| _t-1(·|x)) ] +(ηλ−(ηλ−|ℋ|Rmax2C)(1−1δ)(1−1θ))‖⋆−^t‖22 + ( _λ- ( _λ- |H|R_ ^2C )(1- 1δ)(1- 1θ) )\| λ - λ_t\|_2^2 +|ℋ|Rmax2C∥^t−t−1∥22−(ηθ−C1)x∼[KL(πt(⋅|x)∥π^t(⋅|x))] + |H|R_ ^2C\| λ_t- λ_t-1\|_2^2- ( _θ-C_1 )E_x [KL( _t(·|x)\| π_t(·|x)) ] Define Φt _t as the LHS of eq. 45, i.e., Φt+1:= _t+1= (ηθ+β)x∼[KL(π⋆(⋅|x)∥π^t+1(⋅|x))]+(ηθ+β−C)x∼[KL(π^t+1(⋅|x)∥πt(⋅|x))] ( _θ+β)E_x [KL(π (·|x)\| π_t+1(·|x)) ]+( _θ+β-C)E_x [KL( π_t+1(·|x)\| _t(·|x)) ] +(ηλ+(ηλ−|ℋ|Rmax2C)(1−δ))‖⋆−^t+1‖22 + ( _λ+ ( _λ- |H|R_ ^2C )(1-δ) )\| λ - λ_t+1\|_2^2 +(ηλ−|ℋ|Rmax2(12C1+12C2)+(ηλ−|ℋ|Rmax2C)(1−1δ)(1−θ))‖^t+1−t‖22 + ( _λ-|H|R_ ^2 ( 12C_1+ 12C_2 )+ ( _λ- |H|R_ ^2C )(1- 1δ)(1-θ) )\| λ_t+1- λ_t\|_2^2 If the following requirements are satisfied: 1. Multipliers of all terms of LHS of eq. 45 are positive: ηθ+β>0, _θ+β>0, ηθ+β−C>0, _θ+β-C>0, ηλ+(ηλ−|ℋ|Rmax2C)(1−δ)>0, _λ+ ( _λ- |H|R_ ^2C )(1-δ)>0, ηλ−|ℋ|Rmax2(12C1+12C2)+(ηλ−|ℋ|Rmax2C)(1−1δ)(1−θ)>0. _λ-|H|R_ ^2 ( 12C_1+ 12C_2 )+ ( _λ- |H|R_ ^2C )(1- 1δ)(1-θ)>0. 2. Multipliers of all terms of RHS of eq. 45 are positive: ηθ>0, _θ>0, C2>0, C_2>0, ηλ−(ηλ−|ℋ|Rmax2C)(1−1δ)(1−1θ)>0, _λ- ( _λ- |H|R_ ^2C )(1- 1δ)(1- 1θ)>0, |ℋ|Rmax2C>0, |H|R_ ^2C>0, ηθ−C1>0. _θ-C_1>0. 3. Define ρ:= ρ= max(ηθηθ+β,C2ηθ+β−C,ηλ−(ηλ−|ℋ|Rmax2C)(1−1δ)(1−1θ)ηλ+(ηλ−|ℋ|Rmax2C)(1−δ), ( _θ _θ+β, C_2 _θ+β-C, _λ- ( _λ- |H|R_ ^2C )(1- 1δ)(1- 1θ) _λ+ ( _λ- |H|R_ ^2C )(1-δ), . |ℋ|Rmax2Cηλ−|ℋ|Rmax2(12C1+12C2)+(ηλ−|ℋ|Rmax2C)(1−1δ)(1−θ)), . |H|R_ ^2C _λ-|H|R_ ^2 ( 12C_1+ 12C_2 )+ ( _λ- |H|R_ ^2C )(1- 1δ)(1-θ) ), then ρ<1ρ<1. Then eq. 45 can be written as Φt+1≤ _t+1≤ ρΦt−(ηθ−C1)x∼[KL(πt(⋅|x)∥π^t(⋅|x))](by the definition of ρ) ρ _t- ( _θ-C_1 )E_x [KL( _t(·|x)\| π_t(·|x)) ] (by the definition of $ρ$) ≤ ≤ ρΦt(by η−C1>0 and x∼[KL(πt(⋅|x)∥π^t(⋅|x))]>0) ρ _t (by $η-C_1>0$ and $E_x [KL( _t(·|x)\| π_t(·|x)) ]>0$) Iteratively apply the recursion, we have Φt≤ρtΦ1 _t≤ρ^t _1, where Φ1= _1= (ηθ+β)x∼[KL(π⋆(⋅|x)∥π^1(⋅|x))]+(ηθ+β−C)x∼[KL(π^1(⋅|x)∥π0(⋅|x))] ( _θ+β)E_x [KL(π (·|x)\| π_1(·|x)) ]+( _θ+β-C)E_x [KL( π_1(·|x)\| _0(·|x)) ] +(ηλ+(ηλ−|ℋ|Rmax2C)(1−δ))‖⋆−^1‖22 + ( _λ+ ( _λ- |H|R_ ^2C )(1-δ) )\| λ - λ_1\|_2^2 +(ηλ−|ℋ|Rmax2(12C1+12C2)+(ηλ−|ℋ|Rmax2C)(1−1δ)(1−θ))‖^1−0‖22. + ( _λ-|H|R_ ^2 ( 12C_1+ 12C_2 )+ ( _λ- |H|R_ ^2C )(1- 1δ)(1-θ) )\| λ_1- λ_0\|_2^2. 3.3 guarantees support of the policy does not shrink along the OPD iterates, and also ensures that the KL terms KL(π(y|x)∣πref(y|x))KL(π(y|x) _ref(y|x)) and KL(π(y|x)∣π^t(y|x))KL(π(y|x) π_t(y|x)) are well-defined throughout iterations. We initialize π0 _0 to have the same support as πref _ref and set π^0=πref π_0= _ref. From the closed-form solution of the KL-regularized maximization in eqs. 4 and 6, the policy updates have the form πt(y|x)∝π^t(y|x)ηθηθ+βπref(y|x)βηθ+βexp⁡(Sλt−1(x,y)), _t(y|x) π_t(y|x) _θ _θ+β _ref(y|x) β _θ+β (S_ _t-1(x,y) ), and similarly, π^t+1(y|x)∝π^t(y|x)ηθηθ+βπref(y|x)βηθ+βexp⁡(Sλt(x,y)). π_t+1(y|x) π_t(y|x) _θ _θ+β _ref(y|x) β _θ+β (S_ _t(x,y) ). Since all factors on the right-hand side are strictly positive whenever πref(y|x)>0 _ref(y|x)>0, it follows by induction that for all x∈x and iteration i, we have supp(πt(⋅|x))=supp(π^t(⋅|x))=supp(πref(⋅|x)).supp( _t(·|x))=supp( π_t(·|x))=supp( _ref(·|x)). Therefore, Φ1 _1 is bounded. Furthermore, we have x∼[KL(π⋆(⋅|x)∥π^t(⋅|x))]+∥⋆−^t∥22≤ρtΦ1ρmax⁡(ηθ+β,ηλ+(ηλ−|ℋ|Rmax2C)(1−δ)) _x [KL(π (·|x)\| π_t(·|x)) ]+\| λ - λ_t\|_2^2≤ρ^t _1ρ ( _θ+β, _λ+ ( _λ- |H|R_ ^2C )(1-δ) ) and this shows the desired result. Hyperparameters and Constants Selection Our next step is to choose hyperparameters ηθ _θ and ηλ _λ as well as constants C1C_1, C2C_2, and C to satisfy the requirements. For simplicity, with a little abuse of notations, we denote h=|ℋ|h=|H| and R=RmaxR=R_ in this parameter and constants selection section. Let ηθ=ηλ=η=3hR,C1=C2=C=hR,12<δ<1,12<θ<1. _θ= _λ=η=3 hR, C_1=C_2=C= hR, 12<δ<1, 12<θ<1. We will verify that this set of parameters satisfies the requirements. 1. Verifications that multipliers of all terms of LHS of eq. 45 are positive. (1) Since ηθ>0 _θ>0 and β>0β>0, we have ηθ+β>0 _θ+β>0. (2) ηθ+β−C=β+2hR>0 _θ+β-C=β+2 hR>0. (3) Since ηλ−hR2/C=3hR−hR2/(hR)=2hR>0 _λ-hR^2/C=3 hR-hR^2/( hR)=2 hR>0 and δ<1δ<1, we have (ηλ−hR2/C)(1−δ)>0 ( _λ-hR^2/C )(1-δ)>0. Hence ηλ+(ηλ−hR2/C)(1−δ)>0 _λ+ ( _λ-hR^2/C )(1-δ)>0. (4) ηλ−hR2(1/(2C1)+1/(2C2))+(ηλ−hR2/C)(1−1/δ)(1−θ)=3hR−hR2/(hR)+(2hR−hR2/(hR))(1−1/δ)(1−θ)=hR(2+(1−1/δ)(1−θ)) _λ-hR^2 (1/(2C_1)+1/(2C_2) )+ ( _λ-hR^2/C )(1-1/δ)(1-θ)=3 hR-hR^2/( hR)+(2 hR-hR^2/( hR))(1-1/δ)(1-θ)= hR (2+ (1-1/δ ) (1-θ ) ). Since 1/2<δ,θ<11/2<δ,θ<1, we have −1<1−1/δ<0-1<1-1/δ<0 and 0<1−θ<1/20<1-θ<1/2, hence −1/2<(1−1/δ)(1−θ)<0-1/2< (1-1/δ ) (1-θ )<0. Therefore, 2+(1−1/δ)(1−θ)>02+ (1-1/δ ) (1-θ )>0. 2. Verifications that the multipliers of all terms of the RHS of eq. 45 are positive. (1) ηθ>0 _θ>0 by the definition of ηθ _θ. (2) C2>0C_2>0 by the definition of C2C_2. (3) ηλ−(ηλ−hR2/C)(1−1/δ)(1−1/θ)=3hR−(3hR−hR2/(hR)(1−1/δ)(1−1/θ)=hR(3−2(1−1/δ)(1−1/θ)) _λ- ( _λ-hR^2/C )(1-1/δ)(1-1/θ)=3 hR-(3 hR-hR^2/( hR)(1-1/δ)(1-1/θ)= hR(3-2(1-1/δ)(1-1/θ)). Since 1/2<δ,θ<11/2<δ,θ<1, we have −1<1−1/θ<0-1<1-1/θ<0 and −1<1−1/δ<0-1<1-1/δ<0, hence 0<(1−1/θ)(1−1/δ)<10<(1-1/θ)(1-1/δ)<1. Therefore, we get 3−2(1−1/δ)(1−1/θ)>03-2(1-1/δ)(1-1/θ)>0. (4) As hR2>0hR^2>0 and C=hR>0C= hR>0, we have hR2/C>0hR^2/C>0. (5) ηθ−C1=3hR−hR=2hR>0 _θ-C_1=3 hR- hR=2 hR>0. 3. (1) Since ηθ>0 _θ>0 and β>0β>0, we have ηθηθ+β<1 _θ _θ+β<1. (2) We have C2/(ηθ+β−C)=hR/(3hR−β−hR)<hR/(3hR−hR)=1/2C_2/( _θ+β-C)= hR/(3 hR-β- hR)< hR/(3 hR- hR)=1/2, where the inequality is because β>0β>0. (3) Since ηλ−hR2/C=3hR−hR2/(hR)=2hR>0 _λ-hR^2/C=3 hR-hR^2/( hR)=2 hR>0, (1−1/δ)(1−1/θ)>0(1-1/δ)(1-1/θ)>0, and 1−δ>01-δ>0, we have (ηλ−hR2/C)(1−1/δ)(1−1/θ)>0 ( _λ-hR^2/C )(1-1/δ)(1-1/θ)>0 and (ηλ−hR2/C)(1−δ)>0 ( _λ-hR^2/C )(1-δ)>0, hence ηλ−(ηλ−hR2/C)(1−1/δ)(1−1/θ)<ηλ+(ηλ−hR2/C)(1−δ) _λ- ( _λ-hR^2/C )(1-1/δ)(1-1/θ)< _λ+ ( _λ-hR^2/C )(1-δ), and (ηλ−(ηλ−hR2/C)(1−1/δ)(1−1/θ))/(ηλ+(ηλ−hR2/C)(1−δ))<1( _λ- ( _λ-hR^2/C )(1-1/δ)(1-1/θ))/( _λ+ ( _λ-hR^2/C )(1-δ))<1. (4)Plugging the parameters values into the last requirement, we have hR2/Cηλ−hR2(1/2C1+1/2C2)+(ηλ−hR2/C)(1−1/δ)(1−θ) hR^2/C _λ-hR^2 (1/2C_1+1/2C_2 )+( _λ-hR^2/C)(1-1/δ)(1-θ) =hR2hR+2hR(1−1/δ)(1−θ) = hR2 hR+2 hR(1-1/δ)(1-θ) =12+2(1−1/δ)(1−θ). = 12+2(1-1/δ)(1-θ). As 1/2<θ,δ<11/2<θ,δ<1, −1/2<(1−1/δ)(1−θ)<0-1/2<(1-1/δ)(1-θ)<0. Therefore 1<2+2(1−1/δ)(1−θ)<21<2+2(1-1/δ)(1-θ)<2 and 1/2+2(1−1/δ)(1−θ)<11/2+2(1-1/δ)(1-θ)<1. If we further set δ=θ=34δ=θ= 34, then we can write ρ and Φ1 _1 as ρ=max⁡(3ℋRmax3ℋRmax+β,ℋRmax2ℋRmax+β,5063),ρ= ( 3 HR_ 3 HR_ +β, HR_ 2 HR_ +β, 5063 ), (46) Φ1= _1= (3ℋRmax+β)x∼[KL(π⋆(⋅|x)∥π^1(⋅|x))]+(2ℋRmax+β)x∼[KL(π^1(⋅|x)∥π0(⋅|x))] (3 HR_ +β)E_x [KL(π (·|x)\| π_1(·|x)) ]+(2 HR_ +β)E_x [KL( π_1(·|x)\| _0(·|x)) ] (47) +72ℋRmax‖⋆−^1‖22+116ℋRmax‖^1−0‖22. + 72 HR_ \| λ - λ_1\|_2^2+ 116 HR_ \| λ_1- λ_0\|_2^2. Appendix D Proof of remark 3.5 In this section, we show under the tabular softmax parameterization, the updated policy πθ+ _ _+ is equivalent to π+ _+ with θ+ _+ and π+ _+ shown as follows. θ+=θ+1ηθ+βF(θ)†∇θℒ(πθ,λ), _+=θ+ 1 _θ+βF(θ) _θL( _θ,λ), (48) π+=argmaxπx∼[y∼π(⋅|x)[Sλ(x,y)]−βKL(π(⋅|x)∥πref(⋅|x))−ηθKL(π(⋅|x)∥πθ(⋅|x))], _+= _πE_x [E_y π(·|x) [S_λ(x,y) ]- (π(·|x)\| _ref(·|x) )- _θKL (π(·|x)\| _θ(·|x) ) ], (49) where ℒ(πθ,λ)=x∼[y∼πθ(⋅|x)Sλ(x,y)−βKL(π(⋅|x)∥πref(⋅|x))]L( _θ,λ)=E_x [E_y _θ(·|x)S_λ(x,y)- (π(·|x)\| _ref(·|x)) ] and Sλ(x,y)=∑k∈wkRk(x,y)+∑j∈ℋλjRj(x,y)S_λ(x,y)= _k w_kR_k(x,y)+ _j _jR_j(x,y). If we let θ=θ^tθ= θ_t and λ=λt−1λ= _t-1, then the above equivalence proves that the πθt _ _t with NPG update shown in eq. 8 and πt _t with OPG update shown in eq. 4 are the same under the tabular softmax parameterized distribution. Similarly, if we let θ=θ^tθ= θ_t and λ=λtλ= _t, then we have πθ^t+1 _ θ_t+1 of NPG update shown in eq. 10 and π^t+1 π_t+1 of OPG update shown in eq. 6 are the same. Define Vλπ(x) V_λ^π(x) :=y∼π(⋅|x)[Sλ(x,y)−βlog⁡π(y|x)πref(y|x)], :=E_y π(·|x) [S_λ(x,y)-β π(y|x) _ref(y|x) ], (50) Aλπ(x,y) A_λ^π(x,y) :=Sλ(x,y)−βlog⁡π(y|x)πref(y|x)−Vλπ(x). :=S_λ(x,y)-β π(y|x) _ref(y|x)-V_λ^π(x). (51) We can rewrite ∇θℒ(πθ,λ) _θL( _θ,λ) as ∇θℒ(πθ,λ)= _θL( _θ,λ)= x∼,y∼πθ(⋅|x)[(Sλ(x,y)−βlog⁡πθ(y|x)πref(y|x))∇θlog⁡πθ(y|x)] _x ,y _θ(·|x) [ (S_λ(x,y)-β _θ(y|x) _ref(y|x) ) _θ _θ(y|x) ] (52) = = x∼,y∼πθ(⋅|x)[Aλπθ(x,y)∇θlog⁡πθ(y|x)], _x ,y _θ(·|x) [A_λ _θ(x,y) _θ _θ(y|x) ], where the first equation is because ℒ(πθ,λ)=x∼[y∼πθ(⋅|x)Sλ(x,y)−βKL(π(⋅|x)∥πref(⋅|x))]L( _θ,λ)=E_x [E_y _θ(·|x)S_λ(x,y)- (π(·|x)\| _ref(·|x)) ] and Sλ(x,y)=∑k∈wkRk(x,y)+∑j∈ℋλjRj(x,y)S_λ(x,y)= _k w_kR_k(x,y)+ _j _jR_j(x,y), and the second equation is by the definition of Aλπθ(x,y)A_λ _θ(x,y) and y∼πθ(⋅|x)[Vλπθ(x)∇θlog⁡πθ(y|x)]=0E_y _θ(·|x)[V_λ _θ(x) _θ _θ(y|x)]=0. Then the partial derivation w.r.t. θx,y _x,y is ∂ℒ(πθ,λ)∂θx,y ( _θ,λ)∂ _x,y =x′∼,y′∼πθ(⋅|x′)[Aλπθ(x′,y′)∂θx,ylog⁡πθ(y′|x′)] =E_x ,y _θ(·|x ) [A_λ _θ(x ,y ) ∂ _x,y _θ(y |x ) ] =(a)y′∼πθ(⋅|x)[Aλπθ(x,y′)(y′=y−πθ(y|x))](x) (a)=E_y _θ(·|x) [A_λ _θ(x,y ) (I\y =y\- _θ(y|x) ) ]D(x) =(x)πθ(y|x)(Aλπθ(x,y)−y′∼πθ(⋅|x)[Aλπθ(x,y′)]) =D(x) _θ(y|x) (A_λ _θ(x,y)-E_y _θ(·|x)[A_λ _θ(x,y )] ) =(b)(x)πθ(y|x)Aλπθ(x,y), (b)=D(x) _θ(y|x)A_λ _θ(x,y), where (a)(a) is because ∂θx,ylog⁡πθ(y′|x′)=x′=x(y′=y−πθ(y|x)), ∂ _x,y _θ(y |x )=I\x =x\ (I\y =y\- _θ(y|x) ), and (b)(b) is because y′∼πθ(⋅|x)[Aλπθ(x,y′)]=0E_y _θ(·|x)[A_λ _θ(x,y )]=0. Let x,y∈ℝ||||e_x,y ^|X||Y| with only the position θx,y _x,y has element 11 and all other elements are 0, and πθ,x∈ℝ|||| _θ,x ^|X||Y| with only the positions θx,y _x,y has value πθ(y|x) _θ(y|x) and all other elements are 0. Then we rewrite F(θ)F(θ) as F(θ)= F(θ)= x∼,y∼πθ(⋅|x)[∇θlog⁡πθ(y|x)∇θlog⁡πθ(y|x)⊤] _x ,y _θ(·|x) [ _θ _θ(y|x) _θ _θ(y|x) ] = = x∼,y∼πθ(⋅|x)[(x,y−πθ,x)(x,y−πθ,x)⊤] _x ,y _θ(·|x) [ (e_x,y- _θ,x ) (e_x,y- _θ,x ) ] = = x∼,y∼πθ(⋅|x)[x,yx,y⊤−πθ,xx,y⊤−x,yπθ,x⊤+πθ,xπθ,x⊤] _x ,y _θ(·|x) [e_x,ye_x,y - _θ,xe_x,y -e_x,y _θ,x + _θ,x _θ,x ] = = x∼[diag(πθ,x)−πθ,xπθ,x⊤−πθ,xπθ,x⊤+πθ,xπθ,x⊤] _x [diag( _θ,x)- _θ,x _θ,x - _θ,x _θ,x + _θ,x _θ,x ] = = x∼[diag(πθ,x)−πθ,xπθ,x⊤], _x [diag( _θ,x)- _θ,x _θ,x ], where the second equality uses the partial derivative of θ of log⁡πθ(y|x) _θ(y|x). We now characterize the natural-gradient direction =F(θ)†∇θℒ(πθ,λ)w=F(θ) _θL( _θ,λ), where F(θ)†F(θ) is the Moore–Penrose pseudoinverse of F(θ)F(θ). In other words, F(θ)=∇θℒ(πθ,λ)F(θ)w= _θL( _θ,λ). Let w¯x:=πθ,x⊤=y∼πx[x,y] w_x:= _θ,x w=E_y _x[w_x,y]. Consider the (x,y)(x,y)-th coordinate of the LHS, we have [F(θ)]x,y= [F(θ)w ]_x,y= (x)[(diag(πθ,x)−πxπθ,x⊤)]y (x) [ (diag( _θ,x)- _x _θ,x )w ]_y = = (x)[diag(πθ,x)]y−[πθ,xπθ,x⊤]y (x) [diag( _θ,x)w ]_y- [ _θ,x _θ,x w ]_y = = (x)πθ,x(y|x)(x,y−w¯x), (x) _θ,x(y|x) (w_x,y- w_x ), Comparing with ∂ℒ(πθ,λ)∂θx,y=(x)πθ(y|x)Aλπθ(x,y) ( _θ,λ)∂ _x,y=D(x) _θ(y|x)A_λ _θ(x,y), we have x,y=Aλπθ(x,y)+c(x)w_x,y=A_λ _θ(x,y)+c(x). Plugging x,yw_x,y into eq. 48, θ+=θ+1ηθ+β(Aλπθ(x,y)+c(x)) _+=θ+ 1 _θ+β (A_λ _θ(x,y)+c(x) ). The corresponding policy can be written as πθ+(y|x)=exp⁡(θx,y+)∑y′∈exp⁡(θx,y′+)=exp⁡(θx,y)exp⁡(1ηθ+βAλπθ(x,y))∑y′∈exp⁡(θx,y′)exp⁡(1ηθ+βAλπθ(x,y′)).=πθ(y|x)exp⁡(1ηθ+βAλπθ(x,y))∑y′∈πθ(y′|x)exp⁡(1ηθ+βAλπθ(x,y′)). _θ^+(y|x)= (θ^+_x,y) _y (θ^+_x,y )= ( _x,y) ( 1 _θ+βA_λ _θ(x,y)) _y ( _x,y ) ( 1 _θ+βA_λ _θ(x,y )).= _θ(y|x) ( 1 _θ+βA_λ _θ(x,y)) _y _θ(y |x) ( 1 _θ+βA_λ _θ(x,y )). That is, πθ+(y|x)∝πθ(y|x)exp⁡(1ηθ+βAλπθ(x,y)). _θ^+(y|x) _θ(y|x) ( 1 _θ+βA_λ _θ(x,y) ). As shown in eq. 49 π+=argmaxπx∼[y∼π(⋅|x)[Sλ(x,y)]−βKL(π(⋅|x)∥πref(⋅|x))−ηθKL(π(⋅|x)∥πθ(⋅|x))]. _+= _πE_x [E_y π(·|x) [S_λ(x,y) ]- (π(·|x)\| _ref(·|x) )- _θKL (π(·|x)\| _θ(·|x) ) ]. Solve the maximization problem over the simplex Δ() (Y) yields the softmax solution π+(y|x)∝ π^+(y|x) exp⁡(1ηθ+β(Sλ(x,y)+βlog⁡πref(y|x)+ηθlog⁡πθ(y|x))) ( 1 _θ+β (S_λ(x,y)+β _ref(y|x)+ _θ _θ(y|x) ) ) ∝ πθ(y|x)exp⁡(1ηθ+β(Sλ(x,y)−βlog⁡πθ(y|x)πref(y|x))) _θ(y|x) ( 1 _θ+β (S_λ(x,y)-β _θ(y|x) _ref(y|x) ) ) ∝ πθ(y|x)exp⁡(1ηθ+βAλπθ(x,y)), _θ(y|x) ( 1 _θ+βA_λ _θ(x,y) ), where the last equality is by the definition of Aλπθ(x,y)A_λ _θ(x,y). Comparing πθ+ _ _+ and π+ _+ concludes the proof. Appendix E Proof of corollary 3.10 Let ΠΘ _ denote the class of parameterized policies that have full support on the considered action set, i.e., there exists pmin>0p_ >0 such that πθ(y|x)≥pmin _θ(y|x)≥ p_ for all feasible (x,y)(x,y). Also, the parameter domain Θ⊂ℝd ^d is closed and convex. The Lagrangian problem is minλ≥0⁡maxθ∈Θ⁡ℒ(πθ,λ), _λ≥ 0 _θ∈ L( _θ,λ), where ℒ(πθ,λ)=x∼[VSλπθ(x)−βKL(πθ(⋅|x)∥πref(⋅|x))]L( _θ,λ)=E_x [V _θ_S_λ(x)- ( _θ(·|x)\| _ref(·|x)) ]. Under Slater’s condition in the parameterized policy space, as shown in 3.7, strong duality holds and hence an optimal saddle point (πθ⋆,λ⋆)( _θ ,λ ) exists in the parameterized policy space. Without loss of generality, we denote πθt _ _t by πt _t and πθ^t _ θ_t by π^t π_t. Throughout this section, we further denote the optimal policy πθ⋆πθ by π⋆π . Since π⋆=argmaxπL(π,⋆)π =argmax_πL(π, λ ), we have L(π⋆,⋆)≥L(π,⋆)L(π , λ )≥ L(π, λ ) for any π∈Ππ∈ . Similarly, since ⋆=argminλL(π⋆,λ) λ =argmin_λL(π ,λ), we have L(π⋆,λ)≥L(π⋆,⋆)L(π ,λ)≥ L(π , λ ) for any λ≥0λ≥ 0. Combining these two inequalities together, for any π∈Ππ∈ and λ≥0λ≥ 0, we have L(π⋆,λ)−L(π,⋆)=L(π⋆,λ)−L(π⋆,⋆)⏟≥0+L(π⋆,⋆)−L(π,⋆)⏟≥0≥0L(π ,λ)-L(π, λ )= L(π ,λ)-L(π , λ )_≥ 0+ L(π , λ )-L(π, λ )_≥ 0≥ 0 (53) Let π=πtπ= _t and λ=tλ= λ_t and substituting the definition of L(π,λ)L(π,λ) into the LHS of the above inequality, we have L(π⋆,t)−L(πt,⋆)= L(π , λ_t)-L( _t, λ )= x∼[VStπ⋆(x)−βKL(π⋆(⋅|x)∥πref(⋅|x))]−x∼[VS⋆π(x)−βKL(π(⋅|x)∥πref(⋅|x))] _x [V^π _S_ λ_t(x)- (π (·|x)\| _ref(·|x)) ]-E_x [V^π_S_ λ (x)- (π(·|x)\| _ref(·|x)) ] (54) = = x∼[VStπ⋆(x)−βKL(π⋆(⋅|x)∥πref(⋅|x))]−x∼[VStπt(x)−βKL(πt(⋅|x)∥πref(⋅|x))]⏟A E_x [V^π _S_ λ_t(x)- (π (·|x)\| _ref(·|x)) ]-E_x [V _t_S_ λ_t(x)- ( _t(·|x)\| _ref(·|x)) ]_A +x∼[VStπt(x)−βKL(πt(⋅|x)∥πref(⋅|x))]−x∼[VS⋆πt(x)−βKL(πt(⋅|x)∥πref(⋅|x))])⏟B + E_x [V _t_S_ λ_t(x)- ( _t(·|x)\| _ref(·|x)) ]-E_x [V _t_S_ λ (x)- ( _t(·|x)\| _ref(·|x)) ])_B E.1 Upper bound of term AA We can rewrite term AA as: A= = x∼[VStπ⋆(x)−βKL(π⋆(⋅|x)∥πref(⋅|x))]−x∼[VStπt(x)−βKL(πt(⋅|x)∥πref(⋅|x))] _x [V^π _S_ λ_t(x)- (π (·|x)\| _ref(·|x)) ]-E_x [V _t_S_ λ_t(x)- ( _t(·|x)\| _ref(·|x)) ] (55) = = x∼[(VStπ⋆(x)−VStπt(x))−β(KL(π⋆(⋅|x)∥πref(⋅|x))−KL(πt(⋅|x)∥πref(⋅|x)))] _x [ (V^π _S_ λ_t(x)-V _t_S_ λ_t(x) )-β (KL(π (·|x)\| _ref(·|x))-KL( _t(·|x)\| _ref(·|x)) ) ] =(a) (a)= x∼[⟨π⋆(⋅|x)−πt(⋅|x),St(x,⋅)⟩−β(KL(π⋆(⋅|x))∥πref(⋅|x)))−KL(πt(⋅|x))∥πref(⋅|x))))] _x [ π (·|x)- _t(·|x),S_ λ_t(x,·) -β (KL(π (·|x))\| _ref(·|x)))-KL( _t(·|x))\| _ref(·|x))) ) ] =(b) (b)= x∼[⟨π⋆(⋅|x)−π^t+1(⋅|x),St(x,⋅)⟩−β(KL(π⋆(⋅|x)∥πref(⋅|x))−KL(π^t+1(⋅|x)∥πref(⋅|x))) _x [ π (·|x)- π_t+1(·|x),S_ λ_t(x,·) -β (KL(π (·|x)\| _ref(·|x))-KL( π_t+1(·|x)\| _ref(·|x)) ) . +⟨π^t+1(⋅|x)−πt(⋅|x),St−1(x,⋅)⟩−β(KL(π^t+1(⋅|x)∥πref(⋅|x))−KL(πt(⋅|x)∥πref(⋅|x))) + π_t+1(·|x)- _t(·|x),S_ λ_t-1(x,·) -β (KL( π_t+1(·|x)\| _ref(·|x))-KL( _t(·|x)\| _ref(·|x)) ) +⟨π^t+1(⋅|x)−πt(⋅|x),St(x,⋅)−St−1(x,⋅)⟩] .+ π_t+1(·|x)- _t(·|x),S_ λ_t(x,·)-S_ λ_t-1(x,·) ] where (a)(a) is because the action space is discrete and VStπ(x)=∑yπ(y|x)St(x,y)=⟨π(⋅|x),St(x,⋅)⟩V^π_S_ λ_t(x)= _yπ(y|x)S_ λ_t(x,y)= π(·|x),S_ λ_t(x,·) for any π∈Ππ∈ , and (b)(b) is because adding and subtracting the same term keeps the equality. As we consider the NPG update in the linear parameterized space, where πt _t and π^t+1 π_t+1 updates follow eq. 8 and eq. 10. Using corollary B.12 and letting η=ηθη= _θ, g=St(x,⋅)g=S_ λ_t(x,·), πold=π^t(⋅|x) _old= π_t(·|x), πnew=π^t+1(⋅|x) _new= π_t+1(·|x), and π′=π⋆(⋅|x)π =π (·|x), we have x∼[⟨St(x,⋅),π^t+1(⋅|x)−π⋆(⋅|x)⟩−β(KL(π^t+1(⋅|x)∥πref(⋅|x))−KL(π⋆(⋅|x)∥πref(⋅|x)))] _x [ S_ λ_t(x,·), π_t+1(·|x)-π (·|x) -β (KL( π_t+1(·|x)\| _ref(·|x))-KL(π (·|x)\| _ref(·|x)) ) ] ≥x∼[ηθ(−KL(π⋆(⋅|x)∥π^t(⋅|x))+KL(π⋆(⋅|x)∥π^t+1(⋅|x))+KL(π^t+1(⋅|x)∥π^t(⋅|x)))+βKL(π⋆(⋅|x)∥π^t+1(⋅|x))] _x [ _θ (-KL(π (·|x)\| π_t(·|x))+KL(π (·|x)\| π_t+1(·|x))+KL( π_t+1(·|x)\| π_t(·|x)) )+ (π (·|x)\| π_t+1(·|x)) ] −gap(εapprox,pmin). -gap( _approx,p_ ). Putting a negative sign on both sides, we have x∼[⟨π⋆(⋅|x)−π^t+1(⋅|x),St(x,⋅)⟩−β(KL(π⋆(⋅|x)∥πref(⋅|x))−KL(π^t+1(⋅|x)∥πref(⋅|x)))] _x [ π (·|x)- π_t+1(·|x),S_ λ_t(x,·) -β (KL(π (·|x)\| _ref(·|x))-KL( π_t+1(·|x)\| _ref(·|x)) ) ] (56) ≤x∼[ηθ(KL(π⋆(⋅|x)∥π^t(⋅|x))−KL(π⋆(⋅|x)∥π^t+1(⋅|x))−KL(π^t+1(⋅|x)∥π^t(⋅|x)))−βKL(π⋆(⋅|x)∥π^t+1(⋅|x))] _x [ _θ (KL(π (·|x)\| π_t(·|x))-KL(π (·|x)\| π_t+1(·|x))-KL( π_t+1(·|x)\| π_t(·|x)) )- (π (·|x)\| π_t+1(·|x)) ] +gap(εapprox,pmin) +gap( _approx,p_ ) =x∼[ηθKL(π⋆(⋅|x)∥π^t(⋅|x))−(ηθ+β)KL(π⋆(⋅|x)∥π^t+1(⋅|x))−ηθKL(π^t+1(⋅|x)∥π^t(⋅|x))]+gap(εapprox,pmin) =E_x [ _θKL(π (·|x)\| π_t(·|x))-( _θ+β)KL(π (·|x)\| π_t+1(·|x))- _θKL( π_t+1(·|x)\| π_t(·|x)) ]+gap( _approx,p_ ) Let η=ηθη= _θ, g=St−1(x,⋅)g=S_ λ_t-1(x,·), πold=π^t(⋅|x) _old= π_t(·|x), πnew=πt(⋅|x) _new= _t(·|x), and π′=π^t+1(⋅|x)π = π_t+1(·|x) in corollary B.12, we have x∼[⟨π^t+1(⋅|x)−πt(⋅|x),St−1(x,⋅)⟩−β(KL(π^t+1(⋅|x)∥πref(⋅|x))−KL(πt(⋅|x)∥πref(⋅|x)))] _x [ π_t+1(·|x)- _t(·|x),S_ λ_t-1(x,·) -β (KL( π_t+1(·|x)\| _ref(·|x))-KL( _t(·|x)\| _ref(·|x)) ) ] (57) ≤x∼[ηθ(KL(π^t+1(⋅|x)∥π^t(⋅|x))−KL(π^t+1(⋅|x)∥πt(⋅|x))−KL(πt(⋅|x)∥π^t(⋅|x)))−βKL(π^t+1(⋅|x)∥πt(⋅|x))] _x [ _θ (KL( π_t+1(·|x)\| π_t(·|x))-KL( π_t+1(·|x)\| _t(·|x))-KL( _t(·|x)\| π_t(·|x)) )- ( π_t+1(·|x)\| _t(·|x)) ] +gap(εapprox,pmin) +gap( _approx,p_ ) =x∼[ηθKL(π^t+1(⋅|x)∥π^t(⋅|x))−(ηθ+β)KL(π^t+1(⋅|x)∥πt(⋅|x))−ηθKL(πt(⋅|x)∥π^t(⋅|x))] =E_x [ _θKL( π_t+1(·|x)\| π_t(·|x))-( _θ+β)KL( π_t+1(·|x)\| _t(·|x))- _θKL( _t(·|x)\| π_t(·|x)) ] +gap(εapprox,pmin). +gap( _approx,p_ ). Let C>0C>0 be a constant. For the last term in the RHS of eq. 55, we derive the upper bound as ⟨π^t+1(⋅|x)−πt(⋅|x),St(x,⋅)−St−1(x,⋅)⟩ π_t+1(·|x)- _t(·|x),S_ λ_t(x,·)-S_ λ_t-1(x,·) (58) =⟨π^t+1(⋅|x)−πt(⋅|x),∑j∈ℋ(λt,j−λt−1,j)Rj(x,⋅)⟩ = π_t+1(·|x)- _t(·|x), _j ( _t,j- _t-1,j)R_j(x,·) ≤(a)∥π^t+1(⋅|x)−πt(⋅|x)∥1∥∑j∈ℋ(λt,j−λt−1,j)Rj(x,⋅)∥∞ (a)≤\| π_t+1(·|x)- _t(·|x)\|_1 \| _j ( _t,j- _t-1,j)R_j(x,·) \|_∞ ≤(b)∥π^t+1(⋅|x)−πt(⋅|x)∥1∥t−t−1∥1Rmax (b)≤\| π_t+1(·|x)- _t(·|x)\|_1\| λ_t- λ_t-1\|_1R_ ≤2KL(π^t+1(⋅|x)∥πt(⋅|x))‖t−t−1‖1Rmax(By Pinsker’s inequality in lemma B.2) ≤ 2KL( π_t+1(·|x)\| _t(·|x))\| λ_t- λ_t-1\|_1R_ (By Pinsker's inequality in @crefcreftype~refnumlem:pinsker's ineq) ≤CKL(π^t+1(⋅|x)∥πt(⋅|x))+Rmax22C∥t−t−1∥12(By AM-GM inequality x22C+y2C2≥xy with C>0) ≤ CKL( π_t+1(·|x)\| _t(·|x))+ R_ ^22C\| λ_t- λ_t-1\|_1^2 (By AM-GM inequality $ x^22C+ y^2C2≥ xy$ with $C>0$) ≤CKL(π^t+1(⋅|x)∥πt(⋅|x))+|ℋ|Rmax22C∥t−t−1∥22(By ‖12≤d‖22, ∀∈ℝd) ≤ CKL( π_t+1(·|x)\| _t(·|x))+ |H|R_ ^22C\| λ_t- λ_t-1\|_2^2 (By $\| x\|_1^2≤ d\|x\|_2^2$, $ ^d$) ≤(c)CKL(π^t+1(⋅|x)∥πt(⋅|x))+|ℋ|Rmax2C(∥t−^t∥22+∥^t−t−1∥22), (c)≤CKL( π_t+1(·|x)\| _t(·|x))+ |H|R_ ^2C (\| λ_t- λ_t\|_2^2+\| λ_t- λ_t-1\|_2^2 ), where (a)(a) is by Hölder’s inequality shown in lemma B.1 and letting f(⋅)=π^t+1(⋅|x)−πt(⋅|x)f(·)= π_t+1(·|x)- _t(·|x), g(⋅)=∑j∈ℋ(λt,j−λt−1,j)Rj(x,⋅)g(·)= _j ( _t,j- _t-1,j)R_j(x,·), p=1p=1, and q=∞q=∞. (b)(b) is by ‖∑j∈ℋ(λt,j−λt−1,j)Rj(x,⋅)‖∞≤ \| _j ( _t,j- _t-1,j)R_j(x,·) \|_∞≤ ∑j∈ℋ‖(λt,j−λt−1,j)Rj(x,⋅)‖∞(by triangle inequality) _j \|( _t,j- _t-1,j)R_j(x,·) \|_∞ (by triangle inequality) = = ∑j∈ℋ|λt,j−λt−1,j|‖Rj(x,⋅)‖∞ _j | _t,j- _t-1,j| \|R_j(x,·) \|_∞ ≤ ≤ (∑j∈ℋ|λt,j−λt−1,j|)maxj⁡‖Rj(x,⋅)‖∞ ( _j | _t,j- _t-1,j| ) _j \|R_j(x,·) \|_∞ = = ‖t−t−1‖1maxj⁡‖Rj(x,⋅)‖∞(by definition of 1-norm) \| λ_t- λ_t-1\|_1 _j \|R_j(x,·) \|_∞ (by definition of 1-norm) ≤ ≤ ‖t−t−1‖1Rmax \| λ_t- λ_t-1\|_1R_ (by 3.2 that Rj(x,y)≤RmaxR_j(x,y)≤ R_ for any j∈∪ℋj and (x,y)(x,y) pair). (c)(c) is because ‖t−t−1‖22= \| λ_t- λ_t-1\|_2^2= ‖t−^t+^t−t−1‖22 \| λ_t- λ_t+ λ_t- λ_t-1\|_2^2 = = ‖t−^t‖22+‖^t−t−1‖22+2⟨t−^t,^t−t−1⟩ \| λ_t- λ_t\|_2^2+\| λ_t- λ_t-1\|_2^2+2 λ_t- λ_t, λ_t- λ_t-1 ≤ ≤ 2‖t−^t‖22+2‖^t−t−1‖22 2\| λ_t- λ_t\|_2^2+2\| λ_t- λ_t-1\|_2^2 (by Young’s inequality with p=q=2p=q=2, i.e., ⟨,⟩≤12(‖22+‖22) ,y ≤ 12(\|x\|_2^2+\|y\|_2^2)) Substituting eq. 56, eq. 57, and eq. 58 into the RHS of eq. 55, we have A≤ ≤ x∼[ηθKL(π⋆(⋅|x)∥π^t(⋅|x))−(ηθ+β)KL(π⋆(⋅|x)∥π^t+1(⋅|x))−ηθKL(π^t+1(⋅|x)∥π^t(⋅|x)) _x [ _θKL(π (·|x)\| π_t(·|x))-( _θ+β)KL(π (·|x)\| π_t+1(·|x))- _θKL( π_t+1(·|x)\| π_t(·|x)) . (59) +ηθKL(π^t+1(⋅|x)∥π^t(⋅|x))−(ηθ+β)KL(π^t+1(⋅|x)∥πt(⋅|x))−ηθKL(πt(⋅|x)∥π^t(⋅|x)) + _θKL( π_t+1(·|x)\| π_t(·|x))-( _θ+β)KL( π_t+1(·|x)\| _t(·|x))- _θKL( _t(·|x)\| π_t(·|x)) +CKL(π^t+1(⋅|x)∥πt(⋅|x))+|ℋ|Rmax2C(∥t−^t∥22+∥^t−t−1∥22)]+2gap(εapprox,pmin) .+CKL( π_t+1(·|x)\| _t(·|x))+ |H|R_ ^2C (\| λ_t- λ_t\|_2^2+\| λ_t- λ_t-1\|_2^2 ) ]+2gap( _approx,p_ ) = = x∼[ηθKL(π⋆(⋅|x)∥π^t(⋅|x))−(ηθ+β)KL(π⋆(⋅|x)∥π^t+1(⋅|x)) _x [ _θKL(π (·|x)\| π_t(·|x))-( _θ+β)KL(π (·|x)\| π_t+1(·|x)) . −(ηθ+β)KL(π^t+1(⋅|x)∥πt(⋅|x))−ηθKL(πt(⋅|x)∥π^t(⋅|x)) -( _θ+β)KL( π_t+1(·|x)\| _t(·|x))- _θKL( _t(·|x)\| π_t(·|x)) +CKL(π^t+1(⋅|x)∥πt(⋅|x))]+|ℋ|Rmax2C(∥t−^t∥22+∥^t−t−1∥22)+2gap(εapprox,pmin) .+CKL( π_t+1(·|x)\| _t(·|x)) ]+ |H|R_ ^2C (\| λ_t- λ_t\|_2^2+\| λ_t- λ_t-1\|_2^2 )+2gap( _approx,p_ ) E.2 Upper bound of term BB Similarly, we rewrite the term BB as B= = x∼[VStπt(x)−βKL(πt(⋅|x)∥πref(⋅|x))]−x∼[VS⋆πt(x)−βKL(πt(⋅|x)∥πref(⋅|x))]) _x [V _t_S_ λ_t(x)- ( _t(·|x)\| _ref(·|x)) ]-E_x [V _t_S_ λ (x)- ( _t(·|x)\| _ref(·|x)) ]) (60) = = x∼[VStπt(x)−VS⋆πt(x)] _x [V_S_ λ_t _t(x)-V_S_ λ _t(x) ] = = x∼[(VStπt(x)−VS^t+1πt(x))+(VS^t+1πt(x)−VS⋆πt(x)) _x [ (V_S_ λ_t _t(x)-V_S_ λ_t+1 _t(x) )+ (V_S_ λ_t+1 _t(x)-V_S_ λ _t(x) ) . −(VStπt−1(x)−VS^t+1πt−1(x))+(VStπt−1(x)−VS^t+1πt−1(x))] .- (V_S_ λ_t _t-1(x)-V_S_ λ_t+1 _t-1(x) )+ (V_S_ λ_t _t-1(x)-V_S_ λ_t+1 _t-1(x) ) ] Define Rℋ=[Rj1,Rj2,⋯,Rj|ℋ|]∈ℝ|ℋ|R_H= [R_j_1,R_j_2,·s,R_j_|H| ] ^|H|, where j1<j2<⋯<j|ℋ|j_1<j_2<·s<j_|H|, and jk∈ℋj_k for any integer 1≤k≤|ℋ|1≤ k≤|H|. Define VRℋπ(x)=y∼π(⋅|x)Rℋ(x,y)∈ℝ|ℋ|V_R_H^π(x)=E_y π(·|x)R_H(x,y) ^|H|. By the definition of VSλπ(x)V_S_λ^π(x), we have VSλπ(x)= V_S_λ^π(x)= y∼π(⋅|x)Sλ(x,y)(by definition of VSλπ(x)) _y π(·|x)S_λ(x,y) (by definition of $V_S_λ^π(x)$) = = y∼π(⋅|x)[∑j∈wjRj(x,y)+∑j∈ℋλjRj(x,y)](by definition of Sλ) _y π(·|x) [ _j w_jR_j(x,y)+ _j _jR_j(x,y) ] (by definition of $S_λ$) = = y∼π(⋅|x)[∑j∈wjRj(x,y))]+∑j∈ℋλjy∼π(⋅|x)[Rj(x,y)] _y π(·|x) [ _j w_jR_j(x,y)) ]+ _j _jE_y π(·|x) [R_j(x,y) ] = = y∼π(⋅|x)[∑j∈wjRj(x,y))]+λTVRℋπ(x)(by definition of VRℋπ) _y π(·|x) [ _j w_jR_j(x,y)) ]+λ^TV_R_H^π(x) (by definition of $V_R_ H^π$) Plugging the above expression of VSλπ(x)V_S_λ^π(x) into term BB, we have B= = x∼[(t−^t+1)TVRℋπt(x)+(^t+1−⋆)TVRℋπt(x)−(t−^t+1)TVRℋπt−1(x)+(t−^t+1)TVRℋπt−1(x)] _x [ ( λ_t- λ_t+1 )^TV_R_H _t(x)+ ( λ_t+1- λ )^TV_R_H _t(x)- ( λ_t- λ_t+1 )^TV_R_H _t-1(x)+ ( λ_t- λ_t+1 )^TV_R_H _t-1(x) ] (61) = = x∼[(^t+1−⋆)TVRℋπt(x)+(t−^t+1)TVRℋπt−1(x)+(t−^t+1)T(VRℋπt(x)−VRℋπt−1(x))] _x [ ( λ_t+1- λ )^TV_R_H _t(x)+ ( λ_t- λ_t+1 )^TV_R_H _t-1(x)+ ( λ_t- λ_t+1 )^T (V_R_H _t(x)-V_R_H _t-1(x) ) ] = = (^t+1−⋆)Tx∼[VRℋπt(x)]+(t−^t+1)Tx∼[VRℋπt−1(x)] ( λ_t+1- λ )^TE_x [V_R_H _t(x) ]+ ( λ_t- λ_t+1 )^TE_x [V_R_H _t-1(x) ] +(t−^t+1)T(x∼[VRℋπt(x)]−x∼[VRℋπt−1(x)]) + ( λ_t- λ_t+1 )^T (E_x [V_R_H _t(x) ]-E_x [V_R_H _t-1(x) ] ) Recall eq. 11 gives the λ^t+1,j λ_t+1,j in the optimistic gradient descent in the parameterized space, and we rewrite the update as follows λ^t+1,j=arg⁡minλ≥0⁡λx∼,y∼πt(⋅|x)[Rj(x,y)]+ηλ(λ−λ^t,j)2. λ_t+1,j= _λ≥ 0 _x ,y _t(·|x) [R_j(x,y) ]+ _λ (λ- λ_t,j )^2. Without loss of generality, for a vector a, we write ≥0a≥ 0 to indicate that all entries of a are nonnegative. Rewrite the above update in the vectorized form as follows ^t+1= λ_t+1= arg⁡min≥0⁡Tx∼[VRℋπt(x)]+ηλ‖−^t‖22 _ λ≥ 0 λ^TE_x [V_R_H _t(x) ]+ _λ\| λ- λ_t\|_2^2 = = arg⁡max≥0−Tx∼[VRℋπt(x)]−ηλ‖−^t‖22. _ λ≥ 0- λ^TE_x [V_R_H _t(x) ]- _λ\| λ- λ_t\|_2^2. Let g=−x∼[VRℋπt(x)]g=-E_x [V_R_H _t(x) ], η=ηλη= _λ, h()=‖22h(x)=\|x\|_2^2, Dh(,)=‖−‖22D_h(x,y)=\|x-y\|_2^2, ′=⋆x = λ , new=^t+1x_new= λ_t+1, old=^tx_old= λ_t, and Ω=ℝ+|ℋ| =R_+^|H| in lemma B.9, we have ⟨−x∼[VRℋπt(x)],^t+1−⋆⟩≥ηλ(−‖⋆−^t‖22+‖⋆−^t+1‖22+‖^t+1−^t‖22). -E_x [V_R_H _t(x) ], λ_t+1- λ ≥ _λ (-\| λ - λ_t\|_2^2+\| λ - λ_t+1\|_2^2+\| λ_t+1- λ_t\|_2^2 ). Putting negative sign on both sides, we have ⟨^t+1−⋆,x∼[VRℋπt(x)]⟩≤ηλ(‖⋆−^t‖22−‖⋆−^t+1‖22−‖^t+1−^t‖22). λ_t+1- λ ,E_x [V_R_H _t(x) ] ≤ _λ (\| λ - λ_t\|_2^2-\| λ - λ_t+1\|_2^2-\| λ_t+1- λ_t\|_2^2 ). (62) Similarly, since eq. 9 gives the optimistic update of λt,j _t,j as follows, λt,j=arg⁡minλ≥0⁡λx∼,y∼πt−1(⋅|x)[Rj(x,y)]+ηλ(λ−λ^t,j)2, _t,j= _λ≥ 0 _x ,y _t-1(·|x) [R_j(x,y) ]+ _λ (λ- λ_t,j )^2, Applying lemma B.9 by setting g=−x∼[VRℋπt−1(x)]g=-E_x [V_R_H _t-1(x) ], η=ηλη= _λ, h()=‖22h(x)=\|x\|_2^2, Dh(,)=‖−‖22D_h(x,y)=\|x-y\|_2^2, ′=^t+1x = λ_t+1, new=tx_new= λ_t, old=^tx_old= λ_t, and Ω=ℝ+|ℋ| =R_+^|H|, we have ⟨t−^t+1,x∼[VRℋπt−1(x)]⟩≤ηλ(‖^t+1−^t‖22−‖^t+1−t‖22−‖t−^t‖22). λ_t- λ_t+1,E_x [V_R_H _t-1(x) ] ≤ _λ (\| λ_t+1- λ_t\|_2^2-\| λ_t+1- λ_t\|_2^2-\| λ_t- λ_t\|_2^2 ). (63) We upper bound the last term of BB as (t−^t+1)T(x∼[VRℋπt(x)]−x∼[VRℋπt−1(x)]) ( λ_t- λ_t+1 )^T (E_x [V_R_H _t(x) ]-E_x [V_R_H _t-1(x) ] ) =x∼[(t−^t+1)T(VRℋπt(x)−VRℋπt−1(x))] =E_x [ ( λ_t- λ_t+1 )^T (V_R_H _t(x)-V_R_H _t-1(x) ) ] =x∼[(t−^t+1)T(⟨πt(⋅|x),Rℋ(x,⋅)⟩−⟨πt−1(⋅|x),Rℋ(x,⋅)⟩)] =E_x [ ( λ_t- λ_t+1 )^T ( _t(·|x),R_H(x,·) - _t-1(·|x),R_H(x,·) ) ] (by VRℋπ(x)=y∼π(⋅|x)[Rℋ(x,y)]=⟨π(⋅|x),Rℋ(x,⋅)⟩V_R_H^π(x)=E_y π(·|x) [R_H(x,y) ]= π(·|x),R_H(x,·) ) =x∼[⟨πt(⋅|x)−πt−1(⋅|x),(t−^t+1)TRℋ(x,⋅)⟩] =E_x [ _t(·|x)- _t-1(·|x), ( λ_t- λ_t+1 )^TR_H(x,·) ] =x∼[⟨πt(⋅|x)−πt−1(⋅|x),∑j∈ℋ(λt,j−λ^t+1,j)Rj(x,⋅)⟩] =E_x [ _t(·|x)- _t-1(·|x), _j ( _t,j- λ_t+1,j)R_j(x,·) ] Define constants C1>0C_1>0 and C2>0C_2>0. Fixing x, we have ⟨πt(⋅|x)−πt−1(⋅|x),∑j∈ℋ(λt,j−λ^t+1,j)Rj(x,⋅)⟩ _t(·|x)- _t-1(·|x), _j ( _t,j- λ_t+1,j)R_j(x,·) =⟨πt(⋅|x)−π^t(⋅|x),∑j∈ℋ(λt,j−λ^t+1,j)Rj(x,⋅)⟩+⟨π^t(⋅|x)−πt−1(⋅|x),∑j∈ℋ(λt,j−λ^t+1,j)Rj(x,⋅)⟩ = _t(·|x)- π_t(·|x), _j ( _t,j- λ_t+1,j)R_j(x,·) + π_t(·|x)- _t-1(·|x), _j ( _t,j- λ_t+1,j)R_j(x,·) ≤C1KL(πt(⋅|x)∥π^t(⋅|x))+|ℋ|Rmax22C1∥t−^t+1∥22+C2KL(π^t(⋅|x)∥πt−1(⋅|x))+|ℋ|Rmax22C2∥t−^t+1∥22 ≤ C_1KL( _t(·|x)\| π_t(·|x))+ |H|R_ ^22C_1\| λ_t- λ_t+1\|_2^2+C_2KL( π_t(·|x)\| _t-1(·|x))+ |H|R_ ^22C_2\| λ_t- λ_t+1\|_2^2 (By derivations of eq. 58) =C1KL(πt(⋅|x)∥π^t(⋅|x))+C2KL(π^t(⋅|x)∥πt−1(⋅|x))+|ℋ|Rmax2(12C1+12C2)∥t−^t+1∥22 =C_1KL( _t(·|x)\| π_t(·|x))+C_2KL( π_t(·|x)\| _t-1(·|x))+|H|R_ ^2 ( 12C_1+ 12C_2 )\| λ_t- λ_t+1\|_2^2 Substituting the above inequality into (t−^t+1)T(x∼[VRℋπt(x)]−x∼[VRℋπt−1(x)]) ( λ_t- λ_t+1 )^T (E_x [V_R_H _t(x) ]-E_x [V_R_H _t-1(x) ] ), we have (t−^t+1)T(x∼[VRℋπt(x)]−x∼[VRℋπt−1(x)]) ( λ_t- λ_t+1 )^T (E_x [V_R_H _t(x) ]-E_x [V_R_H _t-1(x) ] ) (64) =x∼[C1KL(πt(⋅|x)∥π^t(⋅|x))+C2KL(π^t(⋅|x)∥πt−1(⋅|x))]+|ℋ|Rmax2(12C1+12C2)∥t−^t+1∥22 =E_x [C_1KL( _t(·|x)\| π_t(·|x))+C_2KL( π_t(·|x)\| _t-1(·|x)) ]+|H|R_ ^2 ( 12C_1+ 12C_2 )\| λ_t- λ_t+1\|_2^2 Combining eq. 62, eq. 63, and eq. 64, we can upper bound BB as B≤ ≤ ηλ(‖⋆−^t‖22−‖⋆−^t+1‖22−‖^t+1−^t‖22)+ηλ(‖^t+1−^t‖22−‖^t+1−t‖22−‖t−^t‖22) _λ (\| λ - λ_t\|_2^2-\| λ - λ_t+1\|_2^2-\| λ_t+1- λ_t\|_2^2 )+ _λ (\| λ_t+1- λ_t\|_2^2-\| λ_t+1- λ_t\|_2^2-\| λ_t- λ_t\|_2^2 ) (65) +x∼[C1KL(πt(⋅|x)∥π^t(⋅|x))+C2KL(π^t(⋅|x)∥πt−1(⋅|x))]+|ℋ|Rmax2(12C1+12C2)∥t−^t+1∥22 +E_x [C_1KL( _t(·|x)\| π_t(·|x))+C_2KL( π_t(·|x)\| _t-1(·|x)) ]+|H|R_ ^2 ( 12C_1+ 12C_2 )\| λ_t- λ_t+1\|_2^2 = = ηλ(‖⋆−^t‖22−‖⋆−^t+1‖22−‖t−^t+1‖22−‖t−^t‖22) _λ (\| λ - λ_t\|_2^2-\| λ - λ_t+1\|_2^2-\| λ_t- λ_t+1\|_2^2-\| λ_t- λ_t\|_2^2 ) +x∼[C1KL(πt(⋅|x)∥π^t(⋅|x))+C2KL(π^t(⋅|x)∥πt−1(⋅|x))]+|ℋ|Rmax2(12C1+12C2)∥t−^t+1∥22 +E_x [C_1KL( _t(·|x)\| π_t(·|x))+C_2KL( π_t(·|x)\| _t-1(·|x)) ]+|H|R_ ^2 ( 12C_1+ 12C_2 )\| λ_t- λ_t+1\|_2^2 E.3 Combining AA and BB Substituting eq. 59 and eq. 65 into the RHS of eq. 54, we get L(π⋆,t)−L(πt,⋆) L(π , λ_t)-L( _t, λ ) ≤x∼[ηθKL(π⋆(⋅|x)∥π^t(⋅|x))−(ηθ+β)KL(π⋆(⋅|x)∥π^t+1(⋅|x))−(ηθ+β)KL(π^t+1(⋅|x)∥πt(⋅|x)) _x [ _θKL(π (·|x)\| π_t(·|x))-( _θ+β)KL(π (·|x)\| π_t+1(·|x)) [rgb]1,0,0-( _θ+β)KL( π_t+1(·|x)\| _t(·|x)) . −ηθKL(πt(⋅|x)∥π^t(⋅|x))+CKL(π^t+1(⋅|x)∥πt(⋅|x))]+2gap(εapprox,pmin) . [rgb]0,0,1- _θKL( _t(·|x)\| π_t(·|x)) [rgb]1,0,0+CKL( π_t+1(·|x)\| _t(·|x)) ]+2gap( _approx,p_ ) +|ℋ|Rmax2C(‖t−^t‖22+‖^t−t−1‖22)+ηλ(‖⋆−^t‖22−‖⋆−^t+1‖22−‖t−^t+1‖22−‖t−^t‖22) + |H|R_ ^2C ( [rgb]1,0,1\| λ_t- λ_t\|_2^2+\| λ_t- λ_t-1\|_2^2 )+ _λ (\| λ - λ_t\|_2^2-\| λ - λ_t+1\|_2^2 [rgb]0,1,1-\| λ_t- λ_t+1\|_2^2- [rgb]1,0,1\| λ_t- λ_t\|_2^2 ) +x∼[C1KL(πt(⋅|x)∥π^t(⋅|x))+C2KL(π^t(⋅|x)∥πt−1(⋅|x))]+|ℋ|Rmax2(12C1+12C2)∥t−^t+1∥22 +E_x [ [rgb]0,0,1C_1KL( _t(·|x)\| π_t(·|x))+C_2KL( π_t(·|x)\| _t-1(·|x)) ]+ [rgb]0,1,1|H|R_ ^2 ( 12C_1+ 12C_2 )\| λ_t- λ_t+1\|_2^2 ≤x∼[ηθKL(π⋆(⋅|x)∥π^t(⋅|x))−(ηθ+β)KL(π⋆(⋅|x)∥π^t+1(⋅|x))−(ηθ+β−C)KL(π^t+1(⋅|x)∥πt(⋅|x)) _x [ _θKL(π (·|x)\| π_t(·|x))-( _θ+β)KL(π (·|x)\| π_t+1(·|x))-( _θ+β-C)KL( π_t+1(·|x)\| _t(·|x)) . −(ηθ−C1)KL(πt(⋅|x)∥π^t(⋅|x))+C2KL(π^t(⋅|x)∥πt−1(⋅|x))] .- ( _θ-C_1 )KL( _t(·|x)\| π_t(·|x))+C_2KL( π_t(·|x)\| _t-1(·|x)) ] −(ηλ−|ℋ|Rmax2C)‖t−^t‖22+|ℋ|Rmax2C‖^t−t−1‖22+ηλ‖⋆−^t‖22−ηλ‖⋆−^t+1‖22 - ( _λ- |H|R_ ^2C )\| λ_t- λ_t\|_2^2+ |H|R_ ^2C\| λ_t- λ_t-1\|_2^2+ _λ\| λ - λ_t\|_2^2- _λ\| λ - λ_t+1\|_2^2 −(ηλ−|ℋ|Rmax2(12C1+12C2))‖t−^t+1‖22+2gap(εapprox,pmin), - ( _λ-|H|R_ ^2 ( 12C_1+ 12C_2 ) )\| λ_t- λ_t+1\|_2^2+2gap( _approx,p_ ), where terms of the same color can be combined. Recall eq. 53 that L(π⋆,t)−L(πt,⋆)≥0L(π , λ_t)-L( _t, λ )≥ 0. Substituting this into the above equation and rearranging the equation, we have (ηθ+β)x∼[KL(π⋆(⋅|x)∥π^t+1(⋅|x))]+(ηθ+β−C)x∼[KL(π^t+1(⋅|x)∥πt(⋅|x))] ( _θ+β)E_x [KL(π (·|x)\| π_t+1(·|x)) ]+( _θ+β-C)E_x [KL( π_t+1(·|x)\| _t(·|x)) ] (66) +ηλ‖⋆−^t+1‖22+(ηλ−|ℋ|Rmax2(12C1+12C2))‖t−^t+1‖22 + _λ\| λ - λ_t+1\|_2^2+ ( _λ-|H|R_ ^2 ( 12C_1+ 12C_2 ) )\| λ_t- λ_t+1\|_2^2 ≤ηθx∼[KL(π⋆(⋅|x)∥π^t(⋅|x))]+C2x∼[KL(π^t(⋅|x)∥πt−1(⋅|x))]+ηλ∥⋆−^t∥22+|ℋ|Rmax2C∥^t−t−1∥22 ≤ _θE_x [KL(π (·|x)\| π_t(·|x)) ]+C_2E_x [KL( π_t(·|x)\| _t-1(·|x)) ]+ _λ\| λ - λ_t\|_2^2+ |H|R_ ^2C\| λ_t- λ_t-1\|_2^2 −(ηθ−C1)x∼[KL(πt(⋅|x)∥π^t(⋅|x))]−(ηλ−|ℋ|Rmax2C)∥t−^t∥22+2gap(εapprox,pmin) - ( _θ-C_1 )E_x [KL( _t(·|x)\| π_t(·|x)) ]- ( _λ- |H|R_ ^2C )\| λ_t- λ_t\|_2^2+2gap( _approx,p_ ) Note that for any δ,θ>0δ,θ>0, we have ‖t−^t‖2 \| λ_t- λ_t\|^2 =‖(t−^t+1)+(^t+1−⋆)+(⋆−^t)‖2 = \| ( λ_t- λ_t+1 )+ ( λ_t+1- λ )+ ( λ - λ_t ) \|^2 (67) ≥(1−δ)‖^t+1−⋆‖2+(1−1δ)(1−θ)‖t−^t+1‖2+(1−1δ)(1−1θ)‖⋆−^t‖2(by lemma B.4). ≥(1-δ)\| λ_t+1- λ \|^2+(1- 1δ)(1-θ)\| λ_t- λ_t+1\|^2+(1- 1δ)(1- 1θ)\| λ - λ_t\|^2 (by @crefcreftype~refnumlem:||a+b+c||_2^2_lower_bd). We set ηλ>|ℋ|Rmax2C _λ> |H|R_ ^2C. Substituting eq. 67 into the last term of the RHS of eq. 66 to get (ηθ+β)x∼[KL(π⋆(⋅|x)∥π^t+1(⋅|x))]+(ηθ+β−C)x∼[KL(π^t+1(⋅|x)∥πt(⋅|x))] ( _θ+β)E_x [KL(π (·|x)\| π_t+1(·|x)) ]+( _θ+β-C)E_x [KL( π_t+1(·|x)\| _t(·|x)) ] +ηλ‖⋆−^t+1‖22+(ηλ−|ℋ|Rmax2(12C1+12C2))‖t−^t+1‖22 [rgb]1,0,0+ _λ\| λ - λ_t+1\|_2^2+ [rgb]0,0,1 ( _λ-|H|R_ ^2 ( 12C_1+ 12C_2 ) )\| λ_t- λ_t+1\|_2^2 ≤ηθx∼[KL(π⋆(⋅|x)∥π^t(⋅|x))]+C2x∼[KL(π^t(⋅|x)∥πt−1(⋅|x))]+ηλ∥⋆−^t∥22+|ℋ|Rmax2C∥^t−t−1∥22 ≤ _θE_x [KL(π (·|x)\| π_t(·|x)) ]+C_2E_x [KL( π_t(·|x)\| _t-1(·|x)) ]+ [rgb]0,1,1 _λ\| λ - λ_t\|_2^2+ |H|R_ ^2C\| λ_t- λ_t-1\|_2^2 −(ηθ−C1)x∼[KL(πt(⋅|x)∥π^t(⋅|x))]−(ηλ−|ℋ|Rmax2C)(1−δ)∥^t+1−⋆∥2 - ( _θ-C_1 )E_x [KL( _t(·|x)\| π_t(·|x)) ] [rgb]1,0,0- ( _λ- |H|R_ ^2C )(1-δ)\| λ_t+1- λ \|^2 −(ηλ−|ℋ|Rmax2C)(1−1δ)(1−θ)‖t−^t+1‖2−(ηλ−|ℋ|Rmax2C)(1−1δ)(1−1θ)‖⋆−^t‖2 [rgb]0,0,1- ( _λ- |H|R_ ^2C )(1- 1δ)(1-θ)\| λ_t- λ_t+1\|^2 [rgb]0,1,1- ( _λ- |H|R_ ^2C )(1- 1δ)(1- 1θ)\| λ - λ_t\|^2 +2gap(εapprox,pmin), +2gap( _approx,p_ ), where terms of the same color can be combined. Rearranging the above equation, we have (ηθ+β)x∼[KL(π⋆(⋅|x)∥π^t+1(⋅|x))]+(ηθ+β−C)x∼[KL(π^t+1(⋅|x)∥πt(⋅|x))] ( _θ+β)E_x [KL(π (·|x)\| π_t+1(·|x)) ]+( _θ+β-C)E_x [KL( π_t+1(·|x)\| _t(·|x)) ] (68) +(ηλ+(ηλ−|ℋ|Rmax2C)(1−δ))‖⋆−^t+1‖22 + ( _λ+ ( _λ- |H|R_ ^2C )(1-δ) )\| λ - λ_t+1\|_2^2 +(ηλ−|ℋ|Rmax2(12C1+12C2)+(ηλ−|ℋ|Rmax2C)(1−1δ)(1−θ))‖^t+1−t‖22 + ( _λ-|H|R_ ^2 ( 12C_1+ 12C_2 )+ ( _λ- |H|R_ ^2C )(1- 1δ)(1-θ) )\| λ_t+1- λ_t\|_2^2 ≤ηθx∼[KL(π⋆(⋅|x)∥π^t(⋅|x))]+C2x∼[KL(π^t(⋅|x)∥πt−1(⋅|x))] ≤ _θE_x [KL(π (·|x)\| π_t(·|x)) ]+C_2E_x [KL( π_t(·|x)\| _t-1(·|x)) ] +(ηλ−(ηλ−|ℋ|Rmax2C)(1−1δ)(1−1θ))‖⋆−^t‖22 + ( _λ- ( _λ- |H|R_ ^2C )(1- 1δ)(1- 1θ) )\| λ - λ_t\|_2^2 +|ℋ|Rmax2C∥^t−t−1∥22−(ηθ−C1)x∼[KL(πt(⋅|x)∥π^t(⋅|x))]+2gap(εapprox,pmin) + |H|R_ ^2C\| λ_t- λ_t-1\|_2^2- ( _θ-C_1 )E_x [KL( _t(·|x)\| π_t(·|x)) ]+2gap( _approx,p_ ) Note the RHS of eq. 68 can be written as ηθηθ+β(ηθ+β)x∼[KL(π⋆(⋅|x)∥π^t(⋅|x))]+C2ηθ+β−C(ηθ+β−C)x∼[KL(π^t(⋅|x)∥πt−1(⋅|x))] _θ _θ+β( _θ+β)E_x [KL(π (·|x)\| π_t(·|x)) ]+ C_2 _θ+β-C( _θ+β-C)E_x [KL( π_t(·|x)\| _t-1(·|x)) ] +ηλ−(ηλ−|ℋ|Rmax2C)(1−1δ)(1−1θ)ηλ+(ηλ−|ℋ|Rmax2C)(1−δ)(ηλ+(ηλ−|ℋ|Rmax2C)(1−δ))‖⋆−^t‖22 + _λ- ( _λ- |H|R_ ^2C )(1- 1δ)(1- 1θ) _λ+ ( _λ- |H|R_ ^2C )(1-δ) ( _λ+ ( _λ- |H|R_ ^2C )(1-δ) )\| λ - λ_t\|_2^2 +|ℋ|Rmax2Cηλ−|ℋ|Rmax2(12C1+12C2)+(ηλ−|ℋ|Rmax2C)(1−1δ)(1−θ)× + |H|R_ ^2C _λ-|H|R_ ^2 ( 12C_1+ 12C_2 )+ ( _λ- |H|R_ ^2C )(1- 1δ)(1-θ)× (ηλ−|ℋ|Rmax2(12C1+12C2)+(ηλ−|ℋ|Rmax2C)(1−1δ)(1−θ))‖^t−t−1‖22 ( _λ-|H|R_ ^2 ( 12C_1+ 12C_2 )+ ( _λ- |H|R_ ^2C )(1- 1δ)(1-θ) )\| λ_t- λ_t-1\|_2^2 −(ηθ−C1)x∼[KL(πt(⋅|x)∥π^t(⋅|x))]+2gap(εapprox,pmin) - ( _θ-C_1 )E_x [KL( _t(·|x)\| π_t(·|x)) ]+2gap( _approx,p_ ) Define Φt _t as the LHS of eq. 68, i.e., Φt+1:= _t+1= (ηθ+β)x∼[KL(π⋆(⋅|x)∥π^t+1(⋅|x))]+(ηθ+β−C)x∼[KL(π^t+1(⋅|x)∥πt(⋅|x))] ( _θ+β)E_x [KL(π (·|x)\| π_t+1(·|x)) ]+( _θ+β-C)E_x [KL( π_t+1(·|x)\| _t(·|x)) ] +(ηλ+(ηλ−|ℋ|Rmax2C)(1−δ))‖⋆−^t+1‖22 + ( _λ+ ( _λ- |H|R_ ^2C )(1-δ) )\| λ - λ_t+1\|_2^2 +(ηλ−|ℋ|Rmax2(12C1+12C2)+(ηλ−|ℋ|Rmax2C)(1−1δ)(1−θ))‖^t+1−t‖22 + ( _λ-|H|R_ ^2 ( 12C_1+ 12C_2 )+ ( _λ- |H|R_ ^2C )(1- 1δ)(1-θ) )\| λ_t+1- λ_t\|_2^2 If the following requirements are satisfied: 1. Multipliers of all terms of LHS of eq. 68 are positive: ηθ+β>0, _θ+β>0, ηθ+β−C>0, _θ+β-C>0, ηλ+(ηλ−|ℋ|Rmax2C)(1−δ)>0, _λ+ ( _λ- |H|R_ ^2C )(1-δ)>0, ηλ−|ℋ|Rmax2(12C1+12C2)+(ηλ−|ℋ|Rmax2C)(1−1δ)(1−θ)>0. _λ-|H|R_ ^2 ( 12C_1+ 12C_2 )+ ( _λ- |H|R_ ^2C )(1- 1δ)(1-θ)>0. 2. Multipliers of all terms of RHS of eq. 68 are positive: ηθ>0, _θ>0, C2>0, C_2>0, ηλ−(ηλ−|ℋ|Rmax2C)(1−1δ)(1−1θ)>0, _λ- ( _λ- |H|R_ ^2C )(1- 1δ)(1- 1θ)>0, |ℋ|Rmax2C>0, |H|R_ ^2C>0, ηθ−C1>0. _θ-C_1>0. 3. Define ρ:= ρ= max(ηθηθ+β,C2ηθ+β−C,ηλ−(ηλ−|ℋ|Rmax2C)(1−1δ)(1−1θ)ηλ+(ηλ−|ℋ|Rmax2C)(1−δ), ( _θ _θ+β, C_2 _θ+β-C, _λ- ( _λ- |H|R_ ^2C )(1- 1δ)(1- 1θ) _λ+ ( _λ- |H|R_ ^2C )(1-δ), . |ℋ|Rmax2Cηλ−|ℋ|Rmax2(12C1+12C2)+(ηλ−|ℋ|Rmax2C)(1−1δ)(1−θ)), . |H|R_ ^2C _λ-|H|R_ ^2 ( 12C_1+ 12C_2 )+ ( _λ- |H|R_ ^2C )(1- 1δ)(1-θ) ), then ρ<1ρ<1. Then eq. 68 can be written as Φt+1≤ _t+1≤ ρΦt−(ηθ−C1)x∼[KL(πt(⋅|x)∥π^t(⋅|x))]+2gap(εapprox,pmin)(by the definition of ρ) ρ _t- ( _θ-C_1 )E_x [KL( _t(·|x)\| π_t(·|x)) ]+2gap( _approx,p_ ) (by the definition of $ρ$) ≤ ≤ ρΦt+2gap(εapprox,pmin)(by η−C1>0 and x∼[KL(πt(⋅|x)∥π^t(⋅|x))]>0) ρ _t+2gap( _approx,p_ ) (by $η-C_1>0$ and $E_x [KL( _t(·|x)\| π_t(·|x)) ]>0$) Iteratively apply the recursion, we have Φt≤ρtΦ1 _t≤ρ^t _1, where Φ1= _1= (ηθ+β)x∼[KL(π⋆(⋅|x)∥π^1(⋅|x))]+(ηθ+β−C)x∼[KL(π^1(⋅|x)∥π0(⋅|x))] ( _θ+β)E_x [KL(π (·|x)\| π_1(·|x)) ]+( _θ+β-C)E_x [KL( π_1(·|x)\| _0(·|x)) ] +(ηλ+(ηλ−|ℋ|Rmax2C)(1−δ))‖⋆−^1‖22 + ( _λ+ ( _λ- |H|R_ ^2C )(1-δ) )\| λ - λ_1\|_2^2 +(ηλ−|ℋ|Rmax2(12C1+12C2)+(ηλ−|ℋ|Rmax2C)(1−1δ)(1−θ))‖^1−0‖22. + ( _λ-|H|R_ ^2 ( 12C_1+ 12C_2 )+ ( _λ- |H|R_ ^2C )(1- 1δ)(1-θ) )\| λ_1- λ_0\|_2^2. Note that we initialize π^0 π_0 having the same support set as πref _ref. Since we use a softmax parameterization over a finite action space, all policies have full support. Hence, the KL terms in Φ1 _1 are finite and Φ1 _1 is bounded. Furthermore, we have x∼[KL(π⋆(⋅|x)∥π^t(⋅|x))]+∥⋆−^t∥22≤ρtΦ1ρmin⁡(ηθ+β,ηλ+(ηλ−|ℋ|Rmax2C)(1−δ))+2(1−ρt)gap1−ρ _x [KL(π (·|x)\| π_t(·|x)) ]+\| λ - λ_t\|_2^2≤ρ^t _1ρ ( _θ+β, _λ+ ( _λ- |H|R_ ^2C )(1-δ) ) [rgb].75,0,.25+ 2(1-ρ^t)gap1-ρ and this shows the desired result. Hyperparameters and Constants Selection Our next step is to choose hyperparameters ηθ _θ and ηλ _λ as well as constants C1C_1, C2C_2, and C to satisfy the requirements. For simplicity, with a little abuse of notations, we denote h=|ℋ|h=|H| and R=RmaxR=R_ in this parameter and constants selection section. Let ηθ=ηλ=η=3hR,C1=C2=C=hR,12<δ<1,12<θ<1. _θ= _λ=η=3 hR, C_1=C_2=C= hR, 12<δ<1, 12<θ<1. We will verify that this set of parameters satisfies the requirements. 0. Verification of ηλ>|ℋ|Rmax2C _λ> |H|R_ ^2C. ηλ=3hR≥hR=hR2hR=hR2C _λ=3 hR≥ hR= hR^2 hR= hR^2C. 1. Verifications that multipliers of all terms of LHS of eq. 68 are positive. (1) Since ηθ>0 _θ>0 and β>0β>0, we have ηθ+β>0 _θ+β>0. (2) ηθ+β−C=β+2hR>0 _θ+β-C=β+2 hR>0. (3) Since ηλ−hR2/C=3hR−hR2/(hR)=2hR>0 _λ-hR^2/C=3 hR-hR^2/( hR)=2 hR>0 and δ<1δ<1, we have (ηλ−hR2/C)(1−δ)>0 ( _λ-hR^2/C )(1-δ)>0. Hence ηλ+(ηλ−hR2/C)(1−δ)>0 _λ+ ( _λ-hR^2/C )(1-δ)>0. (4) ηλ−hR2(1/(2C1)+1/(2C2))+(ηλ−hR2/C)(1−1/δ)(1−θ)=3hR−hR2/(hR)+(2hR−hR2/(hR))(1−1/δ)(1−θ)=hR(2+(1−1/δ)(1−θ)) _λ-hR^2 (1/(2C_1)+1/(2C_2) )+ ( _λ-hR^2/C )(1-1/δ)(1-θ)=3 hR-hR^2/( hR)+(2 hR-hR^2/( hR))(1-1/δ)(1-θ)= hR (2+ (1-1/δ ) (1-θ ) ). Since 1/2<δ,θ<11/2<δ,θ<1, we have −1<1−1/δ<0-1<1-1/δ<0 and 0<1−θ<1/20<1-θ<1/2, hence −1/2<(1−1/δ)(1−θ)<0-1/2< (1-1/δ ) (1-θ )<0. Therefore, 2+(1−1/δ)(1−θ)>02+ (1-1/δ ) (1-θ )>0. 2. Verifications that the multipliers of all terms of the RHS of eq. 68 are positive. (1) ηθ>0 _θ>0 by the definition of ηθ _θ. (2) C2>0C_2>0 by the definition of C2C_2. (3) ηλ−(ηλ−hR2/C)(1−1/δ)(1−1/θ)=3hR−(3hR−hR2/(hR)(1−1/δ)(1−1/θ)=hR(3−2(1−1/δ)(1−1/θ)) _λ- ( _λ-hR^2/C )(1-1/δ)(1-1/θ)=3 hR-(3 hR-hR^2/( hR)(1-1/δ)(1-1/θ)= hR(3-2(1-1/δ)(1-1/θ)). Since 1/2<δ,θ<11/2<δ,θ<1, we have −1<1−1/θ<0-1<1-1/θ<0 and −1<1−1/δ<0-1<1-1/δ<0, hence 0<(1−1/θ)(1−1/δ)<10<(1-1/θ)(1-1/δ)<1. Therefore, we get 3−2(1−1/δ)(1−1/θ)>03-2(1-1/δ)(1-1/θ)>0. (4) As hR2>0hR^2>0 and C=hR>0C= hR>0, we have hR2/C>0hR^2/C>0. (5) ηθ−C1=3hR−hR=2hR>0 _θ-C_1=3 hR- hR=2 hR>0. 3. (1) Since ηθ>0 _θ>0 and β>0β>0, we have ηθηθ+β<1 _θ _θ+β<1. (2) We have C2/(ηθ+β−C)=hR/(3hR−β−hR)<hR/(3hR−hR)=1/2C_2/( _θ+β-C)= hR/(3 hR-β- hR)< hR/(3 hR- hR)=1/2, where the inequality is because β>0β>0. (3) Since ηλ−hR2/C=3hR−hR2/(hR)=2hR>0 _λ-hR^2/C=3 hR-hR^2/( hR)=2 hR>0, (1−1/δ)(1−1/θ)>0(1-1/δ)(1-1/θ)>0, and 1−δ>01-δ>0, we have (ηλ−hR2/C)(1−1/δ)(1−1/θ)>0 ( _λ-hR^2/C )(1-1/δ)(1-1/θ)>0 and (ηλ−hR2/C)(1−δ)>0 ( _λ-hR^2/C )(1-δ)>0, hence ηλ−(ηλ−hR2/C)(1−1/δ)(1−1/θ)<ηλ+(ηλ−hR2/C)(1−δ) _λ- ( _λ-hR^2/C )(1-1/δ)(1-1/θ)< _λ+ ( _λ-hR^2/C )(1-δ), and (ηλ−(ηλ−hR2/C)(1−1/δ)(1−1/θ))/(ηλ+(ηλ−hR2/C)(1−δ))<1( _λ- ( _λ-hR^2/C )(1-1/δ)(1-1/θ))/( _λ+ ( _λ-hR^2/C )(1-δ))<1. (4)Plugging the parameters values into the last requirement, we have hR2/Cηλ−hR2(1/2C1+1/2C2)+(ηλ−hR2/C)(1−1/δ)(1−θ) hR^2/C _λ-hR^2 (1/2C_1+1/2C_2 )+( _λ-hR^2/C)(1-1/δ)(1-θ) =hR2hR+2hR(1−1/δ)(1−θ) = hR2 hR+2 hR(1-1/δ)(1-θ) =12+2(1−1/δ)(1−θ). = 12+2(1-1/δ)(1-θ). As 1/2<θ,δ<11/2<θ,δ<1, −1/2<(1−1/δ)(1−θ)<0-1/2<(1-1/δ)(1-θ)<0. Therefore 1<2+2(1−1/δ)(1−θ)<21<2+2(1-1/δ)(1-θ)<2 and 1/2+2(1−1/δ)(1−θ)<11/2+2(1-1/δ)(1-θ)<1. If we further set δ=θ=34δ=θ= 34, then we can write ρ and Φ1 _1 as ρ=max⁡(3ℋRmax3ℋRmax+β,ℋRmax2ℋRmax+β,5063),ρ= ( 3 HR_ 3 HR_ +β, HR_ 2 HR_ +β, 5063 ), (69) Φ1= _1= (3ℋRmax+β)x∼[KL(π⋆(⋅|x)∥π^1(⋅|x))]+(2ℋRmax+β)x∼[KL(π^1(⋅|x)∥π0(⋅|x))] (3 HR_ +β)E_x [KL(π (·|x)\| π_1(·|x)) ]+(2 HR_ +β)E_x [KL( π_1(·|x)\| _0(·|x)) ] (70) +72ℋRmax‖⋆−^1‖22+116ℋRmax‖^1−0‖22. + 72 HR_ \| λ - λ_1\|_2^2+ 116 HR_ \| λ_1- λ_0\|_2^2.

Instant research discovery