Yonathan Efroni
email: jonathan.efroni@gmail.com

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

Bruno Scherrer
email: bruno.scherrer@inria.fr

Shie Mannor

Multiple-Step Greedy Policies in Online and Approximate Reinforcement Learning

, multiple-step greedy policies and their use in vanilla Policy Iteration algorithms were proposed and analyzed. In this work, we study multiple-step greedy algorithms in more practical setups. We begin by highlighting a counter-intuitive 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

.

. We thus engineer several 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

, 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) 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 ))|s 0 = s]. 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 component-wise):

∀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.

3 The h-and κ-Greedy Policies

In this section, we bring forward necessary definitions and results on two classes of multiple-step greedy policies: hand κ-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 non-stationary, 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 shaped reward r π v,κ def = r π + (1 -κ)γP π v.

In [START_REF] Efroni | Beyond the one step greedy approach in reinforcement learning[END_REF]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 hand κ-greedy policies w.r.t. v π are strictly better then π, unless π = π * . Next, let

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. Specifically, denote by π such multiple-step greedy policy w.r.t. v π . Then, π new = (1 -α)π + απ is not necessarily better than π. Theorem 1. For any MDP, let π be a policy and v π its value. Let π κ ∈ G κ (v π ) and π h ∈ G h (v π ) with κ ∈ [0, 1] and h > 1. Consider the mixture policies with α ∈ (0, 1],

π(α, κ) def = (1 -α)π + απ κ , π(α, h) def = (1 -α)π + απ h .
Then 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 * .

Proof sketch. See Appendix A for the full proof. Here, we only provide a counterexample demonstrating the potential non-monotonicity of π(α, κ) when the stepsize α is not big enough. One can show the same for π(α, h) with the same example.

Consider the Tightrope Walking MDP in Fig. 1. It describes the act of walking on a rope: in the initial state s 0 the agent approaches the rope, in s 1 the walking attempt occurs, s 2 is the goal state and s 3 is repeatedly met if the agent falls from the rope, resulting in negative reward.

First, notice that by definition, ∀v, π * ∈ G κ=1 (v). We call this policy the "confident" policy. Obviously, for any discount factor γ ∈ (0, 1), π * (s 0 ) = a 1 and π * (s 1 ) = a 1 . Instead, consider the "hesitant" policy π 0 (s) ≡ a 0 ∀s. We now claim that for any α ∈ (0, 1) and

c > α 1 -α (5)
the mixture policy, π(α, κ = 1) = (1 -α)π 0 + απ * , is not strictly better than π 0 . To see this, notice that v π0 (s 1 ) < 0 and v π0 (s 0 ) = 0; i.e., the agent accumulates zero reward if she does not climb the rope. Thus, while v π0 (s 0 ) = 0, taking any mixture of the confident and hesitant policies can result in v π(α,κ=1) (s 0 ) < 0, due to the portion of the transition to s 1 and its negative contribution. Based on this construction, let κ ∈ [0, 1]. To ensure π * ∈ G κ (v π ), we find it is necessary that

c ≤ κ 1 -κ . (6)
To conclude, if both ( 5) and ( 6) are satisfied, the mixture policy does not improve over π 0 . Due to the monotonicity of x 1-x , such a choice of c is indeed possible for α < κ. Theorem 1 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, [ 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 convergent PI procedure -the κ-PI algorithm. This algorithm repeats i) finding the optimal policy of small-horizon surrogate MDP 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, it performs i) and ii) simultaneously.

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 1-step-greedy and κ-greedy policies. The 1-step greedy policy is attained via the q π estimate, which is plugged into a q-learning [START_REF] Christopher | Q-learning[END_REF] 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, in which 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 1 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 n-th 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(ν, π), using which we sample state s ∼ ν, sample action a ∼ π(s), apply action a and receive reward r and next state s .

The fast-timescale update rules in lines 6 and 8 can be jointly written as the sum of H π κ (q, q κ ) (defined below) and a martingale difference noise.

Algorithm 1 Two-Timescale Online κ-Policy-Iteration

1: initialize: π 0 , q 0 , q κ,0 .

2: for n = 0, . . . do

3: s n , a n , r n , s n ∼ G(ν, π n ) 4:
# Fast-timescale updates 5:

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

