Active Policy Iteration: Efficient Exploration through Active Learning for Value Function Approximation in Reinforcement Learning

1 Introduction

In practical reinforcement learning (RL), it is often expensive to obtain immediate reward samples while state-action trajectory samples are readily available. For example, let us consider a robot-arm control task of hitting a ball by a bat and drive the ball as far as possible (see Figure 5). Let us use the carry distance of the ball as the immediate reward. In this setting, obtaining state-action trajectory samples of the robot arm is easy and relatively cheap since we just need to control the robot arm and record its state and action trajectories over time. On the other hand, explicitly computing the carry of the ball from the state-action samples is hard due to friction and elasticity of links, air resistance, and unpredictable disturbances such a current of air. Thus, in practice, we may have to put the robot in a large place, let the robot really hit the ball, and measure the carry of the ball manually. Thus gathering immediate reward samples is much more expensive than the state-action trajectory samples.

When the sampling cost of immediate rewards is high, it is important to design the sampling policy appropriately so that a good control policy can be obtained from a small number of samples. In this paper, we first show that the least-squares policy iteration (LSPI) framework [Lagoudakis and Parr, 2003] allows us to use statistical active learning (AL) methods for linear regression [Cohn et al., 1996; Sugiyama, 2006].

In the LSPI framework, the state-action value function is approximated by fitting a linear model with least-squares estimation. A traditional AL scheme [Cohn et al., 1996] is designed to find the input distribution 1 that minimizes the variance of the least-squares estimator. Since the expected approximation error of the value function is expressed as the sum of the (squared) bias and variance, the bias needs to be zero for justifying the use of the traditional AL scheme. To this end, we need to assume that the linear model used for approximating the value function is correctly specified, i.e., if the parameters are learned optimally, the true value function can be perfectly approximated.

However, such a correct model assumption may not be fulfilled in practical RL tasks since the profile of value functions may be highly complicated. To cope with this problem, an importance-sampling based AL method has been developed recently [Sugiyama, 2006]. This AL algorithm is valid even when the model is misspecified, i.e., even when the true value function is not included in the model-which would be a usual case in practice-a good input distribution can be designed.

In this paper, we develop a new exploration scheme for LSPI based on the importance-sampling based AL idea. The proposed method combined with LSPI is called active policy iteration (API). Through batting-robot simulations, the usefulness of API is demonstrated.

2 Formulation of RL Problem

In this section, we review how Markov decision problems (MDPs) can be solved using policy iteration based on value functions.

MDPs: Let us consider an MDP specified by (S,A, PT,R, γ), where S is a set of states, A is a set of actions, PT(s′ |s, a) (∈ [0, 1]) is the conditional probability density of the agent's transition from state s to next state s′ when action a is taken, R(s, a, s′) (∈ R) is a reward for transition from s to s′ by taking action a, and γ (∈ (0, 1]) is the discount factor for future rewards. Let π(a|s) (∈ [0, 1]) be a stochastic policy which is the conditional probability density of taking action a given state s. The state-action value function Qπ (s, a) (∈ R) for policy π is the expected discounted sum of rewards the agent will receive when taking action a in state s and following policy π thereafter, i.e.,

1 When approximating the state-action value function, the input distribution corresponds to the stationary distribution of states and actions.

where Eπ,PT denotes the expectation over {sn, an}∞n=1 following π(an|sn) and PT(sn+1|sn, an).

The goal of RL is to obtain the policy which maximizes the discounted sum of future rewards; the optimal policy can be expressed as π∗ (a|s) ≡ δ(a - argmaxa′ Q∗ (s, a′ )), where δ(·) is Dirac's delta function and Q∗ (s, a) ≡ maxπ Qπ (s, a) is the optimal state-action value function.

Qπ (s, a) can be expressed as the following recurrent form called the Bellman equation: ∀s ∈ S, ∀a ∈ A,

