Approximately Optimal Approximate Reinforcement Learning

Sham Kakade sham@gatsby.ucl.ac.uk Gatsby Computational Neuroscience Unit, UCL, London WC1N3AR, UK

John Langford jcl@cs.cmu.edu Computer Science Department, Carnegie-Mellon University, 5000 Forbes Avenue, Pittsburgh, PA 15217

Abstract

We make a reduction of the reinforcement learning problem to solving two types of problems — “How do we gain access to states?” (exploration) and “How do we solve a regression problem?” (supervised learning). Given solutions to each of these problems, our new algorithm: (1) is guaranteed to improve a performance metric (2) is guaranteed to terminate in a ’small’ number of timesteps and (3) returns an “approximately” optimal policy. The quantified statements of (2) and (3) depend on the quality of the supervised learning problem solution, but not explicitly on the the size of the state space.

1 Introduction

In order to solve realistic reinforcement learning problems, it is critical that approximating algorithms be used. Unfortunately, the two standard approaches, greedy dynamic programming and policy gradient methods, can fail to efficiently improve the policy. Approximate value function methods suffer from a lack of theoretical performance guarantees. We show how policy gradient techniques can require an unreasonably large number of samples in order to determine the gradient accurately. This is due to policy gradient method’s fundamental intertwining of “exploration” and “exploitation”.

Drawing upon the strengths of each approach we propose a new reinforcement learning algorithm based on two critical observations. First, we need to improve the policy at states that are visited infrequently under the current policy, since policy improvement at these states could ultimately lead to large policy improvement, ie we need to incorporate exploration. The second is that we must quantify how much policy improvement is possible with an approximate scheme. At one extreme, greedy methods show that if a large policy update is made then the policy could significantly degrade, while at the other extreme, for a sufficiently small change to the policy, gradient methods guarantee performance improvement. We connect these two extremes, to determine how much policy improvement is possible at finite step sizes. This allows us to determine how long it takes to obtain some ’approximately’ optimal policy. We then show the quality of this ’approximately’ policy is determined both by the level of approximation used and the how ’exploratory’ the start-state distribution is.

The algorithm we present overcomes the problems with both gradient methods and greedy dynamic programming.

2 Preliminaries

A reinforcement learning problem is a finite Markov decision process (MDP) with rewards. It is defined by the tuple (S, D, A, R, P) where: S is finite set of states, D is the starting state distribution, A is a finite set of actions, R is a reward function R : S×A → [0, R], and P is the transition model in which p_{ij}^{a} is the transition probability from state i to j under action a.

The agent’s decision making procedure is characterized by a stochastic policy π(a|s), which is the probability of taking action a in state s. Although in many situations, the goal of the agent is to maximize the average reward, we only consider the case of maximizing the γ-discounted average reward from the starting state distribution D, which has a similar solution for processes that ’mix’ on a reasonable timescale [4]. It is convenient to define a distribution over future states, with respect to some arbitrary start-state distribution μ, in the following way:

(2.1) d(s|π, μ, γ) ≡ (1 − γ) ∑_{t=0}^{∞} γ^{t} Pr(s_{t} = s|π, μ)

where Pr(s_{t} = s|π, μ) is the probability that the state at time t is s, under the policy π and the start-state distribution μ. This is analogous to the stationary distribution in the infinite time setting, since as γ → 1, d(s|π, μ, γ) tends to the stationary distribution. For brevity, we will sometimes write this as d(s|π) when γ and μ are clear from context.

Let δ(s) be the distribution over states which concentrates all mass on state s. We define the value function as the expected reward under π(a|s)d(s|π, δ(s)), or

(2.2)  J_{π}(s) ≡ E_{a,s′∼π(a|s′)d(s′|π,δ(s),γ)}R(s′, a)

which is equivalent to the more-standard definition J_{π}(s) ≡ (1 − γ)E{∑_{t=0}^{∞} γ^{t}R(s_{t}, a_{t})|π, s_{0} = s}. Note that we are using normalized values. The state-action value is defined as: Q_{π}(s, a) ≡ (1 − γ)R(s, a) + γ ∑_{s′} p_{ss′}^{a}J_{π}(s′), and the advantage is defined as A_{π}(s, a) ≡ Q_{π}(s, a) − J_{π}(s). We will sometimes suppress the π subscript when the policy is clear from context.

The goal of the agent is to maximize the discounted reward from the start state distribution D,

