Title: ACCIDENTAL EXPLORATION THROUGH VALUE PRE-DICTORS

Abstract: Infinite length of trajectories is an almost universal assumption in the theoretical foundations of reinforcement learning. In practice learning occurs on finite trajectories. In this paper we examine a specific result of this disparity, namely a strong bias of the time-bounded Every-visit Monte Carlo value estimator. This manifests as a vastly different learning dynamic for algorithms that use value predictors, including encouraging or discouraging exploration. We investigate these claims theoretically for a one dimensional random walk, and empirically on a number of simple environments. We use GAE as an algorithm involving a value predictor and evolution strategies as a reference point.

1. INTRODUCTION:

In practice all reinforcement learning environments produce only trajectories of finite length. In the case of computer simulations this is sometimes hard-coded in the environment, but even when it is not we have to introduce a cutoff to apply most interesting algorithms. Due to this cutoff we are forced to estimate the value function using the time-bounded Every-visit Monte Carlo estimator. As we will show this estimator is significantly biased.

The time bound bias we will investigate stems directly from omitting the suffix of an infinite trajectory in the calculation of the value of a state. Because of that the influence of this bias is stronger in states that tend to appear close to the end of a trajectory. We use this asymmetry in experiments to investigate the bias by examining its influence on exploration for agents that use value predictors.

1.1. INFLUENCE ON EXPLORATION:

To find the optimal solution an agent needs to explore, that is, visit a significant portion of the state space, even if locally the reward does not encourage this behaviour. Exploration plays a fundamental role in reinforcement learning, and ensuring that algorithms explore sufficiently remains a pressing research problem. Exploration can either be undirected or directed (Thrun, 1992) . The former refers to methods like -greedy or softmax strategies (Tijsma et al., 2016) and its effectiveness is very limited. The latter attempts to implement some form of intrinsic motivation, usually based on success rate when attempting to predict future states, with methods ranging from visit counts (Tang et al., 2017) to prediction networks (Anonymous, 2019) .

To show the connection of the time bound bias with exploration consider the influence of the bias on a given state s. If, on average, the missing suffix of the total discounted reward in s is positive (resp. negative), then the bias lowers (resp. increases) the learned value of s. The later the state s appears in trajectories, the stronger the bias. Thus, if in a region of the state space all the missing suffixes have similar magnitude and are positive (resp. negative), then the bias discourages (resp. encourages) the agent to visit states that appear at later points in trajectories.

It would seem natural that negative rewards should therefore encourage exploration -states that are, on average, visited later, usually lie in previously unvisited parts of the latent space. Reaching them quicker might allow the agent to go even further. Perhaps the simplest environment in which this is the case is a constant trajectory length variant of the MountainCar environment (Moore, 1990) from the OpenAI gym (Brockman et al., 2016) . In this environment all rewards received before reaching the target -the single absorbing state -are equal to -1, and zero afterwards. Exploration is a crucial component of solving the problem. We will also show that positive rewards strongly discourage exploration and in some cases the agent simply learns to stay in proximity to the starting state.

However, negative rewards are not a solution to the exploration problem -we will construct an environment where rewards are all equal to -1, but the preference on states introduced by the bias actually discourages exploration. We also propose some ways of mitigating the bias in general.

1.2. RELATED WORK:

This paper investigates issues related to the problem of learning good policies for general Markov Decision Processes with access to only finite experience. A general algorithm for finding a nearoptimal solution of a MDP in polynomial time has been given in Kearns & Singh (2002) . This algorithm is model-based, so it can generate constant length simulations of the environment starting at any state. In our model-free setting, in contrast, the length of future experience available for a given state depends on the time it is visited. As described in the previous section this introduces some undesirable behaviour when using the Every-visit Monte Carlo estimator and our goal is to analyse these issues.

2. THE TIME-BOUND BIAS:

We will use the following notation. When an agent using policy π experiences a trajectory

(s 1 , a 1 , r 1 , s 2 , . . .) ∼ π the total discounted reward is G t := ∞ k=t γ k-t r k .