π n+1 (s n ) ← π n (s n ) + µ s (ν n+1 (s n ))(b sn (q n+1 , q κ,n+1 , π n ) -π n (s n )) 11: end for 12: return: π Definition 1. Let q, q κ ∈ R |S||A| . The mapping H π κ : R 2|S||A| → R 2|S||A| is defined as follows ∀(s, a) ∈ S × A. H π κ (q, 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 [16, Lemma 5.3] (see Appendix B for the proof). Lemma 2. H π κ is a γ-contraction in the max-norm. Its fixed point is [ q π , q π κ ] , as defined in (1), (

Finally, based on several intermediate results given in Appendix C and relaying on Lemma 2, we establish the convergence of Algorithm 1. Theorem 3. 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 8 corresponds to that of q-learning [START_REF] Christopher | Q-learning[END_REF]. For that κ, Algorithm 1 uses an estimated optimal q-function to update the current policy when improvement is assured. For κ < 1, the estimated κ-dependent optimal q-function (see [START_REF] Cameron B Browne | A survey of monte carlo tree search methods[END_REF]) is used, again with the 'cautious' policy update. Moreover, Algorithm 1 combines an off-policy algorithm, i.e., q-learning, with an on-policy Actor-Critic algorithm. To the best of our knowledge, this is the first appearance of these two approaches combined in a single algorithm.

Approximate κ-Policy Iteration with Hard Updates

Theorem 1 establishes the conditions required for guaranteed monotonic improvement of softlyupdated 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 algorithms that perform hard policy-updates. Specifically, we generalize the prominent Approximate Policy Iteration (API) [START_REF] Munos | Error bounds for approximate policy iteration[END_REF][START_REF] Amir-Massoud Farahmand | Error propagation for approximate policy and value iteration[END_REF][START_REF] Lazaric | Analysis of classificationbased policy iteration algorithms[END_REF] and Policy Search by Dynamic Programming (PSDP) [START_REF] Andrew Bagnell | Policy search by dynamic programming[END_REF][START_REF] Scherrer | Approximate policy iteration schemes: a comparison[END_REF]. For both, we obtain performance guarantees that exhibit a tradeoff in the choice of κ, with optimal performance bound achieved with κ > 0. That is, our approximate κ-generalized PI methods outperform the 1-step greedy approximate PI methods in terms of best known guarantees.

For the algorithms here we assume an oracle that returns a κ-greedy policy with some error. Formally, we denote by G κ,δ,ν (v) the set of approximate κ-greedy policies w.r.t. v, with δ approximation error under some measure ν. Definition 2 (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 -δ.
Such a device can be implemented using existing approximate methods, e.g., Conservative Policy Iteration (CPI) [START_REF] Kakade | Approximately Optimal Approximate Reinforcement Learning[END_REF], approximate PI or VI [START_REF] Amir-Massoud Farahmand | Error propagation for approximate policy and value iteration[END_REF], Policy Search [START_REF] Scherrer | Local policy search in a convex space and conservative policy iteration as boosted policy search[END_REF], or by having an access to an approximate model of the environment. 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, ν. For practical purposes, ν can be thought of as the initial sampling distribution to which the MDP is initialized. Lastly, notice that the larger κ is, the harder it is to solve the surrogate κγ-discounted MDP since the discount factor is bigger [START_REF] Petrik | Biasing approximate dynamic programming with a lower discount factor[END_REF][START_REF] Alexander L Strehl | Reinforcement learning in finite mdps: Pac analysis[END_REF][START_REF] Jiang | The dependence of effective planning horizon on model accuracy[END_REF]; i.e., the computational cost of each call to the oracle increases.

Using the concept of concentrability coefficients introduced in [START_REF] Munos | Error bounds for approximate policy iteration[END_REF] (there, they were originally termed "diffusion coefficients"), we follow the line of work in [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] to prove our performance bounds. This allows a direct comparison of the algorithms proposed here with previously studied approximate 1-step greedy algorithms. Namely, our bounds consist of concentrability coefficients C (1) , C (2) , C (2,k) and C π * (1) from [START_REF] Scherrer | Approximate policy iteration schemes: a comparison[END_REF][START_REF] Lazaric | Analysis of classificationbased policy iteration algorithms[END_REF], as well as two new coefficients C π * κ and C π * (1) κ . Definition 3 (Concentrability coefficients [START_REF] Scherrer | Approximate policy iteration schemes: a comparison[END_REF][START_REF] Lazaric | Analysis of classificationbased policy iteration algorithms[END_REF])). Let µ, ν be some measures over S. Let {c(i)} ∞ i=0 be the sequence of the smallest values in [1, ∞) ∪ {∞} such that for every i, for all sequences of deterministic stationary policies π 1 , π 2 , .., π i , µ

i j=1 P πj ≤ c(i)ν. Let C (1) (µ, ν) = (1 - γ) ∞ i=0 γ i c(i) and C (2,k) (µ, ν) = (1 -γ) 2 ∞ i,j=0 γ i+j c(i + j + k).
For brevity, we denote

C (2,0) (µ, ν) as C (2) (µ, ν). Similarly, 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).
We now introduce two new concentrability coefficients suitable for bounding the worst-case performance of PI algorithms with approximate κ-greedy policies.

Definition 4 (κ-Concentrability coefficients). 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 definitions 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 4 it holds that C π * κ=0 (µ, ν) = C π * (µ, ν)
; the latter was previously defined in, e.g, [19, Definition 1]. Before giving our performance bounds, we first study the behavior of the coefficients appearing in them. The following lemma sheds light on the behavior of C π * κ (µ, ν). Specifically, it shows that under certain constructions, C π * κ (µ, ν) decreases3 as κ increases (see proof in Appendix D). Lemma 4. 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 κ. Definition 4 introduces two coefficients with which we shall derive our bounds. Though traditional arithmetic relations between them do not exist, they do comply to some notion of ordering. Remark 2 (Order of concentrability coefficients). In [START_REF] Scherrer | Approximate policy iteration schemes: a comparison[END_REF], an order between the concentrability coefficients was introduced: a coefficient A is said to be strictly better than B -a relation we denote with A ≺ B -if and only if i) B < ∞ implies A < ∞ and ii) there exists an MDP for which A < ∞ and B = ∞. Particularly, it was argued that