where R(s, a) ≡ EPT(s′ |s,a) [R(s, a, s′ )] is the expected reward when the agent takes action a in state s, EPT(s′ |s,a) denotes the conditional expectation of s′ over PT(s′ |s, a) given s and a, and Eπ(a′ |s) denotes the conditional expectation of a′ over π(a′ |s′ ) given s′ .

Policy Iteration: Computing the value function Qπ (s, a) is called policy evaluation. Using Qπ (s, a), we may find a better policy π′ (a|s) by 'softmax' update:

where τ (> 0) determines the randomness of the new policy π′ ; or by ϵ-greedy update:

where I(c) is the indicator function (1 if c is true and 0 otherwise), pu is the uniform probability density over actions, and ϵ (∈ (0, 1]) determines how deterministic the new policy π′ is. Updating π based on Qπ (s, a) is called policy improvement. Repeating policy evaluation and policy improvement, we may find the optimal policy π∗ (a|s). This entire process is called policy iteration [Sutton and Barto, 1998].

Least-squares Framework for Value Function Approximation: Although policy iteration is useful, it is often computationally intractable since the number of state-action pairs |S| × |A| is very large; |S| or |A| becomes infinite when the state space or action space is continuous. To overcome this problem, we approximate the state-action value function Qπ (s, a) using the following linear model:

where φ(s, a) = (φ1(s, a), φ2(s, a), . . . , φB(s, a))⊤ are the fixed linearly independent basis functions, ⊤ denotes the transpose, B is the number of basis functions, and θ = (θ1, θ2, . . . , θB)⊤ are model parameters. Note that B is usually chosen to be much smaller than |S| × |A|.

For N-step transitions, we ideally want to learn the parameters θ so that the squared Bellman residual G(θ) is minimized [Lagoudakis and Parr, 2003]:

EPπ denotes the expectation over the joint probability density function Pπ(s1, a1, s2, a2, . . . , sN, aN, sN+1) ≡ PI(s1) ∏Nn=1 PT(sn+1|sn, an)π(an|sn), where PI(s) denotes the initial-state probability density function.

Value Function Learning from Samples: Suppose that roll-out data samples consisting of M episodes with N steps are available as training data. The agent initially starts from a randomly selected state s1 following the initial-state probability density PI(s) and chooses an action based on a sampling policy ˜ π(an|sn). Then the agent makes a transition following the transition probability PT(sn+1|sn, an) and receives a reward rn(= R(sn, an, sn+1)). This is repeated for N stepsthus the training dataset De π is expressed as

where each episodic sample de πm consists of a set of 4-tuple elements as

We use two types of policies which have different purposes: the sampling policy ˜ π(a|s) for collecting data samples and the evaluation policy π(a|s) for computing the value function ̂Qπ . Minimizing the importance-weighted empirical generalization error ̂G(θ), we can obtain a consistent estimator of θ∗ as follows:

where D(s,a) is a set of 4-tuple elements containing state s and action a in the training data D, ∑s′ ∈D(s,a) denotes the summation over s′ in the set D(s,a), and

is called the importance weight [Sutton and Barto, 1998]. It is important to note that consistency of ̂ θ can be maintained even if we πm,N is replaced by the per-decision importance weight we πm,n [Precup et al., 2000], which is more efficient to calculate. ̂ θ can be analytically expressed with the matrices ̂L(∈ RB×MN ), ̂ X(∈ RMN×B ), W(∈ RMN×MN ), and the vector reπ (∈ RMN×1 ) as

3 Efficient Exploration with Active Learning

The accuracy of the estimated value function depends on the training samples collected following the sampling policy ˜ π(a|s). In this section, we propose a new method for designing a good sampling policy based on a statistical active learning method [Sugiyama, 2006].

Preliminaries: Here we consider the case where collecting state-action trajectory samples is easy and cheap, but gathering immediate reward samples is hard and expensive (examples include the batting robot explained in the introduction). In such a case, immediate reward samples cannot be used for designing the sampling policy, but only state-action trajectory samples are available.