The value function is defined as

V π (s) := E π [G t | s t = s] .

(1)

In the Every-visit Monte Carlo estimator the expected value in equation 1 is replaced by an average over all occurrences of the state s within N sampled trajectories. Denoting the number of times the state s is visited in the j-th trajectory by M j we have:

EQUATION

)

The average is ill defined for states that occur an infinite number of times in any of the N trajectories, but the common assumption is that the only such state is a single absorbing state. We assume that this state has constant reward r a and its discounted value is ra 1-γ . In Sutton et al. (1998) the authors have shown that the Every-visit Monte Carlo estimator has a bias which tends to 0 as N tends to infinity. This is in contrast to the unbiased First-visit Monte Carlo estimator.

In this paper we make the more realistic assumption that every trajectory's length is equal to a constant value T . In such a case we use the time-bounded version of the total discounted reward:

G T t := T k=t γ k-t r k .

The time-bounded Every-visit Monte Carlo estimator is therefore

EQUATION

where M T j counts the occurrences of state s in the truncated trajectory. Finally, we define the time bound bias as the difference between the expected value of the timebounded Every-visit Monte Carlo estimator and the value function in equation 1

EQUATION

Unlike the case of the unbounded Every-visit Monte Carlo estimator this bias does not disappear when N tends to infinity. To show the reason let us define p π (s t = s) as the probability that for a random trajectory sampled using policy π the t-th state is equal to s. Then, by dividing the numerator and denominator of equation equation 3 by N and changing the order of summation we get

V T π,N (s) = T t=1 1 N j : sj,t=s G T j,t 1 N N j=1 M T j .

By plugging this into equation equation 4 and taking the limit with respect to N , we define

EQUATION

The last part of equation equation 5 would be equal to

0 if we replaced all E π G T t | s t = s with E π [G t | s t = s].

Therefore this bias stems directly from the missing suffixes of the trajectories.

We can reach similar conclusions for the First-visit Monte Carlo estimator -both M T j and p π (s t = s) would have to be redefined to be the number of first visits and probability that s t is the first visit respectively. This estimator will also from suffer from a variant of the time bound bias, as the problem with missing suffixes of trajectories persists. In this paper we focus only on the Every-visit variant, as it is more popular.

Finally, let us define

EQUATION

so that we simply have T-bias π (s) = V T π (s) -V π (s). If we try to learn the value function, we encounter three obstacles -the time bound bias, the bias described in (Sutton et al., 1998) , and limitations in how well the model learns. In our paper we assume the model succeeds at approximating the value estimator. We limit the approximation error by using simple environments with low dimensional state spaces and training the value predictor until it converges. We ensure the second bias is low by using a large N . Thus, the effects we describe are mainly caused by T-bias π .

3. RANDOM WALK:

In this section we investigate a simple theoretical model, namely a time-bounded one-dimensional random walk with constant reward r. Let s ∈ {⊥} ∪ ([-B, B] ∩ Z) be the state, and t ∈ {1, . . . , T } -the time. The agent's policy π is constant and defined as (p -1 , p 0 , p +1 ), where p a is the probability of moving from state s to state s + a. Attempting to visit the integers B + 1 or -B -1 causes instant transmission to the absorbing state ⊥. Then the agent receives an infinite stream of rewards equal to r.

In the case of an infinite random walk the value function is constant and equal to V π (s) = r 1-γ . A T -step random walk illustrates how an agent experiences truncated trajectories of the infinite case. We will analyse the function V T π , which here is equal to the T-bias π up to a constant factor. The walk starts at s = 0, thus |s| ≤ T . We also assume that T < B. As a consequence, the time-bounded agent will never reach the boundaries or the absorbing state, so we do not have to treat them in any special way in the calculations below.

We define the probability distribution p π (s, t) to be the probability of the state being s and the time being t. We may assume that the marginal distribution p π (t) is uniform and equal to 1 T -this is convenient, and consistent with the definition of V T π if we say that p π (s

t = s) = p π (s | t) p π (s, t) = p π (s | t) • p π (t) = p π (s | t) T .

