Average-Reward Learning and Planning with Options
Authors: Yi Wan
Abhishek Naik
Richard S. Sutton
Venue: NeurIPS 2021 Poster (2021)
Keywords: average reward
options
reinforcement learning

Abstract: We extend the options framework for temporal abstraction in reinforcement learning from discounted Markov decision processes (MDPs) to average-reward MDPs. Our contributions include general convergent off-policy inter-option learning algorithms, intra-option algorithms for learning values and models, as well as sample-based planning variants of our learning algorithms. Our algorithms and convergence proofs extend those recently developed by Wan, Naik, and Sutton. We also extend the notion of option-interrupting behaviour from the discounted to the average-reward formulation. We show the efficacy of the proposed algorithms with experiments on a continuing version of the Four-Room domain. 

Average-Reward Learning and Planning with Options
Yi Wan', Abhishek Naik?, Richard S. Sutton {wan6, anaik1, rettttoreuaaaaeetttteeeenn ca University of Alberta, Amii Edmonton, Canada
DDeepMind Edmonton, Canada
Abstract
We extend the options framework for temporal abstraction in reinforcement learn- ing from discounted Markov decision processes (MDPs) to average-reward MDPs. Our contributions include general convergent off-policy inter-option learning algo- rithms, intra-option algorithms for learning values and models, as well as sample- based planning variants of our learning algorithms. Our algorithms and conver- gence proofs extend those recently developed by Wan, Naik, and Sutton. We also extend the notion of option-interrupting behavior from the discounted to the average-reward formulation. We show the efficacy of the proposed algorithms with experiments on a continuing version of the Four-Room domain.
Introduction
Reinforcement learning (RL) a formalism of trial-and-error learning in which an agent interacts with an environment to learn a behavioral strategy that maximizes a notion of reward. In many problems of interest, a learning agent may need to predict the consequences of its actions over multiple levels of temporal abstraction. The options framework provides a way for defining courses of actions over extended time scales, and for learning, planning, and representing knowledge with them (Sutton, Precup. & Singh 1999, Sutton & Barto 2018). The options framework was originally proposed within the discounted formulation of RL which the agent tries to maximize the expected discounted return from each state. We extend the options framework from the discounted formulation to the average-reward formulation in which the goal to find policy that maximizes the rate of reward.
The average-rewee reward formulation is of interest because, once genuine function approximation is introduced, there is no longer a well-defined discounted formulation of the continuing RL problem (see Sutton& & Barto 2018, Section 10.4; Naik al. 2019). If we want to take advantage of options in acting, learning, and planning in the continuing (non-episodic) RI. setting, then we must extend options to the average-reward formulation.
Given a Markov decision process (MDP) and a fixed set of options, learning and planning algorithms can be divided into two classes. The first class consists inter-option algorithms, which enable an agent to learn or plan with options instead of primitive actions. Given an option, the learning and planning updates for this option in these algorithms occur only after the option's ''s actual or simulated execution. Algorithms in this class are also called semi-MDP (SMDP) algorithms because given an MDP, the decision process that selects among a set of options, executing each termination, is an SMDP (Sutton et al. 1999). The second class consists of algorithms in which learning or planning updates occur after each state-action transition within options' execution these are called intra-option algorithms. From single state-action transition, these algorithms can learn or plan to improve the values or policies for all options that may generate that transition, and are therefore potentially more efficient than SMDP algorithms.
Several inter-option (SMDP) learning algorithms have been proposed for the average-reward formu- lation (see, e.g., Das et al. 1999, Gosavi 2004, Vien & Chung 2008). To the best of our knowledge,
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

