Approximately Optimal Approximate Reinforcement Learning

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

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

Abstract

In order to solve realistic reinforcement learning problems, it is critical that approximate algorithms be used. In this paper, we present the conservative policy iteration algorithm which finds an “approximately” optimal policy, given access to a restart distribution (which draws the next state from a particular distribution) and an approximate greedy policy chooser. Crudely, the greedy policy chooser outputs a policy that usually chooses actions with the largest state-action values of the current policy, ie it outputs an “approximate” greedy policy. This greedy policy chooser can be implemented using standard value function approximation techniques. Under these assumptions, our 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 greedy policy chooser, but not explicitly on the the size of the state space.

1 Introduction

The two standard approaches, greedy dynamic programming and policy gradient methods, have enjoyed many empirical successes on reinforcement learning problems. Unfortunately, both methods can fail to efficiently improve the policy. Approximate value function methods suffer from a lack of strong 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”.

In this paper, we consider a setting in which our algorithm is given access to a restart distribution and an “approximate” greedy policy chooser. Informally, the restart distribution allows the agent to obtain its next state from a fixed distribution of our choosing. Through a more uniform restart distribution, the agent can gain information about states that it wouldn’t necessarily visit otherwise. Also informally, the greedy policy chooser is a “black box” that outputs a policy that on average chooses actions with large advantages with respect to the current policy, ie it provides an “approximate” greedy policy. This “black box” algorithm can be implemented using one of the well-studied regression algorithms for value functions (see [9, 3]). The quality of the resulting greedy policy chooser is then related to the quality of this “black box”.

Drawing upon the strengths of the standard approaches, we propose the conservative policy iteration algorithm. The key ingredients of this algorithm are:

(1) the policy is improved in a more uniform manner over the state-space and (2) a more conservative policy update is performed in which the new policy is a mixture distribution of the current policy and the greedy policy. Crudely, the importance of (1) is to incorporate “exploration” and the importance of (2) is to avoid the pitfalls of greedy dynamic programming methods which can suffer from significant policy degradation by directly using “approximate” greedy policies. Our contribution is in proving that such an algorithm converges in a “small” number of steps and returns an “approximately” optimal policy, where the quantified claims do not explicitly depend on the the size of the state space. We first review the problems with standard approaches, then state our algorithm.

2 Preliminaries

A finite Markov decision process (MDP) is defined by the tuple (S, D, A, R, {P (s′; s, a)}) where: S is a 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 (s′; s, a)} are the transition probabilities, with P (s′; s, a) giving the next-state distribution upon taking action a in state s.

Although ultimately we desire an algorithm which uses only the given MDP M, we assume access to a restart distribution, defined as follows: Definition 2.1. A μ restart distribution draws the next state from the distribution μ.

This restart distribution is a slightly weaker version of the generative model in [5]. As in [5], our assumption is considerably weaker than having knowledge of the full transition model. However, it is a much stronger assumption than having only “irreversible” experience, in which the agent must follow a single trajectory, with no ability to reset to obtain another trajectory from a state. If μ is chosen to be a relatively uniform distribution (not necessarily D), then this μ restart distribution can obviate the need for explicit exploration.

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 (where the semi-colon is used to distinguish the parameters from the random variables of the distribution). We only consider the case where the goal of the agent is to maximize the γdiscounted average reward from the starting state distribution D, though this has a similar solution to maximizing the average reward for processes that “mix” on a reasonable timescale [4]. Given 0 ≤ γ < 1, we define the value function for a given policy π as

V_{π}(s) ≡ (1 − γ)E [∑_{t=0}^{∞} γ^{t}R(s_{t}, a_{t})|π, s]

where s_{t} and a_{t} are random variables for the state and action at time t upon executing the policy π from the starting state s (see [7] for a formal definition of this expectation). Note that we are using normalized values so V_{π}(s) ∈ [0, R]. For a given policy π, we define the state-action value as

Q_{π}(s, a) ≡ (1 − γ)R(s, a) + γE_{s′∼P (s′;s,a)} [V_{π}(s′)]

and as in [8] (much as in [1]), we define the advantage as

A_{π}(s, a) ≡ Q_{π}(s, a) − V_{π}(s)

Again, both Q_{π}(s, a) ∈ [0, R] and A_{π}(s, a) ∈ [−R, R] due to normalization.