η(π) ≡ E_{s∼D}{J_{π}(s)} .

A well known result is that a solution exists which simultaneously maximizes J_{π}(s) for all states.

3 The Problems with Current Methods

We now examine in more detail the problems with approximate value function methods and policy gradient methods. There are three questions to which we desire answers to:

(1) Is there some performance measure that is guaranteed to improve at every step?

(2) How difficult is it to verify if a particular update will improve this measure?

(3) After a reasonable number of policy updates, what performance level is obtained?

We now argue that both greedy dynamic programming and gradient methods give unsatisfactory answers to these questions. Note that one question we did not ask is “What is the quality of the asymptotic policy?”. We are only interested in policies that we can find in a reasonable amount of time. Understanding the problems with these current methods will give insight into our new algorithm, which addresses these three questions.

3.1 The Weakness of Approximate Value Function Methods

Approximate value function methods suffer from a paucity of theoretical results on the performance of a policy based on the approximate values. This leads to weak answers to all three questions.

Let us consider some function approximator f(s) with the l_{∞}-error:

ε = max_{s} |f(s) − J_{π}(s)|

where π is some policy. Let J_{g} the value of a greedy policy based on this approximation. We have the following guarantee (see [2]) for all states s:

(3.1)  J_{g}(s) ≥ J_{π}(s) − \frac{2γε}{1 − γ} .

In other words, the performance is guaranteed to not decrease by more than \frac{2γε}{1−γ}. Question 2 is not applicable since these methods don’t guarantee improvement and a performance measure to check isn’t well defined.

For approximate methods, the time required to obtain some performance level is not well understood. At best, some asymptotic results exist (see [3]) . In contrast, exact value function methods have bounds showing how fast the values converge to optimal (see [2]).

3.2 The Convergence Problem for Policy Gradients

For policy gradient techniques, question 1 has the appealing answer that the performance measure of interest is guaranteed to improve under gradient descent. We now address question 2 by examining the situations in which estimating the gradient direction will be difficult. We show that the lack of exploration in gradient methods translates into requiring a very large number of timesteps in order to accurately estimate the gradient direction.

Consider the simple MDP shown in Figure 3.1 (adapted from [8]). Under a policy that gives equal probability to all actions, the expected time to the goal from the left most state is 3(2^{n} − n − 1), and with n = 50, the expected time to the goal is about 10^{15}. In general, many MDPs behave in the following manner: random actions are more likely than not to increase the distance to the goal state. For these classes of problems (see [9]), the expected time to reach the goal state using undirected exploration, ie random walk exploration, is exponential in the size of the state space. Thus, any on-policy method will have to run for at least this long before any policy improvement can occur. In online value function methods, this problem is seen as a lack of exploration.

Figure 3.1. Example 1: Two actions move agent to the left and one actions moves agent to the right.

Any sensible estimate of the gradient without reaching the goal state would be zero, and obtaining non-zero estimates requires exponential time with on-policy samples. Importance sampling methods do exist (see [5, 6]), but are not feasible solutions. The reason is that if the agent could follow some ’off-policy’ trajectory to reach the goal state in a reasonable amount of time, the importance weights would have to be exponentially large.

Note that a zero estimate is a rather accurate estimate of the gradient in terms of magnitude, but this provides no information about direction. The direction of the gradient is the crucial quantity of interest since we must step in the “right” direction in order to improve our policy. Some analysis has been done studying the deviation of gradient estimates [1]. However, this analysis focused on obtaining the policy gradient accurately (within some ε tolerance) rather than on obtaining the correct sign. This is a crucial difference because the magnitude of the gradient can be very small when the policy is far from optimal.

Let us give an additional example demonstrating the problems for a simple two state MDP as shown in Figure 3.2A, which uses the common Gibbs table-lookup distribution, Π̃_{G} = {π_{θ} : π(a|s) ∝ exp(θ_{sa})}. Increasing the chance of a self-loop at i decreases the stationary probability of j, which hinders the learning at state j. Under an initial policy that has the stationary distribution ρ(i) = .8 and ρ(j) = .2 (using π(a_{1}|i) = .8 and π(a_{1}|j) = .9), learning at state i reduces the learning at state j leading to an an extremely flat plateau of improvement at 1 average reward shown in Figure 3.2B. Figure 3.2C shows that this problem is so severe that ρ(j) drops as low as 10^{−7} from it’s initial probability of .2. As in example 1, to obtain a nonzero estimate of the gradient it is necessary to visit state j. The situation could be even worse with a few extra states in a chain as in figure 3.1.

