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, rettttrreuaaaaeetttteeeenn 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-xxecuting 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+mmaxpp 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,1 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(Sn, Ö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 for 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, 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 - u('((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', o) 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,
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 (6),
(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) ( ((55411 =))
+ -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+ 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.125 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 dpscovndyscovvery 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.0660
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": "y0s1oY8spE9", "reviewer": "Reviewer_WKn4", "summary": "This paper addresses the problems of learning and planning in MDPs with options (i.e., higher-order policies) in the average-reward (rather than discounted reward) MDPs.  Learning and planning algorithms are proposed for (1) inter-option settings, where learning and planning occur between switches in the option followed by the agent, (2) intra-option settings, where the agent learns or plans between low-level actions, and (3) the interruption setting, where agents can actively choose to cease following an option during its execution.  Theoretical results establish the convergence of the learning and planning algorithms, and their performances are demonstrated on examples of the four room domain. ", "questions": "", "limitations": "", "rating": 7, "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": "===Originality===\n\nAlthough much of this work extends previous results (with proper attribution), it finds novelty by doing so in a less-studied setting (average-reward MDPs).  Indeed, it provides the first intra-option average-reward algorithms and demonstrates their convergence to near-optimal policies, as well as improvements over existing algorithms in the inter-option and interrupted settings.  \n\n===Quality===\n\nThe quality of this work is appropriate for a NeurIPS paper.  The mathematics used to develop the algorithms appear to be sound.  The theoretical results are accompanied by sufficient proofs (albeit in the appendices), and the empirical results are reasonably analyzed.  \n\n===Clarity===\n\nThe paper was well written and relatively easy to follow.  It should be accessible to a general audience with some background in MDPs and RL, which is its target audience.\n\n===Significance===\n\nThis paper offers several significant contributions to the literature on average-reward MDPs with options.  Novel algorithms are proposed for several settings, theoretical results establish their important properties, and empirical results demonstrate their performance.  Average-reward MDPs are not as commonly used as discounted-reward, although increased attention in the literature could change that.\n\nI think the significance of the paper would be strengthened through the use of more than one (relatively simple) domain, and a discussion of why the goal state was changed between some of the experiments would also be helpful to understand the experimental setup (the use of room 3 in the interruption experiments was well explained).\n\n===Minor Suggestions===\n\n-- In equations (1) and (2), it might be helpful to add some notation (possibly as a superscript) to clearly indicate the purposes of the two q(s, o) functions so that they aren't accidentally misunderstood.  And likewise for u^q(s, o) in (11) and (12).\n\n-- I think the summation in line 290 should be over s',l and not r,l, correct?", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Several limitations of the work were addressed in the final section.  I don't anticipate significant negative societal impacts of this research.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3"}, "extra_text": {}}, {"review_id": "jTrotn2s4km", "reviewer": "Reviewer_EQtC", "summary": "The paper extends the options framework to the average reward reinforcement learning setting. The paper proposes methods to learn on SMDP level as well as the intra-option level. Additionally, the paper proposes method for planning and interrupting options under this setting.", "questions": "", "limitations": "", "rating": 5, "confidence": 5, "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": "The paper's structure is similar to the classical options paper: it proposes algorithms for all the settings presented in [1] while adapting them to the average reward setting. The paper is clearly written and flows nicely. The average reward setting is also important when we consider function approximation, and therefore extending options to this setting is a promising avenue.\n\nAlthough the paper tackles multiple settings, it is not clear where some original contributions are being made (as opposed to simple extensions from the discounted setting to the average reward setting). A discussion on the originality and importance after each theorem (as is sometimes done in theory) would really help in understanding the merit of the paper.\n\nThe results for the inter-option algorithm seem to be the most original ones and as such the remarks following the theorem are appreciated. The empirical results compare to [2], however this paper is not cited in the introduction around L40, and as such is harder to situate in terms of existing work. The results presented in Figure 1-2 seem to paint a good picture for the proposed approach. However, the sensitivity in Figure 1 mentions that $\\beta = 2^{-1}$. Why aren't there more values presented?\n\nThe results for the intra-option, planning and interrupting algorithms seem to be less important contributions, more discussion to clarify this would be appreciated. The empirical results also lack a bit of context. Although the discounted setting and the average settings are different, couldn't there be comparisons where a sensitivity to the hyperparameters are shown? In the current form, the paper brings the question as to why we should even bother extend the options to the average setting, as there is little motivation intuitively or through experiments. \n\nA small precision: In L211, it is said that all options are updated. However, in [1] it is clearly said that all consistent options are, which brings a key difference. \n\n[1] Sutton et al., Between MDPs and semi-MDPs: A framework for temporal abstraction in reinforcement learning\n[2] Gosavi et al. Reinforcement Learning for Long-run Average Cost\n\n\n=================Post-rebuttal===================\nI appreciate the authors response. The theoretical derivations seem rigorous, however I am not sure how much novelty overall there is, except for theorem 1. Moreover, the authors did not provide convincing experimental results, and in their rebuttal do not intend to. This is quite negative for me. Although the theoretical contributions are present, but are not really surprising and as such I will keep my score as borderline.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Limitations are not really discussed in a clear way.\n\nNo societal impact discussion.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4"}, "extra_text": {}}, {"review_id": "gR22pgnTi01", "reviewer": "Reviewer_mBza", "summary": "This paper presents an options framework for average-reward MDPs. They present a Q-learning based algorithm for such setting. The authors then provide performance guarantees (almost-sure convergence) and then demonstrate on a Four-Room domain.", "questions": "", "limitations": "", "rating": 7, "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": "The main contribution of this paper is to provide a algorithm with performance guarantees (more generalized than earlier work). While discounted setting is relatively easier to handle (thanks to discount factor), the average-reward criteria needs more work. The author present a variant of Q-learning for average-MDPs with option framework. The proof techniques have been borrowed heavily from Wan et. al. (2021) and Abounadi et al (2001). The authors also presented experiment results on Four-room (a grid domain). ", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "1. The proof techniques have been borrowed heavily from existing literature and the algorithm is a very natural extension of Q-learning to options framework.\n2. The authors compare against Gosavi's work by arguing that its convergence proof requires the underlying SMDP to have a special state that is recurrent under all stationary policies. My question is then is this requirement of a special recurrent state only for theory? Because for experiments, when authors compared with it as a baseline, they did not choose any special state. I believe it might be an artifact of the proof because the proposed algorithm and the existing one are very similar. Numerically, the authors said they observed that their algorithm had less variance than the baseline, what is the reason behind that?", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "5 hours"}, "extra_text": {}}, {"review_id": "5gmdMbNaFz2", "reviewer": "Reviewer_cm1m", "summary": "This paper considers reinforcement learning in an infinite horizon Markov decision process reward function $r$ and transitions $p_{s,a}$ for each $s$ and $a$ in $S \\times A$.  The high level goal is to use the known model efficiently in order to learn a policy $\\pi$ mapping states $s$ to actions $a$ which maximizes the cumulative reward experienced acrossed the trajectory.  In contrast to typical modeling assumptions, here the authors make two distinctions from prior work.  First, they consider the average cost setting instead of the discounted setting, where the goal is to instead maximize the limiting average rewards accumulated across the trajectory.  Second, they consider the so-called 'options' framework where instead of directly learning a policy over actions, the agent has access to a set of options $O$.  Each option consists of two components.  The first, is the policy $\\pi$ mapping states to a distribution over actions.  The second is a probability distribution of the option's termination, mapping states to a value in $[0,1]$ for the probability the option terminates from that specific state.\n\nEach option executes as follows.  First, upon visiting a state $s_t$ the agent choses an action according to the current option's policy.  The agent then observes the next state, picks an action according to the next state, and the option terminates with some probability.  The behavior of the agent is then classified according to the policy mapping states to options (instead of actions).  This process can be marginalized out to generate a new process whose actions correspond direction to options, but loses some of the Markovian properties to become a semi-MDP.  The goal in this framework is exhibited through three separate ways, all of which are addressed by the authors.\n\nFirst the authors consider inter-option learning.  In this model the agent plans with options instead of primitive actions.  Given an option, the learning algorithm occur only after the options simulated execution is finished.  As such, these models are a direct form of Semi-MDP algorithm.  Here the authors provide an extension of differential learning and planning algorithms from average-reward MDPs to MDPs with options, which essentially is a form of $Q$ learning with the updates over options instead of actions, and an extra term scaling with the expected option length.  They show that their approach is consistent, leading to accurate estimates of the value of the policy, or that their algorithm is also consistent in learning the optimal policy as well.\n\nSecond the authors consider the intra option learning.  Different from inter-option, here the algorithms can update after each state-action transition within an options executed is completed.  From a single state-action transition, the algorithm is able to learn or plan to improve the value or policies for all options that may have also generated the same transition.  As such, they are more efficient than inter-option learning.  Here the authors again extend $Q$ learning based algorithms, and present a model based planning algorithm as well.  These algorithms are slight modifications of those for inter-option learning as they are able to update all options simultaneously after taking an action, potentially utilizing importance weights to fix the distribution shift issue.\n\nThird, the authors investigate whether 'early termination' helps improves agent policy performance.  They tackle this issue by understanding the performance of a modified problem where each option is linked to a new option where the termination distribution is replaced via guaranteed termination whenever the value of $Q(s, o)$ is smaller than the value $V(s)$ for being in the state according to a policy $\\mu$.  In Theorem 6 the authors show that this process allows for learning a policy which is no worse than the old one, and strict improvement whenever there is a non-zero probability of encountering an interruption.  In essence, this result highlights that allowing the agent to terminate an options once a state is visited where a separate option can allow for better performance guarantees policy improvement.\n\nLastly they complement these three theoretical directions with experimental results.  The experimental results are constructed to help highlight the theoretical convergence of their algorithm, serving more of a 'theoretical proof of concept' than an empirical performance benchmark.  This seems sufficient for there setting due to a lack of related work to offer comparisons with, and the experiments were chosen in a way to help highlight different aspects of the algorithmic and options framework.\n", "questions": "", "limitations": "", "rating": 6, "confidence": 2, "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:\n\nThe authors present a novel extension of the options framework to average cost MDPs.  While the approach presented seems like a straightforward modification of existing $Q$ learning algorithms for average-cost MDPs formulated in the options setting, the authors clearly express the new strategies required for modeling the options and theoretical tools needed.\n\n### Quality:\n\nThe submission is technically sound and the theoretical and empirical claims are well supported.  The authors are honest and upfront on the new techniques used in the modeling, proof, and algorithm development, namely:\n- access to an existing set of options.  The problem of option discovery is a tangential and related problem, and discussed in the conclusion as a direction for future work and\n- discrete set of state  actions (and small enough to be computationally feasible to store and maintain estimates over)\n\n### Clarity:\n\nThe submission is clearly written and well organized.  However, some of the theorem statements are presented rather informally (with a full presentation in the appendix).  Potentially the main paper should include some more of the technical details to help with readability.  At a high level, the authors never provide any concrete motivation for the options framework in contrast to the typical MDP model.\n\nMoreover, in section 3, the authors present the algorithm assuming that the option length is estimated and unknown.  However, under remark 138 the authors then state the theorem assumes the expected option lengths are used in the equations.  This point should be clarified more and presented in Theorem 1 as it seems to contradict the algorithm presentation.\n\nSimilarly, the introduction paragraph under section five doesn't help highlight the different approach presented in this section, being a model-based algorithm that specifically estimates the semi-MDPs transitions versus a $Q$ learning algorithm presented before.\n\n### Significance: \n\nThe results presented in this paper provide a novel extension of $Q$ learning and model-based algorithms to average cost MDPs under the option framework.  While the novel theoretical basis is quite limited (the technical details are strong, but the model is not motivated at all in the paper). The work can be built upon by better investigating the simultaneous problem of learning options, and extending the algorithms for large state action spaces.\n\n### Strengths:\n\nThe main strengths of the paper are as follows:\n- the extension of average cost MDPs to the options framework\n- the experimental results presented in the main paper and the appendix provide a detailed description of their algorithm's performance\n\n### Weaknesses:\n\nThe main weaknesses of the paper are as follows:\n- the motivation of the options framework is never explicitly described in the main paper\n- some of the technical details are omitted in the main text\n\n### Questions and Comments:\n- Have you performed a comparison between inter and intra option learning frameworks through an experimental simulation?\n- In line 120 - if the option length is known, the algorithm would just plug in the true value? \n- Related work section?", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The paper focuses on the theoretical foundations for developing optimal control and evaluation algorithms for average cost MDPs with options, and so it is expected that it will not have any potential negative impacts. The authors are also clear on the limitations of their work including:\n- access to an existing set of options.  The problem of option discovery is a tangental and related problem, and discussed in the conclusion as a direction for future workand\n- discrete set of state  actions (and small enough to be computationally feasible to store and maintain estimates over)", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4 hours"}, "extra_text": {"ethical_concerns": "The work presented in this paper considers a theoretical algorithm for solving average cost MDPs with options. As such, there are little ethical considerations for this paper, outside of those addressed in the paper and common to all optimization and algorithmic techniques (computational cost and computing resources required for solving for the policy).\n"}}]

Author rebuttal:

Meta-review: After a lot of discussion amongst the reviewers as well as with the authors, this paper was judged to be strictly borderline. Extending the options framework to the average reward setting is a fine line of inquiry, but as such the setup of this paper is rather weakly motivated as observed by multiple reviewers and the algorithms and analysis are relatively incremental in their novelty. Even for toy experiments, we would have at least liked to see the authors illustrate some capability afforded by the average reward formulation which the discounted formulation lacks, for instance. Perhaps the paper is more suited as a comprehensive journal submission, with a treatment of function approximation and/or option learning.
Decision: Accept (Poster)