Title: OPTIONS DISCOVERY WITH BUDGETED REINFORCE-MENT LEARNING

Abstract: We consider the problem of learning hierarchical policies for Reinforcement Learning able to discover options, an option corresponding to a sub-policy over a set of primitive actions. Different models have been proposed during the last decade that usually rely on a predefined set of options. We specifically address the problem of automatically discovering options in decision processes. We describe a new learning model called Budgeted Option Neural Network (BONN) 1 able to discover options based on a budgeted learning objective. The BONN model is evaluated on different classical RL problems, demonstrating both quantitative and qualitative interesting results.

1. INTRODUCTION:

Reinforcement Learning (RL) is one of the key problem in machine learning , and the interest of the research community has been recently renewed with the apparition of models mixing classical reinforcement learning techniques and deep neural networks. These new methods include for example the DQN algorithm (Mnih et al., 2015) and its variants (Van Hasselt et al., 2015) , the use of recurrent architectures with policy gradient models (Wierstra et al., 2010) , or even approaches like Guided Policy Search (Levine & Koltun, 2013) or actor-critic algorithms (Konda & Tsitsiklis, 1999) .

Research in cognitive science based on the study of human or animal behavior have long emphasized that the internal policy of such agents can be seen as a hierarchical process where solving a task is obtained by sequentially solving sub-tasks, each sub-task being treated by choosing a sequence of primitive actions (Botvinick et al., 2009) . In the computer science domain, these researches have been echoed during the last decade with the apparition of the hierarchical reinforcement learning paradigm (Dayan & Hinton, 1993; Dietterich, 1998; Parr & Russell, 1998) and its generalization to options (Sutton et al., 1999) . The underlying idea is to define a policy at two different levels: a level which goal is to choose between options, and a level which will select the actions to apply to the environment based on the current option. Informally, in a maze an option can correspond to an order like go to the door, while the actions are primitive moves (up, down, left, right) . In the literature, the catalog of available options is usually specified manually which is not satisfactory.

We propose a new architecture called BONN (Budgeted Options Neural Network) able to simultaneously discover options and to learn how and when to use them. It is based on the idea that a good policy is a trade-off between policy efficiency and cognitive effort: a system will learn relevant options if these options allow it to reduce the cognitive effort for solving the task, without decreasing the quality of the solution. This idea is implemented here through a budgeted learning problem that encourages the BONN model to learn to acquire as few information as possible.

The contributions of the paper are: (i) We propose the BONN model able to discover options based on a Budgeted Reinforcement Learning problem where information acquisition has a cost, each option being a continuous vector in an learned latent option space. (ii) We propose a discrete variant of BONN (D-BONN) where a discrete set of options is learned, each option corresponding to a particular embedding in the latent option space. (iii) The model is tested on different RL tasks and exhibits interesting properties and a strong ability to capture relevant options.

The paper is organized as follows: we present the background in RL and on recurrent policy gradients methods in Section 2. The BONN model is presented in Sections 3.1 while the budgeted learning problem is described in Section 3.2. The variant of BONN able to extract a discrete set of options is given in Section 3.3. At last, experiments are proposed in Section 4 while the related works are presented in Section 5.

2. BACKGROUND 2.1 (PO-) MARKOV DECISION PROCESSES AND REINFORCEMENT LEARNING:

Let us denote a MDP as a set of states S, a discrete set of possible actions A, a transition distribution P (s t+1 |s t , a t ) and a reward function r(s, a) ∈ R + . We consider that each state s t is associated with an observation x t ∈ R n , and that x t is a partial view of s t (i.e POMDP), n being the size of the observation space. Moreover, we denote P I the probability distribution over the possible initial states of the MDP.

Given a current trajectory x 1 , a 1 , x 2 , a 2 , ...., x t , a policy is defined by a probability distribution such that π(x 1 , a 1 , x 2 , a 2 , ...., x t , a) = P (a|x 1 , a 1 , x 2 , a 2 , ...., x t ) which is the probability of each possible action a at time t, knowing the history of the agent.

2.2. LEARNING WITH RECURRENT POLICY GRADIENT:

Let us denote γ ∈]0, 1] the discount factor, and R t = T -1 k=t γ k-t r(s k , a k ) the discounted sum of rewards (or discount return) at time t 2 , corresponding to the trajectory (s 0 , a 0 , s 1 , a 1 , ...., s T ) with T the size of the trajectories sampled by the policy3 .

