Yonathan Efroni
email: jonathan.efroni@gmail.com

Gal Dalal
email: gald@campus.technion.ac.il

Bruno Scherrer
email: bruno.scherrer@inria.fr

Shie Mannor

Convergence of Online and Approximate Multiple-Step Lookahead Policy Iteration

, multiple-step greedy policies and their use in vanilla Policy Iteration algorithms were proposed and analyzed. In this work, we study multiplestep greedy algorithms in more practical setups. We begin by highlighting a counterintuitive difficulty, arising with soft-policy updates: even in the absence of approximations, and contrary to the 1-step-greedy case, monotonic policy improvement is not guaranteed unless the update stepsize is sufficiently large. Taking particular care about this difficulty, we formulate and analyze online and approximate algorithms that use such a multi-step greedy operator.

Introduction

The use of the 1-step policy improvement in Reinforcement Learning (RL) was theoretically investigated under several frameworks, e.g., Policy Iteration (PI) [START_REF] Martin L Puterman | Markov decision processes: discrete stochastic dynamic programming[END_REF], approximate PI [START_REF] Dimitri | Neuro-dynamic programming: an overview[END_REF]; [START_REF] Kakade | Approximately Optimal Approximate Reinforcement Learning[END_REF]; [START_REF] Munos | Error bounds for approximate policy iteration[END_REF], and Actor-Critic [START_REF] Vijaymohan | Actor-critic-type learning algorithms for markov decision processes[END_REF]; its practical uses are abundant [START_REF] Schulman | Trust region policy optimization[END_REF]; [START_REF] Mnih | Asynchronous methods for deep reinforcement learning[END_REF]; Silver et al. (2017b). However, single-step based improvement is not necessarily the optimal choice. It was, in fact, empirically demonstrated that multiplestep greedy policies can perform conspicuously better. Notable examples arise from the integration of RL and Monte Carlo Tree Search Browne et al. (2012); [START_REF] Tesauro | On-line policy improvement using monte-carlo search[END_REF]; [START_REF] Sheppard | World-championship-caliber scrabble[END_REF]; [START_REF] Bouzy | Monte-carlo go developments[END_REF]; Silver et al. (2017b,a) or Model Predictive Control [START_REF] Rudy R Negenborn | Learningbased model predictive control for markov decision processes[END_REF]; [START_REF] Ernst | Reinforcement learning versus model predictive control: a comparison on a power system problem[END_REF]; [START_REF] Tamar | Learning from the hindsight plan-episodic mpc improvement[END_REF].

Recent work [START_REF] Efroni | Beyond the one step greedy approach in reinforcement learning[END_REF] provided guarantees on the performance of the multiplestep greedy policy and generalizations of it in PI. Here, we establish it in the two practical contexts of online and approximate PI. With this objective in mind, we begin by highlighting a specific difficulty: softly updating a policy with respect to (w.r.t.) a multiple-step greedy policy does not necessarily result in improvement of the policy (Section 4). We find this property intriguing since monotonic improvement is guaranteed in the case of soft updates w.r.t. the 1-step greedy policy, and is central to the analysis of many RL algorithms [START_REF] Vijaymohan | Actor-critic-type learning algorithms for markov decision processes[END_REF]; [START_REF] Kakade | Approximately Optimal Approximate Reinforcement Learning[END_REF]; [START_REF] Schulman | Trust region policy optimization[END_REF]. We thus engineer some algorithms to circumvent this difficulty and provide some non-trivial performance guarantees, that support the interest of using multi-step greedy operators. These algorithms assume access to a generative model (Section 5) or to an approximate multiple-step greedy policy (Section 6).

Preliminaries

Our framework is the infinite-horizon discounted Markov Decision Process (MDP). An MDP is defined as the 5-tuple (S, A, P, R, γ) [START_REF] Martin L Puterman | Markov decision processes: discrete stochastic dynamic programming[END_REF], where S is a finite state space, A is a finite action space, P ≡ P (s |s, a) is a transition kernel, R ≡ r(s, a) ∈ [0, R max ] is a reward function, and γ ∈ (0, 1) is a discount factor. Let π : S → P(A) be a stationary policy, where P(A) is a probability distribution on A. Let v π ∈ R |S| be the value of a policy π, defined in state s as v π (s) ≡ E π [ ∞ t=0 γ t r(s t , π(s t ))]. For brevity, we respectively denote the reward and value at time t by r t ≡ r(s t , π t (s t )) and v t ≡ v(s t ). It is known that v π = ∞ t=0 γ t (P π ) t r π = (I -γP π ) -1 r π , with the component-wise values [P π ] s,s P (s | s, π(s)) and [r π ] s r(s, π(s)). Lastly, let

q π (s, a) = E π [ ∞ t=0 γ t r(s t , π(s t )) | s 0 = s, a 0 = a].
(1)

Our goal is to find a policy π * yielding the optimal value v * such that v * = max π (I -γP π ) -1 r π = (I -γP π * ) -1 r π * .

(2)

This goal can be achieved using the three classical operators (equalities hold componentwise):

∀v, π, T π v = r π + γP π v, ∀v, T v = max π T π v, ∀v, G(v) = {π : T π v = T v},
where T π is a linear operator, T is the optimal Bellman operator and both T π and T are γ-contraction mappings w.r.t. the max norm. It is known that the unique fixed points of T π and T are v π and v * , respectively. The set G(v) is the standard set of 1-step greedy policies w.r.t. v.

The h-and κ-Greedy Policies

In this section, we bring forward necessary definitions and results on two classes of multiplestep greedy policies: h-and κ-greedy [START_REF] Efroni | Beyond the one step greedy approach in reinforcement learning[END_REF]. Let h ∈ N\{0}. The h-greedy policy π h outputs the first optimal action out of the sequence of actions solving a nonstationary, h-horizon control problem as follows:

∀s ∈ S, π h (s) ∈ arg max π 0 max π 1 ,..,π h-1 E π 0 ...π h-1 h-1 t=0 γ t r(s t , π t (s t )) + γ h v(s h ) | s 0 = s .
Since the h-greedy policy can be represented as the 1-step greedy policy w.r.t. T h-1 v, the set of h-greedy policies w.r.t. v, G h (v), can be formally defined as follows:

∀v, π, T π h v = T π T h-1 v, ∀v, G h (v) = {π : T π h v = T h v}. Let κ ∈ [0, 1].
The set of κ-greedy policies w.r.t. a value function v, G κ (v), is defined using the following operators:

∀v, π, T π κ v = (I -κγP π ) -1 (r π + (1 -κ)γP π v) ∀v, T κ v = max π T π κ v = max π (I -κγP π ) -1 (r π + (1 -κ)γP π v) (3) ∀v, G κ (v) = {π : T π κ v = T κ v}.
Remark 1 A comparison of (2) and (3) reveals that finding the κ-greedy policy is equivalent to solving a κγ-discounted MDP with a shaped reward r π v,κ

def = r π + (1 -κ)γP π v.
In (Efroni et al., 2018, Proposition 11), the κ-greedy policy was explained to be interpolating over all geometrically κ-weighted h-greedy policies. It was also shown that for κ = 0, the 1-step greedy policy is restored, while for κ = 1, the κ-greedy policy is the optimal policy. Both T π κ and T κ are ξ κ contraction mappings, where

ξ κ = γ(1-κ) 1-γκ ∈ [0, γ].
Their respective fixed points are v π and v * . For brevity, where there is no risk of confusion, we shall denote ξ κ by ξ. Moreover, in [START_REF] Efroni | Beyond the one step greedy approach in reinforcement learning[END_REF] it was shown that both the h-and κ-greedy policies w.r.t. v π are strictly better then π, unless π = π * .

Next, let the κ-optimal q-function be defined as follows,