Although in the limit a good policy might be found, these results do not bode well for the answer to question 3, which is concerned with how fast we can get there. These results suggest that in any reasonable number of steps, a gradient method could end up being

Figure 3.2. Example 2: A) See text. B) The average reward vs. time (on a 10^{7} scale) of a policy under standard gradient descent in the limit of an infinitesimally small learning rate (initial conditions stated in text). C) The stationary probability of state j in B vs. time (on a 10^{7} scale).

trapped at plateaus where estimating the gradient direction has an unreasonably large sample complexity. The asymptotic results of standard stochastic gradient ascent techniques show that as the number of samples go to ∞ a local optima is found. Unfortunately, these asymptotic results hide the sample complexity issues outlined here. Answering question 3 is crucial to understand how well gradient methods perform, and (to our knowledge) no such analysis exists.

4 Approximately Optimal RL

The fundamental problem with policy gradients is that η, which is what we ultimately seek to optimize, is insensitive to policy improvement at unlikely states though policy improvement at these unlikely states might be necessary in order for the agent to achieve near optimal payoff. Note that in example 1, policy improvement at state 49 will have little impact on the current performance, since the agent hardly ever reaches state 49 anyway. However, policy improvement at these unlikely states can ultimately lead to drastic policy improvement.

We desire an alternative performance measure that does not down weight advantages at unlikely states or unlikely actions. A natural candidate for a performance measure is to weight the improvement from all states more uniformly (rather than by D), such as

ω(π) = E_{s∼μ}{J_{π}(s)} ,

where μ is some ’exploratory’ starting state distribution. To this end, we assume we have the ability to use an arbitrary start-state distribution μ. Note that for the special case when μ = D then ω = η.

Any optimal policy simultaneously maximizes both ω and η. Unfortunately, the policy that maximizes ω within some restricted class of policies may have poor performance according to η. In general, the quality of the optima of ω is related to the the quality of the optima under η.

Greedy policy iteration updates the policy to some π′ based on some approximate state-action values. Instead, let us consider the following more conservative update rule:

(4.1)  π_{new}(a|s) = (1 − α)π(a|s) + απ′(a|s) ,

for some π′ and α ∈ [0, 1]. To guarantee improvement with α = 1, π′ must choose a better action at every state, or else we could suffer the penalty shown in equation 3.1.

4.1 Policy Improvement

A more reasonable situation is one in which we are able to improve the policy with some α > 0 using a π′ that chooses better actions at most but not all states. Let us define the policy advantage 𝔸_{π,μ}(π′) of some policy π′ with respect to the policy π and the startstate distribution μ to be:

𝔸_{π,μ}(π′) ≡ E_{s∼d(s|π,μ)} [∑_{a} π′(a|s)A_{π}(s, a)] .

Intuitively, this measures the expected advantage of π′ over π, with respect to the set of states visited under π. Note that a policy found by one step of policy improvement will maximize the policy advantage.

The gradient of a parameterized policy is

∇ω = ∑_{s,a} d(s|π, μ)∇π(a|s)Q_{π}(s, a) ,

(see [7]). It is straightforward to show that \frac{∂ω}{∂α}|_{α=0} = \frac{1}{1−γ} 𝔸_{π,μ}, so the change in ω is:

(4.2)  Δω = \frac{α}{1 − γ} 𝔸_{π,μ}(π′) + O(α^{2}) .

Hence, for sufficiently small α, policy improvement can occur if the policy advantage is positive, and at the other extreme of α = 1, significant degradation could occur. We now connect these two regimes to determine how much policy improvement is possible.

Theorem 4.1. Let 𝔸 be the policy advantage of π′ with respect to π and μ. and let ε = max_{s} | ∑_{a} π′(a|s)A_{π}(s, a)|. For the update rule 4.1 and for all α ∈ [0, 1]:

ω(π_{new}) − ω(π) ≥ \frac{α}{1 − γ} (𝔸 − \frac{2αγε}{1 − γ(1 − α)}) .

It is possible to construct a two state example showing this bound is tight for all α though we do not provide this example here.

The quantity ε is the average advantage, under π′, with the largest magnitude. The first term is analogous to the first order increase specified in equation 4.2, and the second term is a penalty term. Note that if α = 1, the bound reduces to

ω(π_{new}) − ω(π) ≥ \frac{𝔸}{1 − γ} − \frac{2γε}{1 − γ}