The goal of active learning in the current setup is to determine the sampling policy so that the expected generalization error is minimized. The generalization error is not accessible in practice since the expected reward function R(s, a) and the transition probability PT(s′ |s, a) are unknown, so the generalization error needs to be estimated from samples. A difficulty of estimating the generalization error in the context of active learning is that its estimation needs to be carried out only from state-action trajectory samples without using immediate reward samples; thus standard techniques such as cross-validation [Hachiya et al., 2008] cannot be employed since it requires both state-action and immediate reward samples. Below, we explain how the generalization error could be estimated under the active learning setup.

Decompositionof GeneralizationError: The information we are allowed to use for estimating the generalization error is a set of roll-out samples without immediate rewards:

Let us define the deviation of immediate rewards from the mean as

Note that ϵe πm,n could be regarded as additive noise in leastsquares function fitting. By definition, ϵe πm,n has mean zero and the variance may depend on se πm,n and ae πm,n, i.e., heteroscedastic noise. However, since estimating the variance of ϵe πm,n without using reward samples is not possible, we assume that the variance does not depend on se πm,n and ae πm,n-let us denote the common variance by σ2 .

Now we would like to estimate the generalization error

from De π . Its expectation can be decomposed as

where Eϵ eπ denotes the expectation over 'noise' {ϵe πm,n}M,N m=1,n=1. B, V , and C are the bias term, variance term, and model error defined by

where the matrix U(∈ RB×B ) is defined as

Note that the variance term V can be expressed as

Estimation of Generalization Error for AL: The model error C is constant and can be safely ignored in generalization error estimation. So we only need to estimate the bias term B and the variance term V . However, B includes the unknown optimal parameter θ∗ and therefore it may not be possible to estimate B without using reward samples; similarly, it may not be possible to estimate the 'noise' variance σ2 included in the variance term V without using reward samples.

It is known that the bias term B is small enough to be neglected when the model is approximately correct [Sugiyama, 2006], i.e., θ∗⊤̂ψ(s, a) approximately agrees with the true function R(s, a). Then we have

which does not require immediate reward samples for its computation. Since EPπ included in U is not accessible, we replace U by its consistent estimator ̂U :

Consequently, we have the following generalization error estimator:

which can be computed only from Deπ and thus can be employed in the AL scenarios. If it is possible to gather De π multiple times, the above J may be computed multiple times and its average J may be used as a generalization error estimator.

Designing Sampling Policies: Based on the generalization error estimator derived above, we give an algorithm for designing a good sampling policy, which fully makes use of the roll-out samples without immediate rewards.

1. Prepare K candidates of sampling policy: {˜ πk}Kk=1 .
2. Collect episodic samples without immediate rewards for each sampling-policy candidate: {De πk }Kk=1 .
3. Estimate U using all samples {Deπk }Kk=1 :

1. Estimate the generalization error for each k:

1. (If possible) repeat 2. to 4. several times and calculate the average for each k: {Jk}Kk=1 .
2. Determine the sampling policy: ˜ πAL ≡ argmink Jk.
3. Collect training samples with immediate rewards: De πAL .
4. Learn the value function by LSPI using De πAL .

Numerical Examples: Here we illustrate how the proposed method behaves in the 10-state chain-walk environment shown in Figure 1. The MDP consists of 10 states S = {s(i)}10 i=1 = {1, 2, . . . , 10} and 2 actions A = {a(i)}2i=1 = {'L', 'R'}. The immediate reward function R(s, a, s′ ) is defined by R(s, a, s′ ) ≡ 0.3×(7-|s′ -7|). The transition probability PT(s′ |s, a) is indicated by the numbers attached to the arrows in Figure 1; for example, PT(s(2) |s(1) , 'R') = 0.9 and PT(s(1) |s(1) , 'R') = 0.1. Thus the agent can successfully move to the intended direction with probability 0.9 (indicated by solid arrows in the figure) and the action fails with probability 0.1 (indicated by dashed arrows in the figure). The discount factor γ is set to 0.9. We use the 12 basis functions φ(s, a) defined as

where c1 = 1, c2 = 3, c3 = 5, c4 = 7, c5 = 9, and σ = 3.0.