C π * (µ, ν) ≺ C π * (1) (µ, ν) ≺ C (1) (µ, ν) ≺ C (2) (µ, ν), and
C (2,k1) (µ, ν) ≺ C (2,k2) (µ, ν) if k 2 < k 1 .
In this sense, 1) (µ, ν), while its definition might suggest improvement as κ increases. Moreover, combined with the fact that C π * κ (µ, ν) improves as κ increases, as Lemma 4 suggests, C π * κ (µ, ν) is better than all previously defined concentrability coefficients.

C π * (1) κ (µ, ν) is analogous to C π * (

κ-Approximate Policy Iteration

A natural generalization of API [START_REF] Munos | Error bounds for approximate policy 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] to the multiple-step greedy policy is κ-API, as given in Algorithm 2. In each of its iterations, the policy is updated to the approximate κ-greedy policy w.r.t.

v π k-1 ; i.e, a policy from the set G κ,δ,ν (v π k-1 ). Algorithm 2 κ-API initialize κ ∈ [0, 1], ν, δ, v π0 v ← v π0 for k = 1, .. do π k ← G κ,δ,ν (v) v ← v π k end for return π Algorithm 3 κ-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 Π
The following theorem gives a performance bound for κ-API (see proof in Appendix E), with

C κ-API (µ, ν) = (1 -κ) 2 C (2) (µ, ν) + (1 -γ)κ (1 -κ)C (1) (µ, ν) + (1 -γκ)C π * (1) κ (µ, ν) , C (k,1) κ-API (µ, ν) = (1 -κγ) κ(1 -κγ)C π * κ (µ, ν) + (1 -κ) 2 C (1) (µ, ν)) , C (k,2) κ-API (µ, ν) = (1 -κ)κ (1 -γ)C (1) (µ, ν) + g(κ)(1 -κ)γ k C (2,k) (µ, ν) ,
where g(κ) is a bounded function for κ ∈ [0, 1]. Theorem 5. Let π k be the policy at the k-th iteration of κ-API and δ be the error as defined in Definition 2. Then

µ(v * -v π k ) ≤ C κ-API (µ, ν) (1 -γ) 2 δ + ξ k R max 1 -γ . Also, let k = log Rmax δ(1-γ) 1-ξ . Then µ(v * -v π k ) ≤ C (k,1) κ-API (µ,ν) (1-γ) 2 log Rmax (1-γ)δ δ + C (k,2) κ-API (µ,ν) (1-γ) 2 δ + δ.
For brevity, we now discuss the first part of the statement; the same insights are true for the second as well. The bound for the original API is restored for the 1-step greedy case of κ = 0, i.e, [START_REF] Scherrer | Approximate policy iteration schemes: a comparison[END_REF][START_REF] Lazaric | Analysis of classificationbased policy iteration algorithms[END_REF]. As in the case of API, our bound consists of a fixed approximation error term and a geometrically decaying term. As for the other extreme, κ = 1, we first remind that in the non-approximate case, applying T κ=1 amounts to solving the original γ-discounted MDP in a single step [START_REF] Efroni | Beyond the one step greedy approach in reinforcement learning[END_REF]Remark 4]. In the approximate setup we investigate here, this results in the vanishing of the second, geometrically decaying term, since ξ = 0 for κ = 1. We are then left with a single constant approximation error: Definition 3). It represents the mismatch between µ and ν [START_REF] Kakade | Approximately Optimal Approximate Reinforcement Learning[END_REF].

