On the Convergence of Success Conditioning for Policy Optimization

On the Convergence of Success Conditioning for Policy Optimization Matthew Brun∗

Xu Andy Sun†

arXiv:2610.03642v1 [cs.LG] 2 Oct 2026

Abstract Success conditioning is a strategy for improving decision-making policies in stochastic environments; it updates a policy by increasing the probability of taking actions that yield successful outcomes. Success conditioning is common to many reinforcement learning applications, yet its limiting behavior and convergence rates are not well understood. In this work, we demonstrate that success conditioning converges to an optimal policy on a broad class of Markov decision processes (MDPs). We also derive convergence rates in some common settings. For discounted MDPs, we prove convergence within O(1/εp ) iterations to an ε-optimal policy, where the exponent p depends on problem data. For single-period MDPs, such a policy is obtained within O(log(1/ε)) iterations.

1

Introduction

Success conditioning (SC) is an update rule for policies in stochastic sequential decision-making processes. SC improves a randomized policy by increasing the probability of taking actions that yield high rewards and decreasing the probability of taking those which are not fruitful. When outcomes of the process are labeled as successes and failures, the policy update mimics the distribution of actions which yield successful outcomes. SC and related strategies appear across modern artificial intelligence (AI) contexts, especially in machine learning and reinforcement learning [1, 2]. Rejection sampling fine-tuning refines generative models by sampling outputs, discarding those with low-quality, and continuing to train on the best responses [3]. Posttraining pipelines for large language models apply this strategy [4], and similar concepts are embedded directly in the training process via reinforcement learning [5]. Models for robot control have been trained on successful trajectories from other robots [6] and can autonomously fine-tune on successful outcomes from practice sessions [7]. In reinforcement learning, decision transformers learn to predict actions as a function of downstream rewards, then identify high-quality actions by conditioning on large returns [8]. The SC update was formalized by Russo [9] for a Markov decision process (MDP) where rewards are received at a terminal state. Equivalent updates for dense rewards appear in work on outcome-conditioned behavioral cloning [10] and expectation-maximization algorithms for MDPs [11, 12]. SC is closely related to reward conditioning, which updates policies by conditioning the action distribution on a reward threshold [13, 14]. In previous work, SC has primarily been treated as a heuristic method for policy improvement. Convergence of the SC update has not been rigorously derived and was recently posed as an open question by Russo [9]. ∗ Operations Research Center, Massachusetts Institute of Technology, Cambridge, MA 02139. Email: brunm@mit.edu † Sloan School of Management, Massachusetts Institute of Technology, Cambridge, MA 02139. Email: sunx@mit.edu

1

In this work, we treat SC as an iterative method for policy optimization and present its convergence properties. We prove that, for a broad class of MDPs, SC converges to a restricted optimal policy: one that is optimal on the set of supported actions in the initial policy. For single-period MDPs (i.e., multi-armed bandit problems) and discounted MDPs, we derive upper bounds on the convergence rates to ε-optimal solutions. SC converges in no more than O(log(1/ε)) iterations in the single-period case, and in no more than O(1/εp ) iterations in the discounted case, where the exponent p depends on the instance. These results address several open questions on the limiting behavior and convergence rates of SC. Štrupl et al. [12] analyze reward-weighted regression (RWR), an expectation-maximization algorithm for policy optimization in MDPs. This analysis demonstrates that RWR and SC have equivalent updates and proves that RWR converges in the limit to an optimal policy, under similar assumptions to those described in our work. Štrupl et al. [12] also show that, after sufficiently many iterations, the optimality gap of RWR is bounded by a geometric series, which implies asymptotic linear convergence for discounted MDPs. However, it remains unknown how many iterations are required before this linear convergence rate applies. In contrast, we prove explicit iteration complexities for SC, parametrized by the initial policy. An extensive comparison with Štrupl et al. [12] is provided in Appendix A.

2

Problem Description

Consider a Markov decision process (MDP), defined by a finite set of states S, a finite set of actions A, transition probabilities P , and rewards R. The reward R(s, a) associated with state s ∈ S and action a ∈ A without loss of generality falls on [0, 1]. The probability of a transition to state s′ ∈ S from state s ∈ S when action a ∈ A is taken is given by P (s′ | s, a). Actions are chosen according to a stationary and memoryless policy π that depends only on the current state s, where π(a | s) gives the probability of taking action a ∈ A when in state s ∈ S. Let Π denote the set of such policies. A trajectory of the MDP is an infinite sequence of states and actions: (s0 , a0 , s1 , a1 , . . .), where st ∈ S and at ∈ A. Transitions between states are distributed as st+1 ∼ P (· | st , at ) and actions as at ∼ π(· | st ). We select an absorbing state s, with R(s, a) = 0 and P (s | s, a) = 1 for all a ∈ A. This state represents termination of the process; that is, once s is entered, no other state is reached and no additional rewards are obtained. The set of non-absorbing states is given by S ′ := S \ {s}. We seek to identify policies π ∈ Π that maximize the expected cumulative reward: max Eπ π∈Π

"∞ X

# t

γ R(st , at ) ,

(1)

t=0

where γ ∈ [0, 1] is the discount factor. Undiscounted reward functions (γ = 1) are permitted. We define a value function under policy π, which gives the expected cumulative reward from a trajectory that starts at state s: Vπ (s) := Eπ

"∞ X

# γ t R(st , at ) s0 = s

∀s ∈ S.

(2)

t=0

We also define Q-functions, which give the expected cumulative reward of taking action a at state s: Qπ (s, a) := Eπ

"∞ X

# t

γ R(st , at ) s0 = s, a0 = a

t=0

2

∀a ∈ A, s ∈ S.

(3)

The value functions are a solution to the Bellman equations: ! Vπ (s) =

X

X

π(a | s) R(s, a) + γ

′

′

P (s | s, a)Vπ (s )

∀s ∈ S ′ ,

(4)

s′ ∈S

a∈A

where Vπ (s) = 0. From this system, we can relate the value and Q-functions as follows: Vπ (s) =

X

π(a | s)Qπ (s, a)

and Qπ (s, a) = R(s, a) + γ

X

P (s′ | s, a)Vπ (s′ ).

(5)

s′ ∈S

a∈A