It is convenient to define the γ-discounted future state distribution (as in [8]) for a starting state distribution μ as

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

where the 1 − γ is necessary for normalization. We abuse notation and write d_{π,s} for the discounted future-state distribution with respect to the distribution which deterministically starts from state s. Note that V_{π}(s) = E_{(a′,s′)∼πd_{π,s}} [R(s′, a′)]. This distribution is analogous to the stationary distribution in the undiscounted setting, since as γ → 1, d_{π,s} tends to the stationary distribution for all s, if one such exists.

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

η_{D}(π) ≡ E_{s∼D} [V_{π}(s)] .

Note that η_{D}(π) = E_{(a,s)∼πd_{π,D}} [R(s, a)]. A well known result is that a policy exists which simultaneously maximizes V_{π}(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 improves this measure?

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

We now argue that both greedy dynamic programming and policy gradient methods give unsatisfactory answers to these questions. Note that 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 gives insight into our new algorithm, which addresses these three questions.

3.1 Approximate Value Function Methods

Exact value function methods, such as policy iteration, typically work in an iterative manner. Given a policy π, policy iteration calculates the state-action value Q_{π}(s, a), and then creates a new deterministic policy π′(a; s) such that π′(a; s) = 1 iff a ∈ argmax_{a}Q_{π}(s, a). This process is repeated until the state-action values converge to their optimal values. These exact value function methods have strong bounds showing how fast the values converge to optimal (see [7]).

Approximate value function methods typically use approximate estimates of the state-action values in an exact method. These 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 Ṽ(s) with the l_{∞}-error:

ε = max_{s} |Ṽ(s) − V_{π}(s)|

where π is some policy. Let π′ be a greedy policy based on this approximation. We have the following guarantee (see [3]) for all states s:

(3.1)  V_{π′}(s) ≥ V_{π}(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. Some convergence and asymptotic results exist (see [3]).

3.2 Policy Gradients Methods

Direct policy gradient methods attempt to find a good policy among some restricted class of policies, by following the gradient of the future reward. Given some parameterized class {π_{θ}|θ ∈ R^{m}}, these methods compute the gradient

(3.2)  ∇η_{D} = ∑_{s,a} d_{π,D}(s)∇π(a; s)Q_{π}(s, a)

(as shown in [8]).

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

Consider the simple MDP shown in Figure 3.1 (adapted from [10]). 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}. This MDP falls in the class of MDPs in which random actions are more likely than not to increase the distance to the goal state. For these classes of problems (see [11]), 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 has to run for at least this long before any policy improvement can occur. In

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

Figure 3.2. Example 2: A two state MDP and 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).

online value function methods, this problem is seen as a lack of exploration.

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 [6]), but are not feasible solutions for this class of problems. 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, which is the crucial quantity of interest. The analysis in [2] suggests a relatively small sample size is needed to accurately estimate the magnitude (within some ε tolerance), though this does not imply an accurate direction if the gradient is small. Unfortunately, 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 the simple two state MDP shown in Figure 3.2, which uses the common Gibbs table-lookup distributions, {π_{θ} : π(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

Figure 3.3. The stationary probability (for figure 3.2) of state j vs. time (on a 10^{7} scale).

π(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.2. Figure 3.3 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 asymptotically a good policy might be found, these results do not bode well for the answer to question 3, which is concerned with how fast such a policy can be found. These results suggest that in any reasonable number of steps, a gradient method could end up being trapped at plateaus where estimating the gradient direction has an unreasonably large sample complexity. 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 η_{D}, 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. 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∼μ} [V_{π}(s)]

where μ is some “exploratory” restart distribution. Under our assumption of having access to a μ-restart distribution, we can obtain estimates of η_{μ}(π).

Any optimal policy simultaneously maximizes both η_{μ} and η_{D}. Unfortunately, the policy that maximizes η_{μ} within some restricted class of policies may have poor performance according to η_{D}, so we must ensure that maximizing η_{μ} results in a good policy under η_{D}.

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.

In the remainder of this section, we describe a more conservative policy iteration scheme using α < 1 and state the main theorems of this paper. In subsection 4.1, we show that η_{μ} can improve under the much less stringent condition in which π′ often, but not always, chooses greedy actions. In subsection 4.2, we assume access to a greedy policy chooser that outputs “approximately” greedy policies π′ and then bound the performance of the policy found by our algorithm in terms of the quality of this greedy policy chooser.

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 a policy π and a distribution μ to be

𝔸_{π,μ}(π′) ≡ E_{s∼d_{π,μ}} [E_{a∼π′(a;s)} [A_{π}(s, a)]] .

The policy advantage measures the degree to which π′ is choosing actions with large advantages, with respect to the set of states visited under π starting from a state s ∼ μ. Note that a policy found by one step of policy improvement maximizes the policy advantage.

It is straightforward to show that \frac{∂η_{μ}}{∂α} |_{α=0} = \frac{1}{1−γ} 𝔸_{π,μ} (using equation 3.2), so the change in η_{μ} is:

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

Hence, for sufficiently small α, policy improvement occurs 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} |E_{a∼π′(a;s)} [A_{π}(s, a)] |. For the update rule 4.1 and for all α ∈ [0, 1]:

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

The proof of this theorem is given in the appendix. 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 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 has the same form as that of greedy dynamic programming, where ε, as defined here, is analogous to the l_{∞} error in equation 3.1.

The following corollary shows that the greater the policy advantage the greater the guaranteed performance increase. 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} guarantees 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 Answering 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 find policies with large policy advantages, we assume access to an ε-greedy policy chooser that solves this problem. Let us call this ε-good algorithm G_{ε}(π, μ), which is defined as: Definition 4.3. An ε-greedy policy chooser, G_{ε}(π, μ), is a function of a policy π and a state distribution μ which returns a policy π′ such that 𝔸_{π,μ}(π′) ≥ OPT(𝔸_{π,μ}) − ε, where OPT(𝔸_{π,μ}) ≡ max_{π′} 𝔸_{π,μ}(π′).