For illustration purposes, we evaluate the selection of sampling policies only in one-step policy evaluation; evaluation over iteration will be addressed in the next section. Sampling policies and evaluation policies are constructed as follows.

First, we prepare a deterministic 'base' policy, e.g., 'LLLLLRRRRR', where the i-th letter denotes the action taken at s(i) . Let πϵ be the 'ϵ-greedy' version of the base policy, i.e., the intended action can be successfully chosen with probability 1 - ϵ/2 and the other action is chosen with probability ϵ/2. We use π0.1 as the evaluation policy π. 10 candidates of the sampling-policy {˜ πk}10 k=1 are constructed as follows: with probability (1 - μk), the agent chooses an action following πϵk ; with probability μk, the agent takes action αk. The settings of the sampling-policy parameters {ϵk, αk, μk}10 k=1 are summarized in Table 1.

For each sampling policy, we calculate the J-value 5 times and take the average. The numbers of episodes M and steps N are set to 10 and 5, respectively; the initial-state probability PI(s) is set to be uniform. This experiment is repeated 100 times and we evaluate the mean and standard deviation of the true generalization error and its estimate.

The results are depicted in Figure 2 (the true generalization error) and Figure 3 (its estimate) as functions of the index k of the sampling policies. We are interested in choosing k such that the true generalization error is minimized. The results show that the proposed generalization error estimator overall captures the trend of the true generalization error well. Thus the proposed generalization error estimator would be useful for choosing a good sampling policy.

4 Active Learning in Policy Iteration

In Section 3, we have shown that the unknown generalization error could be accurately estimated without using immediate reward samples in one-step policy evaluation. In this section, we extend the idea to the full policy-iteration setup.

Sample-reuse Policy Iteration (SRPI) with Active Learning: SRPI is a policy-iteration framework which allows us to reuse previously-collected samples efficiently [Hachiya et al., 2008]. Let us denote the evaluation policy at the l-th iteration by πl and the maximum number of iterations by L.

In ordinary policy-iteration methods, new data samples Dπl are collected following the new policy πl during the policy evaluation step. Thus, previously-collected data samples {Dπ1 , Dπ2 , ..., Dπl-1 } are not used:

Figure 3: The mean and standard deviation of the estimated generalization error J over 100 trials.

where 'E : {D}' indicates policy evaluation using the data sample D and 'I' denotes policy improvement. On the other hand, in SRPI, all previously-collected data samples are reused for performing policy evaluation as:

where appropriate importance weights are applied to each set of previously-collected samples in the policy evaluation step.

Here, we apply the active learning technique proposed in the previous section to the SRPI framework. More specifically, we optimize the sampling policy at each iteration. Then the iteration process becomes

Thus, we do not gather samples following the current evaluation policy πl , but following the sampling policy ˜ πl optimized based on the active learning method given in the previous section. We call this framework active policy iteration (API).

Numerical Examples: Here we illustrate how the API method behaves using the same 10-state chain-walk problem (see Figure 1). The initial evaluation policy π1 is set to be uniform and policies are updated in the l-th iteration using the ϵ-greedy rule with ϵ = 2-l . In the sampling-policy selection step of the l-th iteration, we prepare the two sampling-policy candidates {˜ π(l) k }2k=1 with (ϵ1, α1, μ1) = (0.4, 'R', 0.8), (ϵ2, α2, μ2) = (0.4, 'L', 0.8). The number M of episodes and the number N of steps are both set to 5, and J-value calculation is repeated 5 times for active learning. The performance of the learned policy πL+1 is measured by the discounted sum of immediate rewards for test samples {rπL+1 m,n }50 m,n=1 (50 episodes with 50 steps collected following πL+1):

where the discount factor γ is set to 0.9.

We compare the performance of fixed sampling policies {˜ πk}2k=1 and active learning of choosing the best sampling policy from {˜ πk}2k=1 . The results are depicted in Figure 4, showing that the proposed method works very well. Actually, the proposed method outperforms the best fixed strategy (k = 2); this can happen since the optimal sampling policy is not always k = 2 and it varies in each trial depending on randomness of the training dataset. Thus, the results show that the proposed active learning scheme can adaptively choose a good policy based on the training dataset at hand.