q π κ (s, a) = max π E π [ ∞ t=0 (κγ) t (r(s t , π (s t )) + γ(1 -κ)v π (s t+1 ) | s 0 = s, a 0 = a]. ( 4
)
The latter is the optimal q-function of the surrogate, γκ-discounted MDP with v π -shaped reward (see Remark 1). Thus, we can obtain a κ-greedy policy, π κ ∈ G κ (v π ), directly from q π κ :

π κ (s) ∈ arg max a q π κ (s, a), ∀s ∈ S.
See that the greedy policy w.r.t. q π κ=0 (s, a) is the 1-step greedy policy since q π κ=0 (s, a) = q π (s, a).

Multi-step Policy Improvement and Soft Updates

In this section, we focus on policy improvement of multiple-step greedy policies, performed with soft updates. Soft updates of the 1-step greedy policy have proved necessary and beneficial in prominent algorithms [START_REF] Vijaymohan | Actor-critic-type learning algorithms for markov decision processes[END_REF]; [START_REF] Kakade | Approximately Optimal Approximate Reinforcement Learning[END_REF]; [START_REF] Schulman | Trust region policy optimization[END_REF]. Here, we begin by describing an intrinsic difficulty in selecting the step-size parameter α ∈ (0, 1] when updating with multiple-step greedy policies such as of h-and κ-greedy. Specifically, denote by π such multiple-step greedy policy w.r.t. v π . Then, π new = (1 -α)π + απ is not necessarily better than π (see Appendix A for the proof).

Theorem 2 For any MDP, let π be a policy and v π its value. Let

π κ ∈ G κ (v π ) and π h ∈ G h (v π ), α ∈ (0, 1]
where κ ∈ [0, 1] and an integer h > 1. Consider the mixture policies

π(α, κ) def = (1 -α)π + απ κ , π(α, h) def = (1 -α)π + απ h .
We have the following equivalences:

1. The inequality v π(α,κ) ≥ v π holds for all MDPs if and only if α ∈ [κ, 1].
2. The inequality v π(α,h) ≥ v π holds for all MDPs if and only if α = 1.

The above inequalities hold entry-wise, with strict inequality in at least one entry unless

v π = v * .
Theorem 2 guarantees monotonic improvement for the 1-step greedy policy as a special case when κ = 0. Hence, we get that for any α ∈ (0, 1], the mixture of any policy π and the 1-step greedy policy w.r.t. v π is monotonically better then π. To the best of our knowledge, this result was not explicitly stated anywhere. Instead, it appeared within proofs of several famous results, e.g, (Konda and Borkar, 1999, Lemma 5.4), (Kakade and Langford, 2002, Corollary 4.2), and (Scherrer and Geist, 2014, Theorem 1).

In the rest of the paper, we shall focus on the κ-greedy policy and extend it to the online and the approximate cases. The discovery that the κ-greedy policy w.r.t. v π is not necessarily strictly better than π will guide us in appropriately devising algorithms.

Online κ-Policy Iteration with Cautious Soft Updates

In [START_REF] Efroni | Beyond the one step greedy approach in reinforcement learning[END_REF], it was shown that using the κ-greedy policy in the improvement stage leads to a converging PI procedure -the κ-PI algorithm. This algorithm repeats i) solving the optimal policy of small-horizon surrogate MDPs with shaped reward, and ii) calculating the value of the optimal policy and use it to shape the reward of next iteration. Here, we devise a practical version of κ-PI, which is model-free, online and runs in two timescales, i.e, performs i) and ii) simultaneously. update q n+1 (s n , a n ) using TD(0) with stepsize α n 5:

δ κ,n = r n + γ(1 -κ)v π n (s n ) + κγ max a q κ,n (s n , a ) -q κ,n (s n , a n ) 6: q κ,n+1 (s n , a n ) ← q κ,n (s n , a n ) + α n δ κ,n 7:
# Slow-timescale updates 8:

π n+1 (s n ) ← π n (s n ) + β n (b sn (q n+1 , q κ,n+1 , π n ) -π n (s n )) 9:
end for 10: return: π The method is depicted in Algorithm 1. It is similar to the asynchronous PI analyzed in [START_REF] Perkins | Asynchronous stochastic approximation with differential inclusions[END_REF], except for two major differences. First, the fast timescale tracks both q π , q π κ and not just q π . Thus, it enables access to both the κ-greedy and 1step-greedy policies. The 1-step greedy policy is attained via the q π (s, a) estimate, which is plugged into a q-learning Watkins and Dayan (1992) update rule for obtaining the κ-greedy policy. The latter essentially solves the surrogate, κγ-discounted, MDP (see Remark 1). The second difference is in the slow timescale; there, the policy is updated using a new operator, b s , as defined below. To better understand this operator, first notice that in Stochastic Approximation methods such as Algorithm 1, the policy is improved using soft updates with decaying stepsizes. However, as Theorem 2 states, monotonic improvement is not guaranteed below a certain stepsize value. Hence, for q, q κ ∈ R |S×A| and policy π, we set b s (q, q κ , π) to be the κ-greedy policy only when assured to have improvement:

b s (q, q κ , π) = a κ (s) if q(s, a κ ) ≥ v π (s), a 1-step (s) else,
where a κ (s) def = arg max a q κ (s, a), a 1-step (s) def = arg max a q(s, a), and v π (s) = a π(a | s)q(s, a). We respectively denote the state and state-action-pair visitation counters after the nth time-step by ν n (s)

def = n k=1 1 s=s k and φ n (s, a) def = n k=1 1 (s,a)=(s k ,a k ) .
The stepsize sequences µ f (•), µ s (•) satisfy the common assumption (B2) in [START_REF] Perkins | Asynchronous stochastic approximation with differential inclusions[END_REF], among which lim n→∞ µ s (n)/µ f (n) → 0. The second moments of {r n } are assumed to be bounded. Furthermore, let ν be some measure over the state space, s.t. ∀s ∈ S, ν(s) > 0.

Then, we assume to have a generative model G(ν, π), from which we sample state s, sample an action a ∼ π(s), apply action a and receive reward r and next state s . The fast-timescale update rules in lines 4 and 6 can be jointly written as a sum of H π κ (q, q κ ) and a martingale difference noise.

Definition 3 Let q, q κ ∈ R |S||A| . Then the mapping H π κ : R 2|S||A| → R 2|S||A| is defined as follows ∀(s, a) ∈ S × A. H π κ (q(s, a), q κ (s, a)) def = r(s, a) + γE s ,a π q(s , a π ) r(s, a) + γ(1 -κ)E s ,a π q(s , a π ) + κγE s max a q κ (s , a )
,

where s ∼ P (• | s, a), a π ∼ π(s ).
The following lemma shows that, given a fixed π, H π κ is a contraction, equivalently to (Perkins and Leslie, 2013, Lemma 5.3) (see Appendix B for the proof).

Lemma 4 H π κ is a γ-contraction in the max-norm. Its unique fixed point is [ q π , q π κ ] , as defined in (1) and(4). Finally, after several intermediate results in Appendix C and relaying on Lemma 4, we establish convergence of Algorithm 1.

Theorem 5 The coupled process (q n , q κ,n , π n ) in Algorithm 1 converges to the limit (q * , q * , π * ), where q * is the optimal q-function and π * is the optimal policy.

For κ = 1, the fast-timescale update rule in line 6 corresponds to that of q-learning Watkins and Dayan (1992). For that κ, Algorithm 1 uses an estimated optimal q-function to update the current policy when improvement is assured. For κ < 1, the estimated κ-optimal q-function (see ( 4)) is used, again with the 'cautions' policy update.

Approximate κ-Policy Iteration with Hard Updates

Theorem 2 establishes the conditions required for guaranteed monotonic improvement of softly-updated multiple-step greedy policies. The algorithm in Section 5 then accounts for these conditions to ensure convergence. Contrarily, in this section, we derive and study an algorithm that perform hard policy-updates. Specifically, we generalize the Policy Search by Dynamic Programming (PSDP) algorithm [START_REF] Andrew Bagnell | Policy search by dynamic programming[END_REF][START_REF] Scherrer | Approximate policy iteration schemes: a comparison[END_REF]. Our result exhibits a performance tradeoff in the choice of κ, with optimal performance bound achieved in intermediate κ ∈ [0, 1] values.

We denote G κ,δ,ν (v) as the set of approximate κ-greedy policies w.r.t. v, with δ approximation error under some probability measure ν.

Definition 6 (Approximate κ-greedy policy) Let

v : S → R be a value function, δ ≥ 0 a real number and ν a distribution over S. A policy π ∈ G κ,δ,ν (v) if νT π κ v ≥ νT κ v -δ.
The approximate κ-greedy oracle assumed here is less restrictive than the one assumed in [START_REF] Efroni | Beyond the one step greedy approach in reinforcement learning[END_REF]. There, a uniform error over states was assumed, whereas here, the error is defined w.r.t. a specific measure, ν.

We follow the line of work of [START_REF] Munos | Error bounds for approximate policy iteration[END_REF][START_REF] Munos | Performance bounds in l_p-norm for approximate value iteration[END_REF][START_REF] Amir-Massoud Farahmand | Error propagation for approximate policy and value iteration[END_REF][START_REF] Scherrer | Approximate policy iteration schemes: a comparison[END_REF][START_REF] Lazaric | Analysis of classificationbased policy iteration algorithms[END_REF] and use concentrability coefficients to specify our performance bounds. This allows a direct comparison of the algorithms proposed here with previously studied approximate 1-step greedy algorithms. Our bounds includes the concentrability coefficient C π * (1) , e.g, Scherrer (2014, Definition 1), as well as two new coefficients C π * κ and C π * (1) κ , defined as follows.