It is worth noting that in our experiments this distribution can be interpreted as the distribution of data from the point of view of the value predictor. In this case the marginal distribution on time is also uniform, but only because we use Every-visit Monte Carlo as our value estimator.

We can calculate p π (s, t) using the recurrent formula for p π (s | t):

p π (s | t = 1) = 1 if s = 0, 0 otherwise, p π (s | t = k + 1) = p +1 • p π (s -1 | t = k) + p 0 • p π (s | t = k) + p -1 • p π (s + 1 | t = k),

and now we have:

G T t = r γ T -t+1 -1 γ -1 , V T π (s) = T t=1 p π (s, t) • G T t T t=1 p π (s, t) .

For examples of the value function with r = 1 see Figure 1 . As it turns out, the value function is an even function if only p -1 , p +1 > 0. To see this note that every partial trajectory that ends at time t in state s can be bijectively coupled with a mirror partial trajectory, where every step right is replaced with step left and step left replaced with step right. Thus if p -1 , p +1 > 0, then p(s, t) = ( p+1 p-1 ) s p(-s, t), and we get

V T π (-s) = T t=1 p π (-s, t) • G T t T t=1 p π (-s, t) = T t=1 ( p+1 p-1 ) -s p π (s, t) • G T t T t=1 ( p+1 p-1 ) -s p π (s, t) = T t=1 p π (s, t) • G T t T t=1 p π (s, t) = V T π (s).

The value function is linear with respect to the constant reward r. For r = 1 we will observe that the value function has a sharp peak at 0. The optimal policy that maximises the average value of a visited state is to always stay at 0. Thus, generalised policy iteration will be strongly biased towards this particular policy. Learning using an advantage function instead of the reward will have a similar effect, as in the case of constant reward the preference stems only from the value function. If we set r = -1 the effects will be symmetric and in turn encourage moving away from the beginning of the walk.

In Appendix A we perform a detailed analysis of the even simpler case of the Wiener process with no discount factor. This might provide the reader with a better intuition regarding the bias, as it is a good approximation of the discrete random walk.

3.1. BIAS PREVALENCE:

The time bound bias is a result of choosing the time-bound Every-visit Monte Carlo estimator, so it will be present in any setting when such a choice is made. The discrete random walk is a very simple example, but it illustrates the main properties of the bias that we are concerned with, that is the influence on exploration. We argue the bias will also have similar properties in other environments for several reasons.

First of all, the time bound bias is continuous with respect to the reward and policy. As long as rewards are of a similar order of magnitude and are either usually positive or usually negative, the value estimator should end up with a sharp peak (either positive or negative) close to the starting state. Moreover, the time bound bias is local in the sense that it does not require the whole state space to have appropriate properties. As long as an agent ends up in a previously unexplored region of the state space that exhibits the required properties, the value estimator of the new states should be biased in a similar way, encouraging or discouraging exploration in this region.

In the following sections we will carry out experiments, and empirically test the impact of the T-bias. We will also introduce certain modifications to the environments, and discuss the resulting changes in agent's performance in the context of the bias.

4. EXPERIMENTAL SETUP:

The complete codebase used for this paper can be found in the Github repository [anonymised for review] Here we just describe the basics of our experimental setup.

4.1. ALGORITHMS:

We use three algorithms throughout the paper, with various modifications that are described where applicable. Those three are:

Generalized Advantage Estimation also referred to as GAE throughout the paper, as described in Schulman et al. (2016) . In short this algorithm uses two neural networks, one to estimate the value of a state (referred to as the value predictor), and another to actually take the actions (referred to as the agent). We train the value predictor to minimise the difference between predicted value and the estimator defined by equation equation 3, which is one of the approaches discussed in the original paper.