and the penalty term is identical to that of greedy dynamic programming, where the ε defined here is analogous to max-norm error (see equation 3.1). Thus the bound agrees with the local information provided by the gradient and greedy penalty when α = 1.

The following corollary shows that the greater the policy advantage the greater the guaranteed increase in performance.

Corollary 4.2. Let R be the maximal possible reward and 𝔸 be the policy advantage of π′ with respect to π and μ. If 𝔸 ≥ 0, then using α = \frac{(1−γ)𝔸}{4R} will guarantee the following policy improvement:

ω(π_{new}) − ω(π) ≥ \frac{𝔸^{2}}{8R} .

Proof. Using the previous theorem, it is straightforward to show the change is bounded by \frac{α}{1−γ} (𝔸−α\frac{2R}{1−γ}). The corollary follows by choosing the α that maximizes this bound. □

4.2 The answer to question 3

We address question 3 by first addressing how fast we converge to some policy then bounding the quality of this policy. Naively, we expect our ability to obtain policies with large advantages to affect the speed of improvement and the quality of the final policy. Instead of explicitly suggesting algorithms that obtain policies with large advantages, we assume access to an algorithm that solves this problem. Let us call this ε-good algorithm BlackBox_{ε}(π, μ), which is defined as:

Definition 4.3. BlackBox_{ε}(π, μ) is a function of a policy π and start-state distributions μ which returns a policy π′ such that 𝔸_{π,μ}(π′) ≥ OPT(𝔸_{π,μ})−ε, where OPT(𝔸_{π,μ}) = max_{π′} 𝔸_{π,μ}(π′).

We drop the μ dependence when clear. In the discussion, we show how a supervised learning algorithm that fits the advantages with an l_{1}-error of \frac{ε}{2} is sufficient to construct such a BlackBox_{ε} (though direct policy methods could also be sufficient).

The “breaking point” of our supervised learning algorithm is reached when it is no longer guaranteed to return a policy with a positive policy advantage (i.e. when OPT(𝔸_{π,μ}) − ε < 0).

For simplicity, we assume we have knowledge of ε. A crude outline of the Conservative Policy Iteration algorithm is:

(1) Call BlackBox_{ε}(π, μ) to obtain some π′

(2) Use O(\frac{R^{2}}{ε^{2}} log \frac{R^{2}}{δε^{2}} ) samples to obtain a Monte Carlo estimate 𝔸̂ of 𝔸_{π,μ}(π′).

(3) If 𝔸̂ < \frac{2ε}{3}, STOP and return π.

(4) If 𝔸̂ ≥ \frac{2ε}{3}, then update policy π according to

equation 4.1 using \frac{(1−γ)(𝔸̂− \frac{ε}{3} )}{4R} and return to step 1.

The following theorem shows that in polynomial time, the algorithm finds a policy π that is ’close’ to the break-point of the black box.

Theorem 4.4. With probability at least 1 − δ, conservative policy iteration will: i) improve ω with every policy update, ii) cease in at most 72\frac{R^{2}}{ε^{2}} calls to BlackBox_{ε}(π, μ), and iii) return a policy π such that OPT(𝔸_{π,μ}) < 2ε.

The proof is in the next section.

To complete the answer to question 3, we need to address the quality of the policy found by this algorithm. Note that our algorithm ceases in an amount of time that does not depend on the start-state distribution μ used though the policy π that we find will depend on μ since OPT(𝔸_{π,μ}) < 2ε. If d(s|μ) is highly nonuniform, then a small policy advantage will not necessarily imply that all advantages will be small. If there are any large advantages, the policy could be far from optimal. The following theorem quantifies this. We use standard definition of the l_{∞}-norm for some vector f(s), ||f||_{∞} ≡ max_{s} f(s).

Theorem 4.5. (simple version) Assume we have some π such that OPT(𝔸_{π}) < ε. Let π^{∗} be an optimal policy. Then

max_{s} |J_{π}(s) − J_{π_{∗}}(s)| ≤ \frac{ε}{(1 − γ)} ∥\frac{d(s|π^{∗}, μ′)}{d(s|π, μ)}∥_{∞} .