µ(v * -v π k ) ≤ C (2) (µ,ν) (1-γ) 2 δ + γ k Rmax 1-γ
µ(v * -v π k ) ≤ c(0)δ. Notice that c(0) is independent of π * (see
Next, notice that, by definition (see Definition 3), C (2)

(µ, ν) > (1-γ) 2 c(0); i.e., C (2) (µ,ν)
(1-γ) 2 δ > c(0)δ. Given the discussion above, we have that the κ-API performance bound is strictly smaller with κ = 1 than with κ = 0. Hence, the bound suggests that κ-API is strictly better than the original API for κ = 1. Since all expressions there are continuous, this behavior does not solely hold point-wise. Remark 3 (Performance tradeoff). Naively, the above observation would lead to the choice of κ = 1. However, it is reasonable to assume that δ, the error of the κ-greedy step, itself depends on κ, i.e, δ ≡ δ(κ). The general form of such dependence is expected to be monotonically increasing: as the effective horizon of the surrogate κγ-discounted MDP becomes larger, its solution is harder to obtain (see Remark 1). Thus, Theorem 5 reveals a performance tradeoff as a function of κ.

κ-Policy Search by Dynamic Programming

We continue with generalizing another approximate PI method -PSDP [START_REF] Andrew Bagnell | Policy search by dynamic programming[END_REF][START_REF] Scherrer | Approximate policy iteration schemes: a comparison[END_REF]. We name it κ-PSDP and introduce it in Algorithm 3. This algorithm updates the policy differently from κ-API. However, similarly to κ-API, it uses hard updates. We will show this algorithm exhibits better performance than any other previously analyzed approximate PI method [START_REF] Scherrer | Approximate policy iteration schemes: a comparison[END_REF].

The κ-PSDP algorithm, unlike κ-API, returns a sequence of deterministic policies, Π. Given this sequence, we build a single, 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 . Its value v σ κ,k can be seen to satisfy

v σ κ,k = T Π[k] κ T Π[k-1] κ . . . T Π[1] κ v π0 .
This algorithm follows PSDP from [START_REF] Scherrer | Approximate policy iteration schemes: a comparison[END_REF]. Differently from it, the 1-step improvement is generalized to the κ-greedy improvement and the non-stationary policy behaves randomly. The following theorem gives a performance bound for it (see proof in Appendix F). Theorem 6. Let σ κ,k be the policy at the k-th iteration of κ-PSDP and δ be the error as defined in Definition 2. Then

µ(v * -v σ κ,k ) ≤ C π * (1) κ (µ, ν) 1 -ξ δ + ξ k R max 1 -γ . Also, let k = log Rmax δ(1-γ) 1-ξ . Then µ(v * -v σ κ,k ) ≤ C π * κ (µ,ν) (1-ξ) 2 log Rmax (1-γ)δ δ + δ.
Compared to κ-API from the previous section, the κ-PSDP bound consists of a different fixed approximation error and a shared geometrically decaying term. Regarding the former, notice that

C π * (1) κ (µ, ν) ≺ C κ-API (µ, ν)
, using the notation from Remark 2. This suggests that κ-PSDP is strictly better than κ-API in the metrics we consider, and is in line with the comparison of the original API to the original PSDP given in [START_REF] Scherrer | Approximate policy iteration schemes: a comparison[END_REF].

Similarly to the previous section, we again see that substituting κ = 1 gives a tighter bound than

κ = 0. The reason is that C π * (1) (µ,ν) 1-γ
δ > c(0)δ, by definition (see Definition 3); i.e., we have that κ-PSDP is generally better than PSDP. Also, contrarily to κ-API, here we directly see the performance improvement as κ increases due to the decrease of C π * κ prescribed in Lemma 4, for the construction given there. Moreover, the κ tradeoff discussion in Remark 3 applies here as well.

An additional advantage of this new algorithm over PSDP is reduced space complexity. This can be seen from the 1 -ξ in the denominator in the choice of k in the second part of Theorem 6. It shows that, since ξ is a strictly decreasing function of κ, better performance is guaranteed 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 1. To mitigate this caveat, we designed an online PI algorithm 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.

A Proof of Theorem 1

We start with a generalization of a useful lemma; its original version appeared in, e.g., [START_REF] Scherrer | Improved and Generalized Upper Bounds on the Complexity of Policy Iteration[END_REF]Lemma 10]. Lemma 7. 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 [20, Lemma 10], and [9, 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 1 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 π .
(7) Using this, we now prove the first statement of Theorem 1.

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 π ). (8)
For the first relation we use Lemma 7 with κ = 1 and the fact that, by definition, κ) . For the second relation we use [START_REF] Amir-Massoud Farahmand | Error propagation for approximate policy and value iteration[END_REF], for the fourth we again use Lemma 7, 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 (8) are component-wise bigger than or equal to zero. First, using a Taylor expansion, (I -γP π(α,κ) ) -1 = t γ t (P π(α,κ) ) t ≥ 0 component-wise, since it is a weighted sum of transition matrices with positive weights. The same applies for (1 -α)P π + (α -κ)P πκ , when α ≥ κ. Thus, for α ≥ κ, (I + γ(I -γP π(α,κ) ) -1 ((1 -α)P π + (α -κ)P πκ ) ≥ 0 component-wise.

Lastly, since

π κ ∈ G κ (v π ), v π = T π κ v π ≤ T κ v π = T πκ κ v π , with equality holding if and only if v π = v * [5, Lemma 3]. Thus, T πκ κ v π -v π ≥ 0.
This concludes the proof for the first statement, for the κ-greedy policy.

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. 2. Consider the mixture of the "hesitant" and "confident" policies: π(α, κ = 1) = (1 -α)π 0 + απ(α, κ = 1). It can be shown that its value is Thus, we deduce that for any α ∈ (0, 1) and

v π(α,κ=1) (s 0 ) = γα 1 -γ(1 -α) v π(α,κ=1) (s 1 ), v π(α,κ=1) (s 1 ) = γ -c(1 -α) + α 1 -γ .
c > α 1 -α , (9)
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 ). (10)
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 -γ . (11)
Similarly, and since π(s 0 ) = a 0 , we have that

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