Algorithm 2 κ-PSDP initialize κ ∈ [0, 1], ν, δ, v π 0 , Π = [ ] v ← v π 0 for k = 1, .. do π k ← G κ,ν,δ (v) v ← T π k κ v Π ←Append(Π, π k ) end for return Π Definition 7 (Concentrability coefficients) Let µ, ν be measures over S. Let {c π * (i)} ∞ i=0 be the sequence of the smallest values in [1, ∞)∪{∞} such that for every i, µ P π * i ≤ c π * (i)ν. Let C π * (1) (µ, ν) = (1 -γ) ∞ i=0 γ i c π * (i). Next, let C π * (1) κ (µ, ν) = ξ γ C π * (1) (µ, ν) + (1 -ξ)κc(0). Also, let C π * κ (µ, ν) ∈ [1, ∞) ∪ {∞} be the smallest value s.t. d π * κ,µ ≤ C π * κ (µ, ν)ν, where d π * κ,µ = (1 -ξ)µ(I -ξD π * κ P π * ) -1 is a probability measure and D π κ = (1 -κγ)(I -κγP π ) -1 is a stochastic matrix.
In the definition above, ν is the measure according to which the approximate improvement is guaranteed, while µ specifies the distribution on which one measures the loss

E s∼µ [v * (s) -v π k (s)] = µ(v * -v π k )
that we wish to bound. From Definition 7 it holds that C π * κ=0 (µ, ν) = C π * (µ, ν); the latter was defined in, e.g, Scherrer (2014, Definition 1).

The following proposition sheds light on the behavior of C π * κ (µ, ν); it shows that under certain constructions, C π * κ (µ, ν) decreases1 as κ increases (see proof in Appendix D).

Proposition 8 Let ν(α) = (1 -α)ν + αµ.
Then, for all κ > κ, there exists α * ∈ (0, 1)

such that C π * κ (µ, ν(α * )) ≤ C π * κ (µ, ν). The inequality is strict for C π * κ (µ, ν) > 1. For µ = ν this implies that C π * κ (ν, ν) is a decreasing function of κ.

κ-Policy Search by Dynamic Programming

The κ-PSDP depicted in Algorithm 2 returns a sequence of deterministic policies, Π. Given this sequence, we build a stochastic, non-stationary policy by successively running

N k steps of Π[k], followed by N k-1 steps of Π[k -1],
etc, where {N i } k i=1 are i.i.d. geometric random variables with parameter 1 -κ. Once this process reaches π 0 , it runs π 0 indefinitely. We shall refer to this non-stationary policy as σ κ,k , the value of this policy is

v σ κ,k = T Π[k] κ T Π[k-1] κ . . . T Π[1] κ v π 0 .
This algorithm generalizes the PSDP from [START_REF] Scherrer | Approximate policy iteration schemes: a comparison[END_REF]. The 1-step improvement is replaced with the κ-greedy improvement, and unlike the PSDP the returned policy is random for κ > 0. Its performance bound is given in the following theorem (see proof in Appendix E).

Theorem 9 Let σ κ,k be the policy at the k-th iteration of κ-PSDP and δ be the error as defined in Definition 6. Then

µ(v * -v σ κ,k ) ≤ C π * (1) κ (µ,ν) 1-ξ δ+ξ k Rmax 1-γ . Also, let k = log Rmax δ(1-γ) 1-ξ . Then µ(v * -v σ κ,k ) ≤ C π * κ (µ,ν) (1-ξ) 2 log Rmax (1-γ)δ δ + δ.
For κ = 1 this bound is tighter than κ = 0. The reason is that

C π * (1) (µ, ν) > (1 -γ)c(0)
(see Definition 7), and thus

C π * (1) (µ,ν) 1-γ
δ > c(0)δ. Also, from continuity, this behavior is interpolated for a region around κ = 1, i.e., we have that κ-PSDP is generally better than PSDP. More interestingly, under the constructions in Proposition 8, the second form of bound reveals a strict improvement of the bound as κ increases. By recalling that δ is expected to be monotonically increasing function of κ -solving an MDP with larger horizon is 'harder' [START_REF] Jiang | The dependence of effective planning horizon on model accuracy[END_REF] -we see the bounds demonstrate a performance tradeoff as a function of κ.

An additional advantage of this new algorithm over PSDP is reduced space complexity. This can be seen, e.g., from the 1-ξ in the denominator in the choice of k in the second part of Theorem 9. It shows that, since ξ is a strictly decreasing function of κ, performance is preserved with significantly fewer iterations by increasing κ. Since the size of stored policy Π is linearly dependent on the number of iterations, larger κ improves space efficiency.

Discussion and Future Work

In this work, we introduced and analyzed online and approximate PI methods, generalized to the κ-greedy policy, an instance of a multiple-step greedy policy. Doing so, we discovered two intriguing properties compared to the well-studied 1-step greedy policy, which we believe can be impactful in designing state-of-the-art algorithms. First, successive application of multiple-step greedy policies with a soft, stepsize-based update does not guarantee improvement; see Theorem 2. To mitigate this caveat, we designed an online PI with a 'cautious' improvement operator; see Section 5.

The second property we find intriguing stemmed from analyzing κ generalizations of known approximate hard-update PI methods. In Section 6, we revealed a performance tradeoff in κ, which can be interpreted as a tradeoff between short-horizon bootstrap bias and long-rollout variance. This corresponds to the known λ tradeoff in the famous TD(λ).

The two characteristics above lead to new compelling questions. The first regards improvement operators: would a non-monotonically improving PI scheme necessarily not converge to the optimal policy? Our attempts to generalize existing proof techniques to show convergence in such cases have fallen behind. Specifically, in the online case, Lemma 5.4 in [START_REF] Vijaymohan | Actor-critic-type learning algorithms for markov decision processes[END_REF] does not hold with multiple-step greedy policies; similar issues arise when trying to form a κ-CPI algorithm via, e.g., an attempt to generalize Corollary 4.2 in [START_REF] Kakade | Approximately Optimal Approximate Reinforcement Learning[END_REF]. Another research question regards the choice of the parameter κ given the tradeoff it poses. One possible direction for answering it could be investigating the concentrability coefficients further and attempting to characterize them for specific MDPs, either theoretically or via estimation. Lastly, a next indisputable step would be to empirically evaluate implementations of the algorithms presented here.

Christopher JCH Watkins and Peter Dayan. Q-learning. Machine learning, 8(3-4):279-292, 1992.

Appendix A. Proof of Theorem 2

We start with a generalization of a useful lemma; its original version appeared in, e.g., (Scherrer, 2016, Lemma 10).

Lemma 10 Let v be a value function, π a policy, and κ ∈ [0, 1]. Then

T π κ v -v = (I -κγP π ) -1 (T π v -v). Proof
The proof is a straightforward generalization of the proof in (Scherrer, 2016, Lemma 10), and (Kakade and Langford, 2002, Remark 6.1).

T π κ v -v = (I -κγP π ) -1 (r π + (1 -κ)γP π v) -v = (I -κγP π ) -1 (r π + (1 -κ)γP π v -(I -κγP π )v) = (I -κγP π ) -1 (r π + γP π v -v) = (I -κγP π ) -1 (T π v -v).
This elementary lemma relates the 'κ-advantage' to the 1-step advantage and is useful to prove Theorem 2 and some following results.

First, since π(α, κ) = (1 -α)π + απ κ , we have that

P π(α,κ) = (1 -α)P π + αP πκ , r π(α,κ) = (1 -α)r π + αr πκ ; thus, since v π is the fixed-point of T π , T π(α,κ) v π = (1 -α)T π v π + αT πκ v π = (1 -α)v π + αT πκ v π . ( 5
)
Using this, we now prove the first statement of Theorem 2.

v π(α,κ) -v π = (I -γP π(α,κ) ) -1 (T π(α,κ) v π -v π ) = α(I -γP π(α,κ) ) -1 (T πκ v π -v π ) = α(I -γP π(α,κ) ) -1 (I -κγP πκ )(I -κγP πκ ) -1 (T πκ v π -v π ) = α(I -γP π(α,κ) ) -1 (I -κγP πκ )(T πκ κ v π -v π ) = α(I -γP π(α,κ) ) -1 (I -γP π(α,κ) + γ(P π(α,κ) -κP πκ ))(T πκ κ v π -v π ) = α(I + γ(I -γP π(α,κ) ) -1 ((1 -α)P π + (α -κ)P πκ )(T πκ κ v π -v π ). ( 6
)
For the first relation we use Lemma 10 with κ = 1 and the fact that, by definition, α,κ) . For the second relation we use (5), for the fourth we again use Lemma 10, and for the last relation we use that P π(α,κ) -κP πκ = (1 -α)P π + (α -κ)P πκ .

T π(α,κ) κ=1 v π(α,κ) = v π(
Next, we show that for α ≥ κ, all terms in (6) are component-wise bigger than or equal to zero. First, using a Taylor expansion, (I -γP π(α,κ) ) -1 = t γ t (P π(α,κ) ) t ≥ 0 componentwise, since it is a weighted sum of transition matrices with positive weights. The same applies for (1 -α)P π + (α -κ)P πκ , when α ≥ κ. Thus, for α ≥ κ, Efroni et al., 2018, Lemma 3). Thus, T πκ κ v π -v π ≥ 0. This concludes the proof for the first statement, for the κ-greedy policy.