The proof is provided later in the paper. This bound elucidates the problem of using the given start-state distribution, D, instead of a more uniform distribution. The reason is that if d(s|π, D) does not give weight to any state where the optimal visits, then the policy could be far from optimal. The factor of ∥\frac{d(s|π^{∗},μ′)}{d(s|π,μ)} ∥_{∞} represents a mis-match between the distribution of states of the current policy and that of the optimal policy. Intuitively, weight must be given to all states that the optimal could visit. The use of a uniform metric will bound d(s|π, uniform) ≥ \frac{1−γ}{size of state space}. Essentially, exploration is necessary to improve the policy at these unlikely states.

We now discuss and prove these theorems in more detail.

5 Conservative Policy Iteration

After our black box returns some policy π′, we must address how to update the policy. If we knew the policy advantage of this policy was 𝔸 and if 𝔸 > 0, then we could use α = \frac{(1−γ)𝔸}{4R}.

Let us address how many samples are required to accurately determine 𝔸_{π}(π′). We must specify a sampling model to estimate the policy advantage. It is straightforward to show that the policy advantage can be written as 𝔸_{π,μ}(π′) = E_{s∼d(s|π,μ)} [∑_{a}(π′(a|s) − π(a|s))Q(s, a)] which is a more convenient form since we can directly estimate the state-action values.

Each sample required will consist of a sample s from from d(s|π, μ), an a from the uniform distribution, and a nearly unbiased estimate Q̂(s, a) of Q_{π}(s, a). Then, we can use Monte Carlo integration in order to estimate the value of 𝔸_{π,μ}(π′). Given certain assumptions, it is reasonable to suppose that we can obtain these samples in an on-policy manner, using a sample from μ and O(\frac{1}{1−γ}) transitions in our MDP. This can be done by first drawing a state s from d(s|π, μ), which can be done by acting in the MDP. Then we choose an action a from the uniform distribution and obtain an estimate Q̂(s, a) of the Q(s, a) value, by acting according to the policy for O(\frac{1}{1−γ}) steps. We use importance sampling with a uniform proposal distribution over the actions to estimate the policy advantage. We do not use π or π′ as the importance distribution, since if either of these are deterministic the importance weights may be large. The estimate of the policy advantage from the i-th sample will be x_{i} = n_{a}Q̂_{i}(s, a)(π′(a|s) − π(a|s)) where n_{a} is the number of actions.

How many samples are required? Since Q̂_{i} ∈ [0, R], our samples satisfy x_{i} ∈ [−n_{a}R, n_{a}R]. Using Hoeffding’s inequality for k independent identical random variables, we have:

(5.1)  Pr (|𝔸 − 𝔸̂| > δ) ≤ 2e^{− \frac{kδ^{2}}{2n^{2}_{a}R^{2}}} ,

where 𝔸̂ = \frac{1}{k} ∑_{i=1}^{k} x_{i}. Hence, the number of samples required to obtain a δ accurate sample with a fixed error rate is O (\frac{n_{a}^{2}R^{2}}{δ^{2}} ). Consequently, if the policy advantage is large then few samples will be needed.

Now the proof of the conservative policy iteration algorithm is straightforward:

Proof. There are three statements, that must all hold with probability 1 − δ, — ω improves at every step, the algorithms ceases in \frac{72R^{2}}{ε^{2}} iterations, and the policy found has maximal policy advantage less than 2ε. Let us assume that every time we make a Monte-Carlo estimate of the policy advantage, our estimate 𝔸̂ of the policy advantage satisfies |𝔸 − 𝔸̂| < \frac{ε}{3}. We estimate the probability this assumption fails later.

The assumption implies that if we observe 𝔸̂ ≥ \frac{2ε}{3}, then 𝔸 ≥ \frac{ε}{3}. By corollary 4.2, step 4 will guarantee

improvement of ^{\frac{(𝔸̂− \frac{ε}{3})^{2}}{8R}} ≥ \frac{ε^{2}}{72R} using α = \frac{(1−γ)(𝔸̂− \frac{ε}{3} )}{4R}. Since 0 ≤ ω ≤ R, there are at most \frac{72R^{2}}{ε^{2}} steps before ω becomes larger than R, so the algorithm must cease in this time. Our algorithm ceases and returns π when we observe that the policy advantage of some π′ satisfies 𝔸̂_{π}(π′) < \frac{2ε}{3} which implies 𝔸_{π}(π′) < ε. By definition of the black box, it follows that OPT(𝔸_{π}) < 2ε.

To obtain an error probability of less than δ, we must obtain enough samples such that |𝔸 − 𝔸̂| < \frac{ε}{3} for every loop of the algorithm, and there are at most \frac{72R^{2}}{ε^{2}} loops. By the union bound and inequality 5.1, we have