In the discussion, we show that a regression algorithm that fits the advantages with an \frac{ε}{2} average error is sufficient to construct such a G_{ε}.

The “breaking point” at which policy improvement is no longer guaranteed occurs when the greedy policy chooser is no longer guaranteed to return a policy with a positive policy advantage, ie when OPT(𝔸_{π,μ}) < ε. A crude outline of the Conservative Policy Iteration algorithm is:

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

(2) Estimate the policy advantage 𝔸_{π,μ}(π′)

(3) If the policy advantage is small (less than ε), STOP and return π.

(4) Else, update the policy and go to (1).

where, for simplicity, we assume ε is known. This algorithm ceases when an ε small policy advantage (with respect to π) is obtained. By definition of the greedy policy chooser, it follows that the optimal policy advantage of π is less than 2ε. The full algorithm is specified in the next section. The following theorem shows that in polynomial time, the full algorithm finds a policy π that is close to the “break point” of the greedy policy chooser. Theorem 4.4. With probability at least 1 − δ, conservative policy iteration: i) improves η_{μ} with every policy update, ii) ceases in at most 72\frac{R^{2}}{ε^{2}} calls to G_{ε}(π, μ), and iii) returns a policy π such that OPT(𝔸_{π,μ}) < 2ε.

The proof is in the appendix.

To complete the answer to question 3, we need to address the quality of the policy found by this algorithm. Note that the bound on the time until our algorithm ceases does not depend on the restart distribution μ though the performance of the policy π that we find does depend on μ since OPT(𝔸_{π,μ}) < 2ε. Crudely, for a policy to have near optimal performance then all advantages must be small. Unfortunately, if d_{π,μ} is highly non-uniform, then a small optimal policy advantage does not necessarily imply that all advantages are small. The following corollary (of theorem 6.2) bounds the performance of interest, η_{D}, for the policy found by the algorithm. We use the standard definition of the l_{∞}-norm, ||f||_{∞} ≡ max_{s} f(s). Corollary 4.5. Assume that for some policy π, OPT(𝔸_{π,μ}) < ε. Let π^{∗} be an optimal policy. Then

η_{D}(π^{∗}) − η_{D}(π) ≤ \frac{ε}{(1 − γ)} ∥\frac{d_{π^{∗},D}}{d_{π,μ}} ∥_{∞}

≤ \frac{ε}{(1 − γ)^{2}} ∥\frac{d_{π^{∗},D}}{μ} ∥_{∞} .