c ≤ κ 1 -κ . ( 13
)
To finalize the counterexample and show that strict policy improvement is not guaranteed, we choose c such that both (9) and ( 13) 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 [5, 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 (9) alone to show that π(α, h) = (1 -α)π 0 + απ * is not monotonically better then π. Large enough c value ensures that.

B Proof of Lemma 2

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 || ∞ , ( 14
) ||q 1,κ -q 2,κ || ∞ ≤ ||Q 1 -Q 2 || ∞ . ( 15
)
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 ( 14). 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 ( 14)- [START_REF] Rudy R Negenborn | Learningbased model predictive control for markov decision processes[END_REF].

From the above 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. It is clear that the fixed point of the first component is q π . The fixed point of the second component is the fixed point of the optimal Bellman operator of the κγ-discounted, reward shaped, surrogate MDP (see Remark 1). Its solution is, by construction, q π κ (see ( 4)).

C Proof of Theorem 3

The proof of Theorem 3 follows the proof in [16, Section 5.1], with several generalizations given below.

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 8. 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 || ∞ , (16)
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 )|. ( 17
)
We bound each term in [START_REF] Petrik | Biasing approximate dynamic programming with a lower discount factor[END_REF]. 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 || ∞ . (18)
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 ( 17) 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 || ∞ (19)
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 [START_REF] Martin L Puterman | Markov decision processes: discrete stochastic dynamic programming[END_REF], [START_REF] Scherrer | Approximate policy iteration schemes: a comparison[END_REF] to bound [START_REF] Petrik | Biasing approximate dynamic programming with a lower discount factor[END_REF] 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 ( 16) and rearranging yields,

||v π1 -v π2 || ∞ ≤ R max (1 -γ) 2 ||π 1 -π 2 || ∞ , (20)
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 [START_REF] Scherrer | Improved and Generalized Upper Bounds on the Complexity of Policy Iteration[END_REF], 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 on 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.

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 4. Assume a constant