\frac{72R^{2}}{ε^{2}} 2e^{− \frac{kε^{2}}{2n^{2}_{a}R^{2}}} < δ, and so when O (\frac{R^{2}}{ε^{2}} log \frac{R^{2}}{δε^{2}} ) samples are used, the probability of failure is less than δ. □

6 How Good is The Policy Found?

The speed with which our algorithm ceases does not depend on the start-state distribution used. However, we now show that the quality of the resulting policy could strongly depend on this distribution.

The following lemma will be useful:

Lemma 6.1. For any policy π̃ and start-state distribution μ,

ωπ̃(s) − ω_{π}(s) = \frac{1}{1 − γ} E_{s,a∼d(s|π̃,μ)π̃}\{A_{π}(s, a)\}

Proof. Let d_{t}(s) be probability that the state at time t is s while following π̃ under the start-state distribution

μ. We have

ω(π̃)

= (1 − γ) ∑_{t=0}^{∞} γ^{t}E_{s,a∼d_{t}π̃}{R(s, a)}

= ∑_{t=0}^{∞} γ^{t}E_{s,a∼d_{t}π̃}{(1 − γ)R(s, a) − J_{π}(s) + J_{π}(s)}
= E_{s∼d_{0}}{J_{π}(s)}

+ ∑_{t=0}^{∞} γ^{t}E_{s′,s,a∼d_{t+1}d_{t}π̃}{(1 − γ)R(s, a) + γJ_{π}(s′) − J_{π}(s)}

= ω(π) + ∑_{t=0}^{∞} γ^{t}E_{s,a∼d_{t}π̃}{A_{π}(s, a)}

= ω(π) + \frac{1}{1 − γ} E_{s,a∼d(s|π̃,δ(s))π̃}\{A_{π}(s, a)\} .

□

This lemma elucidates a a fundamental measure mismatch in reinforcement learning, which we now analyse. The performance measure of interest, η(π) (defined with respect to start-state distribution D), changes in proportion the policy advantage 𝔸_{π,D}(π′) for small α when using our update rule (see equation 4.2). A resulting improvement of \frac{𝔸^{2}}{8R} can be guaranteed if 𝔸 ≥ 0. Recall that the policy advantage is just the expected advantage under the distribution d(s|π, D)π′(a|s). However, the difference between η and η^{∗} is the average advantage under d(s|π^{∗}, D)π^{∗}(a|s), where π^{∗} is an optimal policy. Thus, if 𝔸_{π,D}(π′) is small and D is highly non-uniform, this will not imply that η is close to optimal. For example, there could still be some large advantages where d(s|π, D) is small and d(s|π^{∗}, D) is large. Also, with 𝔸_{π,D}(π′) small, little improvement is guaranteed and even detecting if the policy advantage is positive (𝔸_{π,D}(π′) ≥ 0) will have large sample complexity. Intuitively, this is the situation where large advantages are at states with low probabilities of being visited under the current policy (as in examples 1 and 2).

We now quantify how far from optimal the resulting policy is using some start-state distribution μ.

Theorem 6.2. Assume we have some π such that OPT(𝔸_{π,μ}) < ε. For any policy π̃ and for any μ′,

ω_{μ′}(π̃) − ω_{μ′}(π) ≤ \frac{ε}{(1 − γ)} ∥\frac{d(s|π̃, μ′)}{d(s|π, μ)}∥_{∞}

≤ \frac{ε}{(1 − γ)^{2}} ∥\frac{d(s|π̃, μ′)}{μ}∥_{∞} .

Proof. The optimal policy advantage is OPT(𝔸_{π,μ}) = ∑_{s} d(s|π, μ) max_{a} A_{π}(s, a). Therefore,

ε > ∑_{s} \frac{d(s|π, μ)}{d(s|π̃, μ′)}d(s|π̃, μ′) max_{a} A_{π}(s, a)

≥ min_{s} (\frac{d(s|π, μ)}{d(s|π̃, μ′)}) ∑_{s} d(s|π̃, μ′) max_{a} A_{π}(s, a)

≥ ∥\frac{d(s|π̃, μ′)}{d(s|π, μ)}∥_{∞}^{−1} ∑_{s,a} d(s|π̃, μ′)π̃(a|s)A_{π}(s, a)