Evolution Strategies as described in Rechenberg (1973) . This is a vary basic algorithm, which nonetheless presents excellent exploration in the problems considered. We use it for reference as an algorithm that achieves very good performance in the simple environments presented here.

Policy Gradient as described in Williams (1992) . This algorithm does not estimate values of states and the effects described in this paper do not occur. Despite being basic, it can significantly outperform algorithms with value predictors if the T-bias degrades their performance.

4.2. NETWORKS:

All the networks used in the experiments have the same architecture, including the value predictor. They consist of two hidden affine layers of size 64, each followed by an application of a leaky ReLU with leak 0.1. The final layer is again affine, with the output size dependent on the purpose of the net. The agents are all stochastic, so their networks (i.e. all but the value predictor) end with an application of softmax. The weights in the networks are initialised with values close to 0 using a normal distribution.

4.3. LEARNING PROCESS:

In the case of the evolution algorithm and policy gradient the learning process is straightforward, we just run a single episode of the environment under consideration and immediately update the agent using the gathered experience. With GAE we update the agent when the first episode is completed after taking 2048 steps. This lowers the bias due to a finite number of trajectories when using the Every-visit Monte Carlo value estimator. By default we use a discount factor of 0.98. In all cases we use the Adam optimiser (Kingma & Ba, 2015) .

GAE needs one more parameter called λ, controlling the impact of advantages with different time gaps between states. Our theoretical discussion essentially assumes λ = 0, that is computing the advantages only using values in consecutive steps. However, the original GAE paper (Schulman et al., 2016) suggests using much bigger values and most implementations follow their advice. In our experiments setting λ = 0.95 did not add significant effects, so to keep our results practical we use this value.

4.4. NORMALISATION:

To provide greater stability we normalise the cumulative discounted rewards passed to the policy gradient and evolution agents, and also the advantages passed to the GAE agent. We use a running normalise with a discount factor of 1 2 . We do not perform any normalisation of target values for the value predictor.

5. ENVIRONMENTS:

We consider two environments to show the effects described in section 3. Later we explore various modifications of those environments to pinpoint the exact nature of the effects.

All the graphs presented in this and further sections contain translucent dots, representing the total episode rewards in specific runs of the algorithms, and lines representing the average reward. We ran 16 copies of every algorithm. When interpreting those one should take note that while the lines move, dots usually appear in the same areas. This is due to the challenge in the environments being mostly exploration, so whenever an algorithm finds any solution it often quickly learns how to achieve it consistently.

5.1. MOUNTAINCAR:

First we consider the MountainCar environment from the OpenAI gym. A single episode ends after at most 200 steps. This is equivalent to saying that we set T = 200 and after reaching the target, the agent enters the absorbing state and receives rewards equal to zero afterwards. Because of the sparse reward in this environment any algorithm not including a nontrivial exploration component gets stuck close to the starting position. In practice no trajectory will randomly reach the goal, so there simply is no data to learn from. Yet, when ran with the GAE algorithm, the environment gets solved quite rapidly. The results are shown in Figure 2a . This is precisely the result we should expect. Since all the steps have reward -1 and all random trajectories have length 200, the states that are visited on average later in a trajectory have a higher value estimation. It remains to note that a random trajectory starts close to the centre of the valley, but will gather some momentum with time, thus making the states further from the centre appear more valuable. With a value predictor the agent will be therefore incentivised to seek out states further from the centre, which eventually leads it to the goal.

5.2. AXIS WALK:

To show that the time bound bias can also have obviously negative consequences we consider a very simple environment, in which the agent walks on the axis of integers, starting at 0. In every step it is allowed to move either right or left and the reward at a step ending up in state s (which is an integer) is 1 -1 8(1+s 2 ) . Every episode ends in the same number of steps, either 20 or 200, depending on the variant of the environment used. It is easy to see that, since states further from the centre have higher rewards, the optimal strategy is to pick a direction and always walk that way. This environment is a very close approximation of the random walk described in Section 3, since all rewards are quite close to 1. Therefore we should expect the GAE agent to avoid states far from 0, which is the exact opposite of the optimal strategy. Our expectations are confirmed in Figure 3 . The effect is weaker in the variant with more steps and we will discuss this phenomenon in Section 6.