For some instances, the Bellman equations (4) may have multiple solutions. To eliminate this and other aberrant behavior, we make the following assumption. Here, π0 denotes an incumbent policy, which will be the initial point for the SC algorithm. Assumption 1. The following properties hold: 1. For any π ∈ Π, the value functions Vπ (s) are finite and the unique solution to (4); and 2. Vπ0 (s) > 0 for all s ∈ S ′ . Assumption 1 ensures that the MDP is reasonably well-behaved. First, it requires that the value functions under any policy are the unique solution to the Bellman equations. This assumption eliminates ill-behaved problems, e.g., undiscounted instances that cycle infinitely between states while accruing rewards. The condition is satisfied for discounted problems (i.e., γ < 1) or for undiscounted stochastic shortest path problems that satisfy minor assumptions, for example, that the absorbing state s can be reached with nonzero probability from any state under any policy [15, Sec. 4.2]. Stochastic shortest path and discounted problems are common classes for analysis of infinite-horizon MDPs. Second, the assumption requires that the value of all states (except s) must be strictly positive under the initial policy π0 . Although this property may not hold in general, states s′ ∈ S ′ with Vπ0 (s′ ) = 0 can be removed from the MDP and transitions into s′ reassigned to the absorbing state s. This construction generates an MDP that satisfies the latter assumption but prohibits optimization of the policy at states with zero initial value.

2.1

The Success Conditioning Update

SC iteratively applies the success conditioning update to the incumbent policy. Let πk be the policy in the k-th iteration. For convenience, we index the value and Q-functions by the iteration index: Qk (s, a) := Qπk (s, a) and Vk (s) := Vπk (s). The policy in the (k + 1)-th iteration is computed by πk+1 (a | s) =

πk (a | s)Qk (s, a) Vk (s)

∀a ∈ A, s ∈ S ′ .

(6)

The initial policy π0 is given. This update increases the probability of selecting actions whose expected rewards are above average under the current policy, and decreases the probability of actions with below average expected rewards. For the update to be well-defined, Vk (s) must be positive. In Lemma 1, we show that the value and Q-functions increase under this update; positivity of Vk (s) follows from Assumption 1. Lemma 1 generalizes Corollary 4.5 of Russo [9] to the dense reward setting. The proofs of Lemma 1 and all other lemmas are deferred to Appendix B.

3

Lemma 1. Let Assumption 1 hold. Then, Vk+1 (s) ≥ Vk (s) and Qk+1 (s, a) ≥ Qk (s, a) for all s ∈ S ′ , a ∈ A, and k ∈ Z≥0 Under the update (6), the policy πk and value function Vk at iteration k can be written in closed form: Qk−1 π0 (a | s) j=0 Qj (s, a) πk (a | s) = Qk−1 j=0 Vj (s)

2.2

Q X π0 (a | s) kj=0 Qj (s, a) Vk (s) = . Qk−1 j=0 Vj (s) a∈A

and

(7)

Motivation by Conditional Probability under Binary Rewards

The SC update is motivated by a setting with binary rewards that are received at the termination of an undiscounted MDP [9]. This setting is a restriction of the one presented above, in which: a) there exists a set of terminal states T ⊂ S ′ that transition directly into the absorbing state (P (s | τ, a) = 1 for all a ∈ A and τ ∈ T ); b) rewards are only received in terminal states (R(s, a) = 0 for s ̸∈ T ), are independent of the action (R(τ ) = R(τ, a) for all τ ∈ T and a ∈ A), and are binary (R(τ ) ∈ {0, 1} for τ ∈ T ); and c) the MDP is undiscounted (γ = 1). Let τ ∈ T be a random variable that gives the terminal state of the trajectory. The SC update is πk+1 (a | s) =

πk (a | s)Qk (s, a) Pπ [a0 = a | s0 = s] Pπk [R(τ ) = 1 | a0 = a, s0 = s] = k Vk (s) Pπk [R(τ ) = 1 | s0 = s]

(8)

= Pπk [a0 = a | s0 = s, R(τ ) = 1] , where the first line replaces the policy, value function, and Q-function with their probabilistic interpretations in the undiscounted setting with binary rewards, and the second line is an application of Bayes’ rule. Thus, the SC update generates a new policy that corresponds to the distribution of actions that yield successful trajectories under policy πk , where successful trajectories are those that receive a reward of 1. In this work, we study the behavior of SC for general MDPs; however, this general setting does not permit interpretation of the next policy iterate as a conditional distribution.

2.3

Optimal Restricted Value Functions

For each s ∈ S ′ , let A0 (s) := {a ∈ A : π0 (a | s) > 0} be the set of supported actions under the initial policy. Clearly, πk (a | s) = 0 for any a ̸∈ A0 (s) by (7). Let Π′ ⊂ Π represent the set of policies π which satisfy π(a | s) = 0 for all s ∈ S ′ and a ∈ A \ A0 (s). We define Vk′ (s) := maxa∈A0 (s) Qk (s, a), which gives the value of the best supported action at state s, when policy πk is followed downstream of the current state. The value functions Vk′ are a greedy value iteration step from the incumbent SC value function Vk . Let the optimal restricted value functions over the policy set Π′ be given by ∗

V (s) := max′ Eπ π∈Π

"∞ X

# t

γ R(st , at ) s0 = s

∀s ∈ S.

(9)

t=0

Under Assumption 1, V ∗ are the unique solutions to the restricted Bellman optimality equations: V ∗ (s) = max a∈A0 (s)

R(s, a) + γ

X

P (s′ | s, a)V ∗ (s′ )

∀s ∈ S ′ ,

(10)

s′ ∈S

where V ∗ (s) = 0. The optimal restricted Q-functions Q∗ are defined analagously. In this work, we show convergence of the SC value functions Vk to the optimal restricted value functions V ∗ . 4

3

Limiting Behavior of Success Conditioning

In this section, we demonstrate that SC converges in the limit to the optimal restricted value functions V ∗ . We begin by analyzing the ratio of the value functions Vk to the value iteration step Vk′ . Proposition 1 shows that the average of the ratios converges to one as the iteration count increases. Proposition 1. Let Assumption 1 hold. For all s ∈ S ′ , k 1 X Vj (s) = 1. k→∞ k + 1 V ′ (s) j=0 j

lim

Proof. By Lemma 1, Vk (s) and Qk (s, a) are increasing sequences in k that are bounded above by V ∗ (s) and Q∗ (s, a). Therefore, the sequences have limits, which we define for s ∈ S ′ and a ∈ A as V (s) := lim Vk (s) k→∞

and Q(s, a) := lim Qk (s, a). k→∞

For any ε ∈ (0, 1), there is some k ε such that (1 − ε)Q(s, a) ≤ Qk (s, a) for all k ≥ k ε , s ∈ S ′ , and a ∈ A. Let a∗ (s) ∈ argmaxa∈A0 (s) Q(s, a) for all s ∈ S ′ . For all k ∈ Z≥0 and s ∈ S ′ , Vk′ (s) = max Qk (s, a) ≤ max Q(s, a) = Q(s, a∗ (s)). a∈A0 (s)

(11)

a∈A0 (s)