C π * κ (µ, ν) < ∞ such that, d π * κ,µ = (1 -ξ)µ(I -ξD π * κ ) -1 < C π * κ (µ, ν)ν. (21)
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 9 in the first line, Equation 21 in the second line, and defined α * = (

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

C π * κ (µ, ν(α * )) -C π * κ (µ, ν) = 1 -ξ κ 1 -κ (κ -κ + ( 1 -κ 1 -ξ κ - 1 -κ 1 -ξ κ )C π * κ (µ, ν)) = 1 -ξ κ 1 -κ (κ -κ)(1 -C π * κ (µ, ν)). (22)
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 κ.

E Proof of Theorem 5

We first prove two technical lemmas. Lemma 10. 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 4,

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

(1 -x) -i = ∞ t=i-1 t! (i -1)!(t -(i -1))! x t-(i-
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) . (23)
Since D π κ = (1 -κγ)(I -κγP π ) -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 [START_REF] Sheppard | World-championship-caliber scrabble[END_REF] 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 11. 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 (24)
+ ∞ 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 . ( 25
)
Let us bound the first sum first [START_REF] Silver | Mastering chess and shogi by self-play with a general reinforcement learning algorithm[END_REF],

∞ 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 [START_REF] Silver | Mastering the game of go without human knowledge[END_REF] 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, ( 25) 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 [START_REF] Silver | Mastering chess and shogi by self-play with a general reinforcement learning algorithm[END_REF] without the need to decouple to two sums. Thus, for this case, the bound on the first term, with n = ∞, bounds the expression.

We are now ready to prove Theorem 5. The proof strategy is similar to the line of work in [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]: Keeping track of the cumulative error and using the definition of c(i) and c π * (i), we bound the performance loss in the µ-weighted L 1 norm.

Since the policy in each iteration is an approximate κ-greedy policy (see Definition 2), it holds that νT π k κ v π k-1 ≥ νT κ v π k-1 -δ in each iteration. Let the error vector at the i-th iteration δi satisfy ν δi ≤ δ. Thus,

v * -v π k = T π * κ v * -T π * κ v π k-1 + T π * κ v π k-1 -v π k = ξD π * κ P π * (v * -v π k-1 ) + T π * κ v π k-1 -v π k = ξD π * κ P π * (v * -v π k-1 ) + T π * κ v π k-1 -T π k κ v π k-1 + T π k κ v π k-1 -v π k ≤ ξD π * κ P π * (v * -v π k-1 ) + T π * κ v π k-1 -max π T π κ v π k-1 + δi + T π k κ v π k-1 -v π k ≤ ξD π * κ P π * (v * -v π k-1 ) + δi + T π k κ v π k-1 -v π k = ξD π * κ P π * (v * -v π k-1 ) + δi + ξD πκ κ P π k (v π k-1 -v π k ), (26)
where we used in the second and last relations that for any policy π, and any value functions

v 1 , v 2 , T π κ v 1 -T π κ v 2 = ξD π κ P π (v 1 -v 2 )
. This can be seen by using the definition of T π κ (see Section 3). Notice that

v π k-1 -v π k = T π k-1 κ v π k-1 -v π k ≤ max π T π κ v π k-1 -v π k ≤ T π k κ v π k-1 -v π k + δi = T π k κ v π k-1 -T π k κ v π k + δi = ξD π k κ P π k (v π k-1 -v π k ) + δi .
Hence,

(I -ξD π k κ P π k )(v π k-1 -v π k ) ≤ δi , i.e., v π k-1 -v π k ≤ (I -ξD π k κ P π k ) -1 δi . (27)
The last equation holds due to [14, Lemma 4.2], combined with the fact that

(I -ξD π k κ P π k ) -1 = ∞ i=0 ξD π k κ P π k ≥ 0, element-wise. Plugging (27) into (26), we have that v * -v π k ≤ ξD π * κ P π * (v * -v π k-1 ) + δi + ξD π k κ P π k (I -ξD π k κ P π k ) -1 δi = ξD π * κ P π * (v * -v π k-1 ) + (I -ξD π k κ P π k ) -1 δi ,
where the second relation holds since for matrix X s.t. X < 1, I + X(I -X) -1 = (I -X) -1 .

We thus get that the errors accumulate as follows.

v * -v π k ≤ k-1 i=0 (ξD π * κ P π * ) i (I -ξD π k-i κ P π k-i ) -1 δi + (ξD π * κ P π * ) k (v * -v π0 ).
We continue by multiplying both sides with µ and get

µ(v * -v π k ) ≤ k-1 i=0 µ(ξD π * κ P π * ) i (I -ξD π k-i κ P π k-i ) -1 δi + ξ k R max 1 -γ . (28)
Using Lemma 9 with κ = 0 and renaming κ to κ, we have that

(I -ξD π k-i κ P π k-i ) -1 = (1 -κ)(I -γP π k-i ) -1 + κI.
Plugging this relation into [START_REF] Tesauro | On-line policy improvement using monte-carlo search[END_REF] gives

µ(v * -v π k ) ≤ k-1 i=0 µ(ξD π * κ P π * ) i ((1 -κ)(I -γP π k-i ) -1 + κI) δi + ξ k R max 1 -γ ≤ (1 -κ) k-1 i=0 µ(ξD π * κ P π * ) i (I -γP π k-i ) -1 δi + κ k-1 i=0 µ(ξD π * κ P π * ) i δi + ξ k R max 1 -γ . (29)
The following two lemmas provide bounds for the first two terms above. The bounds are composed of the concentrability coefficients (see Definition 3 and Definition 4).

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

k-1 i=0 µ(ξD π * κ P π * ) i (I -γP π k-i ) -1 δi ≤ (1 -κ)C (2) (µ, ν) (1 -γ) 2 + κC (1) (µ, ν) 1 -γ δ (30) and k-1 i=0 µ(ξD π * κ P π * ) i (I-γP π k-i ) -1 δi ≤ k (1 -κ)C (1) (µ, ν) 1 -γ + κC (1) (µ, ν) 1 -γ + g(κ)(1 -κ)κγ k C (2,k) (µ, ν) (1 -γ) 2 δ. (31)
Proof. We start with proving (30). Let π be an arbitrary policy. For i > k -1, we define π k-i = π and vectors δi s.

t. ν δi ≤ δ . k-1 i=0 µ(ξD π * κ P π * ) i (I -γP π k-i ) -1 δi ≤ ∞ i=0 µ(ξD π * κ P π * ) i (I -γP π k-i ) -1 δi = µ(I -γP π k ) -1 δ0 + ∞ i=1 µ(ξD π * κ P π * ) i (I -γP π k-i ) -1 δi . (32)
For the first term in (32) we have that

µ(I -γP π k ) -1 δ0 = ∞ l=0 γ l µ(P π k ) l δ0 ≤ ∞ l=0 γ l c(l)ν δ0 ≤ ∞ l=0 γ l c(l)δ = C (1) (µ, ν) 1 -γ δ, (33)
where for the second relation we used the definition of the sequence {c(i)} ∞ i=0 (see Definition 3) and in the third relation we used ν δ0 ≤ δ (see Definition 2).

Next, we bound the second term in (32).

∞ i=1 µ(ξD π * κ P π * ) i (I -γP π k-i ) -1 δi = ∞ l=0 ∞ i=1 γ l µ(ξD π * κ P π * ) i (P π k-i ) l δi (34) = ∞ l=0 ∞ i=1 ∞ t=i-1 t! (i -1)!(t -(i -1))! γ l+t+1 κ t-(i-1) (1 -κ) i µ(P π * ) t+1 (P π k-i ) l δi ≤ ∞ l=0 ∞ i=1 ∞ t=i-1 t! (i -1)!(t -(i -1))! γ l+t+1 κ t-(i-1) (1 -κ) i c(t + 1 + l)δ ≤(1 -κ) ∞ l=0 ∞ t=0 γ l+t+1 c(t + 1 + l)δ (35) =(1 -κ) ∞ l=0 ∞ t=1 γ l+t c(t + l)δ =(1 -κ) ∞ l=0 ∞ t=1 γ l+t c(t + l) + ∞ l=0 γ l c(l) - ∞ l=0 γ l c(l) δ =(1 -κ) ∞ l=0 ∞ t=0 γ l+t c(t + l) - ∞ l=0 γ l c(l) δ = (1 -κ) C (2) (µ, ν) (1 -γ) 2 - C (1) (µ, ν) 1 -γ δ. (36)
For the first relation we used the Taylor expansion (I -

γP π k-i ) -1 = ∞ l=0 γ l (P π k-i ) l ,
for the second we used Lemma 10, for the third we used the definition of the sequence {c(i)} ∞ i=0 and ν δi ≤ δ, for the fourth we applied Lemma 11 with n = ∞ and f (•) = c(•), and for the fifth we shifted the summation index t ← t + 1.

We bound (32) by summing the bounds in (33) and (36) to obtain the first statement of the lemma, (30).

To prove the second statement, (31), we again split expression of interest, similarly to (32).

k-1 i=0 µ(ξD π * κ P π * ) i (I -γP π k-i ) -1 δi ≤ µ(I -γP π k ) -1 δ0 + k-1 i=1 µ(ξD π * κ P π * ) i (I -γP π k-i ) -1 δi .
(37) As in (33), the first term in (37) is bounded by

µ(I -γP π k ) -1 δ0 ≤ C (1) (µ, ν) 1 -γ δ. (38)
Next, we bound the second term in (37).

k-1 i=1 µ(ξD π * κ P π * ) i (I -γP π k-i ) -1 δi = ∞ l=0 k-1 i=1 γ l µ(ξD π * κ P π * ) i (P π k-i ) l δi ≤(1 -κ) ∞ l=0 k-2 t=0 γ t+1+l c(t + 1 + l)δ + g(κ)(1 -κ)κ ∞ l=0 ∞ t=k-1 γ t+1+l c(t + 1 + l)δ =(1 -κ) k-2 t=0 ∞ l=0 γ t+1+l c(t + 1 + l)δ + g(κ)(1 -κ)κγ k ∞ l=0 ∞ t=0 γ t+l c(t + l + k)δ ≤(k -1) (1 -κ)C (1) (µ, ν) 1 -γ δ + g(κ)(1 -κ)κγ k C (2,k) (µ, ν) (1 -γ) 2 δ. (39)
In the first relation we used the Taylor expansion of (I -γP π k-i ). For the second relation we perform the same steps as from (34) to (35), where this time we used Lemma 11 with finite n = k.

Summing the terms in (38) and (39), we obtain the second statement of the lemma, (31).

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

k-1 i=0 µ(ξD π * κ P π * ) i δi ≤ 1 -κγ 1 -γ C π * (1) κ (µ, ν)δ (40)
For the first term in (42),

µ δ0 ≤ c(0)ν δ0 ≤ c(0)δ, (43)
where we used Definition 3 and then Definition 2.

For the second term in (42), 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)δ (µ, ν) to be the same expression as in Definition 4.