(I + γ(I -γP π(α,κ) ) -1 ((1 -α)P π + (α -κ)P πκ ) ≥ 0 component-wise. Lastly, since π κ ∈ G κ (v π ), v π = T π κ v π ≤ T κ v π = T πκ κ v π , with equality hold- ing if and only if v π = v * (
For the κ-greedy policy part of the proof for the second statement, we now provide more details on the counterexample presented in Section 4. For convenience, we bring the MDP example here again in Fig. 1. Consider the mixture of the "hesitant" and "confident" policies: π(α, κ = 1) = (1 -α)π 0 + απ(α, κ = 1). It can be shown that its value is

v π(α,κ=1) (s 0 ) = γα 1 -γ(1 -α) v π(α,κ=1) (s 1 ), v π(α,κ=1) (s 1 ) = γ -c(1 -α) + α 1 -γ .
Thus, we deduce that for any α ∈ (0, 1) and

c > α 1 -α , ( 7
)
v π(α,κ=1) (s 0 ) < v π (s 0 ) = 0, i.e, the mixture policy, π(α, κ = 1), is not strictly better then π 0 .

We now find the conditions to ensure that the κ-greedy policy w.r.t. v π 0 is the optimal policy; this will generalize the above construction, made for κ = 1, to any κ ∈ [0, 1]. Observe that for any c > 0 and κ it holds that π κ (s 1 ) = a 1 = π * (s 1 ), where π κ ∈ G κ (v π 0 ). Thus, we solely need to consider the policy which is different than π * at state s 0 , π(s 0 ) = a 0 = π * (s 0 ) and π(s 1 ) = π * (s 1 ). To find which condition ensures the κ-greedy policy w.r.t. v π 0 is π * (and not π), we require

T π * κ v π 0 (s 0 ) ≥ T π κ v π 0 (s 0 ). ( 8
)
Satisfying this condition insures that π * ∈ G κ (v π 0 ). By definition,

T π * κ v π 0 (s 0 ) = E π * t (κγ) t (r(s t , π * (s t )) + γ(1 -κ)v π 0 (s t+1 ) | s t=0 = s 0 =(κγ) 0 (γ(1 -κ)v π 0 (s 1 ))) + (κγ) 1 (γ(1 -κ)v π 0 (s 2 )) + ∞ t=2 (κγ) t (1 + v π 0 (s 2 )) =(κγ) 0 γ(1 -κ)(- γc 1 -γ ) + (κγ) 1 γ(1 -κ) 1 1 -γ + ∞ t=2 (κγ) t (1 + γ(1 -κ) 1 1 -γ ) =γ(1 -κ)(- γc 1 -γ ) + κγ γ 1 -γ . ( 9
)
Similarly, and since π(s 0 ) = a 0 , we have that

T π κ v π 0 (s 0 ) = 0 (10)
Plugging ( 9) and ( 10) into (8), we get the condition

c ≤ κ 1 -κ . ( 11
) s 0 s 1 s 2 s 3 a 0 0 a 1 0 a 0 0 a 1 0 a 0 1 a 0 -c
Figure 1: The Tightrope Walking MDP used in the proof of Theorem 2. This class of MDPs is parametrized by c > 0.

To finalize the counterexample and show that strict policy improvement is not guaranteed, we choose c such that both ( 7) and ( 11) are satisfied. Such feasible choice exists when α < κ, due to the monotonicity of x 1-x . The monotonic improvement of π(α, h) for α = 1 was proved in [START_REF] Efroni | Beyond the one step greedy approach in reinforcement learning[END_REF], Lemma 1). To build the counter example, again consider the Tightrope MDP. Let π 0 be the 'hesitant' policy. For any γ ∈ (0, 1), h > 1, it holds that π * ∈ G h (v π 0 ). Thus, it suffices to satisfy (7) alone to show that π(α, h) = (1 -α)π 0 + απ * is not monotonically better then π. Large enough c value ensures that.

Appendix B. Proof of Lemma 4

We start by showing the contraction property of H π κ . Let (s, a) be a fixed state-action pair, Q 1 , Q 2 ∈ R 2|S×A| . For any state-action pair (s, a), Q i (s, a) is a two-component vector. We denote its first component by q i (s, a) and its second component by q i,κ (s, a). See that

||q 1 -q 2 || ∞ ≤ ||Q 1 -Q 2 || ∞ (12) ||q 1,κ -q 2,κ || ∞ ≤ ||Q 1 -Q 2 || ∞ . ( 13
)
Taking a component-wise absolute value, we have that

|H π κ Q 1 -H π κ Q 2 |(s, a) = |H π κ (q 1 , q 1,κ ) -H π κ (q 2 , q 2,κ )|(s, a) = γ |E s ,a π [q 1 (s , a π )) -q 2 (s , π(s ))] | |(1 -κ)E s ,a π [q 1 (s , a π ) -q 2 (s , a π ))] + κE s [max a q 1,κ (s , a ) -max a q 2,κ (s , a )]| , where s ∼ P (• | s, a), a π ∼ π(s ).
Let us focus on the first component of the above vector. We have that

γ|E s ,a π q 1 (s , a π ) -q 2 (s , a π ) | ≤ γ||q 1 -q 2 || ∞ ≤ γ||Q 1 -Q 2 || ∞ ,
where we used the standard bound, |E[X]| ≤ ||X|| ∞ and ( 12). Similarly, for the second component, we have that

γ (1 -κ)E s ,a π q 1 (s , a π ) -q 2 (s , a π ) + κE s ,a [max a q 1,κ (s , a ) -max a q 2,κ (s , a )] ≤γ (1 -κ)|E s ,a π q 1 (s , a π ) -q 2 (s , a π ) | + κE s ,a [| max a q 1,κ (s , a ) -max a q 2,κ (s , a )|] ≤γ (1 -κ)|E s ,a π q 1 (s , a π ) -q 2 (s , a π ) | + κE s ,a [max a |q 1,κ (s , a ) -q 2,κ (s , a )|] ≤γ ((1 -κ)||q 1 -q 2 || ∞ + κ||q 1,κ -q 2,κ || ∞ ) ≤γ ((1 -κ)||Q 1 -Q 2 || ∞ + κ||Q 1 -Q 2 || ∞ ) = γ||Q 1 -Q 2 || ∞ ,
where for the first relation we used the triangle inequality, for the second we used the standard bound

| max x∈X f (x) -max x∈X g(x)| ≤ max x∈X |f (x) -g(x)
|, for the third we used the bound |E[X]| ≤ ||X|| ∞ , and for the last ( 12)-( 13).

By taking the sup-norm on both sides, we get that

||H π κ Q 1 -H π κ Q 2 || ∞ ≤ γ||Q 1 -Q 2 || ∞ ;
i.e., the operator H π κ is a γ contraction mapping in the max-norm. We now show that the fixed-point of H κ is (q π , q π κ ), i.e., H κ (q π , q π κ ) = (q π , q π κ ). For ease, we rewrite its form as in Definition 3. For any s, a we have that,

H π κ (q π (s, a), q π κ (s, a)) def = r(s, a) + γE s ,a π q π (s , a π ) r(s, a) + γ(1 -κ)E s ,a π q π (s , a π ) + κγE s max a q π κ (s , a ) , ( 14
)
where

s ∼ P (• | s, a), a π ∼ π(s ).
It is clear that the the first component of ( 14) is q π (s), since it satisfies, q π κ (s, a) = r(s, a) + γE s ,a π q π (s , a π ).

Since q π κ is optimal q-function of the κγ-discounted, with a shaped reward (see Remark 1)

r eff (s, a, s ) = r(s, a) + γ(1 -κ)v π (s ),
it is the solution of the following fixed-point equation,

q π κ (s, a) = E s [r eff (s, a, s ) | s, a] + γκE s [max a q π κ (s , a ) | s, a] = E s [r(s, a) + γ(1 -κ)v π (s ) | s, a] + γκE s [max a q π κ (s , a ) | s, a] = E s ,a∼π(s ) [r(s, a) + γ(1 -κ)q π (s , a ) | s, a] + γκE s [max a q π κ (s , a ) | s, a].
The final equation is the second-component of H κ (q π , q π κ )(s, a) of ( 14), and indeed, q π κ solves the equation.

C.1 Lipschitzness of the Slow Time Scale Fixed-Point

Before following the main lemmas in [START_REF] Perkins | Asynchronous stochastic approximation with differential inclusions[END_REF] and showing they hold for Online κ-PI (Algorithm 1), we shall show that the solution of the fast-time scale ODE (found using a fixed-point argument), [q π , q π κ ], is Lipschitz-continuous in the slow time-scale iterate, π.

Lemma 11 Let π : S ×A → [0, 1] be a stochastic policy. For any π 1 , π 2 and q 1 , q 2 ∈ R |S×A| , let

||π 1 -π 2 || ∞ def = max s a |π 1 (a | s) -π 2 (a | s)|, ||q 1 -q 2 || ∞ def = max s,a |q 1 (s, a) -q 2 (s, a)|.
Then q π and q π κ are Lipschitz-continuous in π in the max-norm; i.e.,