Fix some ε ∈ (0, 1) and let k ≥ k ε . From the closed-form representation of the value function (7), k Y Vj (s) j=0

Vj′ (s)

≥ π0 (a∗ (s) | s)

k Y Qj (s, a∗ (s))

Vj′ (s)

j=0



∗

≥ π0 (a (s) | s)

Q0 (s, a∗ (s)) V ∗ (s)

k ε Y k j=kε



∗

≥ π0 (a (s) | s)

Q0 (s, a∗ (s)) V ∗ (s)

k ε

Qj (s, a∗ (s)) Q(s, a∗ (s))

(12)

(1 − ε)k−kε +1 .

The first inequality selects a single element from the sum in (7), the second uses (11) and the monotonicity of Qk (Lemma 1), and the third uses the definition of k ε . As the sequence Vk (s) has a limit, the sequence Vk′ (s) also has a limit, which is bounded away from zero as Vk′ (s) ≥ V0 (s) > 0 by Assumption 1. Therefore, the limit of the ratios Vk (s)/Vk′ (s) also exists, which is sufficient to ensure the existence of the limits of the partial arithmetic and geometric means in the following inequalities:

1 ≥ lim

k→∞

≥ sup



k X

1  k+1

k Y Vj (s)

Vj (s)  lim  ′ (s) ≥ k→∞ ′ (s) (k + 1)V V j j j=0 j=0 lim

ε∈(0,1) k→∞

π0 (a∗ (s) | s)



Q0 (s, a∗ (s)) V ∗ (s)

k ε

1 ! k+1

(1 − ε)k−kε +1

= sup (1 − ε) = 1. ε∈(0,1)

Here, the first relation is by definition of Vj′ (s), the second is from the AM-GM inequality, the third uses (12), and the fourth is due to the evaluation of the limit for fixed ε. 5

From Proposition 1, we establish convergence of Vk to the optimal restricted value functions V ∗ . Theorem 1 presents this result. Theorem 1. Let Assumption 1 hold. For all s ∈ S ′ , lim Vk (s) = V ∗ (s);

k→∞

that is, the value functions of the SC policies converge to the restricted optimal value functions. Proof. As noted in the proof of Proposition 1, the sequences Vk (s), Vk′ (s), and Vk (s)/Vk′ (s) all have limits. We define L :=

k limk→∞ Vk (s) Vk (s) 1 X Vj (s) . = lim = lim limk→∞ Vk′ (s) k→∞ Vk′ (s) k→∞ k + 1 j=0 Vj′ (s)

The first equality follows from the existence of both limits and the positivity of the denominator under Assumption 1 (Vk′ (s) ≥ V0 (s) > 0), and the second from the equality of the limit of a sequence and the limit of its averages. By Proposition 1, we have that L = 1, so lim Vk (s) = lim Vk′ (s) = max

k→∞

k→∞

R(s, a) + γ

a∈A0 (s)

X

P (s′ | s, a) lim Vk (s).

s′ ∈S

k→∞

Therefore, the values limk→∞ Vk (s) satisfy the Bellman equations (10) and, under Assumption 1, are the unique solution V ∗ (s). Theorem 1 establishes the convergence behavior of SC: policies generated by SC converge in value to the optimal value functions over actions that are supported by the initial policy π0 . In the following sections, we derive convergence rates for MDPs with specific structures.

4

Convergence Rate for Single-Period MDPs

In this section, we consider an MDP that consists of two states (S = {s◦ , s}) and reaches the absorbing state s immediately after the first action (P (s | s◦ , a) = 1 for all a ∈ A). Under this structure, Qπ (s◦ , a) = R(s◦ , a). As the action taken in the first period entirely determines the infinite-horizon reward, we refer to this problem as a single-period MDP. Single-period MDPs are multi-armed bandit problems in which the rewards associated with each arm are known exactly, and are equivalent to maximally-discounted MDPs, i.e., those with γ = 0. Although single-period MDPs can be solved in closed-form by selecting an action which maximizes R(s◦ , a), they provide a simple and instructive setting for analysis of SC convergence rates. With a similar perspective, Russo [9] proposes an example of a single-period MDP that demonstrates how the SC update may make slow progress towards an optimal policy. For single-period MDPs, we derive a rate of convergence of the value function Vk (s◦ ) to the optimal restricted value function V ∗ (s◦ ) = maxa∈A0 (s◦ ) R(s◦ , a). Theorem 2 presents the convergence rate. This rate shows that a policy with an optimality gap of ε is found within O(log(1/ε)) iterations. However, the coefficient on this rate becomes arbitrarily large as the value of the second-best action approaches that of the best action. To avoid this issue, we also show that such a policy is found within O(1/ε) iterations, with a coefficient that depends only on the initial policy.

6

Theorem 2. Let Assumption 1 hold. Let A∗0 := {a ∈ A0 (s◦ ) : R(s◦ , a) = V ∗ (s◦ )} be the set of optimal P actions, let R2 := maxa∈A0 (s◦ )\A∗0 R(s◦ , a) be the reward of the second-best action, let D := a∈A∗ π0 (a | s◦ ), 0

and let E := V ∗ (s◦ )/R2 . For ε ∈ (0, 1) and k ∈ Z≥0 such that  k ≥ min

1 log log(E)



1−D Dε

 ,

log (1/D) ε

 ,

(13)

it holds that V ∗ (s◦ ) − Vk (s◦ ) ≤ ε. Proof. Suppose that k satisfies (13). We first explore the case where k ≥ log(1/D)/ε. We have that 

Vk (s◦ ) V ∗ (s◦ )

k+1 ≥

k Y Vj (s◦ ) j=0

≥

V ∗ (s◦ )

X

=

X

◦

π0 (a | s )

a∈A



◦

π0 (a | s )

a∈A∗ 0

R(s◦ , a) V ∗ (s◦ )



R(s◦ , a) V ∗ (s◦ )

k+1 (14)

k+1

X

=

◦

π0 (a | s ) = D,

a∈A∗ 0

where the first inequality follows from Lemma 1, the first equality from the closed-form description (7) of the value functions, the second inequality by selecting elements from the sum, and the second equality from the definition of A∗0 . Then, Vk (s◦ ) V (s ) − Vk (s ) = V (s ) 1 − ∗ ◦ V (s ) ∗

◦

◦

∗

◦





1

≤ 1 − D k ≤ 1 − exp(−ε) ≤ ε,

where the first inequality follows by taking the (k + 1)-th root of (14) and from R(s◦ , a) ≤ 1, and the final inequality is due to the relation 1 + x ≤ exp(x) for all x ∈ R. Second, we explore the case where k ≥ log((1 − D)/Dε)/ log(E). From (7), we have that P ◦ ◦ k+1 a∈A π0 (a | s )R(s , a) . Vk (s ) = P ◦ ◦ k a∈A π0 (a | s )R(s , a) ◦