We can define the reinforcement learning problem as the optimization problem such that the optimal policy π * is computed by maximizing the expected discounted return J(π):

EQUATION

where s 0 is sampled following P I and the actions are sampled based on π.

Different learning algorithms aim at maximizing J(π). In the case of policy gradient techniques, if we consider that, for sake of simplicity, π also denotes the set of parameters of the policy, the gradient of the objective can be approximated with:

∇ π J(π) ≈ 1 M M m=1 T -1 t=0 ∇ π log π(a t |x 0 , a 0 , ..., x t ) (R t -b t ) (2)

where M is the number of sampled trajectories used for approximating the gradient using Monte Carlo sampling techniques, b t is a variance reduction term at time t estimated during learning, and we consider that future actions do not depend on past rewards (see Wierstra et al. (2010) for details on recurrent policy gradients).

2 Note that R0 = T -1 k=0 γ k r(s k , a k ) correspond to the classical discount return x 1 z 1 a 1 σ 2 x 2 z 2 a 2 σ 3 x 3 z 3 a 3 σ 4 x 4 z 4 a 4 σ 5

x 3 BUDGETED OPTION NEURAL NETWORK

3.1. THE BONN ARCHITECTURE:

We consider here a particular case of POMDP where the agent always observe x t , but can also ask for the supplementary observation y t that will help him to decide which action to choose. This situation corresponds to many practical cases: for example a robot that acquires information through its camera (x t ) but can sometimes decide to make a complete scan of the room (y t ); a user driving a car (using x t ) but who decides to consult its map or GPS (y t ); a virtual agent taking decisions in a virtual world (based on x t ) but that can ask instructions from a human (y t ), etc. Note that x t or y t can be an empty observation.

We now describe the budgeted option neural network. This model is composed of three components.

The underlying idea is that the first component will use the additional observations y t to compute which option to use, while the second component will use the basic observations x t and the lastly chosen option to sample primitive actions; the third component being used to decide when to switch between options. A new option will thus be computed each time y t is acquired. Let us now describe how each component works: (i) The first one (or option model) aims at choosing which option to apply depending on the observations y t collected over the states of the process. In our model, an option is represented by a vector denoted o t ∈ R O , O being the size of the options representation space. (ii) Choosing a new option o t will then initialize the second component (or actor model).

During the next time steps, the actor model will sequentially choose actions based on observations x t and update its state until a new option is generated. (iii) The acquisition model denoted σ t ∈ {0; 1} will decide if the model has to acquire y t or not.

To better understand this two-levels architecture, we provide the inference pseudo-code in Algorithm 2 and the architecture of BONN in Figure 1 . We now describe the resulting components (the details are given in the Appendix):

Option model: The option model will be denoted f such that f (y t ) = o t generates an option o t as a latent vector in a latent space R O , O being the dimension of this space. Note that the option model is a deterministic model where the option is computed based on the current observation using a neural network (see Appendix). Recurrent versions of the option model will be studied in a future work.

Actor Model: The state of the actor model is represented by a vector z t ∈ R Z , Z being the size of the latent space of the actor model. Execute the chosen action 13:

end for 14: end procedure a new option is not generated, the actor state is updated with a classical recurrent mechanism i.e z t+1 = g(z t , a t , x t+1 ) Acquisition Model: The acquisition model aims at deciding if a new option has to be generated. It is a stochastic process such that σ t = 1 (new option) or σ t = 0 (keep the same option) and is computed over the state of the actor and the new observation x t : P (σ t+1 = 1) = h(z t , a t , x t+1 ). In our case, this probability is based on a Bernoulli distribution over a sigmoid-based h function (see Appendix).

3.2. BUDGETED LEARNING FOR OPTIONS DISCOVERY:

The way options emerge in a hierarchical reinforcement learning system has been the topic of many different works in both reinforcement learning and cognitive science. Most of these techniques associate the problem of option discovery with the problem of sub-goals discovery where different strategies are used to discover the sub-goals -see Botvinick et al. (2009) for a review on links between cognitive research and hierarchical reinforcement learning. The BONN model is based on a different approach, where we consider that the discovery of options will result in learning a good trade-off between policy efficiency and the cognitive effort generated by such a policy. The underlying idea is that a system will learn relevant options if these options allow to reduce the cognitive effort that is generated when solving the task, without decreasing the quality of the solution. Note that the reduction of the cognitive effort has already been studied in cognitive science (Kool & Botvinick, 2014) , and very recently in the RL context (Bacon & Precup, 2015b ) but defined differently.