||q π 1 -q π 2 || ∞ ≤ L a ||π 1 -π 2 || ∞ , ||q π 1 κ -q π 2 κ || ∞ ≤ L b ||π 1 -π 2 || ∞ , where L a , L b > 0, are functions of γ, κ, R max . Proof We start by proving that ||v π 1 -v π 2 || ∞ ≤ L||π 1 -π 2 || ∞ , i.e, v π is Lipschitz in π. ||v π 1 -v π 2 || ∞ = ||T π 1 v π 1 -T π 2 v π 2 || ∞ ≤ ||T π 1 v π 1 -T π 1 v π 2 + T π 1 v π 2 -T π 2 v π 2 || ∞ ≤ ||T π 1 v π 1 -T π 1 v π 2 || ∞ + ||T π 1 v π 2 -T π 2 v π 2 || ∞ ≤ γ||v π 1 -v π 2 || ∞ + ||T π 1 v π 2 -T π 2 v π 2 || ∞ , (15)
where the last relation is due to the fact T π 1 is a γ-contraction. We continue by calculating

|T π 1 v π 2 -T π 2 v π 2 |(s). |T π 1 v π 2 -T π 2 v π 2 |(s) ≤ | a π 1 (a | s) -π 2 (a | s) r(s, a)| + γ| s (P π 1 s ,s -P π 2 s ,s )v π 2 (s )|. ( 16
)
We bound each term in ( 16). The first term can be bounded by,

| a π 1 (a | s) -π 2 (a | s) r(s, a)| ≤ a | π 1 (a | s) -π 2 (a | s) ||r(s, a)| ≤ R max max s a |(π 1 (a | s) -π 2 (a | s))| = R max ||π 1 -π 2 || ∞ . ( 17
)
In the first relation we used the triangle inequality and in the second inequality the fact that |r(s, a)| is bounded by R max .

The second term in ( 16) can be bounded by,

| s (P π 1 s ,s -P π 2 s ,s )v π 2 (s )| = | s ,a P (s | s, a)(π 1 (a | s) -π 2 (a | s))v π 2 (s )| ≤ a s P (s | s, a)|(π 1 (a | s) -π 2 (a | s))v π 2 (s )| ≤ a s P (s | s, a)|(π 1 (a | s) -π 2 (a | s))||v π 2 (s )| ≤ a s P (s | s, a)|(π 1 (a | s) -π 2 (a | s))| R max 1 -γ = a |(π 1 (a | s) -π 2 (a | s))| R max 1 -γ s P (s | s, a) = a |(π 1 (a | s) -π 2 (a | s))| R max 1 -γ ≤ max s a |(π 1 (a | s) -π 2 (a | s))| R max 1 -γ = R max 1 -γ ||π 1 -π 2 || ∞ (18)
In the first relation we used the triangle inequality, in the forth relation we used the fact that for any π and s, v π (s) ≤ Rmax 1-γ , and in the fifth relation the fact that for any s and a, P (s | s, a) is a probability function, thus sums to one.

Using ( 17), ( 18) to bound ( 16) yields that for any s,

|T π 1 v π 2 -T π 2 v π 2 |(s) ≤ R max 1 -γ ||π 1 -π 2 || ∞ . Thus, ||T π 1 v π 2 -T π 2 v π 2 || ∞ ≤ Rmax 1-γ ||π 1 -π 2 || ∞ .
Plugging this bound into (15) and rearranging yields,

||v π 1 -v π 2 || ∞ ≤ R max (1 -γ) 2 ||π 1 -π 2 || ∞ , (19)
giving that L = Rmax (1-γ) 2 . We continue by analysing ||T κ v π 1 -T κ v π 2 || ∞ . We remind the reader that T κ v π satisfies the following fixed-point equation:

T κ v π (s) = max a r(s, a) + γ(1 -κ) s P (s | s, a)v π (s ) + κγ s P (s | s, a)(T κ v π )(s ) def = T π κ T κ v π (s)
, where we defined the 'optimal' Bellman operator of the surrogate MDP to be T π κ (see Remark 1). Furthermore, since this operator is the optimal Bellman operator of a κγdiscounted MDP, it is a κγ contraction mapping. We now use a similar technique as the above to show

||T κ v π 1 -T κ v π 2 || ∞ ≤ L κ ||π 1 -π 2 || ∞ , i.e, T κ v π is Lipschitz in π. ||T κ v π 1 -T κ v π 2 || ∞ = || T π 1 κ T κ v π 1 -T π 2 κ T κ v π 2 || ∞ ≤ || T π 1 κ T κ v π 1 -T π 1 κ T κ v π 2 || ∞ + || T π 1 κ T κ v π 2 -T π 2 κ T κ v π 2 || ∞ ≤ κγ||T κ v π 1 -T κ v π 2 || ∞ + || T π 1 κ T κ v π 2 -T π 2 κ T κ v π 2 || ∞ .
We now bound the second term.

| T π 1 κ T κ v π 2 -T π 2 κ T κ v π 2 |(s) ≤ max a γ(1 -κ)| s P (s | s, a)(v π 1 -v π 2 )(s )| ≤ max a γ(1 -κ) s P (s | s, a)|v π 1 -v π 2 |(s ) ≤ max a γ(1 -κ) s P (s | s, a)||v π 1 -v π 2 || ∞ = γ(1 -κ)||v π 1 -v π 2 || ∞ ,
where we used the definition of T π κ and the identity

| max x∈X f (x) -max x∈X g(x)| ≤ max x∈X |f (x) -g(x)
| in the first relation and the triangle inequality in the second.

Using ( 19), we have

||T κ v π 1 -T κ v π 2 || ∞ ≤ γ(1 -κ) 1 -κγ ||v π 1 -v π 2 || ∞ ≤ γ(1 -κ) 1 -κγ R max (1 -γ) 2 ||π 1 -π 2 || ∞ .
These results transform to results on q π and q π κ as follows. Starting with q π ,

|q π 1 -q π 2 |(s, a) = |r(s, a) + γ s P (s | s, a)v π 1 -r(s, a) -γ s P (s | s, a)v π 2 | = γ| s P (s | s, a)(v π 1 -v π 2 )| ≤ γ||v π 1 -v π 2 || ∞ .
By taking the max-norm both sides we get the result since ||v π 1 -v π 2 || ∞ was shown to be Lipschitz in π.

Next, for q π κ we have

|q π 1 κ -q π 2 κ |(s, a) =|γ(1 -κ) s P (s | s, a)(v π 1 (s ) -v π 2 (s )) + κγ s P (s | s, a)(T κ v π 1 -T κ v π 2 )(s )| ≤γ(1 -κ)||v π 1 (s ) -v π 2 (s )|| ∞ + κγ||T κ v π 1 -T κ v π 2 || ∞ .
By taking the max-norm on both sides we get the result since, as shown above, both

||v π 1 -v π 2 || ∞ and ||T κ v π 1 -T κ v π 2 || ∞ are Lipschitz in π.
Finally, since the vector space is finite (due to the finite state and action space), all L p norms are equivalent. Thus, the Lipschitzness result applies in any L p norm as well.

C.2 Improvement Step

Here, we prove an equivalent lemma to (Perkins and Leslie, 2013, Lemma 5.4) which shows that the mean value of the process improves. Denote b s ≡ b s (q π , q π κ , π) as the policy defined in the Algrorithm 1. By using Lemma 10 and setting κ = 0 we have that

v (1-α)π+αbs -v π = α(I -γP (1-α)π+αbs ) -1 (T bs v π -v π ).
We see that the following relation holds for any κ ∈ [0, 1],

(I -γP π ) -1 = 1 1 -κ ((I -ξ κ D π κ P π ) -1 -κI).
Plugging this relation into the previous one we get,

(I -ξ κ D π κ P π ) -1 = κ I + (1 -κ )(I -γP π ) -1 = κ I + 1 -κ 1 -κ ((I -ξ κ D π κ P π ) -1 -κI) = κ -κ 1 -κ I + 1 -κ 1 -κ (I -ξ κ D π κ P π ) -1 .
We are now ready to prove Lemma 8. Assume a constant C π * κ (µ, ν) < ∞ such that,

d π * κ,µ = (1 -ξ)µ(I -ξD π * κ ) -1 < C π * κ (µ, ν)ν. ( 20
)
Given that, we shall calculate C π * κ (µ, ν) where κ > κ.

d π * κ ,µ = (1 -ξ κ )µ(I -ξD π * κ ) -1 = (1 -ξ κ ) κ -κ 1 -κ µ + 1 -κ 1 -κ µ((I -ξ κ D π κ P π ) -1 ) ≤ 1 -ξ κ 1 -κ (κ -κ)µ + 1 -κ 1 -ξ κ C π * κ (µ, ν)ν = 1 -ξ κ 1 -κ (κ -κ + 1 -κ 1 -ξ κ C π * κ (µ, ν)) (α * µ + (1 -α * )ν) def = C π * κ (µ, ν(α))ν(α),
where we used Lemma 12 in the first line, Equation 20 in the second line, and defined α * = (1 +

1-κ (1-ξκ)(κ -κ) C π * κ (µ, ν))) -1 ∈ (0, 1) and C π * κ (µ, ν(α * )) = 1-ξ κ 1-κ (κ -κ + 1-κ 1-ξκ C π * κ (µ, ν))
. By plugging the expressions of ξ κ , ξ κ we see that,