(15)

Then, ∗

◦

P

◦

V (s ) − Vk (s ) =

◦ ∗ ◦ ◦ ◦ k a∈A π0 (a | s ) (V (s ) − R(s , a)) R(s , a) P ◦ ◦ k a∈A π0 (a | s )R(s , a)

π0 (a | s◦ ) (V ∗ (s◦ ) − R(s◦ , a)) R(s◦ , a)k 1−D a∈A0 (s◦ )\A∗ 0 P ≤ ε, ≤ ◦ ∗ ◦ k DE k a∈A∗ π0 (a | s )V (s )

P ≤

0

where the first relation follows from (15), the second relation follows from the definitions of A0 (s◦ ) and A∗0 , and the third relation is due to R(s◦ , a) ∈ [0, 1] and the definition of E.

5

Convergence Rate for Discounted MDPs

In this section, we derive a convergence rate for discounted MDPs, that is, problems with γ < 1. Discounting is common for infinite-horizon MDPs, and standard convergence rates for many typical policy optimization algorithms assume that the MDP is discounted [16]. The analysis in this section requires Assumption 2, which requires discounting and that the value functions V ∗ and Vk fall on (0, 1]. The latter assumption is for convenience and can be achieved by rescaling the rewards R(s, a). Assumption 2. The following properties hold: 7

1. The MDP is discounted with γ ∈ [0, 1); and 2. V ∗ (s) ∈ (0, 1] for all s ∈ S ′ . We also define π := min′

s∈S a∈A0 (s)

π0 (a | s),

Φ := min′ s∈S

max a∈A0 (s)

Q0 (s, a),

and

a∗k (s) ∈ argmax Qk (s, a). a∈A0 (s)

Parameter π gives the smallest weight on a supported action under the initial policy, Φ is a lower bound across states on the value of the best action under the initial policy, and a∗k (s) gives the best action at state s under policy πk . By Assumption 1 and the definition of A0 (s), both π and Φ are strictly positive. To derive a convergence rate, we define a sequence of indices {ji }∞ i=0 ⊂ Z≥0 and treat the SC value functions Vji as iterates of an approximate value iteration (AVI) algorithm, where there is some error εi between the value iteration step Vj′i and the SC value function Vji+1 at the next index. Lemma 2 gives a convergence rate for AVI, parametrized by the errors εi . Then, Proposition 2 bounds the errors εi by the values of the index sequence {ji }∞ i=0 . Lemma 2. Let Assumptions 1 and 2 hold, and let {ji }∞ i=0 ⊂ Z≥0 be a non-decreasing set of iteration indices, with j0 = 0 and ji+1 ≥ ji . Fix some index i ∈ Z≥0 , and, for all indices ℓ ≤ i, define εℓ > 0 such that Vj′ℓ (s) − Vjℓ+1 (s) ≤ εℓ for all s ∈ S ′ . Then, for all s ∈ S ′ , V ∗ (s) − Vji+1 (s) ≤ γ i+1 +

i X

γ i−ℓ εℓ .

ℓ=0

Proposition 2. Let Assumptions 1 and 2 hold, and let {ji }∞ i=0 ⊂ Z≥0 be a non-decreasing set of iteration indices, with j0 = 0 and ji+1 ≥ ji . For all s ∈ S ′ and i ∈ Z≥0 ,  Vj′i (s) − Vji+1 (s) ≤ 1 − π

i−1 Y ℓ=0

Qjℓ (s, a∗jℓ (s)) Q∗ (s, a∗jℓ (s))

!(jℓ+1 −jℓ )  1+j1i+1 .



Proof. Fix some i ∈ Z≥0 and s ∈ S ′ . We have that Vji+1 (s) Vj′i (s)

!1+ji+1

ji+1

≥

Y Vj (s)

V ′ (s) j=0 ji

≥π

ji+1

≥ π0 (a∗ji (s) | s)

Qji (s, a∗ji (s)) Qji (s, a∗ji (s))

Y Qj (s, a∗j (s)) i

Qji (s, a∗ji (s)) j=0

!(1+ji+1 −ji ) i−1 Y ℓ=0

Qjℓ (s, a∗ji (s)) Qji (s, a∗ji (s))

(16)

!(jℓ+1 −jℓ ) ,

where the first inequality follows from the monotonicity of the value functions (Lemma 1), the second by selecting a single action in the closed-form representation (7) and from the definition of a∗j (s), and the third from the monotonicity of the Q-functions (Lemma 1). Then, Vj (s) Vj′i (s) − Vji+1 (s) = Vj′i (s) 1 − i+1 Vj′i (s)



!

≤ 1 − π

i−1 Y ℓ=0

8

Qjℓ (s, a∗ji (s)) Qji (s, a∗ji (s))

!(jℓ+1 −jℓ )  1+j1i+1 

,

where the final inequality follows from Assumption 2 and taking the (1 + ji+1 )-th root of (16). This relies on the observation that the lower bound in (16) is no larger than 1. Theorem 3 derives a convergence rate for discounted MDPs by combining the previous two results with appropriately selected indices ji and errors εi . Specifically, we show that a policy with an optimality gap of ε is obtained within O(1/εp ) iterations, where p is determined by problem data and some tunable parameter B. In Theorem 3, p > 1 as the denominator in its definition (17) is negative. To prove Theorem 3, we leverage the convergence of the SC value functions Vji+1 to the AVI iterates Vj′i , as described in Proposition 2.

We first define parameters B, k, ji , εi , and ∆i . Parameters ji separate

the SC iterations into blocks {ji + 1, . . . , ji+1 }, where each block corresponds to an AVI step. Parameter εi gives an upper bound on the error between the SC iterate Vji+1 and the AVI iterate Vj′i , and ∆i is an upper bound on the error between the SC iterate Vji and the optimal value function V ∗ . Parameter B represents the proportion of the overall error ∆i allocated to the AVI error εi , that is, εi = B∆i . Finally, k denotes the number of AVI steps required to ensure an overall error of ∆k ≤ ε. Using Proposition 2, we show that the SC-to-AVI errors are bounded by εi at each iterate ji . We then use Lemma 2 to show that the overall errors are bounded by ∆i . Lemma 3 gives a relevant bound on the ratio of logarithms, which is used in the proof of Theorem 3. In Lemma 3 and Theorem 3, we take log(1/(1 − x))/x = 1 at x = 0, so that the expression is continuous on [0, 1). Lemma 3. Let a ∈ (0, 1), b ∈ R>0 , and c ∈ [0, 1). Then, b log(1/(1 − c)) log(max{1 − b, 1 − c}) ≤ . log(1 − a) ac Theorem 3. Let Assumptions 1 and 2 hold and fix some ε ∈ (0, 1). The following result holds for any B ∈ (0, 1 − γ). Define  C := max