Here, the cognitive effort is associated with the acquisition of the additional information y t , this additional information (and its computation) being considered costly but crucial for discovering a good policy: an agent only using the observations x t would be unable to solve the task, but using y t at each time step would be "too expensive". The design choice of x t and y t is fundamental in the architecture, and is a distinct solution for bringing expert knowledge rather than explicitly defining sub-tasks.

Let us denote C =:

T -1 t=0 σ t the acquisition cost for a particular episode: by reducing C, we will encourage the agent to learn relevant options that will be used during many time steps, the model extracting relevant sub-policies. We propose to integrate the acquisition cost C (or cognitive effort) in the learning objective, relying on the budgeted learning paradigm already explored in different RL-based applications (Contardo et al., 2016; Dulac-Arnold et al., 2012) . We define an augmented reward r * that includes the generated cost:

r * (s t , a t , σ t ) = r(s t , a t ) -λσ t (3)

where λ controls the trade-off between the task efficiency and the cognitive charge. The resulting discounted return denoted R * 0 will be used as the objective to maximize instead of the classical discounted return R 0 , resulting in the following policy gradient update rule:

π ← π -γ T -1 t=0 (∇ π log P (a t |z t ) + ∇ π log P (σ t |z t-1 , a t-1 , x t )) (R * t -b * t ) (4)

where γ is the learning rate. Note that this rule now updates both the probabilities of the chosen actions a t , but also the probabilities of the σ t that can be seen as internal actions and that decide if a new option has to be computed or not, b * t being the new resulting variance reduction term.

3.3. DISCOVERING A DISCRETE SET OF OPTIONS:

In the previous sections, we considered that the option o t generated by the option model is a vector in a latent space R O . This is slightly different than the classical option definition which usually considers that an agent has a given "catalog" of possible sub-routines i.e the set of options is a finite discrete set. We propose here a variant of the model where the model learns a finite discrete set of options.

Let us denote K the (manually-fixed) number of options one wants to discover. Each option will be associated with a (learned) embedding denoted o k . The option model will store the different possible options and choose which one to use each time an option is required. In that case, the option model will be considered as a stochastic model able to sample one option index denoted i t in {1, 2, ..., K} by using a multinomial distribution on top of a softmax computation. In that case, as the option model computes some stochastic choices, the policy gradient update rule will integrate these additional internal actions with: 

EQUATION

4. EXPERIMENTS:

The complete details of the architecture used for the experiments are provided in the Appendix. We have tested this architecture on 3 different types of environments and compared it to a Recurrent Policy Gradient algorithm using a GRU-based neural network (R-PG):

CartPole: This is the classical cart-pole environment as implemented in the OpenAI Gym4 platform where observations are (position, angle, speed, angularspeed), and actions are right or lef t. The reward is +1 for every time step without failure. For BONN, the observation is only used by the option model i.e y t = (position, angle, speed, angularspeed), the actor model receiving an empty observation x t = ∅ at each time step.

Lunar Lander: This environment corresponds to the Lunar Lander environment proposed in OpenAI Gym where observations describe the position, velocity, angle of the agent and if he is in contact with the ground or not, and actions are do nothing, fire left engine, fire main engine, fire right engine. The reward is +100 if landing, +10 for each leg on the ground, -100 if crashing and -0.3 each time the main engine is fired. As for the cart-pole, the observation is only acquired by the option model, the actor model receiving an empty observation x t = ∅ at each time step.

Multi-room Maze: The Multi-room Maze corresponds to a maze composed of k × k rooms (k = 2 or k = 3), with doors between them (see Figure 3 ). The agent always starts at the upper-left corner, while the goal position is chosen randomly at each episode: it can be in any room, in any position and its position changes at each episode. The reward function is -1 when moving and +20 when reaching the goal, while 4 different actions are possible: (up, down, lef t, right). We consider two variants: M AZE 1 where x t = ∅ is the empty observation and the agent must learn when to acquired the more informative observation y t which contains the observed doors, the agent position and the goal position if the goal is in the same room than the agent (i.e the agent only observes the current room).