C π * κ (µ, ν(α * )) -C π * κ (µ, ν) = 1 -ξ κ 1 -κ (κ -κ + ( 1 -κ 1 -ξ κ - 1 -κ 1 -ξ κ )C π * κ (µ, ν)) = 1 -ξ κ 1 -κ (κ -κ)(1 -C π * κ (µ, ν)). ( 21
)
Since C π * κ (µ, ν) ≥ 1 and

1-ξ κ 1-κ (κ -κ) > 0 we get that C π * κ (µ, ν(α * )) -C π * κ (µ, ν) ≤ 0, where the inequality is strict for C π * κ (µ, ν) > 1. Finally, since for µ = ν it holds that ν(α * ) = (1 -α * )ν + α * ν = ν for, we get that C π * κ (ν, ν) is a decreasing function of κ.

Appendix E. Proof of Theorem 9

We first prove two technical lemmas.

Lemma 13 Let π be a policy, κ ∈ [0, 1], γ ∈ (0, 1) and i ∈ N\{0}. Then

(ξD π κ P π ) i = ∞ t=i-1 t! (i -1)!(t -(i -1))! γ t+1 (1 -κ) i κ t-(i-1) (P π ) t+1 ,
where, as also given in Definition 7,

D π κ = (1 -κγ)(I -κγP π ) -1 .
Proof First, for any x ∈ R s.t |x| < 1 and i ∈ N\{0} we have that,

(1 -x) -i = ∞ t=i-1 t! (i -1)!(t -(i -1))! x t-(i-1) .
Since it holds that ||γκP π || = γκ < 1, where || • || is the spectral norm of the matrix, we can use the same Taylor expansion when replacing x with γκP π . Thus,

(I -γκP π ) -i = ∞ t=i-1 t! (i -1)!(t -(i -1))! (γκ) t-(i-1) (P π ) t-(i-1) . ( 22
)
Since D π κ = (1 -κγ)(I -π ) -1 and any matrix commutes with any function of itself we have that,

(ξD π κ P π ) i = γ i (1 -κ) i (D π κ P π ) i = γ i (1 -κ) i ((I -κγP π ) -1 ) i (P π ) i .
By using ( 22) and packing the terms we conclude the proof.

(ξD

π κ P π ) i = γ i (1 -κ) i (I -κγP π ) -i (P π ) i = ∞ t=i-1 t! (i -1)!(t -(i -1))! γ t+1 (1 -κ) i κ t-(i-1) (P π ) t+1 Lemma 14 Let κ ∈ [0, 1], γ ∈ (0, 1), n ∈ N ∪ {∞} and f : N → R. Then ∞ l=0 n-1 i=1 ∞ t=i-1 t! (i -1)!(t -(i -1))! γ t+l+1 κ t-(i-1) (1 -κ) i f (t + 1 + l) ≤(1 -κ) ∞ l=0 n-2 t=0 γ t+l+1 f (t + 1 + l) + g(κ)(1 -κ)κ ∞ l=0 ∞ t=n-1 γ t+l+1 f (t + 1 + l),
where g(κ) is a bounded function of κ. When n → ∞ the second term vanishes.

Proof We start by exchanging the summation indices i and t. In order to do so, we decouple the summation to two sums. The range of the indices of the first sum is t ∈ {0, .., n -2} and i ∈ {1, .., t + 1} and the range of the indices of the second sum is t ∈ {n -1, .., ∞} and i ∈ {1, .., n -1}

∞ l=0 n-1 i=1 ∞ t=i-1 t! (i -1)!(t -(i -1))! γ t+l+1 κ t-(i-1) (1 -κ) i f (t + 1 + l) = ∞ l=0 n-2 t=0 γ t+l+1 f (t + 1 + l) t+1 i=1 t! (i -1)!(t -(i -1))! κ t-(i-1) (1 -κ) i (23) + ∞ l=0 ∞ t=n-1 γ t+l+1 f (t + 1 + l) n-1 i=1 t! (i -1)!(t -(i -1))! κ t-(i-1) (1 -κ) i . ( 24
)
Let us bound the first sum first (23),

∞ l=0 n-2 t=0 γ t+l+1 f (t + 1 + l) t+1 i=1 t! (i -1)!(t -(i -1))! κ t-(i-1) (1 -κ) i = ∞ l=0 n-2 t=0 γ t+l+1 f (t + 1 + l) t i=0 t! i!(t -i)! κ t-i (1 -κ) i+1 =(1 -κ) ∞ l=0 n-2 t=0 γ t+l+1 f (t + 1 + l),
where in the first line we changed the index summation i ← i -1 and in the second line we used the binomial identity

t i=0 t! i!(t-i)! κ t-i (1 -κ) i = (1 -κ + κ) t = 1.
In order to bound the second term (24) we define the following function, g :

[n -1, ∞) → R, g(t) def = n-2 i=0 t! i!(t -i)! κ t-i (1 -κ) i .
The function g(t) is a sum of polynomial terms multiplied by a geometric decaying term, κ t . Thus, this function is bounded from above, i.e, exists t * ∈ [n -1, ∞) such that g(t) ≤ g(t * ), ∀t ∈ [n -1, ∞). For such t * , by construction, we have that

n-1 i=1 t! (i -1)!(t -(i -1))! κ t-(i-1) (1 -κ) i = (1 -κ) n-2 i=0 t! i!(t -i))! κ t-i (1 -κ) i ≤ (1 -κ) n-2 i=0 t * ! i!(t * -i)! κ t * -i (1 -κ) i = (1 -κ)κ t * -(n-2) n-2 i=0 t * ! i!(t * -i)! κ (n-2)-i (1 -κ) i ≤ (1 -κ)κ n-2 i=0 t * ! i!(t * -i)! κ (n-2)-i (1 -κ) i
where the last line holds since for κ ∈

[0, 1], t * ∈ [n -1, ∞) it holds that κ t * -(n-2) ≤ κ. We now define g(κ) def = n-2 i=0 t * ! i!(t * -i)! κ (n-2)-i (1 -κ) i
, and observe that it is a bounded function of κ ∈ [0, 1], since it is a sum of positive powers of κ. Thus, ( 24) is bounded by

∞ l=0 ∞ t=n-1 γ t+l+1 f (t + 1 + l) n-1 i=1 t! (i -1)!(t -(i -1))! κ t-(i-1) (1 -κ) i ≤g(κ)(1 -κ)κ ∞ l=0 ∞ t=n-1 γ t+l+1 f (t + 1 + l)
Finally, for the case n = ∞ observe we can repeat the same analysis we did for the first term (23) without the need to decouple to two sums. Thus, for this case, the bound on the first term, with n = ∞, bounds the expression.

Lemma 15 Let κ ∈ [0, 1]. For any sequence of policies {π k-i } k-1 i=0 , optimal policy π * , and error vectors which satisfy ν δi ≤ δ, ,

κ P π * ) i δi ≤ k 1 -κγ 1 -γ C π * κ (µ, ν)δ. ( 26
)
Proof We begin proving the first statement. For i > k -1, we define vectors δi s.t. ν δi ≤ δ. Thus,

k-1 i=0 µ(ξD π * κ P π * ) i δi ≤ µ δ0 + ∞ i=1 µ(ξD π * κ P π * ) i δi . ( 27
)
For the first term in (27),

µ δ0 ≤ c(0)ν δ0 ≤ c(0)δ, ( 28
)
where we used Definition 7 and then Definition 6.

For the second term in (27), we have

∞ i=1 µ(ξD π * κ P π * ) i δi = ∞ i=1 ∞ t=i-1 t! (i -1)!(t -(i -1))! γ t+1 (1 -κ) i κ t-(i-1) µ(P π * ) t+1 δi ≤ ∞ i=1 ∞ t=i-1 t! (i -1)!(t -(i -1))! γ t+1 (1 -κ) i κ t-(i-1) c π * (t + 1)δ ≤(1 -κ) ∞ t=0 γ t+1 c π * (t + 1)δ =(1 -κ) ∞ t=0 γ t c π * (t)δ -(1 -κ)c(0)δ = (1 -κ)C π * (1) (µ, ν) 1 -γ δ -(1 -κ)c(0)δ. ( 29
)
For the first relation we apply Lemma 13, for the second we use the definition of π * (i)} ∞ i=0 and use ν δi ≤ δ. For the third relation we apply Lemma 14 with n = ∞, f (•) = c π * (•) and drop the l summation. Summing the terms in ( 28) and ( 29), we get