Note that here even the policy gradient performs well in comparison to the GAE. This task is extremely easy, but the T-bias makes it impossible to solve, in reasonable time, using algorithms relying on value predictors. 

5.3. DRAGCAR:

The above examples might give the impression, that just setting rewards in every step to a constant negative value encourages exploration. To dispel this notion we present a slight modification of MountainCar in which standard value predictors discourage exploration. This requires two modifications. First, one needs to introduce drag to the environment. The drag coefficient is not substantial and decreases the maximal achievable reward insignificantly. It's especially worth pointing out that just adding drag makes the algorithms perform about as good as without it.

Second, one needs to move the starting position. Instead of starting in the middle of the valley, the car randomly starts either halfway up the left or halfway up the right hill. Due to the drag, if the agent does nothing the car will slowly converge to the middle of the valley. So will in fact a random agent. It will obviously still create some swinging, but it's amplitude will be significantly smaller than the difference between the starting points. In this case the value predictor cannot extrapolate good rewards uphill. When this happens the agent often learns to stay at the bottom of the valley, never leaving the spot. This is confirmed by the results visible on Figure 2b , which presents a sharp drop in the performance of GAE compared to Figure 2a , as it never reaches the goal. Also note that the evolution strategy performs better on this problem than on the standard MountainCar. This is due to the fact that the car starts with greater potential energy.

5.4. MOUNTAINCAR+R:

To see the scope of the effects described above it is useful to look at another set of slight modifications of the MountainCar environment. Observe that adding a constant value R to every reward does not change the goal of the (infinite) environment -the optimal policy is still to reach the absorbing state in as few steps as possible. Note that the value V π of every state increases by R 1-γ . This also includes the absorbing state, as now the agent receives infinite stream of rewards R after reaching the top of the hill.

The OpenAI implementation of the MountainCar environment treats it as an episodic task, which ends immediately after reaching the target state. To fit it into our paradigm, we extend all trajectories to be of infinite length, and treat the goal state as an absorbing state. The agent cannot leave it, and all steps after reaching it give reward zero. We set T = 200. Next, we produce two new environments by setting R to either 1 or 2. We will call them MountainCar+1 and MountainCar+2 respectively. Even if the time limit T was a part of the task, and not just a restriction on the trajectory length, these Under review as a conference paper at ICLR 2019 modifications would not change the goal or the optimal strategy of an agent. They do, however, change the behaviour of GAE agents, precisely because of the time bound bias.

After adding 1, all the rewards in a trajectory that does not reach the goal state are 0. In such a case the value estimator V T π is nearly 0, so the impact of the bias on exploration is negligible. Adding 2 on the other hand makes all the rewards 1, so early states are more valuable, which discourages exploration. The results can be seen in Figure 4 . Note that the performance of the evolution strategy remains unchanged. Figure 4 : Performance of all the algorithms on the modified MountainCar environment, as described in Section 5.4.

In the case of MountainCar+1 we can still see some exploration. We argue that this is mainly due to the "consistent noise", by which we mean that a randomly initialised value predictor will assign higher value to some areas in state space, so the GAE agent will be attracted to those areas. We discuss this phenomenon briefly in Appendix C. Nevertheless, we see that its impact on exploration is significantly weaker.

6. MITIGATING EFFECTS OF THE BIAS:

In this section we propose three attempts at removing effects caused by the time bound bias. None of the solutions are completely satisfactory, but each one approaches the problem from a different angle and partially explains the relationship between the bias and exploration.

6.1. ADJUSTING γ:

We can limit the bias by lowering the discount factor γ. When we do so, rewards included in the missing suffixes of the trajectories become more discounted, so removing them introduces weaker bias. Note that lengthening the episode has a similar effect, as mentioned in Section 5.2. The results of adjusting the discount factor can be seen in Figure 5 . Of course this does not completely eliminate the biases, they are still influential near the ends of the trajectories. What is perhaps a more important problem with this solution is the obvious trade-off.