γ log(1/Φ) ,1 BΦ(1 − Φ)

 and

p := 1 −

log(2C) . log(γ + B)

(17)

Then, for all iterations j ∈ Z≥0 that satisfy  j≥

log(1/π) B

  p 1 , ε

(18)

it holds that V ∗ (s) − Vj (s) ≤ ε for all s ∈ S ′ . Proof. Fix some ε ∈ (0, 1) and B ∈ (0, 1 − γ). For i ∈ Z≥0 , define ∆i := (γ + B)i and εi := B∆i . We also define iteration indices 

log(ε) k := log(γ + B)



 and

ji+1 :=

log(π) log(1 − εi )



i

(2C)

 ∀i ∈ Z≥0 ,

with j0 = 0. From the definitions, we establish two relations between these quantities: for all i ∈ Z≥0 , it holds that εi ≥ 1 −

π

i−1 Y ℓ=0



γ∆ℓ max Φ, 1 − Φ

9

(jℓ+1 −jℓ ) ! 1+j1i+1 (19)

and ∆i = γ i +

i−1 X

γ i−ℓ−1 εℓ .

(20)

ℓ=0

To show (19), we have that 

log(π) log(1 − εi )





log(π) log(1 − εi )



log(π) log(1 − εi )



log(π) log(1 − εi )



1 log(1 − εi )



1 log(1 − εi )



ji+1 + 1 ≥ =  ≥  ≥  ≥  ≥

(2C)i 1+

i−1 X

! ℓ

2

Ci

ℓ=0

1+

i−1 X γ log(1/Φ) ℓ=0

1+

BΦ(1 − Φ)

! ℓ

(2C)

i−1 X log(max{Φ, 1 − γ∆ℓ /Φ})

log(1 − εℓ )

ℓ=0

log(π) +

! ℓ

(2C)

!

i−1 X

log(max{Φ, 1 − γ∆ℓ /Φ})jℓ+1

ℓ=0

log(π) +

!

i−1 X

log(max{Φ, 1 − γ∆ℓ /Φ})(jℓ+1 − jℓ ) ,

ℓ=0

where the first relation follows by definition of ji+1 , the second from the identity 2n − 1 = i

from C ≥ C

ℓ+1

Pn−1

i i=0 2 , the third

for ℓ ≤ i − 1, the fourth from Lemma 3 with (a, b, c) = (εℓ , γ∆ℓ /Φ, 1 − Φ), and the fifth by

definition of jℓ+1 . Rearranging the final inequality gives that 1 log(1 − εi ) ≤ 1 + ji+1

log(π) +

i−1 X

! log(max{Φ, 1 − γ∆ℓ /Φ})(jℓ+1 − jℓ ) ,

ℓ=0

and exponentiation of both sides yields (19). To show (20), observe as a base case that ∆0 = 1 = γ 0 . Suppose for induction that (20) holds at index i ∈ Z≥0 . Then, i−1 X

∆i+1 = (γ + B)∆i = εi + γ i+1 +

γ i−ℓ εℓ = γ i+1 +

ℓ=0

i X

γ i−ℓ εℓ ,

ℓ=0

and (20) holds at index i + 1. By induction, we conclude that (20) holds for all i ∈ Z≥0 . We now proceed to prove the result. Suppose for induction that, at index i ∈ Z≥0 , the following condition holds for all s ∈ S ′ and all ℓ ∈ Z≥0 such that ℓ ≤ i − 1: Vj′ℓ (s) − Vjℓ+1 (s) ≤ εℓ .

(21)

As a base case, this condition is trivially satisfied when i = 0. By Lemma 2, we have for all ℓ ≤ i and s ∈ S ′ that V ∗ (s) − Vjℓ (s) ≤ γ ℓ +

ℓ−1 X m=0

10

γ ℓ−m−1 εm = ∆ℓ ,

(22)

where the final equality is due to (20). Then, for all ℓ ≤ i and s ∈ S ′ , we have ! Q∗ (s, a∗jℓ (s)) − Qjℓ (s, a∗jℓ (s)) Q∗ (s, a∗jℓ (s)) P   γ s′ ∈S P (s′ | s, a∗jℓ (s)) (V ∗ (s′ ) − Vjℓ (s′ )) γ∆ℓ ≥1− ≥1− , Φ Φ

Qjℓ (s, a∗jℓ (s)) =1− Q∗ (s, a∗jℓ (s))

as Φ ≤ Q0 (s, a∗0 (s)) ≤ Qjℓ (s, a∗jℓ (s)) ≤ Q∗ (s, a∗jℓ (s)) by the monotonicity of the Q-functions (Lemma 1). We also have under Assumption 2 that

Qjℓ (s, a∗jℓ (s)) ≥ Φ, Q∗ (s, a∗jℓ (s))

as Q∗ (s, a) ≤ 1. Therefore, by Proposition 2, we have for all s ∈ S ′ that  Vj′i (s) − Vji+1 (s) ≤ 1 − π

i−1 Y

Qjℓ (s, a∗jℓ (s)) Q∗ (s, a∗jℓ (s))

ℓ=0

≤1−

π

i−1 Y ℓ=0



!(jℓ+1 −jℓ )  1+j1i+1

γ∆ℓ max Φ, 1 − Φ

 (jℓ+1 −jℓ ) ! 1+j1i+1 ≤ εi ,

where the final inequality follows from (19). The inductive hypothesis (21) is then satisfied at index i + 1. Then, both (21) and (22) hold for any i ∈ Z≥0 . From (22), for all s ∈ S ′ , V ∗ (s) − Vjk (s) ≤ (γ + B)k ≤ ε. Therefore, at the jk -th iteration, the optimality gap is no larger than ε. For j satisfying (18),     log(2C) − log(ε) log(ε) 1 log(1/π) log(γ+B) (ε) = (γ + B) log(γ+B) (2C) log(γ+B) j≥ ε B  k−1      2C log(1/π) log(1/π) log(π) k−1 = (2C)k−1 ≥ jk , ≥ (2C) ≥ B γ+B εk−1 log(1 − εk−1 ) 

log(1/π) B

where we apply the property log(1 − x) ≤ −x for x ∈ (−∞, 1) in the third inequality. By Lemma 1, we then have V ∗ (s) − Vj (s) ≤ ε, as j ≥ jk . Corollary 1 gives an explicit, parameter-free convergence rate that follows from Theorem 3 by taking B = min{γ/Φ2 , (1 − γ)/2}. The resulting rate falls into two regimes that differ in the exponent p. A proof of this result is provided in Appendix B. Corollary 1. Let Assumptions 1 and 2 hold and fix some ε ∈ (0, 1). Define  
 2 log(1/π) 1 p1 if 2γ ≥ Φ2 (1 − γ), 1−γ ε  j ∗ := 