≤(1 -κ)
For the second statement of the lemma, (41), we use 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 π * κ (µ, ν).

So far, the proof went as follows. First, we expressed the cumulative error in (29) as the sum of three terms. Bounding the first and second terms is done with Lemmas 12 and 13, respectively. Each of those two lemmas gives bounds of two forms. These two forms correspond to the two statements in Theorem 5. We now apply the bounds so as to obtain the first statement. Specifically, plugging (30) and ( 40) into [START_REF] Christopher | Q-learning[END_REF] gives the first statement in Theorem 5.

To obtain the second statement of Theorem 5, we apply the second form of the bounds in Lemmas 12 and 13. Specifically, we plug (31) and ( 41) into [START_REF] Christopher | Q-learning[END_REF]. This gives

µ(v * -v π k ) ≤ k κC π * κ (µ, ν) 1 -ξ + k (1 -κ) 2 C (1) (µ, ν) 1 -γ + (1 -κ)κC (1) (µ, ν) 1 -γ + g(κ)(1 -κ) 2 κγ k C (2,k) (µ, ν) (1 -γ) 2 δ + ξ k R max 1 -γ .
We now carefully choose the iteration number k to make the last term smaller than δ:

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

F Proof of Theorem 6

Here, we merely follow the arguments of [19, Appendix A], while using the operators T π κ instead of T π and the approximate operator defined in Definition 2. As in Section E, we define the componentwise 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 13. The two statements in that lemma lead to the two statements in Theorem 6. Again, for the second statement, we set k as in (45).