Lowering the discount factor actually makes the agents less sensitive to rewards further away in the future. In the case of many environments this is not an acceptable sacrifice.

6.2. BETTER APPROXIMATION OF REWARDS AFTER EPISODE END:

The second class of solutions we propose focuses on finding a better guess for what the rewards after time T should be. We discuss some approaches, but once again none are quite satisfactory. A very simple idea would be to assume the value of the last state is the discounted average reward summed to infinity.1 This approach introduces a new bias, but in our environments it works reasonably well in practice, see Figure 6 . Figure 6 : Performance when the value of the last state is assumed to be the average reward summed to infinity.

Another approach would be to use the value predictor to simply predict the value of the last state and assume this prediction is correct. The assumption introduces some reflective dependency on the learning process, which is of course worrying because of the added complexity. This proves to be a problem also in practice, see Figure 7 . In particular note that the biases are all still present, but at least in the case of Axis walk the modification eventually helps. The prediction of the value for an absorbing state is still a problem, since if we cannot distinguish it from other states we cannot set it to 0, and it keeps being determined by the state of the value predictor. Figure 7 : Performance where the value of the last state is assumed to be correctly predicted by GAE.

6.3. ENFORCING THE MARKOV PROPERTY:

The final approach is to present a different perspective on the effects' origin. Let us observe that cutting off trajectories early is equivalent to stating that we modify the environment's definition, so that after time T the agent enters an absorbing state, and all consecutive rewards are equal to zero.

These two descriptions are indistinguishable from the agent's perspective, thus all effects observed during training must be explainable in the latter case. Note that this modification does not change the optimal policies of the environments we present in this work.

In the modified environment the time-bound bias vanishes completely, but the time-dependence of the last transition violates the definition of a Markov Decision Process. Therefore, we can attempt to remove the undesirable effects by reintroducing the Markov property. We did it by making one final modification: we append time to states. The results can be seen in Figure 8 . The remaining exploration in the case of MountainCar is mostly caused by the consistent noise effect. In particular, compare this to Figure 4a . This solution lets us gain an important insight into the problem, but is unsatisfactory, because the environment represents a completely different, although related, process.

Another way of removing the problematic effects would be, instead of using a "hard" cutoff for trajectory length, to allow the trajectory to randomly enter the absorbing state at any time with constant probability p. This approach might be an interesting area of research, as it might provide a better way of representing infinite Markov decision processes in finite implementations. However, it violates our assumption about trajectories of constant length, so it is beyond the scope of this paper.

7. CONCLUSIONS:

In many environments using value predictors might result in unexpected learning patterns. We demonstrated that both discouragement and encouragement of exploration, as well as constraining movement to a small segment of the state space, occur in simple environments. When using GAE or similar algorithms one should therefore exercise caution, keep in mind the possibility of bias, and where applicable attempt some form of mitigation. We proposed a couple partial solutions together with advise when to use or avoid them.

Value predictors are of course very useful and work quite well in many settings, so despite the flaws we demonstrated they should enjoy continued popularity. We hope that further research will discover either better ways of mitigating the biases described in this paper or some algorithms that avoid the problems altogether while keeping the strengths of value predictors.

A WIENER PROCESS:

We will use the following properties of a Wiener process:

1. A Wiener process W t is a family of probability distributions on R.

2. W 0 = 0 almost surely. 3. W t ∼ N (0, t).

Since it is a normal distribution, W t has density function

f t (x) = 1 √ 2πt exp(-x 2 2t

). Constraining ourselves to the time-bounded case translates directly into the assumption that t ∈ [0, T ]. If we further assume that the time is distributed uniformly, we can define the density function on R×(0, T ]:

f (x, t) = 1 T 1 √ 2πt exp - x 2 2t .