k-1 i=0 µ(ξD π * κ P π * ) i δi ≤ 1 1 -γ (1 -κ)C π * (1) (µ, ν) + (1 -γ)κc(0) δ = 1 -κγ 1 -γ C π * (1) κ (µ, ν)δ,
where we identify C π * (1) κ (µ, ν) to be the same expression as in Definition 7. For the second statement of the lemma, (26), we continue by using the identity (ξD π κ P π * ) i ≤ (I -ξD π * κ P π * ) -1 .

k-1 i=0 µ(ξD π * κ P π * ) i δi ≤ k-1 i=0 µ(I -ξD π * κ P π * ) -1 δi ≤ k-1 i=0 C π * κ (µ, ν) 1 -ξ ν δi ≤ k C π * κ (µ, ν) 1 -ξ δ = k 1 -κγ 1 -γ C π * κ (µ, ν)δ,
where the second relation holds due to the definition of C π * κ (µ, ν).

To prove Theorem 9, we follow the arguments of (Scherrer, 2014, Appendix A), while using the operators T π κ instead of T π and the approximate operator defined in Definition 6, and then use Lemma 15. We define the component-wise error at the i-th iteration, δi , which satisfies ν δi ≤ δ. We have that for all k,

v * -v σ κ,k = T π * κ v * -T π * κ v σ k-1 + T π * κ v σ k-1 -T π k κ v σ k-1 ≤ ξD π * κ P π * (v * -v σ k-1 ) + δk .
Thus, by induction on k, we obtain:

v * -v σ κ,k ≤ k-1 i=0 (ξD π * κ P π * ) i δi + (ξD π * κ P π * ) k (v * -v π 0 ) ≤ k-1 i=0 (ξD π * κ P π * ) i δi + ξ k R max 1 -γ
We can directly bound this term by applying Lemma 15. The two statements in that lemma lead to the two statements in Theorem 9. For the second statement, we carefully choose the iteration number k to make the last term smaller than δ:

k =     log Rmax δ(1-γ) 1 -ξ     =     (1 -κγ) log Rmax δ(1-γ) 1 -γ     . ( 30
)
By doing so we see that ξ k * Rmax 1-γ < δ and obtain the second statement of the result.

A smaller coefficient is obviously better. The best value for any concentrability coefficient is 1.

Appendix C. Proof of Theorem 5

The proof of Theorem 5 follows the proof in (Perkins and Leslie, 2013, Section 5.1), with several generalizations given below. Thus, by taking the limit α → 0 we have

where the last inequality is since T bs v π -v π ≥ 0 by construction and (I -γP π ) -1 ≥ 0 component-wise. We thus get that

C.3 Convergence of the Algorithm

We define the same Lyapunov function as defined in (Perkins and Leslie, 2013, Lemma 5.5).

Due to previous section it is indeed a Lyapunov function since its derivative is negative and the function is bigger than 0 by construction. The presence of the Lyapunov function leads to the convergence of the policy to the optimal policy, similarly to (Perkins and Leslie, 2013, Corollary 5.6), which leads to the convergence of q π to q * . Lastly, since et al., 2018, Lemma 4) we have that,

which concludes the proof.

Appendix D. Proof of Lemma 8

We first prove a useful lemma that relates the (unnormalized) future distribution, measured in different κ scales.

Lemma 12 For any policy π and κ, κ ∈ [0, 1],

Proof We prove the lemma by using the definition and by some algebraic manipulations.

= (I -γP π ) -1 -κ γP π (I -γP π ) -1 = (I -γP π ) -1 -κ (I + γP π (I -γP π ) -1 -I)

= (I -γP π ) -1 -κ ((I -γP π ) -1 -I)


Matthieu Geist
email: matthieu.geist@univ-lorraine.fr

Bruno Scherrer
email: bruno.scherrer@inria.fr

Anderson Acceleration for Reinforcement Learning

Keywords:

acceleration is an old and simple method for accelerating the computation of a fixed point. However, as far as we know and quite surprisingly, it has never been applied to dynamic programming or reinforcement learning. In this paper, we explain briefly what Anderson acceleration is and how it can be applied to value iteration, this being supported by preliminary experiments showing a significant speed up of convergence, that we critically discuss. We also discuss how this idea could be applied more generally to (deep) reinforcement learning.

Introduction

Reinforcement learning (RL) [START_REF] Richard | Reinforcement learning: An introduction[END_REF] is intrinsically linked to fixed-point computation: the optimal value function is the fixed point of the (nonlinear) Bellman optimality operator, and the value function of a given policy is the fixed point of the related (linear) Bellman evaluation operator. Most of the time, these fixed points are computed recursively, by applying repeatedly the operator of interest. Notable exceptions are the evaluation step of policy iteration and the least-squares temporal differences (LSTD) algorithm 1 [START_REF] Bradtke | Linear Least-Squares algorithms for temporal difference learning[END_REF]. [START_REF] Donald G Anderson | Iterative procedures for nonlinear integral equations[END_REF] acceleration (also known as Anderson mixing, Pulay mixing, direct inversion on the iterative subspace or DIIS, among others 2 ) is a method that allows speeding up the computation of such fixed points. The classic fixed-point iteration applies repeatdly the operator to the last estimate. Anderson acceleration considers the m previous estimates. Then, it searches for the point that has minimal residual within the subspace spanned by these estimates, and applies the operator to it. This approach has been successfully applied to fields such as electronic structure computation or computational chemistry, but it has never been applied to dynamic programming or reinforcement learning, as far as we know. For more about Anderson acceleration, refer to Walker and Ni (2011), for example.

1. In the realm of deep RL, as far as we know, all fixed points are computed iteratively, there is no LSTD. 2. Anderson acceleration and variations have been rediscovered a number of times in various communities in the last 50 years. Walker and Ni (2011) provide a brief overview of these methods, and a close approach has been recently proposed in the machine learning community [START_REF] Scieur | Regularized nonlinear acceleration[END_REF].

Anderson Acceleration for Value Iteration

In this section, we briefly review Markov decision processes, value iteration, and show how Anderson acceleration can be used to speed up convergence.

Value Iteration

Let ∆ X be the set of probability distributions over a finite set X and Y X the set of applications from X to the set Y . By convention, all vectors are column vectors. A Markov Decision Process (MDP) is a tuple {S, A, P, R, γ}, where S is the finite state space, A is the finite action space, P ∈ (∆ S ) S×A is the Markovian transition kernel (P (s |s, a) denotes the probability of transiting to s when action a is applied in state s), R ∈ R S×A is the bounded reward function (R(s, a) represents the local benefit of doing action a in state s) and γ ∈ (0, 1) is the discount factor.

A stochastic policy π ∈ (∆ A ) S associates a distribution over actions to each state (deterministic policies being a special case of this). The policy-induced reward and transition kernels, R π ∈ R S and P π ∈ (∆ S ) S , are defined as

R π (s) = E π(.|s) [R(s, A)] and P π (s |s) = E π(.|s) [P (s |s, A)].
The quality of a policy is quantified by the associated value function v π ∈ R S :

v π (s) = E[ t≥0 γ t R π (S t )|S 0 = s, S t+1 ∼ P π (.|S t )].
The value v π is the unique fixed point of the Bellman operator T π , defined as

T π v = R π + γP π v for any v ∈ R S .
Let define the second Bellman operator T as, for any v ∈ R S , T v = max π∈(∆ A ) S T π v. This operator is a γ-contraction (in supremum norm), so the iteration v k+1 = T v k converges to its unique fixed-point v * = max π v π , for any v 0 ∈ R S . This is the value iteration algorithm.

Accelerated Value Iteration

Anderson acceleration is a method that aims at accelerating the computation of the fixed point of any operator. Here, we describe it considering the Bellman operator T , which provides an accelerated value iteration algorithm.

Assume that estimates have been computed up to iteration k, and that in addition to v k the m previous estimates v k-1 , . . . , v k-m are known. The coefficient vector α k+1 ∈ R m+1 is defined as follows:

α k+1 = argmin α∈R m+1 m i=0 α i (T v k-m+i -v k-m+i ) s.t. m i=0 α i = 1.
Notice that we don't impose a positivity condition on the coefficients. We will consider practically the 2 -norm for this problem, but it could be a different norm (for example 1 or ∞ , in which case the optimization problem is a linear program). Then, the new estimate is given by:

v k+1 = m i=0 α k+1 i T v k-m+i .
The resulting Anderson accelerated value iteration is summarized in Alg. 1. Notice that the solution to the optimization problem can be obtained analytically for the 2 -norm, using the Karush-Kuhn-Tucker conditions. With the notations of Alg. 1 and writting 1 ∈ R m k +1 the vector with all components equal to one, it is

α k+1 = (∆ k ∆ k ) -1 1 1 (∆ k ∆ k ) -1 1 . ( 1
)
This can be regularized to avoid ill-conditioning.