1 p2  log(1/π)Φ2 otherwise, γ ε   4γ log Φ2 (1−γ) log(2) where p1 := 1 − and p2 := 1 − . log((1 + γ)/2) log(γ + γ/Φ2 ) Then, for j ∈ Z≥0 such that j ≥ j ∗ , it holds that V ∗ (s) − Vj (s) ≤ ε for all s ∈ S ′ .

11

Corollary 1 illustrates the behavior of the convergence threshold j ∗ as the values of γ and Φ vary. When γ is large (∼ 1) and Φ is small (∼ 0), the convergence rate is O(1/εp1 ). For small γ and large Φ, the convergence rate is O(1/εp2 ). The exponents p1 and p2 increase as γ increases and decrease as Φ increases. Thus, the order p of the convergence rate O(1/εp ) is small when the problem is highly discounted (γ ∼ 0) and when the best action under the initial policy yields large returns (Φ ∼ 1). The single-period MDP described in Section 4 is equivalent to a maximally-discounted MDP, with γ = 0. In Corollary 1, as γ → 0, the second regime applies and p2 → 1. For this high-discount setting, the limiting behavior of Corollary 1 recovers an asymptotic convergence rate of O(1/ε), which is slower than the O(log(1/ε)) rate of Theorem 2. This suggests that there are key differences between single-period and general MDPs, or that Theorem 3 gives a loose rate as γ approaches zero.

6

Discussion and Conclusion

Theorem 1 establishes that SC converges to a restricted optimal solution for well-behaved MDPs satisfying Assumption 1. Theorem 2 shows that SC converges to an ε-optimal policy within O(log(1/ε)) iterations for single-period MDPs, and Theorem 3 shows that SC converges within O(1/εp ) iterations for discounted MDPs, with an exponent p ≥ 1 that depends strongly on problem data and may be arbitrarily large. These results address several open questions on the convergence behavior of SC. Our convergence rates give upper bounds on the worst-case performance of SC; SC may converge faster on typical instances, and further analysis may prove convergence at a faster rate. Relative to comparable policy optimization algorithms, the SC convergence rates presented in this work are slow. For single-period MDPs, selecting the action with the largest reward recovers an exact optimal policy in a single iteration. For discounted MDP, value iteration and policy iteration both converge linearly, yielding an ε-optimal policy in O(log(1/ε)) iterations [16]. Policy iteration may even converge quadratically, requiring only O(log(log(1/ε))) iterations [16, Thm. 6.4.8]. The slow convergence of SC can be viewed as a feature. Russo [9] describes SC as a “conservative” operator that does not deviate significantly from the incumbent policy π0 . Changes in the policy under the SC update directly correspond to improvements in its performance [9, Prop. 4.4]. Although this conservatism inhibits efficient convergence, it permits stability in learning by avoiding drastic changes in the distribution of actions. SC also exhibits stability by converging to an optimal restricted solution, and cannot produce policies that take actions which were not taken by the initial policy π0 . Another strength of SC is that it generates stochastic policies, in which actions that were supported under the initial policy remain supported at every iteration. In contrast, value and policy iteration generate policies that deterministically select a single action. Stochastic policies are desirable for many applications, especially in the context of generative AI [17, 18]. Additionally, stochastic policies permit on-policy learning, where the Q-functions Qk (s, a) are approximated by sampling trajectories under the incumbent policy πk . As SC maintains non-zero probabilities on the set of supported actions, a sufficiently large number of trajectory samples will visit all supported state-action pairs, permitting an estimate of the Q-functions. Because deterministic policies always select a single action, value and policy iteration are not compatible with Qfunction estimation by on-policy sampling. Similar properties (conservatism and stochastic policy iterates) are shared by trust-region policy optimization [TRPO; 19] and proximal policy optimization [PPO; 20]. However, these methods require parameter tuning and generally do not have well-understood convergence rates, although some variants converge in

12

O(1/ε2 ) iterations [21]. For comparison to TRPO and PPO, interesting open directions include designing on-policy variants of SC that estimate the Q-functions from trajectory samples and investigating the sample complexity of these variants.

Acknowledgements We thank Daniel Russo for introducing us to this topic and providing his perspectives on open directions and challenges. We also are grateful to the anonymous referees whose comments suggested a path to tighten the single-period convergence rates.

References [1] Marcin Andrychowicz, Filip Wolski, Alex Ray, Jonas Schneider, Rachel Fong, Peter Welinder, Bob McGrew, Josh Tobin, Pieter Abbeel, and Wojciech Zaremba. Hindsight experience replay. In Advances in Neural Information Processing Systems, volume 30, 2017. [2] Yiming Ding, Carlos Florensa, Pieter Abbeel, and Mariano Phielipp. Goal-conditioned imitation learning. In Advances in Neural Information Processing Systems, volume 32, 2019. [3] Hanze Dong, Wei Xiong, Deepanshu Goyal, Yihan Zhang, Winnie Chow, Rui Pan, Shizhe Diao, Jipeng Zhang, Kashun Shum, and Tong Zhang. RAFT: Reward ranked finetuning for generative foundation model alignment. Transactions on Machine Learning Research, 2023. [4] Aaron Grattafiori, Abhimanyu Dubey, Abhinav Jauhri, Abhinav Pandey, Abhishek Kadian, Ahmad Al-Dahle, Aiesha Letman, Akhil Mathur, Alan Schelten, Alex Vaughan, et al.

The Llama 3 herd of models, 2024.

arXiv:2407.21783 [cs.AI]. [5] Daya Guo, Dejian Yang, Haowei Zhang, Junxiao Song, Peiyi Wang, Qihao Zhu, Runxin Xu, Ruoyu Zhang, Shirong Ma, Xiao Bi, et al. DeepSeek-R1 incentivizes reasoning in LLMs through reinforcement learning. Nature, 645:633–638, 2025. [6] Anthony Brohan, Noah Brown, Justice Carbajal, Yevgen Chebotar, Joseph Dabis, Chelsea Finn, Keerthana Gopalakrishnan, Karol Hausman, Alex Herzog, Jasmine Hsu, et al. RT-1: Robotics transformer for real-world control at scale. In Robotics: Science and Systems, volume 19, 2023. [7] Seyed Kamyar Seyed Ghasemipour, Ayzaan Wahid, Jonathan Tompson, Pannag Sanketi, and Igor Mordatch. Self-improving embodied foundation models. In Advances in Neural Information Processing Systems, volume 38, 2025. [8] Lili Chen, Kevin Lu, Aravind Rajeswaran, Kimin Lee, Aditya Grover, Misha Laskin, Pieter Abbeel, Aravind Srinivas, and Igor Mordatch. Decision transformer: Reinforcement learning via sequence modeling. In Advances in Neural Information Processing Systems, volume 34, 2021. [9] Daniel Russo. Success conditioning as policy improvement: The optimization problem solved by imitating success. In Proceedings of the 43th International Conference on Machine Learning, 2026. [10] Benjamin Eysenbach, Soumith Udatha, Ruslan Salakhutdinov, and Sergey Levine. Imitating past successes can be very suboptimal. In Advances in Neural Information Processing Systems, volume 35, 2022. [11] Marc Toussaint, Amos Storkey, and Stefan Harmeling.