5 Experiments

Finally, we evaluate our proposed method using a ball-batting robot illustrated in Figure 5, which consists of two links and two joints. The goal of the ball-batting task is to control the robot arm so that it drives the ball as far as possible. The state space S is continuous and consists of the angles ϕ1[rad] (∈ [0, π/4]) and ϕ2[rad] (∈ [-π/4, π/4]) and the angular velocities ˙ ϕ1[rad/s] and ˙ ϕ2[rad/s]. Thus a state s (∈ S) is described by a four-dimensional vector: s = (ϕ1, ˙ ϕ1, ϕ2, ˙ ϕ2)⊤. The action space A is discrete and contains two elements: A = {a(i)}2i=1 = {(50, -35)⊤, (-50, 10)⊤}, where the i-th

90

80

70

60

50

40

30

k = 1(fixed)

k = 2(fixed)

k = 3(fixed)

AL

1

2

3

4

Iteration

Figure 6: The mean performance over 100 trials in the ballbatting experiment. The dotted lines denote the performance when fixed sampling policies are used and the solid line denotes the performance when the sampling policies are optimized by the proposed AL method. The error bars are omitted for clear visibility.

element (i = 1, 2) of each vector corresponds to the torque [N · m] added to joint i.

We use the Open Dynamics Engine ('http://ode.org/') for physical calculations including the update of the angles and angular velocities, and collision detection between the robot arm, ball, and pin. The simulation time-step is set to 7.5[ms] and the next state is observed after 10 time-steps; the action chosen in the current state is kept taken for 10 time steps. To make the experiments realistic, we add noise to actions: if action (f1, f2)⊤ is taken, the actual torques applied to the joints are f1 + δ1 and f2 + δ2, where δi(i = 1, 2) follows the standard normal distribution independently.

The immediate reward is defined as the horizontal carry of the ball; this reward is given only when the robot arm collides with the ball for the first time at the state s′ after taking action a at the current state s.

We use the 110 basis functions defined as

where σ is set to 3π/2 and cj (j = 1, 2, . . . , 54) are located on the regular grid {-π/4, 0} × {-π, 0, π} × {-π/4, 0, π/4} × {-π, 0, π}. We set M = 20 and N = 12 and the initial state is always set to s = (π/4, 0, 0, 0)⊤. The initial evaluation policy is set to the ϵ-greedy version of the

Performance(average)

base policy with ϵ = 0.5; the base policy is defined by the greedy update using the 'constant' ̂Q function with ̂ θi = 0.5 (1≤i≤B). Policies are updated in the l-th iteration using the ϵ-greedy rule with ϵ = 2-(1+l) . The set of samplingpolicy candidates {π(l) k }3k=1 in the l-th iteration is defined as (ϵ1, α1, μ1) = (0.1, (50,-35)⊤, 0.7), (ϵ2, α2, μ2) = (0.4, ∗, 0.0), and (ϵ3, α3, μ3) = (0.1, (-50, 10)⊤, 0.25), where the symbol '∗' means "don't care" since the value of μ is zero. The discount factor γ is set to 0.95 and the performance of the learned policy πL+1 is measured by the discounted sum of immediate rewards for test samples {rπL+1 m,n }20,12 m=1,n=1 (20 episodes with 12 steps collected following πL+1):

The results are depicted in Figure 6, showing that the proposed method works very well and it is comparable to or slightly better than the best fixed strategy (k = 2). Based on the experimental evaluation, we conclude that the proposed sampling-policy design method, API, is useful in improving the RL performance.

6 Conclusions

When we cannot collect many training samples, it is important to choose the most 'informative' samples for efficiently learning the value function. In this paper, we proposed a new data sampling strategy based on a statistical active learning method. The proposed procedure called active policy iteration (API)-which effectively combines the framework of sample-reuse policy iteration with active sampling-policy selection-was shown to perform very well in simulations with chain-walk and ball-batting robot control.