The factor of ∥\frac{d_{π^{∗},D}}{d_{π,μ}} ∥_{∞} represents a mismatch between the distribution of states of the current policy and that of the optimal policy and elucidates the problem of using the given start-state distribution D instead of a more uniform distribution. Essentially, a more uniform d_{π,μ} ensures that the advantages are small at states that an optimal policy visits (determined by d_{π^{∗},D}). The second inequality follows since d_{π,μ}(s) ≥ (1 − γ)μ(s), and it shows that a uniform measure prevents this mismatch from becoming arbitrarily large.

We now discuss and prove these theorems.

5 Conservative Policy Iteration

For simplicity, we assume knowledge of ε. The conservative policy iteration algorithm is:

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

(2) Use O(\frac{R^{2}}{ε^{2}} log \frac{R^{2}}{δε^{2}} ) μ-restarts to obtain an \frac{ε}{3}- accurate 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.

where δ is the failure probability of the algorithm. Note that the estimation procedure of step (2) allows us to set the learning rate α.

We now specify the estimation procedure of step (2) to obtain \frac{ε}{3}-accurate estimates of 𝔸_{π}(π′). It is straightforward to show that the policy advantage can be written as 𝔸_{π,μ}(π′) = E_{s∼d_{π,μ}} [∑_{a}(π′(a; s) − π(a; s))Q_{π}(s, a)]. We can obtain a nearly unbiased estimate x_{i} of 𝔸_{π,μ}(π′) using one call to the μ-restart distribution (see definition 2.1). To obtain a sample s from from d_{π,μ}, we obtain a trajectory from s_{0} ∼ μ and accept the current state s_{τ} with probability (1 − γ) (see equation 2.1). Then we chose an action a from the uniform distribution, and continue the trajectory from s to obtain a nearly unbiased estimate Q̂_{π}(s, a) of Q_{π}(s, a). Using importance sampling, the nearly unbiased estimate of the policy advantage from the i-th sample is x_{i} = n_{a}Q̂_{i}(s, a)(π′(a; s) − π(a; s)) where n_{a} is the number of actions. We assume that each trajectory is run sufficiently long such that the bias in x_{i} is less than \frac{ε}{6}.

Since Q̂_{i} ∈ [0, R], our samples satisfy x_{i} ∈ [−n_{a}R, n_{a}R]. Using Hoeffding’s inequality for k independent, identically distributed 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} (and 𝔸 here is \frac{ε}{6} biased). Hence, the number of trajectories required to obtain a Δ accurate sample with a fixed error rate is O (\frac{n_{a}^{2}R^{2}}{Δ^{2}} ).

The proof of theorem 4.4, which guarantees the soundness of conservative policy iteration, is straightforward and in the appendix.

6 How Good is The Policy Found?

Recall that the bound on the speed with which our algorithm ceases does not depend on the restart distribution used. In contrast, we now show that the quality of the resulting policy could strongly depend on this distribution.

The following lemma is useful:

Lemma 6.1. For any policies π̃ and π and any starting state distribution μ,

η_{μ}(π̃) − η_{μ}(π) = \frac{1}{1 − γ} E_{(a,s)∼π̃d_{π̃,μ}} [A_{π}(s, a)]

Proof. Let P_{t}(s′) ≡ P (s_{t} = s′; π̃, s_{0} = s). By definition of Vπ̃(s), Vπ̃(s)

= (1 − γ) ∑_{t=0}^{∞} γ^{t}E_{(a_{t},s_{t})∼π̃P_{t}} [R(s_{t}, a_{t})]

= ∑_{t=0}^{∞} γ^{t}E_{(a_{t},s_{t})∼π̃P_{t}} [(1 − γ)R(s_{t}, a_{t})

+V_{π}(s_{t}) − V_{π}(s_{t})]

= ∑_{t=0}^{∞} γ^{t}E_{(a_{t},s_{t},s_{t+1})∼π̃P_{t}P (s_{t+1};s_{t},a_{t})} [(1 − γ)R(s_{t}, a_{t})

+γV_{π}(s_{t+1}) − V_{π}(s_{t}))] + V_{π}(s)

= V_{π}(s) + ∑_{t=0}^{∞} γ^{t}E_{(a_{t},s_{t})∼π̃P_{t}} [A_{π}(s_{t}, a_{t})]

= V_{π}(s) + \frac{1}{1 − γ} E_{(a,s′)∼π̃d_{π̃,s}} [A_{π}(s′, a)]

and the result follows by taking the expectation of this equation with respect to μ. □