Algorithm 1: Anderson Accelerated Value Iteration given: v 0 and m ≥ 1 Compute v 1 = T v 0 ; for k = 1, 2, 3 . . . do Set m k = min(m, k); Set ∆ k = [δ k-m k , . . . , δ k ] ∈ R S×(m+1) with δ i = T v i -v i ∈ R S ; Solve min α∈R m+1 ∆ k α s.t. m k i=0 α k = 1; Set v k+1 = m k i=0 α i T v k-m k +i ;
The rationale of this acceleration scheme is better understood with an affine operator. We consider here the Bellman evaluation operator T π . Given the current and the m previous estimates, define

ṽα k+1 = m i=0 α i v k-m+i with m i=0 α i = 1.
Thanks to this constraint, for an affine operator (here T π ), we have that

T π ṽα k+1 = m i=0 α i T π v k-m+i .
Then, one searches for a vector α (satisfying the constraint) that minimizes the residual

T π ṽα k+1 -ṽα k+1 = m i=0 α i (T π v k-m+i -v k-m+i ) .
Eventually, the new estimate is obtained by applying the operator to the vector ṽα k+1 of minimal residual.

The same approach can be applied (heuristically) to non-affine operators. The convergence of this scheme has been studied (e.g., [START_REF] Toth | Convergence analysis for anderson acceleration[END_REF]) and it can be linked to quasi-Newton methods [START_REF] Fang | Two classes of multisecant methods for nonlinear acceleration[END_REF].

Preliminary Experimental Results

We consider Garnet problems [START_REF] Archibald | On the generation of Markov decision processes[END_REF][START_REF] Bhatnagar | Natural actor-critic algorithms[END_REF]. They are a class of randomly built MDPs meant to be totally abstract while remaining representative of the problems that might be encountered in practice. Here, a Garnet G(|S|, |A|, b) is specified by the number of states, the number of actions and the branching factor. For each (s, a) couple, b different next states are chosen randomly and the associated probabilities are set by randomly partitioning the unit interval. The reward is null, except for 10% of states where it is set to a random value, uniform in (1, 2).

We generate 100 random MDPs G(100, 4, 3) and set γ to 0.99. For each MDP, we apply value iteration (denoted as m = 0 in the graphics) and Anderson accelerated value iteration for m ranging from 1 to 9. The inital value function v 0 is always the null vector. We run all algorithms for 250 iterations, and measure the normalised error for algorithm alg

at iteration k, v * -v alg k 1 v * 1
, where v * stands for the optimal value function of the considered MDP. Figure 1: Results on the Garnet problems.

Fig. 1 shows the results. Fig. 1.a shows how the normalized error evolves with the number of iterations (recall that m = 0 stands for classic value iteration). Shaded areas correspond to standard deviations and lines to means (due to randomness of the MDPs, the algorithms being deterministic given the fixed initial value function). Fig. 1.b and 1.c show respectively the mean and the standard deviation of these errors, in a logarithmic scale. One can observe that Anderson acceleration consistently offers a significant speed-up compared to value iteration, and that rather small values of m (m ≈ 5) seem to be enough.

Nuancing the Acceleration

We must highlight that the optimal policy is the object of interest, the value function being only a proxy to it. Regarding the value function, its level is not that important, but its relative differences are. This is addressed by the relative value iteration algorithm (Puterman, 1994, Ch. 6.6). For a given state s 0 , it iterates as

v k+ 1 2 = T v k , v k+1 = v k+ 1 2 -v k+ 1 2 (s 0 )1.
It usually converges much faster than value iteration (towards v * -v * (s 0 )1), but the greedy policies resp. to each iterate's estimated values are the same for both algorithms. This scheme can also be easily accelerated with Anderson's approach. We provide additional results on Fig. 2 (for the same MDPs as previously). Fig. 2.a shows the error of the greedy policy, that is v

* -v π alg k 1 / v * 1 , with π alg k
being greedy respectively to v alg k , for the first 10 iterations (same data as for Fig. 1). This is what we're really interested in. One can observe that value iteration provides more quickly better solutions than Anderson acceleration. This is due to the fact that if the level of the value function converges slowly, its relative differences converge more quickly.

So, we compare relative value iteration and its accelerated counterpart in Fig. 2.b (normalized error of the estimate, not of the greedy policy), to be compared to Fig. 1.b. There is still an acceleration with Anderson, at least at the beginning, but the speed-up is much less than in Fig. 1. We compare the error on greedy policies for the same setting in Fig. 2.c, and all approaches perform equally well.

Anderson Acceleration for Reinforcement Learning

So, the advantage of Anderson acceleration applied to exact value iteration on simple Garnet problems is not that clear. Yet, it could still be interesting for policy evaluation or in the approximate setting. We discuss briefly its possible applications to (deep) RL.

Approximate Dynamic Programming

Anderson acceleration could be applied to approximate dynamic programming and related methods. For example, the well-known DQN algorithm [START_REF] Mnih | Human-level control through deep reinforcement learning[END_REF] is nothing else than a (very smart) approximate value iteration approach. A state-action value function Q is estimated (rather than a value function), and this function is represented as a neural network. A target network Q k is maintained, and the Q-function is estimated by solving the least-squares problem (for the memory buffer {(s i , a i , r i , s i ) 1≤i≤n })

1 n n i=1 (y i -Q θ (s i , a i )) 2 with y i = r i + γ max a∈A Q k (s i , a).
Anderson acceleration can be applied directly as follows. Assume that the m + 1 previous target networks Q k , . . . , Q k-m are maintained. Define for k -m ≤ j ≤ k m+1) . Solve α k+1 as in Eq. ( 1) and define for all 1 ≤ i ≤ n

δ j = [r 1 + γ max a Q j (s 1 , a) -Q j (s 1 , a 1 ), . . . , r n + γ max a Q j (s n , a) -Q j (s n , a n )] ∈ R n and ∆ k = [δ k-m , . . . , δ k ] ∈ R n×(
y i = n j=0 α j (r i + γ max a∈A Q k-m+j (s i , a)).
So, Anderson acceleration would modify the targets in the regression problem, the necessary coefficients being obtained with a cheap least-squares (given m is small enough, as suggested by our preliminary experiments). Notice that the estimate α k+1 is biased, as being the solution to a residual problem with sampled transitions. However, if a problem, this could probably be handled with instrumental variables, giving an LSTD-like algorithm [START_REF] Bradtke | Linear Least-Squares algorithms for temporal difference learning[END_REF]. Variations of this general scheme could also be envisionned, for example by computing the α vector on a subset of the memory replay or even on the current minibatch, or by considering variations of Anderson acceleration such as the one of [START_REF] Nicholas | Damped anderson acceleration with restarts and monotonicity control for accelerating em and em-like algorithms[END_REF].

This acceleration scheme could be more generally applied to approximate modified policy iteration, or AMPI [START_REF] Scherrer | Approximate modified policy iteration and its application to the game of tetris[END_REF], that generalizes both approximate policy and value iterations. Modified policy iteration is similar to policy iteration, except that instead of computing the fixed point in the evaluation step, the Bellman evaluation operator is applied p times (p = 1 gives value iteration, p = ∞ policy iteration), the improvement step (computing the greedy policy) being the same (up to possible approximation). In the approximate setting, the evaluation step is usually performed by performing the regression of p-step returns, but it could be done by applying repeatedly the evaluation operator, this being combined with Anderson acceleration (much like DQN, but with T π instead of T ).

Policy Optimization

Another popular approach in reinforcement learning is policy optimization, or direct policy search [START_REF] Peter Deisenroth | A survey on policy search for robotics[END_REF], that maximizes J(w) = E S∼µ [v πw (S)] (or a proxy), for a user-defined state distribution µ, over a class of parameterized policies. This is classically done by performing a gradient ascent:

w k+1 = w k + η∇ w J(w)| w=w k .
(

) 2
This gradient is given by ∇ w J(w) = E S∼dµ,π w ,A∼π [Q πw (S, A)∇ w ln π w (A|S)]. Thus, it depends on the state-action value function of the current policy. This gradient can be estimated with rollouts, but it is quite common to estimate the Q-function itself. Related approaches are known as actor-critic methods (the actor being the policy, and the critic the Q-function). It is quite common to estimate the critic using a SARSA-like approach, especially in deep RL. In other words, the critic is estimated by applying repeatedly the Bellman evaluation operator. Therefore, Anderson acceleration could be applied, in the same spirit as what we described for DQN.

Yet, Anderson acceleration could also be used to speed up the convergence of the policy. Consider the gradient ascent in Eq. ( 2). This can be seen as a fixed-point iteration to solve w = w+η∇ w J(w). Anderson acceleration could thus be used to speed it up. Seeing gradient descent as a fixed point is not new [START_REF] Jung | A fixed-point of view on gradient methods for big data[END_REF], nor is applying Anderson acceleration to speed it up [START_REF] Scieur | Regularized nonlinear acceleration[END_REF][START_REF] Xie | Interpolatron: Interpolation or extrapolation schemes to accelerate optimization for deep neural networks[END_REF]). Yet, it has never been applied to policy optimization, as far as we know.

Figure 2 :

 2 Figure 2: Additional results.