Gosavi's (2004) algorithm is the only wroven-coovergeeee off aff-policy inter-option learning algorithm. However, its convergence proof requires the underlying SMDP to have special state that is recur- rent under all stationary policies. Recently, Wan, Naik, and Sutton (2021) proposed Differential Q-learning, an off-pollicy control learning algorithm for average-reward MDPs that is proved to converge without requiring any special state. We extend this algorithm and its convergence proof from primitive actions to options and highlight some challenges we faced in developing inter-option Differential Q-learning. For planning, we propose inter-option Differential Q-planning, which is the first convergent incremental (sampled-based) planning algorithm. The existing proven-convergent inter-option planning algorithms (e.g.. Schweitzer 1971, Puterman 1994, Li & Cao 2010) are not incremental because they perform a full sweep over states for each planning step.
Additionally, the literature lacks intra-option learning and planning algorithms within the average- reward formulation for both values and models. We fill this gap by proposing such algorithms in the everage-reward formulation and provide their convergence results. These algorithms are stochastic approximation algorithms solving the average-reward intra-option value and model equations, which are also introduced in this paper for the first time.
Sutton et al. (1999) also introduced an algorithm to improve an agent's behavior given estimated option values. Instead of letting an option execute to termination, this algorithm involves potentially interrupting an option's 's execution to check if starting a new option might yield a better expected outcome. If so, then the surrently-executing option is terminated, and the new option is executed. Our final contribution involves extending this notion of an interruption algorithm from the discounted to the average-reward formulation.
2 Problem Setting
We formalize an agent's interaction with its environment by a finite Markov decision process (MDP)
M and a finite set of options O. The MDP is defined by the tuple A = (S, R),,, where S is set of states, A is set of actions, R is set of rewards, and p S x R x S x A + [0, 1] is the dynamics of the environment. Each option o in O has two components: the option's 's policy
T" : A x S + [0, 1), and probability distribution of the option's 's termination 8 S - [0, 1]. For simplicity, for any s E S O. we use π [a s, o) to denote (a s) and B(s, o) to denote (s). Sutton et al.'s (1999) options additionally have an initiation set that consists of the states which the option can be initiated. To simplify the presentation in this paper, we allow all options to be initiated in all states of the state space; the algorithms and theoretical results can easily be extended to incorporate initiation from specific states.
In the continuing (non-episodic) setting, the agent-environment interactions go on forever without any resets. If an option o initiated at time in state S,, then the action A, is chosen according to the option's policy ((- O). The agent then observes the next state S1+1 and reward Re+1 according to p. The option terminates at S,41 with probability 3(S++1, o) or continues with action Ac+1 chosen according x(- SS+1,0). It then possibly terminates in S142 according to ((S o), and on. At an option termination, one way to govern an agent's behavior is to choose a new option according to hierarchical policy /4 : S x O - [0, 1). In this case, when option terminates at time the next option is selected stochastically according to ns (-1S)) The option initiates at S and terminates at S.4k, where K is a random variable denoting the number of time steps the option executed. At S.4K. a new option is again chosen according to (-|[;++k) and so on. We use the notation O to denote whatever option is being executed at time step l. Note that O will remain the same for as many steps as the option executes. Also note that actions are special case of options: every action an option o that terminates after exactly one step (B(s, o) 1, As) and whose policy is to pick in every state (T(a s, = 1, Vs).
Let T, denote the time step when the 1h option terminates and the th option is chosen. Denote the th option by Ō, = OT., its starting state by S, = ST., the cumulative reward during its exccution by R. = Σi Re, the state it terminates in by S ST.T. and its length by i., = TTa+1 Tn- Note that every option's length is random variable taking values among positive integers. The option's 's transition probability is then defined as ò(s', r, s, o) = Pr(Š..+ = s', R., r, i.,, = 1 S. = 8, Ó, = o). Throughout the paper, we assume that the expected execution time of every option starting from any state is finite.
2

---

An MDP M and set of options O results in an SMDP M = (S,02,,,, where ł is the set of all possible lengths of options and R is the set of all possible options' cumulative rewards. For this SMDP, the reward rate policy given a starting state s and option can be defined as re (p)(s, lim E E R So = 8, Ou = ol/t. Alternatively, at the level of option transitions, rs))(s, = 1im E IE: R. So = Ou o) |E L S. Ôu o). Both the limits exist and are equivalent (Puterman's (1994) propositions 11.4.1 and 11.4.7) under the following assumption:
The Markov chain induced by any stationary policy in the MDP (8, O, R. p') is unichain, where pl (s', 8.0) E,8(8', 8, 0) V & 5,,,00
Assumption 1.
Note: In unichain MDP, there could be some states that only oceur a finite number of times in single stream of experience. In other words, these states are /ransient under all stationary policies. Thus, their values can not be correctly estimated by any learning algorithm. However, this inaccurate value estimation is not a problem because the decisions made in these transient states do not affect the reward rate. We refer to the non-transient states as recurrent states and denote their set by S' S.
Under Assumption 1, the reward rate does not depend on the starting state-option pair and hence denote it by just r(u). The optimal reward rate then be defined as r. = sup, supyem r(u), where II denotes the set of all policies. The differential option-value function for policy is defined for all E S,0 O (s, o) - E - r(u) + Re+2 - r(u) +... S. = 8, Oz o). The evaluation and optimality equations for SMDPs, as given by Puterman (1994), are:
((s,0)= =5 p(s (r F.I+ Σ p(o'ls
(1)
s'r,
(s8 0) = ΣMs
Ms r, 1 1,, - F +a+maaxpp maxq(s'
s.r.
where g and denote estimates of the option-value function and the reward rate respectively. Assumption I holds, the SMDP Bellman equations have unique solution for F r-r(p) for evaluation and r, for control - and a unique solution for only up to a constant (Schweitzer & Federgruen 1978). Given MDP and set of options, the goal of the prediction problem is, for given policy μ., to find the reward rate r(u) and the differential value function (possibly with some constant offset). The goal of the control problem is find a policy that achieves the optimal reward rate r..
3 Inter-Option Learning and Planning Algorithms
In this section, we present our inter-option learning and planning, prediction and control algorithms, which extend Wan al.'s (2021) differential learning and planning algorithms for average-reward MDPs from actions to options. We begin with the control learning algorithm and then move on to the prediction and planning algorithms.
Consider Wan et al.'s (2021) control learning algorithm:
QS, A.) = Qs(),, + andr, Re+1 = R₁ +made
where Q is a vector of size |S x A that approximates a solution of in the Bellman optimality equation for MDPs, R is scalar estimate of the optimal reward rate, a; is step-size sequence, is positive constant, and 6, is the lemporal-difference -difference (TD) error: 8, = Rr Rd + max, (s(S++1,))
Qe,S,, At). The most straightforward inter-option extension of Differential Q-learning is:
(S Ô.. = Qn Ô,) an,n,
(3)
Rn+1 = R., na,,
(4)
where Q is vector of size |S O that approximates solution of q in (2), R is scalar estimate of Tx, Oi is step-size sequence, and 6, is the TD error:
8, = R. i, R. + max Qn Qn((Sn11.) (S,, O.).
(5)
Such an algorithm prone to instability because the sampled option length i.,, can be quite large, and any error in the reward-rate estimate R,, gets multiplied with the potentially- option length.
3

---

Using small step sizes might make the updates relatively stable, but at the cost of slowing down learning for options of shorter lengths. This could make the choice step size quite critical, especially when the range of the options' lengths is large and unknown. Alternatively, inspired by Schweitzer (1971), we propose scaling the updates by the estimated length of the option being executed:
Qu+1(Sm, On) (S,. On) + 5n/ La Ln On),
(6)
Ra+1 = R. + 8 Ln (Sn. On),
(7)
where Ozn is a step-size sequence, (. comes from an additional vector estimates L S x O R that approximates the expected lengths of state-option pairs, updated from experience by:
-
In+1(S, Ó,) I. Ô.,) + Bn (fn. [nn Ów)):
where 3, is an another step-size sequence. The TD-error ó, in (6) and (7) is
ón = Rr (Sn, On + max Qn (Sx1..0) (S On):
which is different from (5) with the estimated expected option length I,, (Sn, On. being used instead of the sampled option length L, (6-9) make up our inter-option Differential Q-learning algorithm. Similarly, our prediction learning algorithm, called inter-option Differential Q-evaluation, also has update rules (6-8) with the TD error:
En Rr - Lu (Sn, Rn + Entol 1a+1)
Qn(S,, Ön).
(10)
Theorem (Convergence of inter-option algorithms; informal). If Asssumption I holds, step sizes are decreased appropriately, all state-option pairs (s, o) in S' and are visited for an infinite number of times, and the relative visitation frequency between any two pairs is finite:
1. inter-option Differential Q-learning (6-9) converges almost surely, Rn to and Qu(8, o) to a solution of q(8,0) 0) in for all s S', O, and r(jo)) to T., where pn is a greedy policy w.r.f. Q
2. inter-option Differential Q-evaluation (6-8, 10) converges almost surely, Rr, r(u) and Qn (s to solution of of q(s. o) in for all E S' O.
The convergence proofs the inter-option (as well as the subsequent intra-option) algorithms are based on result that generalizes Wan et al.'s (2021) and Abounadi et al.'s (2001) proof techniques from primitive actions to options. We present this result in Appendix A.1; the formal theorem statements and proofs in Appendix A.2.
Remark: It is important for the scaling factor in the algorithm to be the expected option length L,, (S.: Ô,,) and not the sampled option length Ln. Scaling the updates by the expected option lengths ensures that fixed points of the updates are the solutions of (2). This is not guaranteed to be true when using the sampled option length. We discuss this in more detail in Appendix C.I.
Figure 1: A continuing vari- ant the Four-Room do- main where the task is peatedly go from the yellow start state one of the three green goal states. There is one goal state per experi- ment, chosen to demonstrate particular aspects of the pro- posed algorithms. shown an option policy to go to the upper hallway cell; more details in-text.
The inter-option planning algorithms for prediction and control are similar to the learning algorithms except that they use simulated experi- ence generated by (given or learned) model instead of real experience. In addition, they only have two update rules, (6) and (7), not (8), be- cause the model provides the expected length of given option from a given state (see Section for a complete specification option models). The planning algorithms and their convergence results are presented in Appendix A.2.
Also
Empirical Evaluation. We tested our inter-option Differential Q- learning with Gosavi's (2004) algorithm as a baseline variant of Sutton et al.'s (1999) Four-Room domain (shown in Figure 1). The agent starts in the yellow cell. The goal states are indicated by green cells. Every experiment this paper uses only one of the green cells goal state; the other two considered as empty cells.

---

There are four primitive actions of moving up. down, left, right. The agent receives reward of +1 when it moves into the goal cell. 0 otherwise.
In addition to the four primitive actions, the agent has eight options that take it from a given room to the hallways adjoining the room. The arrows in Figure 1 illustrate the policy of one of the eight options. For this option, the policy in the empty cells (not marked with arrows) is to uniformly- randomly pick among the four primitive actions. The termination probability is 0 for all the cells with arrows and for the empty cells. The other seven options are defined in a similar way. Denote the set of primitive actions as A and the set of hallway options as H. Including the primitive actions, the agent has 12 options in total.
In the first experiment, we tested inter-option Differential Q-learning with three different sets of options, O E [A,H, A + H}. The task was to reach the green cell G1, which the agent can achieve with combination of options and primitive actions. The shortest path to G1 from the starting state takes 16 time steps, hence the best possible reward rate for this task is 1/16 = 0.0625. The agent used an e-greedy policy with e 0.1. For each of the two step-sizes at and 8,, we tested five choices: 2 2-,,I E {1, 3, 5, 7, 9). In addition. we tested five choices of 10 ----,00 I E {0, 1, 2, 3, 4}. Q and R were initialized to 0. L to Each parameter setting was run for 200,000 steps and repeated 30 times. The left subfigure of Figure shows a typical learning curve for each of the three sets of options, with a
2-1 and 1) = 10-1 The parameter study for O A + w.r.t. a and with 5 = 2 2_1,,-_, is presented in the right subfigure of Figure 2. The metric is the average reward obtained over the entire training period. Complete parameter studies for all the three sets of options are presented in Appendix B.I.
The learning curves in the left panel of Figure 2 show that the agent achieved relatively stable reward rate after 100,000 steps in all three cases. Using just primitive actions A, the learning curve rises the slowest, indicating that hallway options indeed help the agent reach the goal faster. But solely using the hallway options H is not very useful in the long run as the goal G1 is not a hallway state. Note that because of the e-greedy behavior policy, the learning curves do not reach the optimal reward rate of 0.0625. These observations mirror those by Sutton et al. (1999) in the discounted formulation.
The sensitivity curves of inter-option Differential Q-learning (right panel of Figure 2) indicate that, in this Four-Room domain, the algorithm was not sensitive to parameter 7), performed well for wide range of step sizes a, and showed low variance across different runs. We also found that the algorithm not sensitive to 8 either; this parameter study is also presented in Appendix B.1.
0.08
0.06
Hallway Options and Actions
0.06
10
" 10
Actions
Reward 0.04
Reward 0.04
7
Rate
Rate
4
10 n=
10
0.02
0.02
Hallway Options
0.00
50000
100000
150000
200000
0.00
2
2 Step-size
Total Steps
Figure 2: Plots showing some learning curves and the parameter study of inter-option Differential Q-learning on the continuing Four-Room domain when the goal was to go G1. Left: point on the solid line denotes reward rate over the last 1000 time steps and the shaded region indicates one standard error. The behavior using the three different sets of options was as expected. Right: Sensitivity of performance to and 1) when using O = A H and B 2-1 The x-axis denotes step size at the y-axis denotes the rate of the rewards averaged over 200,000 steps of training, reflecting the rate of learning. The error bars denote standard error. The algorithm's 's rate of learning varied little over a broad range of 17.
5

---

We also tested Gosavi's (2004) algorithm as baseline. We chose not to compare the proposed algorithms in this paper with Sutton et al.'s (1999) discounted versions because the discounted and average-reward problem formulations are different; comparing the performance of their respective solution methods would be inappropriate and difficult to interpret. We have proposed new solution methods for the average-reward formulation, hence this case Gosavi's (2004) algorithm is the most appropriate baseline. Recall is the only proven-convergent average-reward SMDP off- off-policy control learning algorithm prior to our work. estimates the reward rate by tracking the cumulative reward C obtained by the options and dividing it by the another estimate the tracks the length of the options. If the nthh option executed is greedy choice, then these estimates are updated using:
D:08-
0.00-
Pm 2-1
P-2-1
Reward 0.01 Rate
P.
0.02-
1
23
0.00
Stepedioo
Figure Parameter studies showing the baseline algorithm's ' (Gosavi 2004) rate of learning relatively more sensitive to the choices of its two parameters com- pared to our inter-option Differential Q- learning. The experimental setting and the plot axes are the same as mentioned in Figure 2's caption.
Cu+1 On + Bn BRn Cn),
Tu+1 = Tn + 3n (Inn Tn),
Rut1 = Cn+1//TT7
When Ö,, is not greedy, Rx+1 Rup The vatue function updated with (3) with 6, as defined in (5). Og and 3 are two step-size sequences. The sensitivity of this algorithm with O = A + H shown in Figure 3. Compared to inter-option Differential Q-learning, this baseline has one less parameter, but its performance was found to be more sensitive to the values of both its step-size parameters. addition, the error bars were generally larger, suggesting that the variance across different runs was also higher.
To conclude, experiments with the continuing Four-Room domain show that our inter-option Differential Q-learning indeed finds the optimal policy given a set of options, in accordance with Theorem 1. In addition, its performance seems more robust the choices of parameters compared to the baseline. Experiments with the prediction algorithm, inter-option Differential Q-evaluation, are presented in Appendix B.4.
4 Intra-Option Value Learning and Planning Algorithms
In this section, we introduce intra-option value learning and planning algorithms. The objectives are same as that of inter-option value learning algorithms. As mentioned earlier, intra-option algorithms learn from every transition St, Ar, R4+1, S during the execution of a given option O, Moreover, intra-option algorithms also make updates for every option E O, including ones that may potentially never be executed.
To develop algorithms, we first establish the intra-option evaluation and optimality equations in the average-reward case. The general form of the intra-option Bellman equation is:
g(s, o)
Σ a(als,o
Σ p(s' ss, F - F('((s (s'
(11)
where q RS x |0) and F E R are free variables. The optimality and evaluation equations ua = ul and u² = ut, respectively, defined s S O as:
" (s', = ( o) = (1 - (1-8(s' o)) o) B(s', ,0) max qlsxgls'''') ('(s'0 (s', = (1 B(s' 0) ( + B(s', ,) Enlols)a(ss
(12)
(13)
Intuitively, the u term accounts for the two possibilities an option terminating or continuing in the next state. These equations generalize the average-reward Bellman equations given by Puterman (1994). The following theorem characterizes the solutions to the intra-option Bellman equations.

---

Theorem 2 (Solutions to intra-option Bellman equations). If Assumption 1 holds, then:
1. a) there exists a f E R and a E IR S1x for which (11) and (12) hold,
b) the solution of F unique and equal to T., let qı be one solution of q, the solutions of form set {qı + ce | e C R} where is an all-one vector of size |S] x |0),
c) a greedy policy w.E. a solution of q achieves the optimal reward rate T=- 2. a) there exists a F E R and a E IR [1 for which (11) and (13) hold,
b) the solution of F unique and is equal to r(p), the solutions of q form set {qn- + ce
c E RJ.
The proof extends those of Corollary 8.2.7, Theorem 8.4.3, Theorem 8.4.4 by Puterman (1994) and is presented in Appendix A.3.
Our intra-option control and prediction algorithms are stochastic approximation algorithms solving the intra-option optimality and evaluation equations respectively. Both the algorithms maintain a vector of estimates Q(s, o) and scalar estimate R. just like inter-option algorithms. However, unlike inter-option algorithms, intra-option algorithms need not maintain an estimator for option lengths (L) because they make updates after every transition. Our control algorithm, called intra-option Differential Q-learning, updates the estimates Q and R by:
Qi+1(Se, o) = =Q((S,, o) + (p)) VOEO,
(14)
Ri+1 Rs + nat Σ ((())),(o),
(15)
aEO
where on is step-size sequence, pr(o) = =(A,(S.o) [(A,[S,,0,)
is the importance sampling ratio, and:
60(0)= RR+1 - R, + a (S - ().
(16)
Our prediction algorithm, called intra-option Differential Caaeentiii----eeleaeeee Q-evaluation, also updates Q and by (14) and (15) but with the TD error:
6,(0) = R,41 R, + 2. - Q).
(17)
Theorem (Convergence of intra-option algorithms; informal). Under the conditions of Theorem 1:
1. intra-option Differential Q-learning algorithm (14-16) converges almost surely, R₁ to r.. Q 0) to a solution of q(s, o) in (11) and (12) for all s E 8 e O, and r(pe) to T.. where pe is greedy policy w.r.t. Qt,
2. intra-option Differential Q-evaluation algorithm (14.15,17) converges almost surely, R, to r(u), Qi(s, 0) to solution of q(8,0) o) in (11) and for all E S O.
The intra-option learning methods introduced in this section can be used with options having stochastic policies. This is possible with the use of the important sampling ratios as described above. Sutton et al.'s 's (1999)
Remark:
0,68
0.06
discounted intra-option learning methods were restricted to options having deterministic policies.
Reward 0.04 Rale
Again, the intra-option value planning algorithms are sim- ilar to the learning algorithms except that they use simu- lated experience generated by given learned model instead of real experience. The planning algorithms and their convergence results are presented in Appendix A.4.
0.00
50100
100000
150000
200000
Tocal Stepe
Figure 4: Learning curve showing that the greedy policy corresponding to the hallway options' option-value function achieves the optimal reward rate on the continuing Four-Room domain. The value function was learned via intra- option Differential Q-learning using a behavior policy consisting only of prim- itive actions; the hallway options were never executed.
Empirical Evaluation. We conducted another experi- ment in the Four-Room domain to show that intra-option Differential Q-learning can learn the values of hallway options 7 using only primitive actions A. As mentioned earlier, there are no baseline intra-option average-reward algorithms, this is proof-of-coneey experiment.
The goal state for this experiment was G2 which can reached using the option that leads to the lower hallway.
7

---

The optimal reward rate in this case is 1/14 R 0.714 with both O = H. and O = A. We applied intra-option Differential Qllearning using behavior policy that chose the four primitive actions with equal probability in all states. This choice of behavior policy and goal G2 would test if the intra-option algorithm leads to a policy consisting exclusively of options by interacting with the environment using only primitive actions. Each parameter setting was run for 200,000 steps and repeated 30 times. For evaluation, we saved the learned option value function after every 1000 steps and computed the average reward of the corresponding greedy policy over 1000 steps.
Figure 4 shows the learning curve of this average reward across the 30 independent runs for parameters = 0.125, 0.1. The agent indeed succeeds in learning the option-value function corresponding to the hallway options using a behavior policy consisting only of primitive actions. The parameter study of intra-option Differential Q-learning is presented in Appendix B.2. Experiments with the prediction algorithm, intra-option Differential Q-evaluation, are presented Appendix B.4.
5 Intra-Option Model Learning and Planning Algorithms
In this section, we first describe option models within the average-reward formulation. We then introduce an algorithm to learn such models in an intra-option fashion. This option-model learning algorithm can be combined with the planning algorithms from the previous section to obtain complete model-basee average-reward options algorithm that learns option models and plans with them (we present this combined algorithm in Appendix C.2).
The average-reward option model is similar the discounted options model but with key distinctions. Sutton et al.s (1999) discounted option model has two parts: the dynamics part and the reward part. Given state and an option, the dynamics part predicts the discounted occupancy of states upon termination, and the reward part predicts the expected (discounted) sum of rewards during the execution of the option. In the average-reward setting, apart from the dynamics and the reward parts, an option model has third part the duration part that predicts the duration of execution of the option. In addition, the dynamics part predicts the state distribution upon termination without discounting and reward part predicts the undiscounted cumulative rewards during the execution of the option.
p(s', r, [8, o), the probability that option o terminates in state s' when starting from state The reward part approximates m m²(s,o) o) = Ev ((s', r, [s, o) r, the expected cumulative reward during the execution of option o when starting from state s. Finally, the duration part approximates m (s. = ,.s''(('' ... r, |s, o) I, the expected duration of option when starting from state s.
Formally, the dynamics part approximates m²(s'(s, =
We now present a set of recursive equations that are key to model-learning algorithms. These equations extend the discounted Bellman equations for option models (Sutton et al. 1999) to the average-reward formulation.
m 0)
Σ x(a s))
8' Σ Ells'r (.))s, 5') (1 11-966 3(5 -(5 (0)mm(=) (18)
m (s Σ x(als,0) Σ 1.06 3(5',)))m mm ()),
(19)
m (.,00) Σ (
(1 3(8', o) ml (s', o)).
(20)
The first equation are different from the other two because the total reward and length of the option are incremented irrespective of whether the option terminates in s' or not. The following theorem shows that (m², m", m') is the unique solution of (18-20) and therefore the models can be obtained by solving these equations (see Appendix A.5 for the proof).
Theorem 4 (Solutions to Bellman equations for option models). There exist unique mp e ||||||||x|S| m" E six(01, and m² E [ for which (18), (19), and (20) hold. Further, if m. m", m² satisfy (18), (19), and (20), then m = m², m² = m", m² m'.
8

---

Our intra-option model-learning algorithm solves the above recursive equations using the following TD-like update rules for each option o:
M2+1 (o) 0) = Mf 0t, + aspi(o) ( ((5541) =))
+ -1- (1-B(S(+1,0)) Mf) 0) Mf(x St,oo), A VxES,
(21)
M[+1(S6,0) (Sr, oupe Re41 + (1- 11-1((S+11:0) ol) M (8 Mr (St,
(22)
(4+1 0) = (S ( (
(i MS(S,,
(23)
where M is a [S] x [ x -sized vector of estimates, M" and M' are both |S| x |O|esized vectors of estimates, and 0r is sequence of step sizes. Standard stochastic approximation results can be applied to show the algorithm's 's convergence (see Appendix A.6 for details).
Theorem (Convergence of the intra-option model learning algorithm; informal). If the step sizes are set appropriately and all the state-option pairs are updated an infinite number of times, then intra-option model-learning learning (21-23) converges almost surely, M. to m², MI to m", and M; to m
Our intra-option generated by a given action model, resulting in a planning algorithm that produces an estimated option model. The planning algorithm and its convergence result are presented in Appendix A.6.
algorithms (21-23) can be applied with simulated one-step transitions
6 Interruption to Improve Policy Over Options
In all the algorithms we considered so far, the policy over options would select an option, execute the option policy till termination, then select new option. Sutton et al. (1999) showed that the policy over options can be improved by allowing the interruption of an option midway through its execution to start seemingly better option. We now show that this interruption result applies for average-reward options as well (see Appendix A.7 for the proof).
Theorem 6 (Interruption). For any MDP, any set of options O and any policy μ S x O - 10. 1, define a new set of options, O', with a one-to-one mapping between the two option sets as follows: for every = (T, E O, define corresponding o' = (I,3") E O' where 3 = 3, but for any state s in which qu (). < va(s), 8 (s, = (where Up policy p¹ be such that for all 8 E S and for all o' E O', O',,'' ,s = u(s,0), where is the option in O corresponding to o' Then:
E. ()),(s,)) ())))). Let the interrupted
1. the new policy over options μl is not worse than the old one μ. i.e. r(p')= 2 r((),
2. if there exists a state s E S from which there is non-zero probability of encountering an interruption upon initiating yl in s, then r(y²) > r(n).
In short, the above theorem shows that interruption pro- duces behavior that achieves a higher reward rate than without interruption. Note that interruption behavior is
0.08
only applicable with intra-option algorithms; complete option transitions are needed inter-option algorithms.
0.06
Acting with Interruption
Reward 0.04
Empirical Evaluation. We tested the intra-option Differ- ential Q-learning algorithm with and without interruption in the Four-Room domain. We set the goal as G3 and al- lowed the agent to choose and learn only from the set of all hallway options H. With just hallway options, without interruption, the best strategy is to first move to the lower hallway and then try to reach the goal by following options that pick random actions in the states near the hallway and goal. With interruption, the agent can first move to the left hallway, then take the option that moves the agent to the lower hallway but terminate when other options have higher option-values. This termination is most likely to occur in the cell just above G3. The agent then needs fewer number of steps in expectation to reach the goal.
0.02
Acting without Internuption
0.00 100000
200000
300000
400000
"Beaal Stopp
Figure 5: Learning curves showing that executing options with interruptions can achieve higher reward rate than execut- ing options till termination in the domain described the adjoining text.

---

Figure 5 shows learning curves using intra- oitra-optonn Differential Q-learning with and without interrup- tions on this problem. Each parameter setting was run for 400,000 steps and repeated 30 times. The learning curves shown correspond to a 0. 0.1 and 7 = 0.1. As expected, the agent achieved higher reward rate by using interruptions. The parameter study of the interruption algorithm along with the rest of the experimental details is presented in Appendix B.3.
7 Conclusions, Limitations, and Future Work
In this paper, we extended learning and planning algorithms for the options framework - originally proposed by Sutton al. (1999) for discounted-reward MDPs average-reward MDPs. The inter-option learning algorithm presented in this paper is more general than previous work in that its convergence proof does not require existence of any special states in the MDP. We also derived the intra-option Bellman equations in average-reward MDPs and used them to propose the first intra-option learning algorithms for average-reward MDPs. Finally, we extended the interruption algorithm and its related theory from the discounted to the average-reward setting. Our experiments on a continuing version of the classic Four-Room domain demonstrate the efficacy of the proposed algorithms. We believe that our contributions will enable widespread use of options in the average- reward setting.
We now briefly comment on the novelty of our theoretical and algorithmic contributions. Our primary theoretical contribution to generalize Wan et al.'s (2021) proof techniques to obtain unified convergence proof for actions and options. The same proof techniques then apply for both the inter- and intra-option algorithms. Our primary algorithmic contribution is the scaling of the updates by option lengths in the inter-option algorithms. The lack of scaling makes the algorithms unstable and prone to divergence. Furthermore, we show the correct way of scaling involves estimated option lengths, not sampled option lengths.
The most immediate line of future work involves extending these ideas from the tabular case the general case of function approximation, starting with linear function approximation. One way to incorporate function approximation is extend algorithms presented in this paper to those using linear options (Sorg & Singh 2010, Yao et al. 2014), perhaps by building on Zhang et al.'s (2021) work. Using the results developed in this paper, we also foresee extensions to more ideas from the discounted formulation involving function approximation, such as Bacon et al.'s (2017) option-critte architecture, the average-reward formulation.
This paper assumes that a fixed set of options is provided and the agent then learns or plans using them. One of the most important challenges in the options framework is the discovery of options. We think the discovery problem is orthogonal to the problem formulation. Hence, another line of future work is to extend existing ppscovndyscoveer algorithms developed for the discounted formulation to the average-reward formulation (e.g.. algorithms by McGovern & Barto 2001, Menache et al. 2002, Simşek & Barto 2004, Singh et al. 2004, Van Djik & Polani 2011. Machado al. 2017). Relatively more work might be required in extending approaches that couple the problems of option discovery and learning (c.g., Gregor et al. 2016. Eysenbach et 2018, Achiam et al. 2018, Veeriah et al. 2021).
Another limitation of this paper is that it deals with learning and planning separately. We also need combined methods that learn models as well as plan with them; we discuss some ideas in Appendix C. Finally, we would like to get more empirical experience with the algorithms proposed in this paper, both in pedagogical tabular problems and challenging large-scale problems. Nevertheless, we believe this paper makes novel contributions that are significant for the use of temporal abstractions in average-reward reinforcement learning.
Acknowledgements
The authors were supported by DeepMind, Amii, and CIFAR. The authors wish to thank Huizhen Yu for extensive discussions on several related works; Benjamin Van Roy, Csaba Szepesvári, Dale Schuurmans, Martha White, and the anonymous reviewers for valuable feedback.
10

---

References
Abounadi, J., Bertsekas, D., & Borkar, V. S. (2001). Learning Algorithms for Markov Decision Processes with Average Cost. SIAM Journal Control and Optimization.
Achiam, J., Edwards, H., Amodei, D., & Abbeel, P. (2018). Variational Option Discovery Algorithms.
WxXiv:8877.10299
Almezel, S., Ansari, Q. H., & Khamsi, M. A. (2014). Topics in Fixed Point Theory (Vol. 5). Springer.
Bacon, L., Harb, J., & Precup, D. (2017). The Option-Critic Architecture. AAAI Conference on Artificial Intelligence.
Borkar, V. S. (1998). Asynchronous Stochastic Approximations. SIAM Journal on Control and Optimization.
Borkar, V. S. (2009). Stochastic Approximation: A Dynamical Systems Viewpoint. Springer.
Borkar, V. S., & Soumyanatha, K. (1997). An Analog Scheme for Fixed Point Computation. I. Theory. IEEE Transactions Circuits and Systems I: Fundamental Theory and Applications.
Brunskill, E., Li. (2014). PAC-inspired Option Discovery in Lifelong Reinforcement Learning. International Conference on Machine Learning.
Das, T. K., Gosavi, A., Mahadevan, S., & Marchalleck, N. (1999). Solving Semi-Markov Decision Problems Using Average Reward Reinforcement Learning. Management Science.
Eysenbach, B., Gupta, A., Ibarz, J., & Levine, S. (2018). Diversity is All You Need: Learning Skills without Reward Function. ArXiv:1802.0000
Fruit, R., Lazaric, (2017). Auploration-Exxloittttie in MDPs with Options. Artificial Intelli- gence and Statistics.
Gosavi, A. (2004). Reinforcement Learning for Long-run Average Cost. European Journal of Operational Research.
Gregor, K., Rezende, D. J., & WWierstr, D. (2016). Variational Intrinsic Control. ArXiv:1611.07507.
Li, Y., & Cao, F. (2010), RVI Reinforcement Learning for Semi-Markov Decision Processes with Average Reward. JEEE World Congress on Intelligent Control and Automation.
Machado, M. C., Bellemare, M. G., & Bowling, M. (2017). Laplacian Framework for Option
Discovery in Reinforcement Learning. International Conference on Machine Learning.
McGovem, A., & Barto, A. G. (2001). Automatic Discovery of Subgoals in Reinforcement Learning using Diverse Density. International Conference on Machine Learning.
Menache, I., Mannor, S., & Shimkin, N. (2002). Q-Cut-Dynamic Discovery of Sub-goals in Reinforcement Learning. European Conference on Machine Leurning.
Puterman, M. (1994). Markov Decision Processes: Discrete Stochastic Dynamic Programming.
John Wiley & Sons.
Schweitzer, P. J. (1971), Iterative Solution of the Functional Equations of Undiscounted Markov Renewal Programming. Journal of Mathematical Analysis and Applications.
Schweitzer, P. J., & Federgruen, A. (1978). The Functional Equations of Undiscounted Markov Renewal Programming, Mathematics of Operations Research.
Şimyek, Ö. & Barto, G. (2004). Using Relative Novelty Identify Useful Temporal Abstractions
in Reinforcement Learning. International Conference on Machine Learning.
Singh, S., Barto, A. G., & Chentanez, N. (2004). Intrinsically Motivated Reinforcement Learning. Advances in Neural Information Processing Systems.
Sorg, J., & Singh, S. (2010). Linear Options. International Conference on Autonomous Agents and Multiagent Systems.
Sutton, R. S., Precup. D., Singh, S. (1999). Between MDPs and Semi-MDPs: A Framework for Temporal Abstraction in Reinforcement Learning, Artificial Intelligence.
Sutton, R. S., & Barto, A. G. (2018). Reinforcement Learning: An Introduction. MIT Press.

---

Tsitsiklis, J. N. (1994). Asynchronous Stochastickapproximatin and Q-learning. Machine Learning.
van Dijk, S. G., & Polani, D. (2011). Grounding Subgoals in Information Transitions. IEEE Symposium on Adaptive Dynamic Programming and Reinforcement Learning.
Veeriah, V., Zahavy, T., Hessel, M., Xu, Z., Oh, J., Kemaev, I., van Hasselt, H., Silver, D., & Singh S. Subgoals. ArXiv:2/02.06741
(2021). Discovery of Options via
Vien, N. A., & Chung, T. (2008). Policy Gradient Semi-Markov Decision Process. IEEE International Conference on Tools with Artificial Intelligence.
Wan, Y., Naik, A., & Sutton, R. S. (2021). Learning and Planning in Average-Reward Markov Decision Processes. International Conference on Machine Learning.
Yao, H., Szepesvári, C., Sutton, R. S., Modayil, J., & Bhatnagar, S. (2014). Universal Option Models. Advances in Neural Information Processing Systems.
Zhang, S., Wan, Y., Sutton, S.. Whiteson, S. (2021). Pverage-Rewart Off-Policy Policy Evaluation with Function Approximation. International Conference on Machine Learning.
12


Reviews:
[{"review_id": "yxlTeewxn1B", "reviewer": "Reviewer_ufJp", "summary": "This paper extends options framework to average-reward Markov Decision Processes. This paper presents inter-option learning and planning algorithms, and intra-option learning and planning algorithms, as well as provide theoretical analyses that support these algorithms. It also uses an idea of allowing interruption during the option, which allows behaviors with a potentially higher than without interruption - and combine it in its framework. ", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Detailed summary\n- The introduction part explains the concept of RL, options framework, SMDP, inter-/intra-option algorithms, etc. I think the intro part was well written, but it would've been a bit better if it contained a brief background explanation about average-reward MDP either in section 1 or in section 2.  \n- Inter-option: Q_{n+1}(S_n, O_n) = Q_n(S_n, O_n) + \\alpha_n \\delta_n / L_n(S_n, O_n), where L approximates the expected length of s-o pairs. L_n is also updated by using another step-size \\beta_n. The L_n(s_n, o_n) is different from the sampled option length. \n- I've checked the convergence proofs for inter-options, and didn't find any flaws\n- Intra-option: q(s,o) = \\sum_{a} \\pi(a|s,o) \\sum_{s',r} p(s',r|s,a) (r-R + u^q(s',o)). The intra-option differential q-learning and q-evaluation algorithms are suggested. Again, the proof for theorem3 checked. \n- intra-option model learning/planning: should predict the duration of execution of the option. \n- Interruption improves the performance of intra-option models. \n\nI think this paper is a well-written paper with a combinations of novel, original ideas (average-reward MDP and option framework) and mathematical approach. Although the level of experiments are not extensive, the main idea in this paper has a potential to be extended to more general cases including function approximation. \n\nI have two questions. \n\nQ1. General question: I get the idea of combining average-reward MDP and option framework; but other than achieving high reward empirically, is there any motivation or necessity to use average-reward MDP in the setting of option framework?  \n\nQ2. Empirical results in Appendix: the algorithm's sensitivity to hyperparameter \\alpha, \\beta, \\eta varies; in the case of inter-option differential q-learning, the algorithm is not very sensitive to any parameter \\alpha, \\beta, \\eta. In the case of inter-option learning with options O=A, the algorithm was more sensitive to the choice of \\alpha; in the case of intra-option algorithms; the choice of \\alpha and \\eta didn't make much difference. Can you give us an intuition of why this difference happens in different cases?", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "None", "review_text": "", "extra_scores": {"ethical_concerns": "None", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "7"}, "extra_text": {}}, {"review_id": "ZEBhFsl6Amr", "reviewer": "Reviewer_Dp3F", "summary": "This paper extended the learning and planning algorithms and their theoretical properties for options framework in discounted settings MDP settings to average-reward MDPs. The main contributions include three algorithms their convergence property. These algorithms include off-policy inter-option learning and planning, intra-option value learning and planning, intra-option model learning and planning. The convergence property is justified based on the resulted developed for differential Q-learning, an off-policy control algorithm. The paper also extended the notion of option-interrupting behavior from the discounted case to the average-reward formulation and showed it’s efficacy on a continuing version of the 4room domain. Importantly, the intra-option differential Q-learning introduced in this paper can be sued with options having stochastic policies (by using the importance sampling ratio), whereas the original discounted intra-option learning methods were restricted to options with deterministic policies.", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "In all the paper is well written and provides some didactic results for options learning and planning in average-reward MDP settings which are complementary to the existing literature on the same topic but mostly for discounted MDP settings.\n\nOne issue I have is that many theoretical results seem are directly and trivially extend from some existing work, e.g. Wan et al.’s differential Q learning and Wan et al.’s differential learning and planning algorithms for average-reward MDPs. The paper would be stronger if the difficulties of the theoretical results that are unique to the average-reward settings for options can be highlighted. Another issue is the sufficiency of empirical study. Admittedly the paper is mostly for didactic purpose and the algorithms are developed based on tabular representations. It would be better if more baselines can be compared. i.e,  in figure 4, maybe the authors can include some method from discounted case, but set the discount factor to be large.  Also there is only one domain used for empirical study, it might be stronger if results based on a problem different from 4rooms and described by average reward MDP can be provided.  \n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The limitations of this work has been discussed in the last section of the paper. ", "review_text": "", "extra_scores": {"ethical_concerns": "I don't have any ethical concerns.", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3h"}, "extra_text": {}}, {"review_id": "HpiqTiapxQn", "reviewer": "Reviewer_Pn3J", "summary": "The paper presents an extension of the options framework to the average-reward formulation in RL. To this end, the key contributions of this paper are: 1) it extends an off-policy control algorithm by Wan, Naik, Sutton’s differential q learning to inter-option differential q learning, 2) presents an incremental sample-based inter-option differential q learning planning algorithm. For 1) they guarantee convergence without requiring a special state, and prove convergence for 2) as well. 3) Next, the work presents intra-option learning and planning algorithms for the average reward formulation including their convergence guarantees. 4) Finally, this work also extends the interruption algorithm from Sutton 1999 to the average reward case. The empirical results support the theoretical claims but could be extended further. ", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "**Originality and Significance**:\nThe work builds upon the foundations laid in Wan, Naik, Sutton (2021) such as Assumption 1, concept of reward rate and the differential value function, etc. Despite that, there are a lot of interesting and important challenges that the work addresses by extending the options framework to the average reward formulation. For instance, the instability incurred due to the large option length and consequently the dependence of the step size on the option length is a key challenge.  \n \nThe ideas presented in the paper are presented with clarity and technically sound. I appreciate the inclusion of extended discussion in the appendix on the attempts for this which did not work. This gives further insight on the merits of the work.  \n\nRe option models: Can you comment on the comparison to the option multi-time-models both theoretically and empirically? Any insights would be helpful. While the duration component is an explicit additional component as presented here, the MTM captures the full distribution of all possible lengths of the options. What do we gain by explicitly modelling the length of the options? Is the key impact in the scaling component in the TD error (Alg 6, L21-23)? It would be good to expand on this impact in the main paper. \n \n\n**Empirical Analysis**:  The empirical analysis provided more confidence and understanding of the ideas presented in the work and its impact on the robustness for example. The inter-option differential q learning in Fig 2 and 3 helps in establishing the improvements in robustness of the algorithm proposed towards the hyper-parameters including a comparison to the baseline. However, I have the following concerns and questions:  \n\n* The empirical analysis as it stands seems rather weak. For instance, in Fig 1 we conclude that the results indeed match theorem 1, but potentially a lot more analysis can be done to show the utility of the proposed algorithms.\n* Why do we not see the Gosavi’s (2004) algorithm compared in Fig 1 left? \n* I wonder if it would be valuable to compare with the primitive actions differential q learning (Wan, Naik and Sutton, 2021) as a baseline. Especially since the work derives a lot from the aforementioned paper? This could potentially highlight the trade-offs between actions and options in the average reward case.\n* As also pointed out by the authors, it would be helpful to provide a stronger empirical analysis in other domains with closely related baselines. For instance, an interesting comparison can be made between the original options framework and the one present in this paper to understand and analyse the trade-off. This analysis might highlight the \n* Additionally, would a baseline such as the average cost TD learning be a suitable candidate to compare with? If not, could you please shed some light on why?\n \n\n**Writing and Presentation**:  \nI suggest expanding the introduction specifically to address the motivation for average-reward setting. It is clear that the existing literature has the discounted formulation already, but it is hard for the reader to gauge why the average-setting is important. This is easy to address by rewriting parts of the introduction and the paper.\n \n**Miscellaneous**:\n * I was a bit confused in the figures because only the proposed algorithm is shown with little to no comparisons. The sensitivity analysis could be placed side by side perhaps to show the robustness difference.\n* It took a while to understand that Fig 3 is the baseline method. Perhaps you might want to make it more explicit. \n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes, limitations of the work have been discussed in Sec 7. \nI do not see a broader impact statement, I encourage you to write one and add that to the paper.\n", "review_text": "", "extra_scores": {"ethical_concerns": "None.", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4"}, "extra_text": {}}, {"review_id": "BDi3vA8ciHS", "reviewer": "Reviewer_TT1t", "summary": "This paper extends the Options framework from the discounted MDP setting to the average-reward setting. The authors introduce 4 main contributions: (1) an off-policy inter-option learning algorithm with convergence guarantees; (2) intra-option techniques for learning value functions and models; (3) a method that allows for these ideas to be deployed under sample-based planning algorithms; and (4) an extended definition of interrupting options, adapting its original definition (as proposed for the discounted case) to the average-reward formulation.\n", "questions": "", "limitations": "", "rating": 8, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "This is a well-written paper that makes an important set of contributions to the area. Average-reward RL has been (comparatively) less studied than the discounted setting, but it is equally important. Being able to extend important key concepts in Hierarchical RL to the average reward formulation is certainly relevant to the community.\n\nBesides being significant, I found the paper to be clear and technically sound. I have a few questions and suggestions:\n\n1) when defining the reward rate of a policy, r^C(mu), what does the \"C\" superscript stand for? I do  understand the difference between r^C(mu) and r(mu), but was confused about the terminology.\n\n2) regarding Assumption 1: why are all stationary policies in the proposed MDP recurrent? Is this a well-known result? If so, a citation would be helpful. If not: is this statement a claim (that can be proved) or part of the assumption itself?\n\n3) in Equations 1 and 2, \\bar{r} was never defined, I believe.\n\n4) in Equation 2, shouldn't it be q*(s,o) instead of q(s,o)?\n\n5) regarding the technique presented in Section 3: my understanding is that the main contribution, here, is the idea of scaling the step-size not by the observed option length, but by an estimate (model) of the option's length. Is that the case? If so, what is the theoretical justification for doing this? Is this meaningful because the option length model \\hat{L} encodes the expected length, and using that (the expectation, instead of individual length realizations) decreases the variance of the update rule? A discussion motivating this idea would be helpful.\n\n6) even though the discussion of Equations 6-9 is clear, it was not immediately clear to me how all of these ideas could be combined to construct a planning algorithm. I suggest including high-level pseudo-code, or at least a discussion (in English) about the overall steps involved.\n\n7) regarding the results presented in Figure 2: is the setting of O=A+H faster than the alternatives because options allowed the agent to explore more efficiently, during the early stages of its life? If so, were the options helpful *only* during the initial exploratory phase? One simple way of checking whether options were helpful mostly with exploration, or if they were used by the agent to express optimal policies, is to check whether the final learned policy made use of options or, alternatively, whether it used mostly primitives. A discussion about this would be helpful.\n\n8) still regarding Figure 2, the authors claim the the algorithm's rate of learning varied little over a broad range of parameters. However, it seems like the reward rate can vary from approximately 0.03 up to 0.06. This is twice the reward rate, which is not a little change. I suggest either revisiting this claim or better supporting it.\n\n9) Figure 3 shows the parameter-sensitivity of Gosavi's algorithm. Why did you not include an analysis of its reward rate, like you did in Fig2a when analyzing your proposed algorithm?\n\n10) in Equation 17, where is s' coming from? Perhaps the second summation should be sum_{s', r'} instead of sum_r?\n\n11) in Theorem 6, what is v_mu(s)? This was never defined, I believe\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "My understanding is that this paper's main contributions are theoretical. The paper does show a few simple experiments, but additional experimental analysis (even for these simple domains) could be made; see, for instance, my comment #9, above. In terms of technical limitations, I believe that the main one is that the paper tackles only the tabular setting, which is usually not of particular interest for real-world applications. The authors, however, do acknowledge this, and propose extending these ideas to the case of linear function approximation as future work.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4"}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper advances the state of the art for average reward hierarchical RL.  The reviewers unanimously recommended acceptance.  The work is theoretically solid and novel.  Well done!
Decision: Accept (Poster)