This lemma elucidates a fundamental measure mismatch. The performance measure of interest, η_{D}(π) changes in proportion the policy advantage 𝔸_{π,D}(π′) for small α (see equation 4.2), which is the average advantage under the state distribution d_{π,D}. However, for an optimal policy π^{∗}, the difference between η_{D}(π^{∗}) and η_{D}(π) is proportional to the average advantage under the state distribution d_{π^{∗},D}. Thus, even if the optimal policy advantage is small with respect to π and D, the advantages may not be small under d_{π^{∗},D}. This motivates the use of the more uniform distribution μ.

After termination, our algorithm returns a policy π which has small policy advantage with respect to μ. We now quantify how far from optimal π is, with respect to an arbitrary measure μ̃. Theorem 6.2. Assume that for a policy π, OPT(𝔸_{π,μ}) < ε. Let π^{∗} be an optimal policy. Then for any state distribution μ̃,

ημ̃(π^{∗}) − ημ̃(π) ≤ \frac{ε}{(1 − γ)} ∥\frac{d_{π^{∗},μ̃}}{d_{π,μ}} ∥_{∞}

≤ \frac{ε}{(1 − γ)^{2}} ∥\frac{d_{π^{∗},μ̃}}{μ} ∥_{∞} .

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_{π^{∗},μ̃}}{d_{π,μ}} ∥_{∞}^{−1} ∑_{s,a} d_{π^{∗},μ̃}(s)π^{∗}(a; s)A_{π}(s, a)

= (1 − γ) ∥\frac{d_{π^{∗},μ̃}}{d_{π,μ}} ∥_{∞}^{−1} (ημ̃(π^{∗}) − ημ̃(π))

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