Expectation-maximization methods for solving

(PO)MDPs and optimal control problems. In Bayesian Time Series Models. Cambridge University Press, 2011.

13

[12] Miroslav Štrupl, Francesco Faccio, Dylan R Ashley, Rupesh Kumar Srivastava, and Jürgen Schmidhuber. Reward-weighted regression converges to a global optimum. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 36, pages 8361–8369, 2022. [13] Jan Peters and Stefan Schaal. Reinforcement learning by reward-weighted regression for operational space control. In Proceedings of the 24th International Conference on Machine Learning, 2007. [14] David Brandfonbrener, Alberto Bietti, Jacob Buckman, Romain Laroche, and Joan Bruna. When does returnconditioned supervised learning work for offline reinforcement learning?

In Advances in Neural Information

Processing Systems, volume 35, 2022. [15] Dimitri P Bertsekas. Reinforcement Learning and Optimal Control. Athena Scientific, 2019. [16] Martin L Puterman. Markov Decision Processes: Discrete Stochastic Dynamic Programming. John Wiley & Sons, 2005. [17] Angela Fan, Mike Lewis, and Yann Dauphin. Hierarchical neural story generation. In Proceedings of the 56th Annual Meeting of the Association for Computational Linguistics, pages 889–898, 2018. [18] Yuheng Wu, Azalia Mirhoseini, and Thierry Tambe. On the role of temperature sampling in test-time scaling, 2025. arXiv:2510.02611 [cs.AI]. [19] John Schulman, Sergey Levine, Pieter Abbeel, Michael Jordan, and Philipp Moritz. Trust region policy optimization. In Proceedings of the 32nd International Conference on Machine Learning, 2015. [20] John Schulman, Filip Wolski, Prafulla Dhariwal, Alec Radford, and Oleg Klimov. Proximal policy optimization algorithms, 2017. arXiv:1707.06347 [cs.LG]. [21] Lior Shani, Yonathan Efroni, and Shie Mannor. Adaptive trust region policy optimization: Global convergence and faster rates for regularized MDPs. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 34, pages 5668–5675, 2020.

14

A

Comparison to Reward-Weighted Regression

Reward-weighted regression (RWR) is an algorithm that applies expectation-maximization to improve policies of MDPs. RWR generates policy iterates by the rule πk+1 (a | s) ∈ argmax Eπk [Qπk (s, a) log(π(a | s))] . π∈Π

Štrupl et al. [12] prove two key results on RWR for compact state and action spaces, under the assumption that all rewards are strictly positive (R(s, a) > 0) and all state-action pairs are supported in the initial policy (π(a | s) > 0). First, the RWR update is equivalent to the SC update (6) [12, Thm. 3.1]. Second, RWR converges in the limit to an optimal policy [12, Thm. 5.1]. Together, these results demonstrate that both SC and RWR converge to an optimal solution. This convergence property corresponds to our Theorem 1, under a modified set of assumptions. Štrupl et al. [12] also analyze the asymptotic convergence rate of RWR, showing that the optimality gap is bounded by a geometric sequence after sufficiently many iterations. Theorem A.1 presents a version of this result. We take A∗0 (s) := {a ∈ A0 (s) : Q∗ (s, a) = V ∗ (s)} as the set of optimal supported actions at state s ∈ S ′ and define the following parameters: λ := max′ s∈S

Q∗ (s, a) a∈A0 (s)\A0 (s) V ∗ (s) max ∗

and

α :=

2λ . 0.9 + 1.1λ

The parameter λ is the ratio between the Q-value of the second-best action and of the best action, and α < 1 is the common ratio of the bounding geometric sequence. Theorem A.1 ([12], Corr. 5.1). Let Assumption 2 hold, and suppose that R(s, a) > 0 for all s ∈ S and ′ a ∈ A0 (s). Let n ∈ Z≥0 such that Q∗ (s, a) − Qn (s, a) < 1−λ 20 for all s ∈ S and a ∈ A0 (s). Then, there exists

some constant F > 0 such that V ∗ (s) − Vj (s) ≤ F · αj−n for all j ∈ Z≥0 with j > n and all s ∈ S ′ . In Theorem A.1, the optimality gap begins to converge linearly at the n-th iteration, where n is chosen as an iteration where the gap between the incumbent and optimal Q-functions is sufficiently small. This approach does not characterize how large n must be to ensure the condition is met; the coefficient F may also grow arbitrarily large with n. In contrast, Theorems 2 and 3 give explicit convergence rates which quantify the number of iterations required to guarantee a bound on the optimality gap. The setting of Theorem A.1 has similarities to the single-period MDP described in Section 4. First, the condition Q∗ (s, a) − Qn (s, a) < 1−λ 20 ensures that the Q-functions correctly indicate which action is optimal; that is, there is no a ̸∈ A∗0 (s) such that Qn (s, a) > Qn (s, a∗ ), where a∗ ∈ A∗0 (s). Similarly, for single-period MDPs, the Q-functions Qj (s◦ , a) are exactly the rewards R(s◦ , a) and therefore indicate the set of optimal actions at any iteration j. Second, the geometric rate in Theorem A.1 depends on the ratio λ between the values of the first- and second-best actions. The proof of Theorem 2 similarly gives that 1−D V ∗ (s◦ ) − Vk (s◦ ) ≤ DE k , where the common ratio 1/E is equivalent to λ.

15

B

Deferred Proofs

Proof of Lemma 1 Proof. Let Bπ be the Bellman operator under policy π, defined for V : S → R as ! (Bπ V )(s) =

X

π(a | s) R(s, a) + γ

X

′

′

P (s | s, a)V (s ) .

s′ ∈S

a∈A

This operator preserves monotonicity; that is, V+ ⪰ V− implies that Bπ V+ ⪰ Bπ V− , where ⪰ is the component-wise inequality over states s ∈ S. Under Assumption 1, a fixed point of Bπ is the unique solution Vπ to the Bellman equations (4). (j)