In the M AZE 2 world, x t is the agent position in the room, while y t corresponds to the description of the room and the goal position if the goal is in the same room (i.e contrary to M AZE 1 , the agent always observes his position). The R-PG baseline has access to all these information (doors, position, goal) at each time step. Note that this environment is much more difficult than other 4rooms problems (introduced by Sutton et al. ( 1999)) in others RL works, where there is only one or two goal position(s), and that, in a more realistic way, the agent only observes the room he is in.

For all the environments, we consider different levels of stochasticity such that the movement of the agent can fail with probability , in which case a random transition is applied.

the action chosen by the agent is applied with probability 1while a random action is chosen with probability . The higher epsilon is, the more the environment is stochastic.

4.1. QUANTITATIVE ANALYSIS:

We illustrate the quality of BONN with cost/reward curves (see Figure 2 ) where the X-axis corresponds to the number of times an option is computed (normalized w.r.t the size of the episode) while the Y-axis corresponds to the overall reward R = r(s t , a t ) obtained on each task, for different levels of stochasticity . Note that cost/reward curves are generated by computing the Pareto front over all the learned models at different cost levels λ. These curves have been obtained by first learn- ing our model with a zero cost λ = 0 and then by progressively increasing this cost, forcing the model to acquire y t less frequently and to discover options5 .

First, one can see that even at low cost values (with only a few options computed), the BONN model is able to keep the same performance than the R-PG model, even if R-PG uses all the information contained in both x t and y t at each time step. Some specific cost/reward values are given in Table 1 for different environments and different values of λ, confirming that BONN is able to keep a high performance level while discovering relevant options. Note that if the cost of computing a new option is too expensive, the BONN model is not able to find a good policy since it is not allowed to switch between options.

We can also see that the obtained reward decreases when the environments are more stochastic, which seems intuitive since stochasticity makes the tasks harder. Figure 4a compares the results obtained on the M AZE 1 environment and the M AZE 2 environment when λ = 0.25. We note that the drop of performance in M AZE 2 happens at a lower cost than the one in M AZE 1 . Indeed, in M AZE 2 , the agent has access to its position at each time step and is more able to "compensate" the stochasticiy of the environment than in the M AZE 1 case, where the position is only available through y t .

Figures 3b and 3a illustrates trajectories generated by the agent in the M AZE 2 environment, and the positions where the options are generated. We can see that the agent learns to observe y t only once in each room and that the agent uses the resulting option until it reaches another room (thus the agent deducts from y t if he must move to another room, or reach the goal if it is in the current room). Note that the agent cannot find the shortest path to the goal's room because, having no information about the position of the goal in another room, it learns to explore the maze in a "particular" order until reaching the goal's room. We have visualized the options latent vectors using the t-SNE algorithm (Figure 4b ). Similar colors (for example all green points) mean that the options computed correspond to observations where the goals are in similar areas. We can for example see that all green options are close, and it shows that the latent option space has captured a particular structure. Analyzing this latent structure will be the topic of a future research.

The D-BONN model has been experimented on the M AZE 1 2 × 2, and an example of generated trajectories is given in Figure 3c . Each color corresponds to one of the learned discrete options. One can see that the model is still able to learn a good policy, but the constraint over the fixed number of discrete options clearly decreases the quality of the obtained policy. It seems thus more interesting to use continuous options instead of discrete ones, the continuous options being regrouped in smooth clusters as illustrated in Figure 4b . (Dayan & Hinton, 1993; Dietterich, 1998; Parr & Russell, 1998) has been the surge of many different works during the last decade because it is considered as one solution to solve long-range planning tasks and allows to transfer knowledge between tasks. Many different models have been proposed where subtasks are a priori known like Dietterich (1998) which proposes the MAXQ method. The concept of option has been introduced by Sutton et al. (1999) . In this architecture, each option consists of an initiation set, its own policy (over primitive actions or other options), and a termination function which defines the probability of ending the option given a certain state. Other works defines hierarchical policies based on different levels of observations: the Abstract Hidden Markov Model (Bui et al., 2002) is based on discrete options defined on each space region, while in Heess et al. (2016) the architecture uses a low-level controller that as only access to the proprioceptive information and a high-level controller has access to all observations.