Note that ∥\frac{d_{π^{∗},μ̃}}{μ} ∥_{∞} is a measure of the mismatch in using μ rather than the future-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 difference between the performance of π and optimal is \frac{1}{1−γ} times the average advantage under d_{π^{∗},μ̃}(s) (see lemma 6.1) and another factor of \frac{1}{1−γ} is due to the inherent non-uniformity of d_{π,μ} (since d_{π,μ}(s) ≤ (1 − γ)μ(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 a few related points.

7.1 The Greedy Policy Chooser

The ability to find a policy with a large policy advantage can be stated as a regression problem though we don’t address the sample complexity of this problem. Let us consider the error given by:

E_{s∼d_{π,μ}} 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 straightforward to see that if we can keep this error below \frac{ε}{2}, then we can construct an ε-greedy policy chooser by choosing a greedy policy based on these approximation f_{π}. This l_{1} condition for the regression problem is a much weaker constraint than minimizing an l_{∞}-error over the state-space, which is is the relevant error for greedy dynamic programming (see equation 3.1 and [3]).

Direct policy search methods could also be used to implement this greedy policy chooser.

7.2 What about improving η_{D}?

Even though we ultimately seek to have good performance measure under η_{D}, we show that it is important to improve the policy under a somewhat uniform measure. An important question is “Can we improve the policy according to both η_{D} and η_{μ} 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 η_{D} is allowed if the optimal policy has large advantages under D, though we do not formalize this here. The only situation where joint improvement with η_{D} is not possible is when OPT(𝔸_{π,D}) is small. However, this is the problematic case where, under D, the large advantages are not at states visited frequently.

7.3 Implications of the mismatch

The bounds we have presented directly show the importance of ensuring the agent starts in states where the optimal policy tends to visit. It also suggests that certain optimal policies are easier to learn in large state spaces — namely those optimal policies which tend to visit a significant fraction of the state space. An interesting suggestion for how to choose μ, is to use prior knowledge of which states an optimal policy tends to visit.

Acknowledgments

We give warm thanks to Peter Dayan for numerous critical comments.

References

[1] L. C. Baird. Advantage updating. Technical report, Wright Laboratory, 1993.

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

[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] M. Kearns, Y. Mansour, and A. Y. Ng. A sparse sampling algorithm for near-optimal planning in large markov decision processes. IJCAI, pages 1324–1231, 1999.

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

[7] M. Puterman. Markov decision processes : Discrete stochastic dynamic programming. John Wiley and Sons, 1994.

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

[9] R. S. Sutton and A. G. Barto. Reinforcement Learning: An Introduction. MIT Press, 1998.

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

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

8 Appendix: Proofs

The intuition for the proof of theorem 4.1 is that α determines the probability of choosing an action from π′. If the current state distribution is d_{π,μ} when an action from π′ is chosen, then the performance improvement is proportional to the policy advantage. The proof involves bounding the performance decrease due to the state distribution not being exactly d_{π,μ}, when an action from π′ is chosen.

Proof. Throughout the proof, the μ dependence is not explicitly stated. For any state s,

∑_{a} π_{new}(s; a)A_{π}(s, a)

= ∑_{a}((1 − α)π(a; s) + απ′(a; s))A_{π}(s, a)
= α ∑ π′(a; s)A_{π}(s, a) .

where we have used ∑_{a} π(a; s)A_{π}(s, a) = 0.

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. Hence, Pr(c_{t} = 0) = (1 − α)^{t}. Defining ρ_{t} ≡ Pr(c_{t} ≥ 1) = 1 − (1 − α)^{t} and P (s_{t}; π) to be distribution over states at time t while following π starting from s ∼ μ, it follows that

E_{s∼P (s_{t};π_{new})} [∑_{a} π_{new}(a; s)A_{π}(s, a)]

= αE_{s∼P (s_{t};π_{new})} [∑_{a} π′(a; s)A_{π}(s, a)]

= α(1 − ρ_{t})E_{s∼P (s_{t}|c_{t}=0;π_{new})} [∑_{a} π′(a; s)A_{π}(s, a)]

+αρ_{t}E_{s∼P (s_{t}|c_{t}≥1;π_{new})} [∑_{a} π′(a; s)A_{π}(s, a)]

≥ αE_{s∼P (s_{t}|c_{t}=0;π_{new})} [∑_{a} π′(a; s)A_{π}(s, a)]

−2αρ_{t}ε

= αE_{s∼P (s_{t};π)} [∑_{a} π′(a; s)A_{π}(s, a)] − 2αρ_{t}ε

where we have used the definition of ε and P (s_{t}|c_{t} = 0; π_{new}) = P (s_{t}; π).

By substitution and lemma 6.1, we have:

η_{μ}(π_{new}) − η_{μ}(π)

= ∑_{t=0}^{∞} γ^{t}E_{s∼P (s_{t};π_{new})} [∑_{a} π_{new}(a; s)A_{π}(s, a)]

≥ α ∑_{t=0}^{∞} γ^{t}E_{s∼P (s_{t};π)} [∑_{a} π′(a; s)A_{π}(s, a)]

−2αε ∑_{t=0}^{∞} γ^{t}(1 − (1 − α)^{t})

= \frac{α}{1 − γ} E_{s∼d_{π}} [∑_{a} π′(a; s)A_{π}(s_{t}, a)]

−2αε(\frac{1}{1 − γ} − \frac{1}{1 − γ(1 − α)}) .

The result follows from simple algebra. □

The proof of theorem 4.4 follows.

Proof. During step (2), we need enough samples such that |𝔸−𝔸̂| < \frac{ε}{3} for every loop of the algorithm and, as proved below, we need to consider at most \frac{72R^{2}}{ε^{2}} loops. If we demand that the probability of failure is less than δ, then by the union bound and inequality 5.1, we have

for k trajectories P (failure) < \frac{72R^{2}}{ε^{2}} 2e^{− \frac{kε^{2}}{36n^{2}_{a}R^{2}}} < δ, where we have taken Δ = \frac{ε}{6} since the bias in our esti-

mates is at most \frac{ε}{6}. Thus, we require O (\frac{R^{2}}{ε^{2}} log \frac{R^{2}}{δε^{2}} ) trajectories.

Thus, if 𝔸̂ ≥ \frac{2ε}{3}, then 𝔸 ≥ \frac{ε}{3} > 0. By corollary 4.2, step 4 guarantees improvement of η_{μ} by at least

\frac{(𝔸̂− \frac{ε}{3})^{2}}{8R} ≥ \frac{ε^{2}}{72R} using α = \frac{(1−γ)(𝔸̂− \frac{ε}{3} )}{4R}, which proves i. 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, which proves ii. In order to cease and return π, on the penultimate loop, the G_{ε} must have returned some π′ such that 𝔸̂ < \frac{2ε}{3}, which implies 𝔸_{π}(π′) < ε. By definition of G_{ε}, it follows that OPT(𝔸_{π}) < 2ε, which proves iii. □