Let Bk := Bπk . Consider the sequence {Bk+1 Vk }∞ j=0 , where the superscript (j) denotes that Bk+1 is applied j times to Vk . Observe that, for s ∈ S ′ , X

(Bk+1 Vk )(s) =

πk+1 (a | s)Qk (s, a) =

a∈A

≥

X πk (a | s)Qk (s, a)2 Vk (s)

a∈A

1 Vk (s)

!2 X

πk (a | s)Qk (s, a)

= Vk (s),

a∈A

where the inequality is due to Jensen’s inequality. Thus, Bk+1 Vk ⪰ Vk . By the preservation of monotonicity, (j+1)

(j)

Bk+1 Vk ⪰ Bk+1 Vk ⪰ Vk for any j ∈ Z≥0 . Under Assumption 1, there exist some finite optimal value functions V and Q-functions Q such that V (s) = max Q(s, a) a∈A

and

Q(s, a) = R(s, a) + γ

X

P (s′ | s, a)V (s′ ).

s′ ∈S

Then, (Bk+1 V )(s) =

X

πk+1 (a | s)Q(s, a) ≤ max Q(s, a) = V (s), a∈A

a∈A

(j)

and V ⪰ Bk+1 V . Again by the preservation of monotonicity, V ⪰ Bk+1 V for all j ∈ Z≥0 . As V ⪰ Vk , we (j)

(j)

(j)

(j)

have Bk+1 V ⪰ Bk+1 Vk . Thus, V ⪰ Bk+1 Vk and the sequence {Bk+1 Vk }∞ j=0 is bounded. (j)

Therefore, {Bk+1 Vk }∞ j=0 is a bounded non-decreasing sequence and has a limit. By the continuity of the operator Bk+1 , we have (j)

(j−1)

L := lim Bk+1 Vk = Bk+1 lim Bk+1 Vk = Bk+1 L. j→∞

j→∞

Thus, L is a fixed point of Bk+1 , and therefore L = Vk+1 . By the monotonicity of the sequence, we conclude that Vk+1 = L ⪰ Vk . By (5), Vk+1 ⪰ Vk directly implies that Qk+1 (s, a) ≥ Qk (s, a) for all s ∈ S ′ and a ∈ A.

16

Proof of Lemma 2 Proof. The proof follows standard analysis for the contractivity of Bellman operators. For all ℓ ∈ Z≥0 such that ℓ ≤ i,

max V ∗ (s) − Vjℓ+1 (s) ≤ εℓ + max V ∗ (s) − Vj′ℓ (s) s∈S s∈S  = εℓ + max max Q∗ (s, a) − max s∈S

≤ εℓ + max s∈S

a∈A0 (s)

max a∈A0 (s)

a∈A0 (s)

 Qjℓ (s, a)

∗

(Q (s, a) − Qjℓ (s, a))

≤ εℓ + γ max (V ∗ (s′ ) − Vjℓ (s′ )) . ′ s ∈S

Nesting the above inequalities over indices ℓ gives that i X
max V ∗ (s) − Vji+1 (s) ≤ γ i+1 max (V ∗ (s) − V0 (s)) + γ i−ℓ εℓ . s∈S

s∈S

ℓ=0

By Assumptions 1 and 2, V ∗ (s) − V0 (s) ≤ 1 for all s ∈ S, which gives the desired result.

Proof of Lemma 3 Proof. If c = 0, we have log(max{1 − b, 1 − c}) b b log(1/(1 − c)) =0< = , log(1 − a) a ac where we take log(1/(1 − x))/x = 1 at x = 0. Otherwise, c > 0. Let b′ := min{b, c} ∈ (0, 1). As the function log(1 − x) is concave, it is upper bounded by its tangent at x = 0, so log(1 − a) ≤ −a. As log(1 − b′ ) < 0, this gives that − log(1 − b′ ) log(1 − b′ ) ≤ . log(1 − a) a Next, we write b′ as a convex combination of c and 0:  ′   b c − b′ b = c+ 0, c c ′

where the coefficients fall on [0, 1] by definition of b′ . By Jensen’s inequality, log(1 − b′ ) ≥

 ′   b c − b′ b′ log(1 − c) log(1 − c) + log(1) = . c c c

Therefore, we conclude that log(1 − b′ ) −b′ log(1 − c) b log(1/(1 − c)) ≤ ≤ . log(1 − a) ac ac

17

Proof of Corollary 1 Proof. Fix some ε ∈ (0, 1). As Φ > 0, 1/Φ − 1 1 log(1/Φ) ≤ = , 1−Φ 1−Φ Φ

(23)

where the inequality follows from log(x) ≤ x − 1 for all x ∈ R>0 . Let  B := min

γ 1−γ , Φ2 2

 .

By definition, B ∈ (0, 1 − γ). Let C and p be defined with respect to B as in (17), and consider any j ∈ Z≥0 such that j ≥ j ∗ . First, consider the case where 2γ ≥ Φ2 (1 − γ). In this case, B = (1 − γ)/2 and  C = max

γ log(1/Φ) ,1 BΦ(1 − Φ)



 ≤ max

2γ ,1 Φ2 (1 − γ)

 =

2γ , Φ2 (1 − γ)

where the inequality is due to (23). Then, p=1−

log(2C) ≤ p1 , log((1 + γ)/2)

as log((1 + γ)/2) < 0 by Assumption 2. Thus, ∗



j≥j =

2 log(1/π) 1−γ

  p1    p 1 log(1/π) 1 ≥ , ε B ε

and V ∗ (s) − Vj (s) ≤ ε for all s ∈ S ′ by Theorem 3. Next, consider the other case, in which 2γ < Φ2 (1 − γ) and B = γ/Φ2 . Now,  1 ≤ C = max

γ log(1/Φ) ,1 BΦ(1 − Φ)

 ≤ max

n γ o , 1 = 1, BΦ2

so C = 1. The inequality is again due to (23). Then, p=1−

log(2) = p2 . log(γ + γ/Φ2 )

Thus, ∗

j≥j =



log(1/π)Φ2 γ

   p2    p 1 log(1/π) 1 = , ε B ε

and again V ∗ (s) − Vj (s) ≤ ε for all s ∈ S ′ by Theorem 3.

18

Related documents

• On the Convergence of Success Conditioning for Policy Optimization#1188353
• Dyna-Style Safety Augmented Reinforcement Learning: Staying Safe in the Face of Uncertainty#141493
• Maximum Likelihood Reinforcement Learning#652193
• Maximum Likelihood Reinforcement Learning#650740
• SafePG: Safe and Globally Optimal Reinforcement Learning with Hard Constraints#1083552