Figure 1 :

 1 Figure 1: The Tightrope Walking MDP used in the counter example of Theorem 1.

10 ,

 10 Lemma 5.4], [9, Corollary 4.2], and [21, Theorem 1].

Figure 2 :

 2 Figure 2: The Tightrope Walking MDP used in the proof of Theorem 1. This class of MDPs is parametrized by c > 0.

  We begin proving the first statement. For i > k -1, we define vectors δi s.t. ν δi ≤ δ. Thus,π * κ P π * ) i δi ≤ µ δ0 + ∞ i=1 µ(ξD π * κ P π * ) i δi .

∞γ( 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)δ. (44)For the first relation we apply Lemma 10, for the second we use the definition of {c π * (i)} ∞ i=0 and use ν δi ≤ δ. For the third relation we apply Lemma 11 with n = ∞, f (•) = c π * (•) and drop the l summation.Summing the terms in (43) and (44), we get κ)C π *(1) (µ, ν) + (1 -γ)κc(0) δ = 1 -κγ 1 -γ C π * (1) κ (µ, ν)δ,where we identify C π * (1) κ

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

Acknowledgments

This work was partially funded by the Israel Science Foundation under contract 1380/16.

C.2 Improvement Step

Here, we prove an equivalent lemma to [START_REF] Perkins | Asynchronous stochastic approximation with differential inclusions[END_REF]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 7 and setting κ = 0 we have that

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 componentwise. We thus get that

C.3 Convergence of the Algorithm

We define the same Lyapunov function as defined in [START_REF] Perkins | Asynchronous stochastic approximation with differential inclusions[END_REF]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 [16, Corollary 5.6], which leads to the convergence of q π to q * . Lastly, since T κ v * = v * [5, Lemma 4] we have that,

which concludes the proof.

D Proof of Lemma 4

We first prove a useful lemma that relates the (unnormalized) future distribution, measured in different κ scales. Lemma 9. For any policy π and κ, κ ∈ [0, 1],

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

We see that the following relation holds for any κ ∈ [0, 1],

(I -γP π ) -1 = 1 1 -κ ((I -ξ κ D π κ P π ) -1 -κI).