= (1 − γ) ∥\frac{d(s|π̃, μ′)}{d(s|π, μ)}∥_{∞}^{−1} (ω_{μ′}(π̃) − ω_{μ′}(π))

where the last step follows from lemma 6.1. The second inequality is due to min_{s} d(s|π, μ) ≤ (1 − γ) min_{s} μ(s). □

Note that ∥\frac{d(s|π^{∗},μ′)}{μ} ∥_{∞} is a measure of the mismatch in using μ rather than the start-state distribution of an optimal policy. The interpretation of each factor of \frac{1}{1−γ} is important. In particular, one factor of \frac{1}{1−γ} is due to the fact that policy is \frac{1}{1−γ} times the average advantage (under d(s|π^{∗})) away from optimal and another factor of \frac{1}{1−γ} is due to the inherent un-uniformity of d(s|π, μ).

7 Discussion

We have provided an algorithm that finds an “approximately” optimal solution that is polynomial in the approximation parameter ε, but not in the size of the state space. We discuss the difficulty of constructing our BlackBox function and also make a few other points.

7.1 The Black Box Algorithm

The ability to find a policy with a large policy advantage can be stated as a supervised learning problem, though we do not specify the sample complexity of this supervised learning problem. Let us consider the loss given by:

E_{s∼d(s|π,μ)} max_{a} |A_{π}(s, a) − f_{π}(s, a)| .

This loss is an average loss over the state space (though it is an ∞-loss over actions). It is in general much more tractable to deal with an average loss than an ∞-loss over the state-space. In general, it is the ∞-loss that is the relevant measure for greedy dynamic programming (see equation 3.1 and [3]).

It is straightforward to see that if we can keep this error below ε, then we can construct an 2ε-good black box by choosing π′(a|s) to be nonzero only for actions in argmax_{a}f(s, a). Thus, the difficulty of constructing an 2ε-good black box is at most as difficult as solving a regression problem with ε loss.

Direct policy search methods could also be used to construct this BlackBox. Equation 5.1 states that the sample complexity of determining the policy advantage to δ accuracy is O (\frac{n_{a}^{2}R^{2}}{δ^{2}} ), which is related to the sample complexity of searching a set of polices to obtain one with the largest policy advantage.

7.2 What about improving η?

Eventhough we ultimately seek to have good performance measure under η (which is under D), we show that it is important to improve the policy under a somewhat uniform measure. An interesting question is “Can we improve the policy according to both η and ω (which is under μ) at each update?” In general the answer is “no”, but consider improving the performance under μ̃ = (1 − β)μ + βD instead of just μ. This metric only slightly changes the quality of the asymptotic policy. However, by giving weight to D, the possibility of improving η is allowed if the optimal policy has large advantages under D. Essentially if OPT(𝔸_{π,D}) is large (greater than \frac{ε}{β}) , then finding a policy with large policy advantage with respect to μ̃, will also find a policy with large policy advantage under D. Joint improvement will be possible for this case, with an appropriate setting of α.

The only situation where joint improvement with η is not possible is when OPT(𝔸_{π,D}) is small. However, this is just the usual problematic case where, under D, the large advantages are inaccessible.

7.3 Prior Knowledge

A very interesting suggestion of how to chose μ, is to use prior knowledge of which states an optimal policy tends to visit or where any good policy tends to visit. The bounds we have presented show directly the importance of ensuring the agent starts in states where the optimal tends to visit.

7.4 Practical Variants

The algorithms we have suggested leads to a variety of practical variants. The most pragmatic for doing greedy dynamic programming is to fit the value functions under a more uniform metric and to use a line search over α with the greedy policy, rather than using the greedy α = 1. Further tricks must be done to ensure a compact representation of the policy. The most pragmatic variant for using gradient methods is to use a more uniform start state distribution, and then decay the distribution μ to D.

Acknowledgments

We give many thanks to Peter Dayan for suggestions on what constitutes efficient learning.

References

[1] P. Bartlett and J. Baxter. Estimation and approximation bounds for gradient-based reinforcement learning. Technical report, Australian National University, 2000.

[2] D. P. Bertsekas. Dynamic Programming and Optimal Control, Volumes 1 and 2. Athena Scientific, 1995.

[3] D. P. Bertsekas and J. N. Tsitsiklis. Neuro-Dynamic Programming. Athena Scientific, 1996.

[4] S. Kakade. Optimizing average reward using discounted rewards. In Proc. of Computational Learning Theory, 2001.