The concept of options is at the core of many recent articles, for example in Kulkarni et al. ( 2016), the Deep Q-Learning framework is extended to integrate hierarchical value functions using intrinsic motivation to learn the option policies. But in these different models, the options have to be manually chosen a priori and are not discovered during the learning process. Still in the option framework, Daniel et al. (2016) learns options (both policies and termination probabilities) without supervision using the Expectation Maximization algorithm. More recently, Bacon & Precup (2015a) does the same with the option-critic architecture, close to an actor-critic algorithm where options are discrete. They used a similar experiment to ours with four rooms but only one (fixed) goal ; learning both option policies and termination functions, the model converges to an option in the first room followed by a second one in rooms 2 and 3. The closest work to our seems to be Bacon & Precup (2015b) but the model is also based on a discrete set of options in the POMDP framework. Note that this article also introduces the cognitive effort concept. Some models are focused on the problem of learning macro-actions (Hauskrecht et al., 1998; Mnih et al., 2016) . In that case a given state is mapped to a sequence of actions (i.e macro-actions), similar than when having x t empty in the BONN-model. But macro-actions are more restricted than options since the sequence of actions is fixed.

The main difference between these works and the BONN architecture is that, in the case of BONN, options are latent vectors and the model is able to learn a manifold of possible options -even if a discrete version has also been proposed with less convincing performances.

Outside reinforcement learning, our work is also in relation with the Hierarchical Multiscale Recurrent Neural Networks (Chung et al., 2016) that discover hierarchical structure in sequences.

6. CONCLUSION AND PERSPECTIVES:

We have proposed a new model for learning options in POMDP where the agent can choose to acquire a more informative observation at each time step. The model is learned in a budgeted learning setting where the acquisition of an additional information, and thus the use of a new option, has a cost. The learned policy is a trade-off between the efficiency and the cognitive effort of the agent. In our setting, the options are handled through learned latent representations, and we have also proposed a discrete version of BONN where the number of options is kept constant. Experimental results show that the model is able to extract relevant options in complex environments. This work opens different research directions. One is to study if BONN can be applied in multi-task reinforcement learning problems (the environment M AZE, since the goal position is randomly chosen at each episode, can be seen as a particular simple multitask RL problem). Another question would be to study problems where many different observations can be acquired by the agent at different costs -e.g many different sensors on a robot.

:

code available here: https://github.com/aureliale/BONN-model

We describe finite-horizon problems where T is the size of the horizon and γ ≤ 1, but the approach can also be applied to infinite horizon problems with discount factor γ < 1

https://gym.openai.com/

Learning separate models for many λ values is time-consuming and does not significantly improve the obtained results

An open-source version of the model is available at https://github.com/aureliale/BONN-model.

Figures and Tables:

Figure 2: Cost/reward curves for cart-pole (a) and M AZE 2 (b) with different levels of stochasticity.The X-axis corresponds to the ratio of options used in each episode (100% means that the agent observes y t and computes a new option at each time step). The Y-axis corresponds to the reward R obtained on the task. The dashed lines are the R-PG performance. Note that the R-PG performance is obtained without options (i.e using all the information available at each time step)

Figure 4: (a) Cost/reward curve for M AZE 1 and M AZE 2 with a stochasticity level of = 0.25. (b) The options latent vectors visualized through the t-SNE algorithm. Similar colors mean the goal is in similar areas in the room, except for the red points that corresponds to the options used to reach one of the four possible doors, or when the goal is just near a door.

Note that when σ t = 1 the model observes y t and compute a new option (in this example we have σ 3 = 1 and σ 6 = 1 ), and that when σ t = 0 (everywhere else in this example) the model doesn't use y t and keeps the same option.

Table content: <table><tr><td>y 3</td><td/><td>y 6</td><td/></tr><tr><td>Option Model</td><td/><td/><td/></tr><tr><td>o 3</td><td/><td>o 6</td><td/></tr><tr><td>5</td><td>x 6</td><td>x 7</td><td>x 8</td></tr><tr><td>Actor Model</td><td>z 5</td><td>z 6</td><td>z 7</td></tr><tr><td/><td>a 5</td><td>a 6</td><td>a 7</td></tr><tr><td>Acquisition Model</td><td/><td/><td/></tr><tr><td>σ 6</td><td>σ 7</td><td>σ 8</td><td/></tr><tr><td colspan="4">Figure 1: The BONN Architecture. Arrows correspond to dependencies, dashed arrows correspond</td></tr><tr><td>to sampled values.</td><td/><td/><td/></tr></table>