We now can define the average time at the state x, denoted by T (x). This value is of interest to us, because in the discrete case with constant reward r in every step, visiting state x at time t results in (undiscounted) cumulative reward equal to r(T -t). In that case the average value of state x is equal to r (T -T (x)). The average time at the state x is

T (x) = T 0 tf (x, t)dt T 0 f (x, t)dt = - x 2 3 + T 3 1 1 - √ π |x| √ 2T exp(x 2 /2T ) erfc(|x|/ √ 2T )

, where erfc is the complementary error function:

EQUATION

See appendix B for detailed calculations.

For clarity, we may write

T (-x √ 2T ) = T (x √ 2T ) = T 3 -2x 2 + 1 1 - √ πx • exp(x 2

) erfc(x) for x ≥ 0. This cannot be expressed in terms of elementary functions, but the part √ πx • exp(x 2 ) erfc(x) can be approximated with small relative error, see Oldham (1968) .

Even though erfc is not an elementary function we know that erfc(0) = 1 and (erfc(x)) = 2 π exp(-x 2 ). Thus we may calculate the exact value of T and its directional derivatives at zero. For example T (0) = T 3 and T (0) = T π 18 . This gives some intuition about the steepness of the function in the proximity of the beginning of the walk. The value at zero grows linearly with T , while the steepness -sublinearly. The expected time for several trajectory lengths can be seen in Figure 9 . Setting W t ∼ N (0, tσ 2 ) for σ > 0 entails f σ 2 (x, t) = 1 σ f ( x σ , t) and, as a consequence, T σ (x) = T (x/σ). This should remind us of the discrete N -step random walk, where a single step has mean zero and variance σ 2 . For large t the probability distribution of states in such a walk converge in distribution to N (0, tσ 2 ) due to the central limit theorem.

B THE AVERAGE TIME AT A STATE IN THE WIENER PROCESS:

In this appendix we compute the average time at a state in the Wiener process. First some definitions relating to the error function:

erf(x) = 2 √ π x 0 e -y 2 dy, erfc(x) = 1 -erf(x) = 2 √ π ∞ x e -y 2 dy, erf(+∞) = 1.

We will also use the following integrals:

EQUATION

EQUATION

We want to calculate the expected time at state x

EQUATION

).

First we compute the denominator:

EQUATION

)).

(10)

Under review as a conference paper at ICLR 2019 Now the numerator:

T 0 tf (x, t)dt = T 0 t 1 T 1 √ 2πt exp(- x 2 2t )dt = . . . w 2 = x 2 2t , dt = - x 2 w 3 dw, √ t = |x| w √ 2 . . . = 1 T |x| 3 2 √ π +∞ |x| √ 2T

e -w 2 w 4 dw

EQUATION

))

(11)

Thus, combining the results: We argue that the main source of exploration is the value predictor, which is being initialised randomly and therefore containing some bias. By "consistent noise" we mean that a randomly initialised value predictor will assign higher value to some areas in state space, so the GAE agent will be attracted to those areas. Since the predictor is updated relatively slowly, this attraction will be somewhat consistent between episodes. Also, the advantages are normalised before passing them to the agent. If the value network is trained to predict zero everywhere, then even small deviations from the target will be magnified after the normalisation.

T (x) =

We further validate this explanation by showing that the standard MountainCar environment can be solved by a variant of the GAE algorithm, which does not update the value predictor (see Figure 10 ). Note that the results are comparable to the MountainCar+1.

C.2 OPTIMISTIC INITIALISATION:

It is valuable to compare the experiments with the MountainCar environment to the experiments in Sutton et al. (1998) . There the source of exploration is the biased initialisation of (tabular) value predictor. All states have initial value equal to zero, and then the algorithm learns that the visited states actually have negative value, thus tries to explore the unseen parts of the state space.

This kind of bias is weaker if the value predictor is a neural network, as it can generalise to new regions of the state space. Also, it does not help to solve the DragCar environment. On the other hand, the T-bias has much stronger influence, because it can boost the exploration even on the already seen part of the state space, and not only on the borders of the known region.