[5] L. Peshkin an K. Kim N. Meuleau. Exploration in gradient-based reinforcement learning. Technical report, Massachusetts Institute of Technology, 2001.

[6] D. Precup, R. Sutton, and S. Dasgupta. Off-policy temporal-difference learning with function approximation. ICML, in press, 2001.

[7] R. Sutton, D. McAllester, S. Singh, and Y. Mansour. Policy gradient methods for reinforcement learning with function approximation. Neural Information Processing Systems, 13, 2000.

[8] S. B. Thrun. Efficient exploration in reinforcement learning. Technical report, Carnegie Mellon University, 1992.

[9] S. D. Whitehead. Complexity and cooperation in qlearning. Proc. 8th International Conf. on Machine Learning, pages 363–367, 1991.

8 Appendix: Proof of Theorem4.1

The intuition for the proof is that α determines the probability of choosing a ’deviant’ action from π′. If the current state distribution is d(s|π, μ) when an action from π′ is chosen, then the performance change from this deviant action will be proportional to the policy advantage. The first deviant action will be chosen when the state distribution is approximately d(s|π, μ), and in the worst case scenario, all following deviant actions could be chosen when the state distribution is arbitrarily different. The penalty for the approximation in the former and the worst-case situation in the latter will be approximately ε.

Proof. The expected advantage with respect to π_{new} is,

E_{a∼π_{new}(a|s)}{A_{π}(s, a)}
= ∑_{a}((1 − α)π(a|s) + απ′(a|s))A_{π}(s, a)

= α ∑ π′(a|s)A_{π}(s, a)
= αE_{a∼π′(a|s)}{A_{π}(s, a)} .

For any timestep, the probability that we choose an action according to π′ is α. Let c_{t} be the random variable indicating the number of actions chosen from π′ before time t. In particular, while no action has been chosen from π′ we have c_{t} = 0 and after one action has been chosen c_{t} = 1. Hence, Pr(c_{t} = 0) = (1 − α)^{t} and Pr(c_{t} ≥ 1) = 1 − (1 − α)^{t}. For any π′, let d_{t}(s|π′) be the probability that the state at time t is s while following π′ under the start-state distribution μ. It follows that for all timesteps t:

E_{a,s∼π_{new}(a|s)d_{t}(s|π_{new})}A_{π}(s, a)
= αE_{a,s∼π′(a|s)d_{t}(s|π_{new})}A_{π}(s, a)
= α Pr(c_{t} = 0)E_{a,s∼π′(a|s)d_{t}(s|π_{new},c_{t}=0)}A_{π}(s, a)
+α Pr(c_{t} ≥ 1)E_{a,s∼π′(a|s)d_{t}(s|π_{new},c_{t}≥1)}A_{π}(s, a)
≥ α(1 − Pr(c_{t} ≥ 1))E_{a,s∼π′(a|s)d_{t}(s|π_{new},c_{t}=0)}A_{π}(s, a)
−α Pr(c_{t} ≥ 1)ε
≥ αE_{a,s∼π′(a|s)d_{t}(s|π_{new},c_{t}=0)}A_{π}(s, a) − 2α Pr(c_{t} ≥ 1)ε
= αE_{a,s∼π′(a|s)d_{t}(s|π)}A_{π}(s, a) − 2α(1 − (1 − α)^{t})ε

where we have used the definition of ε and d_{t}(s|π_{new}, c_{t} = 0) = d_{t}(s|π).

By substitution and lemma 6.1, we have:

ω(π_{new}) − ω(π)
= \frac{1}{1 − γ} E_{a,s∼π_{new}(a|s)d(s|π_{new})}A_{π}(s, a)

= ∑_{t=0}^{∞} γ^{t}E_{a,s∼π_{new}(a|s)d_{t}(s|π_{new})}{A_{π}(s, a)}

≥ ∑_{t=0}^{∞} γ^{t}(α ∑_{s,a} d_{t}(s|π)π′(a|s)A_{π}(s, a) − 2α(1 − (1 − α)^{t})ε)

= \frac{α}{(1 − γ)}E_{a,s∼π′(a|s)d(s|π)}A_{π}(s, a) − 2αε ∑_{t=0}^{∞} γ^{t}(1 − (1 − α)^{t})

= α\frac{𝔸_{π}(π′)}{(1 − γ)} − 2αε(\frac{1}{1 − γ} − \frac{1}{1 − γ(1 − α)}) .

The result follows from simple algebra. □