The pseudo code of the inference algorithm for the BONN model. Acquire y t and compute a new option o t = f (y t ) Initialize the actor z t = r(o t , x t ) Update the actor state z t = h(z t-1 , a t-1 , x t )

Table content: <table><tr><td>5:</td><td>if σ t == 1 then</td></tr><tr><td colspan="2">6: option level: 7: actor level: 8: else</td></tr><tr><td colspan="2">9: actor level: 10: end if</td></tr><tr><td>11:</td><td>actor level: Choose the action a t w.r.t z t</td></tr><tr><td>12:</td><td/></tr></table>

Peer review (iclr2017):
In this paper, the authors study the problem of discovering options for reinforcement learning. They introduce the Bi-POMDP model, which is a POMDP where the observations are structured as a pair of elements, with the first element only available to the option-choosing component (the *option level*) and the second element only to the action-choosing component (the *action level*) and the termination component (the *acquisition model*). They also detail the BONN learning model, which consists of three artificial neural network that implement these three components. Finally, they suggest optimizing a tradeoff between the value achieved by the model and the cost of switching between options (the *cognitive effort*), and demonstrate this approach in three simple domains: Cart-Pole, Lunar Lander and two variants of a grid-world maze. The paper is interesting, and adds considerably to the increasing body of research in hierarchical reinforcement learning (HRL). I found no critical flaws in the paper, but also no high-impact insights or impressive improvements. This paper offers some good ideas that are moderately novel and may advance the field, but has some issues. The first issue is that it is unclear how much easier it is to compose Bi-POMDPs than hand-crafted options or subgoals. If Bi-POMDPs are to alleviate the design costs of using HRL with human-defined structure, one needs to show that the splitting of observations into two elements (x, y) is easier to do well enough. For example, in Section 5 the authors are correct in pointing out that sequences of actions (*macro-actions*) are open-loop, and therefore not as expressive as closed-loop options. However, by setting x empty in all but one experiment, the authors also restrict themselves to open-loop sub-policies, albeit stochastic ones. Such sub-policies may be sufficiently expressive for the simple domains in this paper, but this is unlikely so in more realistic domains. In the MAZE_2 domain, x is the agent*s position relative to the current room. Designing this domain-specific observation model requires domain knowledge, arguably no less than designing relevant subgoals. It is hard to judge the effectiveness of this approach without design principles for these domain-specific observation models, and more realistic experiments to evaluate their quality. Finally, it is revealing that the drive for hierarchy is only achieved by limiting x. In Section 3.3 the authors mention that acquisition of y is *crucial for discovering a good policy: an agent only using the observations x_t would be unable to solve the task*, which suggests that the design choice of x directly impacts one side of the trade-off between the value and the cognitive effort. Such an important factor should be addressed explicitly. The authors may be interested in the paper *Learning and Transfer of Modulated Locomotor Controllers* (Heess et al., 2016), which has a similar split observation model, and suffers from the same issue. The second issue is that the option space seems to be expressive enough to represent y with high fidelity. If this is the case, and if the learned option model indeed maintains a good image of y, then the algorithm is really solving a different problem: reinforcement learning with costly observability of y. This means that it learns how to act given a stale value of y and when to refresh it. It should then be framed accordingly and compared with the relevant literature. It may or may not be as interesting or novel. In contrast, the standard options framework calls for compression of y into the choice of option o (usually in a small finite space). The agent should learn to extract subtask-relevant information from y, in a way that generalizes to unseen states or subtasks. That said, the embedding of y in the option space can be interesting in itself, even if it is lossless (1-to-1). Unfortunately, no such analysis was offered by the authors. Minor issues: - In 3.3: error in citation, (?) appears instead. - In 4.1: it is confusing to say that *the environments are more stochastic* when epsilon is increased. It is the agent*s policy, not the environment, that becomes more stochastic, which is useful for exploration. If this hurts performance, some discussion is needed of why too much exploration is detrimental to learning. In particular, the paper does not make explicit the number of iterations in the experiments, and it is not clear whether learning with larger epsilon is worse after some fixed number of iterations or asymptotically.