:

We want to thank [name redacted] for bringing this idea to our attention.

Figures and Tables:

Figure 1: Value functions for a finite discrete random walk. Note that the vertical axis varies between the 4 plots.

Figure 2: Performance of three algorithms on both the Car problems.

Figure 3: Performance of three algorithms on two variants of axis walk.

(a) Axis walk, 20 steps per episode (b) MountainCar

Figure 5: Performance when we lower the discount factor in GAE from 0.98 to 0.8.

Figure 8: Performance when time is part of the state.

Figure 9: Expected time at a state, for several trajectory lengths.

the phenomenon shown in Figure4a. In case of the MountainCar+1 environment the agent receives constant reward equal to zero until it reaches the absorbing state. It turns out that the GAE agent sometimes manages to solve the environment, despite having no exploration boost caused by the T-bias -the Monte-Carlo value estimator is equal to zero.

Figure 10: Performance of the GAE algorithm on the MountainCar environment when the value predictor is never updated.

Peer review (iclr2019):
 UPDATE: I have read the authors’ response and the other reviews. While the authors have made some improvements, my core criticism remains – the paper does not produce concrete theoretical or empirical results that definitively address the problems described. In addition, there are many confusing statements throughout the paper. For instance, the discussion of positive and negative rewards in the introduction does not conform with the rest of the literature on exploration in RL. The authors also seemed to have missed the point of the Kearns & Singh reference. The authors are right that the older paper is a model-based approach, but the idea is that they too were solving infinite-horizon MDPs with finite trajectories and not introducing a bias. Summary: The paper attempts to link the known mismatch between infinite horizon MDP values and finite trajectory sums to the problem of exploration. Trajectories in environments requiring exploration (mountain car and a number-line walk) are shown and the effects of changing trajectory lengths and initial values are discussed. Potential solutions to the problem are proposed though the authors did not deem any of the solutions satisfactory. Review: The paper brings up a number of important issues in empirical reinforcement learning and exploration, but fails to tackle them in a manner that convincingly isolates the problem nor proposes a solution that seems to adequately address the issue. Specifically, several issues seem to be studied at once here (including finite-horizon MDPs, function approximation, and exploration), relevant work from the exploration and RL community is not cited, the early experiments do not reach a formal theoretical claim, and the proposed solutions do not appear to adequately address the problem). These issues are detailed below. First, the paper is considering many different issues and biases at once, including those introduced by initialization of the value function, exploration policies, function approximation, and finite/infinite length trajectories. While the authors claim in several places that they show one bias is more important than another, no definitive experiment or theorem is given showing that finite-length trajectories are the cause of bad behavior. While it is well known that infinite-horizon MDPs do not exactly match value functions for finite horizon MDPs, so many other factors are included in the current work (for instance the use of neural networks) that it remains unclear that the finite/infinite mismatch is an issue. The paper also fails to cite much of the relevant work on these topics. For instance, the use of infinite-horizon MDPs to study finite learning trajectories is often done under the guise of epsilon-optimal guarantees, with epsilon derived from the discount factor (see “Near-Optimal Reinforcement Learning in Polynomial Time”). In addition, the effects shown in mountain car when changing the values or the initialization function, mirror experiments with Q-learning that have shown that there is no one initialization scheme that guarantees optimal exploration (see Strehl’s thesis “Probably Approximate Correct Exploration in Reinforcement Learning” ). Overall, the paper seems to confuse the problems of value initialization and trajectory length and does not show that they are particularly related. In addition, the early sections covering theoretical models such as Wiener Processes and Random Walks lay out many equations but do not come to a specific formally proven point. No theorem or proof is given that compactly describes which exact problem the authors have uncovered. Therefore, when the solutions are presented, it remains unclear if any of them actually solve the problem. Finally, several of the references are only ArXiv pre-prints. Papers submitted to ICLR or other conferences and journals should only cite papers that have been peer-reviewed unless absolutely necessary (e.g. companion papers).