Oracle-Efficient Reinforcement Learning for Max Value Ensembles
Authors: Marcel Hussing
Michael Kearns
Aaron Roth
Sikata Bela Sengupta
Jessica Sorrell
Venue: NeurIPS 2024 poster (2024)
Keywords: Reinforcement Learning Theory
Ensembling
Max-Following
Learning Theory
Primary area: reinforcement_learning
TL;DR: We provide an efficient algorithm to learn an approximate max-following policy using K constituent policies in large state spaces.

Abstract: Reinforcement learning (RL) in large or infinite state spaces is notoriously challenging, both theoretically (where worst-case sample and computational complexities must scale with state space cardinality) and experimentally (where function approximation and policy gradient techniques often scale poorly and suffer from instability and high variance). One line of research attempting to address these difficulties
makes the natural assumption that we are given a collection of base or *constituent* policies (possibly heuristic) upon which we would like to improve in a scalable manner. In this work we aim to compete with the *max-following policy*, which at each state follows the action of whichever constituent policy has the highest value. The max-following policy is always at least as good as the best constituent policy, and may be considerably better. Our main result is an efficient algorithm that learns to compete with the max-following policy, given only access to the constituent policies (but not their value functions). In contrast to prior work in similar settings, our theoretical results require only the minimal assumption of an ERM oracle for value function approximation for the constituent policies (and not the global optimal policy or the max-following policy itself) on samplable distributions. We illustrate our algorithm's experimental effectiveness and behavior on several robotic simulation testbeds.

Oracle-Efficient Reinforcement Learning for Max Value Ensembles
Marcel Hussing
Michael Kearns
Dept. of Computer and Information Science
Dept. of Computer and Information Science University of Pennsylvania
University of Pennsylvania Philadelphia, PA 19104
Philadelphia, PA 19104
mhussing@seas. upenn. edu
mkearns@cis.upg upennn upenn. edu
Aaron Roth
Sikata Bela Sengupta Dept. of Computer and Information Science University of Pennsylvania Philadelphia, PA 19104
Dept. of Computer and Information Science University of Pennsylvania Philadelphia, PA 19104 aaroth@cis.. upenn. edu
sikata@seas. upenn edu
Jessica Sorrell
Dept. of Computer Science Johns Hopkins University Baltimore, MD 21218 jess@jhu edu
Abstract
Reinforcement learning (RL) in large infinite state spaces is notoriously challeng- ing, both theoretically (where worst-case sample and computational complexities must scale with state space cardinality) and experimentally (where function ap- proximation and policy gradient techniques often scale poorly and suffer from instability and high variance). One line of research attempting to address these difficulties makes the natural assumption that we are given collection of base or constituent policies (possibly heuristic) upon which would like to improve in scalable manner. In this work we aim to compete with the max-following policy, which each state follows the action of whichever constituent policy has the highest value. The max-following policy is always at least as good as the best constituent policy, and may be considerably better. Our main result an efficient algorithm that learns compete with the max-following policy, given only access to the constituent policies (but not their value functions). In contrast to prior work in similar settings, our theoretical results require only the minimal assumption an ERM oracle for value function approximation for the constituent policies (and not the global optimal policy or the max-following policy itself) samplable distributions. We illustrate our algorithm's experimental effectiveness and behavior several robotic simulation testheds.
Introduction
Computationally efficient RL algorithms are known for simple environments with small state spaces such tabular Markov decision processes (MDPs) [Kaars and Singh 2002 Brafman and Tennen: holtz 2002), but practical applications often require dealing with large or even infinite state spaces.
"This work was completed while this author was the University of Pennsylvania.
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

Learning efficiently in these cases requires computational complexity independent of the state space. but this is statistically impossible without strong assumptions on the class of MDPs paksch et al.)
2010 I Lattimore and Hutter 2012 Du et al. 2019 Domingues et al. 202T]. Even in structured MDPs
that admit statistically efficient algorithms, learning an optimal policy can still be computationally
intractable (Kane et al. 2022 Golowich et al., 2024).
These obstacles to practical RL motivate the study of ensembling methods [Lee et al. 202 Peer
et al. 2021 Chen et al. 2021 Hiraoka et al. 2022]. which assume access to multiple sub- sub-optimal
policies for the same MDP and aim to leverage these constituent policies to improve upon them.
There are now several provably efficient ensembling algorithms, but their guarantees require strong assumptions on the representation of the target policy learned by the algorithm. [Brukhim et al. [2022] use the boosting framework for ensembling developed in the supervised learning setting [Freund and
Schapire 1997] to learn an optimal policy, assuming access to a weak learner for a parameterized policy class. To efficiently converge to an optimal policy, the target policy must be expressible as depth-two circuit over policies from a base class which is efficiently weak-learnable. The convergence guarantees additionally require strong bounds on the worst-case distance between state-visitation distributions of the target policy and policies from the base class.
Another line of ensembling work considers a weaker objective than learning an optimal policy [Cheng ct al. 2020 Liu et al. 2023 2024]. These works instead aim to learn policy competitive with a max- aggregation policy, which take whichever action maximizes the advantage function with respect to a max-following policy at the current state. When these works have provable guarantees, they require the assumption that the target aggregagat policy can be approximated in an online-learnable parametric class, as well as the assumption that policy gradients within the class can be efficiently estimated with low variance and bias.
Our goal learn policy competitive with similar but incomparable benchmark to that of Cf iet al. [2020] under comparatively weak assumptions. We give an efficient algorithm for learning a policy competitive with max-following policy (Definition 2.1). assuming the learner has access to squared- error regression oracle for the value functions of the constituent policies. Our algorithm exclusively queries this oracle on distributions over states that are efficiently samplable, thereby reducing the problem of learning a max maxx-foloowig competitive policy to supervised learning of value functions. Notably, our learnability assumptions pertain only to the value functions of the constituent policies and not to the more complicated class of max-following benchmark policies or their value functions. Our algorithm is simple and effective, which we demonstrate empirically in Section [
It is natural to wonder if access to an oracle such as ours could be leveraged to instead efficiently learn an optimal policy, obviating the need for weaker benchmarks (and our results). However, was recently shown by [Golowich et al. 2024) that learning an optimal policy in particular family of block MDPs is computationally intractable under reasonable cryptographic assumptions, even when the learnrr has access to squared-error regression oracle. Their oracle captures a general class of regression tasks that includes value function estimation, and therefore also captures our oracle assumption. Our work shows that when we instead consider the simpler objective of efficiently learning policy that competes with max- max-following a regression oracle is in fact sufficient. We leave open the interesting question of whether such an oracle is necessary.
1.1 Results
Our main contribution is a novel algorithm for improving upon a set of K given policies that is oracle efficient with respect to a squared-error regression oracle, and therefore scalable in large state spaces (Algorithm [] Theorem 3. D. We consider the episodic RL setting in which the learner interacts with its environment for episodes of fixed length H. The algorithm incrementally constructs an improved policy over H iterations, learning an improved policy for step h E [H] of the episode at iteration h. This incremental approach allows the algorithm explicitly construct efficiently samplable distributions over states visited by the improved policy at step h by simply executing the current policy for h steps. It can then query its oracle to obtain approximate value functions for all constituent policies with respect to this distribution. This in turn allows the algorithm to learn an improved policy for step h ++ 1 by following the policy with highest estimated value. By incrementally constructing an improved policy over steps of the episode, we can avoid making assumptions like those of Brukhim et al. [2022) about the overlap between state-visitation distributions of the target policy and the intermediate policies constructed by the algorithm.

---

As our oracle only gives us approximate value functions, we take as our benchmark class the set of approximate max-following policies (Definition 2.3). This is superset of the class of max-following policies and contains all policies that at each state follow the action of some constituent policy with near-maximum value. Section 4 we prove that for any set of constituent policies, the worst approximate max-following policy is competitive with the best constituent policy (Lemma 4.1 and provide several example MDPs illustrating how our benchmark relates to other natural benchmarks.
Finally, we demonstrate the practical feasibility of our algorithm using a heuristic version on a set of robotic manipulation tasks from the CompoSuite benchmark Mendez et al. [002]] Hussing et al. (2024). We demonstrate that in all cases, the max- max-following policy we find is at least as good as the constituent policies and in several cases outperforms it significantly.
1.2 Related work
Our work is related to a recent line of research learning a mux-aggregation policy [Cheng et al. 2020 Liu et al. 2023, 2024), which can be viewed as a one-step look-ahead mox-foolowing policy and is incomparable to the class of max-following policies (see Cheng et al. [2020) for example
MDPs demonstrating this fact). [Sekhari et al. (2024) consider the problem of imitation learning from multiple noisy experts using selective sampling. For queried experts, their algorithm invokes an online regression oracle assumption and they leave as an open direction learning with offlin regression oracles. These works all assume online learnability of the target policy class, which is strictly stronger than our batch learnability assumption for constituent policy value functions.
The work of Cheng et al. 2020 proposes an algorithm (MAMBA) that uses policy gradient methods. and the convergence of the learned policy to their benchmark depends on the bias and variance of
those policy gradients. Liu et al. [2023 2024] builds on the work of [Cheng et al., 2020]. Their
algorithm MAPS-SE modifies MAMBA to promote exploration when there is uncertainty about which constituent policy has the greatest value at a state, via an upper confidence bound (UCB) approach to policy selection. Reducing uncertainty about the constituent policies' value functions reduces the bias and variance of the gradient estimates, improving convergence guarantees. However, policy gradient techniques are known to generally have high variance [Wu et al. 2018). and this appears to affect the practical performance of MAPS-SE in certain cases (see Section for additional discussion).
The boosting approach to policy ensembling of Brukhim et al. [022 also necessitates very strong assumptions. This follows from the computational separation in Golowich et al. [2024], which shows that our oracle assumption is insufficient to learn an optimal policy, whereas the assumptions made in Brukhim et al. [2022) enable convergence to optimality.
Much work on policy improvement considers improving upon a single base policy and do not address
the challenge of ensembling (Sun al. 2017 Schulman al. 2015 Chang et al. 2015 Barreto
et al. 2017 2020), Aleegr et al. [2024] consider the problem of Generalized Policy Improvement (GPI) by decomposing complex tasks into a set of multiple smaller tasks where they use transfer learning. However, they make strong assumptions about the joint representation of rewards (tasks) as linear in successor feature representations. which may be challenging to explicitly learn in MDPs that are not tabular. Zaki et al. (022) consider the setting of access to M base controllers with the aim of optimally combining them to produce a controller that is competitive with the base set. They approach this problem with the aim of considering a single controller from the softmax policy class over the base set of policies that is competitive with all the others, but not in a depende manner. Empirical work on ensemble imitation learning (IL) also studies the problem of leveraging multiple base policies for learning [Li et al. 2018, Kurenkov et al. 2019), but these works lack provable guarantees of efficient convergence to meaningful benchmark. [Song et al.) 2023 provide survey of a variety of more complex techniques to ensemble policies, mainly from practical perspective.
2 Preliminaries
We consider an episodic fixed-horizon Markov decision process (MDP) [Puterman] 1994 which we formalize as tuple M (S, AA R, P. No, H) where S is the set of states, A the set of actions, R is a reward function, P the transition dynamics, f40 distribution over starting states and H the horizon
Sutton and Barto 2018 [NV] will denote the set (O...., N 1}. In the beginning, an initial state so
3

---

is sampled from Aa. At any time h E [H], the agent is in some state Sn E S and chooses an action a, E A based on a function Ti mapping from states distributions over actions II S + A (AA). As consequence, the agent traverses to new next state Sh+1 sampled from P(-|sh, a4) and obtains reward R( (.). Without loss of generality, we assume that rewards bounded within [0, 1). The
sequence of functions TA used by the agent is referred to as its policy, and is denoted π = { ( A trajectory is the sequence of (state, action) pairs taken by the agent over an episode of length Hi, and is denoted = {55,, HeEM trajectory by first sampling a starting state so ~ (lo, and then executing policy π from 80-
We will use the notation T π (Ho)) to refer to sampling
The goal of the learner is to maximize the expected cumulative reward Eeo |Et-o' R(s 0t)] over episodes of length H. We further define the value function the expected cumulative return of following some policy π from some state 8 as V (s)
H 111---1-66
R P = R(s;, az) I 80 = 8). Due to the finite horizon of the episodic setting, we will also need to refer to the expected cumulative reward from state 8 under policy from time h E [A]] We denote this time-specific value function by ViT(() = Er R( ae) [e) Sp. = s]. Finally, the key object of interest is a max-following policy. Given access to a set of I arbitrarily defined policies II = {-"} and their respective value functions which we denote by the shorthand V V², a max-following policy is defined as a policy that at every step follows the action of the policy with the highest value in that state.
Definition 2.1 (Max-folla follwwolooiing policy class). Fix a set of policies IIe for a common MDP M and an episode length H. The class of max- max-following policies 11 is defined
11th max = { Vh E
[H]. Vs E S, (s)) = n² (s) for some k" E &argmax V2 (s)} kE[K]
Note that for any collection of constituent policies III there may be many max-following policies, due to ties between the value functions. Different max-following policies may have different expected return, and we refer the reader Observation 4.5 for an example demonstrating this fact.
We assume access to a value function oracle that allows us to approximate a value function of a policy under samplable distribution at any specified time h E: [H]. This oracle is intended to capture the common assumption that the value function of a policy can be efficiently well-approximated by a function from a fixed parameterized class. In practice, one might imagine implementing this oracle as a neural network minimizing the squared error to a target value function.
Definition 2.2 (Oracle for π value function estimates). We denote by O an oracle satisfying the following guarantee for a policy л. For any a E (0, 1], and any h E [H], given as imput time h E (H) and sampling access to any efficiently samplable distribution ju, the oracle outputs
VIT t O (a, p. h) such that Es~H (s) VØ (s))²] S a. We use the notation O = O (a....) to denote OF with fixed accuracy parameter a. We will also use the shorthand O O=
Looking ahead to Section 3 we note that for every distribution μ on which Algorithm M queries an oracle, y is not only efficiently samplable, but samplable by executing explicitly constructed policy Tammp for h steps in MDP M, starting from (Ag. Thus, for any distribution 14, policy n², and time h for which we query O we could efficiently obtain an unbiased estimate of EEssulV [V, (s)] by following a known sammp for h steps from No. and then switching to x² for the remainder of the episode. We mention this to highlight that oracle is not eliding any technical obstacles to sampling in the episodic setting. It is simply abstracting the supervised learning task of converting unbiased estimates of [V, (s)] into an approximation 1% with small squared error with respect to μ.
Lastly, we define our benchmark class of policies. Given a set of constituent policies T our benchmark defines for each state and time set of permissible actions: any action taken by a policy n' E 1I for which the value (s) is sufficiently close to the maximum value max VíA (s). The class of approximate follfollowing policies is then any policy that exclusively takes permissible actions. We refer the reader to Section for further explanation of this benchmark.
Definition 2.3 (Approximate max max-following policies). We define set of 3-good policies at state E S and time h E [H], selected from a set 11,, as follows.
(s,((s) = (Tt & Vx) Z max V/+ (3)
kE[K]
Then we define the set of approximate max-following policies for & be
11/5 = {T: Vh E [H], Vs E (s) (i) for some n' E {s))

---

3 The Maxlteration learning algorithm
In this section, we introduce our algorithm for learning an approximate max-following policy, Maxiteration (Algorithm[] |
This algorithm learns a good approximation of a max-following policy step h, assuming access to a good approximation of max-following policy for all previous steps.
For the first step (h 0), the algorithm learns good approximation Vi for all constituent policies nz on the starting distribution yo- These approximate value functions can in turn he used to define the first action taken by the approximate max-following policy, namely #o (s)ss) " argmax, Vo (a) (s). Following
#o(s) from po generates a samplable distribution over states jn (s) = Exgrrol [P 8o, To (x)))) and so our oracle assumption allows us obtain good estimates V with respect to μa for all x². We can then define the second action of the approximate nol-foglo policy, and so on, for all / steps.
Notice that sampling from Pa, does not require that the agent can reset the environment at will. It only requires what is typically required in the episodic setting - that the agent explores for an episode of H steps, where H is finite and fixed across all of training. After these H steps, the agent is then reset to a state sampled from the distribution over starting states. The distributions μ4, are (informally) defined as follows: at iteration h E [H] of our algorithm, the agent has already learned good approximate max- max-following policy for the first h steps the episode. The distribution 14, the distribution over states visited by the agent at step h if it begins from a state drawn from the starting state distribution and then follows the approximate max-following policy has learned thus far for steps. That means to sample from (4s the oracle can simply run the approximate max-following policy for h steps to arrive at a state 8h, which is a sample from μaa. It can then do anything for the remainder of the episode, and so does not need to reset at arbitrary time steps. In practice, since the oracle needs to produce a good approximation of the value function V at time for policy л on states sampled from un,, one should think of it using the remainder of the episode to obtain an unbiased estimate of the expectation of V on the distribution μA. That is, once it has sampled a state 8%, by running the approximate max-following policy for steps, it just executes policy x for the remainder the episode. The accumulated reward obtained by following policy x² from state Sh, for steps h through H gives the oracle an unbiased estimate of Ess..p. [V% (s²))- To implement this oracle assumption, one could use many such unbiased estimates training data train neural network, to learn good approximate value function for n² at time h on distribution (4h-
Algorithm 1 Maxlteration M (
1:
for h [H] do for k E [K] do
2:
3:
let ps be the distribution sampled by exccuting the following procedure:
4:
sample a starting state so ~ 140
5:
for i [h] do
6:
8;+1 ~ P( 81, argmax, (t)) end for output 8h
7:
8:
9:
V + (Hn,
end for end for
11:
return policy म (#ntnEjH) where (s) argmaxuc ()))))))
For any e E (0, 11. any MDP M with starting state distribution po, any episode length H, and any K policies & defined on M, let a E O e Maxlteration
Theorem 3.1.
kg)) and O Then M (II²) makes O(H oracle queries and outputs a such that
E 807114
[
2 min E [V"(s))]-O(G #Ells 8a
Proof. For all h E [H] A E [K]. let 1/ denote the approximate value function obtained from We then define, for every h E [H], the set of states for which some ap-
Ok (ps, h) in Algorithm 1 proximate value function (s) has large absolute error (Bx) and the set of bad trajectories (B,) that
5

---

pass through state in B, for any h [ B, = fs 3K E
- (+)) ス 2H [K]ss. s.t. (s)
and B, ((<5).a))eei an) 3h E [H] s.t. S, E B.). We will show that there exists an approx- imate max-following policy т E ny such that for any trajectory T' $ B,, Prr = - Pr, PTz=)(po)(7 |T = = We then bound the probability PTz~*(po)(T By]. and the contribution to Eso [V (so)] from these trajectories, proving the claim.
Let V (s) denote the value of the policy that at follows at time h and state a. From the definition of the bad set B₁, and the setting of B E O f for any state of Bn.
V (s) k (s)
E 2H
max
V (s)
(s)
c 2 max V (s) - B. 2H
KEIK
KE[K]
In other words, if a state s is not bad at time h, then (s) = ( for policy nh that has value V (s) within 8 of the true max value ma V/((s) (s). It then follows from the definition of the class of approximate max-following policies II (Definition 2.3) that there exists some E II such that for all h [HT) for all & BR, (s) = (s).
For any trajectory T', P 71 Pr [su] 10 P( 18h tn (s))) Then for any trajectory 7' & B,, Pry (T = =1 = Pryns(Hu)) [T T'J. and therefore
H
H
E (No((WO)
Σ A=
R(sh: an) r E Br
E TNT((H))
Σ h=
R( an)
TT Br
For T Br, we have lower and upper-bounds Er~A(HO) 2n R(sh, an) 1 TE E Br] 2 and ET~h(Ho) 1E/-10 R(sh, as) T B,] S H. We can then write:
E
[*00) = E (wo(HH)
Σ R(sh. and T E B,
Pr [T {B) Toot(ma)
H-1
E (ma)
R(sh, an) T B-
Pr [T E Br] TmR(Ha)
haD
1-1
R(sh; an) T Br
Pr [T $ B+]
(wo(pg)
h
Tma(Ha))
E (agl(pg)
R(sh, an)
T Br
Pr [T E Br] (ma)(1g)
E Tuo((p))
R(sh, an)
- H.
Pr [T B.] roml(m))
(using total probability and upper bound rewards)
min *EnT
[V' H
Pr Two((p))
Br).
remains to upper- PTyra(Po)(T E B.). We have already argued Pro=e(ro)[T E B,] PT+~A(ma)T IT E Br]. Observing that Pry [T E B,] ΣHI Pry [sh E Bp]. it is sufficient to show Prywatun) [8h. Br] O (T)) to prove the claim. For all h E [M]. let
(s) = Pry-a(po))e [sh = s), and note that this is the distribution supplied to the oracle at iter-
ation of Algorithm It follows from our oracle assumption (Definition 2.2) that for all E [K]. Eaa [(V* (sn) v (sn)) < a. We apply Markov's inequality to conclude that for all k E [K].
Pr 11 (s.) V/ (s:)) 2 2H 8% ~4
4 e E 50(Ki O(KH))
Union bounding over the K constituent policies gives Pre cus [9h E B&] E O tion of B,. Union bounding over the trajectory length H. we then have Pr, Pry~a(m)) B,] O(F). It follows that
me ), from the defini-
E Sp
[V*(s))]
2 min E [V*) -
EETTS sg
completing the proof.

---

84
0
80
81
82
83
81
0
0
(b) MDP with A = (right, left, up] where starting from $2, max-following is far worse than optimal and starting from So. different max-following policies have different values (depending tie-breaking).
(a) MDP in which two policies going either only left or right obtain low return but max- following them would be optimal.
Figure I: Examples of MDPs with max-following policy performance comparison
4 The approximate max-following benchmark
In this section, we provide additional context for our benchmark class of approximate max-following policies. We show that the worst policy in our benchmark class competes with the best fixed policy from the set of constituent policies. We also provide examples of MDPs that showcase properties of the set of (approximate) max- followigg policies.
Lemma 4.1 (Worst approximate max-following policy competes with best fixed policy). For any & (0, 1] and any episode length H, let 3 E (())) Then for any MDP M with starting state distribution μa, and any K policies II defined on M.
min TEm
E Barupo
[V)(] 2 max E
[[V((so)] - O()).
KE[K] 90mpto
We defer the proof of Lemma
4.1 Appendix B
is an immediate corollary Theorem 3.1 and Lemma 4.1 that the policy learned by Algorithm ! competes with the best constituent policy.
Corollary 4.2. For any (0, 1], any MDP M with starting state distribution po, any episode length H, and any K policies & defined on M, let a E O( ((T)), and let â denote the policy oulput by Maxlteration (II*). Then
E Sg
[V))
max E KE K] Spr-too
-
We provide diagrams of MDPs examples for the observations that we make below. States in S are denoted by the labels on the nodes. Actions A are indicated by arrows from given states with deterministic transition dynamics and the rewards R(s, are labeled over the corresponding arrows. Arrows may be omitted for transitions that are self-loops with reward
Observation 4.3. The worst approximate max-following policy can be arbitrarily better than the best constituent policy.
Consider in Figure two policies on this MDP: 78) right and प r'(s) left, for all E S. Note that for any episode length > 2, for all & E {0, 1}, max V*(s) = 2. For any B < 1, IT comprises policies ग such that π (s0)) = right, π (S2) = left, and (s1) E (right, left]. Therefore for any episode length H, and state s S, min V V*(()
H. In this example, any approximate max-following policy is also an optimal policy, whose gap in expected return with the best constituent policy can be made arbitrarily large by increasing Il.
Observation 4.4. max-following policy cannot always compete with an optimal policy:
In Figure lb consider policies nt (s)) right, π. <'(s) = left, and (s) = for all S. At state 82, " is the only policy with non-zero value. Thus, any max-following policy will take action right from 82, receiving reward and then reward ( for the remainder of the episode. Given starting state distribution supported entirely on 82, for any episode length H 2 3, the optimal policy will obtain cumulative reward H - 2. whereas any max-following policy will only obtain reward
7

---

85
1
83
84
R(a,1] 11
$2
Ris, -1)
start
(a) MDP where small value approximation so hinder max-following. Arrows representing transition dynamics are color-coded red to indicate actions taken by x² and blue to indicate actions taken by xt
state
(b) MDP where the max- max-following value function is piecewise linear, but constituent policy's s values are affine functions of the state for fixed actions.
Figure 2: Examples for Observation 4.6 and Observation 4.7
Observation 4.5. Different max-following policies may have different expected cumulative reward.
We again consider Figure lb but suppose now the starting state distribution is supported entirely on Su. For all & [3]. V Su) 0 and so max-following policy may take any action from so. A max-following policy that always takes actions left or up from 8, will only ever obtain cumulative reward 0, but max-following policy that takes action right will move to and (so long more than one step remains in the episode) will then take action up and move to state 84, where it will stay obtain cumulative reward H 2.
the value functions of constituent policies are exactly known, is easy to construct a max-following policy, but the learner may not have access to these functions. If the learner only has access to approximations and follows whichever policy has the larger approximate value at the current state, the resulting policy can have much lower expected cumulative reward than the mox-following policy. This is true even for state-wise bounds on the value approximation error. This observation previously motivated our definition of the approximate max-following class (Definition 2.3
Observation 4.6. Small value function approximation errors can be obstacle to learning max-following policy.
we again consider policies N (s) right and (s) left for all states 8 E S, color coding the actions taken by T" with red and T with blue in Figure 2a For starting state distribution supported entirely on 80, a max-following policy æ will take action (50) = left, (82) = right, and
In Figure 2a
(sa)) = left for the remainder of the episode, obtaining reward // 2 2s. However, given only approximate value functions f with state-wise absolute error bound (s) (*) S e for all
states and times h, the policy that takes action TH (s) for k* = argmax kE|2] V (s) can have much lower expected cumulative reward than max-following policy. For example if 10 (so) and V/J (=o) in our Figure eaxemplee then will have expected return
Observation 4.7. A max-following policy's 's value function is not always of the same parametric class as the constituent policies' value functions.
As a simple first example, consider an MDP with states S = [0, 1] and actions A = 1) Every action leads to a self-loop (for all A, P(s]s, a) = and for fixed action, rewards are - s and R(s, 1) = s). We consider two policies: 1 for all E S. Notice that for episode length H. (* H1 R(s, 1) and (s) = HR(s. 1). Since the dynamics keep the state at the same fixed place independent of the action, the max- max-followe mollowin policy state will simply be the max the two individual value functions at s and therefore its parametric class will be piecewise linear. unlike the constituent policies' which are affine (see Figure 2b). To provide a more complex MDP example, we consider traditional control problem with continuous state and action spaces: the discrete linear quadratic regulator. In this example the constituent linear policies have quadratic value functions, but the max-foll mal-follooing policy is not of the same parametric class. See Appendix A for further discussion.
affine functions of the state (e.g. R(s, -1)
(s) - and (1(s)

---

5 Experiments
We proceed to examine our MaxIteration algorithm in a set of experiments that uses neural network function approximation as oracles. These experiments aim to provide scenario to demonstrate the usefulness of max-following. While previous works in this line of research have studied the ability to integrate knowledge from the constituent policies increase performance of a learnable policy [Cheng et al. 2020] [iu et al.) 2023 2024) our algorithm offers an alternative approach. We consider a common scenario from the field of robotics where one has access to older policies from robotic simulator that were used in previous projects. As long as the dynamics of the MDP of interest do not differ, such old policies can be simply be re-used in new applications. In such cases, training completely from scratch can be incredibly expensive due to the vast search space [Schulman et al.
2017
Haarnoja et al. 2018]. We note that this setup is related to the one used by Barreto et al. 20117
2020
but we do not put any constraints on the reward functions.
Experimental setup A recent robotic simulation benchmark called CompoSuite [Mendez et al.
2022] and its corresponding offline datasets [Hussing et al. (024) offer an instantiation of such a scenario. CompoSuite consists of four axes: robot arms, objects, objectives and obstacles. Tasks are simply constructed by combining one element from each axis. We consider tasks with a fixed IIWA robotic manipulator and no obstacle. This leaves us with total of 16 tasks. These 16 tasks are randomly grouped into pairs of two. Each group is one experiment where the policies trained on tasks correspond to our constituents. To create a new target task, we change one element per task, creating novel combinations for each group. For example, we start with the constituent policies that can 1) put and place a box into a trashcan and 2) push a plate. The target task can be to push the box. We train our constituent policies on the expert datasets using the offline RL algorithm Implicit Q-learning [Kostrikov al. [022] (IQL.) This ensures we obtain very strong constituent policies for their respective tasks. After training the constituents, we run Maxlteration and the baselines for short amount of time in the simulator. We report mean performance and standard error over 5 seeds using an evaluation of 32 episodes.
Algorithms For practical purposes, we use heuristic version of Maxlteration which does not re-compute the max-following policy at every step h but rather after multiple steps. For our baselines, we ran the code provided by (Liu al. 2023 train the MAPS algorithm but were unable obtain non-trivial return even after reasonable amount of tuning. MAPS has been shown to have difficulties with leveraging very performant constituent policies such as the ones we are using (see the Walker experiment by [iu et al. 2023 in Figure 1 (d) in which the algorithm struggles to be competitive with the best, high-return constituent policy). They conjecture that in this case, their estimates of the constituent value functions will be less accurate in early training, resulting in gradient estimates with large bias and variance, weakening their convergence guarantees. We provide an evaluation of Maxlteration on tasks originally used by Liu et al. [2023] in Appendix C.3
For now, we opt to use IQL's in fine-tuning capabilities that offer policy improvement style method on top of the best cest-performing constituent policy for comparison. Fine-tuning provides strong baseline in the sense that has access to the already trained value functions of the constituent policies providing it with inherently more starting information. For comparability, we limit the number of episodes available for fine-tuning to the same number of episodes available for training Maxtteration. For more details we refer to Appendix C
Experimental Results Figure contains a set of demonstrative results. The full results are deferred to Appendix C The selected results in FigureBhiggh highlighh three properties of Maxlteration:
1. There are cases where max-following not only increases the return but actually leads to solving task successfully even when none of the constituent policies achieve success.
2. With successful constituent policies, max-following can significantly increase the success rate.
3. max-following can sometimes increase return but not necessarily lead to success demonstrating the need to better understand which attributes make up good constituent policies in the future.
The results Appendix C demonstrate that all cases, Maxlteration at least as good as the best constituent policy which is not the case for algorithms from prior work [Liu et al. 2023 as discussed earlier. Moreover, Maxlteration consistently leads to greater return improvement than fine-tuning given the same amount of data. Fine-tuning with substantially more resources would

---

Policy
Policy
IQL
Maxiteration
Dumbbell, Pickflace
Box, PickPlace Dumbbell, Push
Plate, Shelf
Box, Treshcan
Dumbbell, Trashran
Dumbbell, Trashcan Dumbbell, PickPlace
Plate, Trashcan
300
Success Rate
Retums
200
0.5
100
0.0
Figure 3: Policies 0 and correspond to the pre-trained policies using IQL. on the intial tasks above the arrow in each graph. That is, in the left most subfigure, Policy O corresponds to the policy of picking and placing a dumbbell, whereas Policy 1 corresponds the policy moving box into the trashcan. Mean return and success rate over seeds of Maxlteration compared to fine-tuning IQL on selected tasks. Error-bars correspond standard error. Full bars correspond returns and red lines indicate the success rate of each algorithm. Maxlteration can yield improvements in return but increased return does not always yield success.
eventually surpass the performance of Maxiteration Maxiteration is limited to competing with the max-following benchmark which can be suboptimal.
Conclusion
We introduce Maxiteration, algorithm to efficiently learn policy that is competitive with the approximate max-following benchmark (and hence also with all constituent policies). We provide empirical evidence that max-following utilizing skill-learning enables learn how complete tasks that it would be inefficient to learn from scratch, but that are superior to other individually trained experts for fixed given skills.
Limitations and Future Work Our goal in this work has been to learn policy that competes with an approximate max-following policy under minimal assumptions. However, we still assume efficient batch learnability of constituent value functions, which will not always be feasible in practice. While seems likely that our oracle assumption necessary for learning an approximate hol-follo policy, we leave proving this claim for future work. We also leave consideration of alternative ensembling approaches to future work. Max-value ensembling sensitive slight differences in the values between constituent policies whereas, e.g., softmax takes into account the relative 'weighting' of values. In addition, would be interesting characterize the amount improvement we can obtain over our constituent policies or prove conditions under which our approximate max-following policy competitive with true max-following policy the optimal policy. One could also extend this analysis ensembling methods like softmax and study the nature of guarantees in that setting. Extending beyond MDPs to the partially observable setting, and to the discounted infinite-horizon setting, would also add richness the class of problems could consider.
10

---

Acknowledgments and Disclosure of Funding
The authors are partially supported by ARO grant W91 INF2010080, DARPA grant 1238001 the Simons Foundation Collaboration on Algorithmic Fairness, and NSF grants FAI-2147212 and CCF-2217062.
References
Lucas Alegre, Ana Bazzan, Ann Nowé, and Bruno C da Silva. Multi-step generalized policy improvement by leveraging approximate models. Advances in Neural Information Processing Systems, 36, 2024.
Ron Amit, Ron Meir, and Kamil Ciosek. Discount factor as a regularizer reinforcement learning. In Hal Daumé III and Aarti Singh, editors, Proceedings of the 37th International Conference on Machine Learning, volume 119 of Proceedings of Machine Learning Research, pages 269-278.
PMLR, 13-18 Jul 2020.
Andre Barreto, Will Dabney, Remi Munos. Jonathan J Hunt, Tom Schaul, Hado P van Hasselt, and David Silver. Successor features for transfer in reinforcement learning. I. Guyon, U. Von Luxburg. S. Bengio, H. Wallach, R. Fergus, S. Vishwanathan, and R. Garnett, editors, Advances in Neural Information Processing Systems, volume 30, 2017.
André Barreto, Shaobo Hou, Diana Borsa, David Silver, and Doina Precup. Fast reinforcement learning with generalized policy updates. Proceedings of the National Academy of Sciences, 117 (48):30079-30087,, 2020. doi: 10.
Dimitri Bertsekas. Dynamic programming and optimal control: Volume 1, volume 4. Athena scientific, 2012.
Ronen Brafman and Moshe Tennenholtz. R-max-a general polynomial time algorithm for near- optimal reinforcement learning. Journal of Machine Learning Research, 3(0ct):213-231 2002.
Nataly Brukhim, Elad Hazan, and Karan Singh. A boosting approach to reinforcement learning. Advances in Neural Information Processing Systems, 35:33806-33817, 2022.
Kai-Wei Chang, Akshay Krishnamurthy, Alekh Agarwal, Hal Daumé III, and John Langford. Learning to search better than your teacher. In International Conference Machine Learning, pages 2058- 2066. PMLR, 2015.
Xinyue Chen, Che Wang, Zijian Zhou, and Keith W. Ross. Randomized ensembled double q-learning: Learning fast without a model. In International Conference on Learning Representations, 2021.
Ching-An An Cheng, Andrey Kolobov, and Alekh Agarwal. Policy improvement via imitation of multiple oracles. Advances in Neural Information Processing Systems. 33:5587-5598, 2020.
Omar Darwiche Domingues, Pierre Ménard, Emilie Kaufmann, and Michal Valko. Episodic rein- forcement learning in finite mdps: Minimax lower bounds revisited. In Algorithmic Learning Theory, pages 578-598. PMLR, 2021.
Simon S Du, Sham M Kakade, Ruosong Wang, and Lin F Yang. Is good representation sufficient for sample efficient reinforcement learning? arXiv preprint arXiv:1910.03011 2019.
Yoav Freund and Robert E. Schapire A decision-theoreed generalization on-line learning and an application to boosting. Journal of computer and system sciences,
1997.
Xavier Glorot, Antoine Bordes, and Yoshua Bengio. Deep sparse rectifier neural networks. In Geoffrey Gordon, David Dunson, and Miroslav Dudík, editors, Proceedings of the Fourteenth International Conference on Artificial Intelligence and Statistics. volume 15 of Proceedings of Machine Learning Research, pages 315-323, Fort Lauderdale, FL,, USA, 11-13 Apr 2011. 1. PMLR.
Noah Golowich, Ankur Moitra, and Dhruv Rohatgi. Exploration is harder than prediction: Cryptographically separating reinforcement learning from supervised learning. arXiv preprint arXiv:2404.03774, 2024.

---

Tuomas Haarnoja, Aurick Zhou, Pieter Abbeel, and Sergey Levine. Soft actor-critic Off-policy maximum entropy deep reinforcement learning with a stochastic actor. In Jennifer Dy and Andreas Krause, editors, Proceedings of the 35th International Conference on Machine Learning. volume 80 of Proceedings of Machine Learning Research, pages 1861-1870. PMLR, 10-15 Jul 2018.
Takuya Hiraoka, Takahisa Imagawa, Taisei Hashimoto, Takashi Onishi, and Yoshimasa Tsuruoka. Dropout q-functions for doubly efficient reinforcement learning. International Conference on Learning Representations, 2022.
Marcel Hussing, Jorge A. Mendez, Anisha Singrodia, Cassandra Kent, and Eric Faton. Robotic manipulation datasets for offline compositional reinforcement learning. In Reinforcement Learning Conference, 2024.
Thomas Jaksch, Ronald Ortner, and Peter Auer. Near-optimal regret bounds for reinforcement learning. Journal of Machine Learning Research, 11(51):1563-1600, 2010.
Daniel Kane, Sihan Liu, Shachar Lovett, and Gaurav Mahajan. Computationallstatiitti gap in reinforcement learning. In Conference on Learning Theory, pages 1282-1302. PMLR, 2022.
Michael Kearns and Satinder Singh. Near-optimal reinforcement learning in polynomial time.
Machine learning, 49:209-232, 2002.
Ilya Kostrikov, Ashvin Nair, and Sergey Levine. Offline reinforcement learning with implicit q-learning. In International Conference on Learning Representations, 2022. URL https://
Andrey Kurenkov, Ajay Mandlekar, Roberto Martin-Martin, Silvio Savarese, and Animesh Garg. Ac-teach: A bayesian actor-critic method for policy learning with an ensemble of suboptimal teachers. arXiv preprint
2019.
Tor Lattimore and Marcus Hutter. Pac bounds for discounted mdps. In Algorithmic Learning Theory, pages 320-334, Berlin, Heidelberg, 2012. Springer Berlin Heidelberg. ISBN 978-3-642-34106-9
Kimin Lee, Michael Laskin, Aravind Srinivas, and Pieter Abbeel. Sunrise: A simple unified framework for ensemble learning in deep reinforcement learning. In International Conference on Machine Learning. PMLR, 2021.
Guohao Li, Matthias Mueller, Vincent Casser, Neil Smith, Dominik L Michels, and Bernard Ghanem. Oil: Observational imitation learning. arXiv preprint arXiv: 080 2018
Xuefeng Liu, Takuma Yoneda, Chaoqi Wang, Matthew Walter, and Yuxin Chen. Active policy improvement from multiple black-box oracles. International Conference on Machine Learning, PMLR, 2023.
pages
Xuefeng Liu, Takuma Yoneda, Rick Stevens, Matthew Walter, and Yuxin Chen. Blending imitation and reinforcement learning for robust policy improvement. In The Twelfth International Conference on Learning Representations, 2024. URL URL /tttpss//openreveeee
net/forummid -idemmddddddddeeeeeeeeee JJOzzPJq1F
Jorge A. Mendez, Marcel Hussing, Meghna Gummadi, and Eric Eaton. Composuite: A compositional reinforcement learning benchmark. 1st Conference on Lifelong Learning Agents, 2022.
Oren Peer. Chen Tessler, Nadav Merlis, and Ron Meir. Ensemble bootstrapping for gelearning In Marina Meila and Tong Zhang, editors, Proceedings of the 38th International Conference on Machine Learning, volume 139 of Proceedings of Machine Learning Research, pages 8454-8463. PMLR, 18-24 Jul 2021.
Martin L. Puterman. Markov Decision Processes: Discrete Stochastic Dynamic Programming. John Wiley & Sons, Inc., USA, 1st edition, 1994. ISBN 0471619779.
John Schulman, Philipp Moritz, Sergey Levine, Michael Jordan, and Pieter Abbeel. High-dimensional continuous control using generalized advantage estimation. arXiv preprint arXiv: 024.02438 2015.
12

---

John Schulman, Filip Wolski, Prafulla Dhariwal, Alec Radford, and Oleg Klimov. Proximal policy optimization algorithms. CoRR, abs/1707.06347, 2017. URL http::///aaxii..//g///////////// baagg/bbs/100/ 06347
Ayush Sekhari, Karthik Sridharan, Wen Sun, and Runzhe Wu. Contextual bandits and imitation learning with preference- active queries. Advances in Neural Information Processing Systems, 36, 2024.
Takuma Seno and Michita Imai. d3rlpy: An offline deep reinforcement learning library. Journal of Machine Learning Research, 23(315):1-20, 2022. URL http://jmlr.orr org. wwt.h//rrrpppppee////eaoaaas v 22-0017 html
Yanjie Song, Ponnuthurai Nagaratnam Suganthan, Witold Pedrycz, Junwei Ou, Yongming He, Yingwu Chen, and Yutong Wu. Ensemble reinforcement learning: A survey. Applied Soft Computing, page 110975, 2023.
Wen Sun, Arun Venkatraman, Geoffrey Gordon, Byron Boots, and J Andrew Bagnell. Deeply aggrevated: Differentiable imitation learning for sequential prediction. In International conference on machine learning, pages 3309-3318. PMLR, 2017.
Richard Sutton and Andrew G Barto. Reinforcement learning: An introduction. MIT press, 2018.
Saran Tunyasuvunakool, Alistair Muldal, Yotam Doron, Siqi Liu, Steven Bohez, Josh Merel, Tom Erez, Timothy Lillicrap, Nicolas Heess, and Yuval Tassa. dm_control: Software and tasks for continuous control. Software Impacts, 6: 6:100022, 2020. ISSN 2665-9638. doi: https://doi.org/10.
N016fj.simpa.2220.100
Cathy Wu, Aravind Rajeswaran, Yan Duan, Vikash Kumar, Alexandre M Bayen, Sham Kakade, Igor Mordatch, and Pieter Abbeel. Variance reduction for policy gradient with action-dependent factorized baselines. arXiv preprint arXiv: /e.../00300755 2018
Mohammadi Zaki, Avi Mohan, Aditya Gopalan, and Shie Mannor. Actor-critic based improper reinforcement learning. In International Conference on Machine Learning, pages PMLR, 2022.
13

---

Somewhat more formally, recalling the definition the set of approximate max-following policies II (Definition 2.3). at every time h E [H] and state s E S. policy æ II takes action (s(ss) A MDP Examples
A.1 LQR max-following parametric class vs. constituent policies
min (1
Σ
(a Qu, + u Ru,))
t=
t=0
subject to 21+1 Ar + Bu, + We,
To motivate the use of max- max-following policies in richer class of MDPs, we consider traditional control problem with continuous state and action spaces: the discrete linear quadratic regulator. Note that here analyze the infinite horizon discounted value function, but episodic analogues exist. Consider the following setting where 7 E [0. is discount factor, and W, ~ (N o T). Here, consider the simple
that
analyze the time-invariant
where Q. R. A 7 and B = (1 - e)d. We know that the optimal policy is of the form = ~K* [Bertsekas] 2012] and we set two policies that only stable along one component and unstable along the other of the form 2 = - K₁ and U2 K2 It is important to note that the value functions of the individual policies and the optimal policies have exact quadratic forns like V(x) = xx' Px + q. but the max- following policy is not necessarily within the same parametric class. For example, Pi is the solution the Lyapunov equation P1 (I + KJ K1 + (AA P1 (A K1)) and q1 I- similar formula exists for policy 2.
2 o² tr(P)).
In LQR, for the Ki, K2 controllers described above, a max-following policy is able to attain higher value than the individual expert policies that have unstable direction in one axis. Moreover, see that the optimal policy is obviously superior to all the other policies, but that max-following competitive with it than the other individual expert policies. A max-following policy
policy is is ultimately able to benefit from the stabilizing component of each axis of the individual policies, which ultimately lets it perform better than any given individual one.
B Additional Proofs
Lemma 4.1 (Worst approximate max-following policy competes with best fixed policy). For any E (0, 1] and any episode length H. let 3 E ) Then for any MDP M with starting state distribution po, and any K policies IT defined M,
min EEn
E BEMAo
[V*(s
2 max E
[V*(su)] - O(E).
K Sorpto
Proof. We will prove the claim inductively, showing that for all C E [H], if run any approximate max-following policy for C' steps, and then continue following the policy x/th chosen at step C' for the rest of the episode, then our expected return is not much worse than we had followed any fixed zk for the whole episode.
for a x² E 4 such that (s) 2 maxxe(k) (s) 3. Letting (*,A)) denote the x' E II that π follows at state and time h, we will show that if at some step C' E [H] we have
H-1
R(sh.
Σ
R(sh,
(sa.CC (sw.)) a
(s:))
max E [V*(s)) -O( -0(5(C+1)
Som=ooo P
kE[K] sq
A=C41
for all π E n then the same holds for C' + 1 for all n.
In the base case, C 0, the claim
E
R(sh. T (sw)))
2 max
E [s*]s -0(
P
kE(K) [K] spraro
A=U
14

---

for all π E ny and all Th E II,, follows straightforwardly from the definition of H and setting of B E ) since
H
R(sh, 1(50.00 (sn))
/ (so)]
E Bg ppp
Th
=
E 80m110
max (s0) -( kE[K]
E 9ompo
[V*)] - -(()).
kE K
We now prove the inductive step. We wish to show that if at step C, we have for some π E 11
H-1
Σ A=
R(sh ((ec.C) (lc.))(ss))
[v* - ((=()))) BumPp
E So
+
max E kE[K]
H
then continuing to follow at step C + 1 and following x (+0411,,++) thereafter reduces expected return by 0 ( Now if TC+1(50+1) (f+11(5++)) for T' E II, it must the case that
Ve+1($c+1) 2 max V (5+1() -(()) kE[K]
otherwise HI'.. It follows that
C+1
E
R(sh, (s()))
Σ
R(sh. Th
H0c+1 (oo+n.Ct))ss)
PP..
P
h=
h=C+2
E
R(sh, (sn)) +
6+1
y((o0+1,+1) (8c+1)
(by definition V and (++4())4)))
Po
(s(h)) + max
Va (5p4)) -
S P
kE[K]
E
R(sh, (sb) +
((s (8c+1) -
C+1
P P
#-1 Σ
(100.0) (sn))
E P
R(sh, TA (sn)) +
R(sh, Tb
(by definition V)
--=0
h=C+1
h
max
E Pam//o
[v*(s)]
- -(( (CC+))
inductive hypotieesis)
and the claim holds for time C for any 11 for which it holds for time C. We showed
the base case C = 0 hold for all E Tl and therefore we have
C
H-1
IE
Σ
R(sh, (sn)) +
Σ R(sh,
Th
Kec.C) (sn))
2 max IE k
[V} O (((++))
P
500110
h==
A=C+1
for all C [H]. In particular, for C H we conclude that
E som-a..P
Σ h=
R(sn, Tn ((W))
max -s)
KE[K sprupo
and it follows that
min rell
[sa)
max ke [] Spreto
[V*(s)) O(e).
15

---

C Additional information about experiments
heuristic version of Maxiteration that operates in rounds. First, the algorithm collects a set of trajectories using every policy to initialize the respective value functions. Then, in every round the algorithm for every policy exectues the max-following policy for , steps and the switches to the respective constituent policy. At the end of each round, value functions of constituent policies are updated. 3 is uniformly spaced along the full horizon and thus, depends on the number of rounds and the horizon. The total number of episodes is an upper bound on the number of samples collected which is what we determine compare run-times between Maxiteration and IQL. Finally, we use a 7 discounting which has been shown to have regularizing effects on the value function updates [Amit al. 2020
For our experiments,
For IQL., we use the d3rlpy implementations [Seno and Imai 2022 and code provided by Hussing al. 2024
C.1 Hyperparameters
Both algorithms to pre-fill the buffer for IQL) before doing updates and then for 50, 000 steps for online training.
for 10, 000 steps initially (to initialize value functions for Maxlteration and
All neural networks use ReLU [Glorot et al. 2011 Multi-layer perceptrons with 2 layers and hidden dimension of 256 per layer.
Table 1: Hyperparameters for Maxlteration
Optimizer
Adam
Adam B1
0.9
Adam B2
0.999
Adam
Te
Value Function Learning Rate
1e 4
Number of rounds
50
Number of gradient steps per
40,000
round
Batch Size
64
7
0.99
Table 2: Hyperparameters for Implicit Q-Learning
Optimizer
Adam
Adam 31
0.9
Adam B2
0.999
Adam
le
Actor Learning Rate
4e 3
Critic Learning Rate
4e
Batch Size
#Tasks x25
n_steps
7
0.99
T
0.005
n critics
2
expectile
0.7
weight_temp
3.0
max_ mex_weeigtt
100
16

---

C.2 Full results on CompoSuite
Policy 0
Policy
IQL
Maxiteration
Hollowbox, troooxx Trashca
Hollowbox, Plate, Push
Plate, Trashcan
Plate, Trashcan
Plate, Push
Box, Shelf
Box, Shelf
Hollowbox, Push
Plate, Trashcan
Plate, Shelf
Box, Trashcan
400
1.0
Success Rate
Returns
200
0.5
0
0.0
Dumbbell, Shelf
Dumbbell, Shelf Hollowbox, Push
Box, PickPlace Dumbbell, Push
Box, PickPlace Dumbbell, Push
Hollowbox, Push
Dumbbell, Push
Hollowbox, Shelf
Box, Push
Dumbbell, PickPlace
400
1.0
Success Rate
Returns
200
0.5
0
0.0
Box, Push Plate. Shelf Hollowbox, PickPlac tollowbox, PickPlac Dumbbell, Trashcal Dumbbell, Trashcan
Box, Push
Plate, Shelf
Box, PickPlace
Hollowbox, Push
Plate, Trashcan
Dumbbell, Shelf
400
1.0
Success Rate
Returns
200
0.5
0
0.0
Dumbbell, BockPlaccJumbble PickPlaci
Hollowbox, Shelf Plate, PickPlace
Hollowbox, Shelf Plate, PickPlace
Box, Trashcan
Box, Trashcan
Dumbbell, Trashca
Box, PickPlace
Hollowbox, PickPlac
Plate, Shelf
400
1.0
Success Rate
Returns
200
0.5
0
0.0
Figure 4
17

---

C.3 Results on DM Control
We rum our MaxIteration algorithm on the DM Control benchmarks (Tunyasuvunakool al. 2020 similar to the MAPS (Liu et al. [023] setup. In their setup, the constituent policies correspond to different checkpointed models in one run of the online Soft-Actor critic (Haarnoja et al. 2018) algorithm. As result, it is generally true that the latest checkpointed model will outperform the previous two checkpoints meaning one constituent policy strictly better everywhere than the others. We report the final performance over 5 seeds using 16 evaluation trajectories in Figure 5 The results show that our algorithm behaves as expected and always uses the best oracle. Without policy improvement operator, this setup does not allow us exceed the performance of the constituent policies.
Policy
Policy
Policy 2
Maxiteration
Cheetah-run
Walker-wlkk
500
400
300
200
100
Figure 5: Mean return over 5 seeds of Maxlteration on DM Control tasks (Tunyasuvunakool et al. 2020). Error-bars correspond standard error. MaxIteration always selects the best performing constituent policy.
C.4
Computational Resources
Our experiments were conducted using a total 17 GPUs inclusing both server-grade (e.g., NVIDIA RTX A6000s) and consumer- grade (e.g., NVIDIA RTX 3090) GPUs. Training the constituent policies from offline data takes less than 2 hours. Our MaxIteration algorithm takes about 3 hours to train while the baseline fine-tuning takes around hour. large chunk of the runtime cost stems from executing the simulator.
18

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: Our abstract and the results I.1 Summary sections provide an overview of theoretical and experimental results. We then proceed to explain the setup in preliminaries 2 and provide our main theoretical results 3 immediately after. We also provide our experimental results at the end of the paper.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made the paper and important assumptions and limitations. A No or
NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize other settings.
is fine to include aspirational goals as motivation as long as is clear that these goals not attained by the paper.
2. Limitations
Question:
Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification: We discuss limitations and possibilities for future work/open questions as paragraph section(s) of the conclusion 6
Guidelines:
The answer NA means that the paper has limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create separate "Limitations" section in their paper.
The paper should point any strong assumptions and how robust the results are to violations of these assumptions (e.g.. independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution is low or images are taken in low lighting. Or speech-to-text system might not be used reliably provide closed captions for online lectures because it fails handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairesss.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't acknowledged
the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory Assumptions and Proofs
19

---

Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
Justification: We provide extensive discussion of our setting and preliminaries and cor- responding proofs of theorems Ba about the nature of our assumptions about the oracle and literature.
definitions and also about how they compare with corresponding theoretical works in the
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced in the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but they appear in the supplemental material, the authors are encouraged to provide short proof sketch provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental Result Reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that it affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Answer: [Yes]
Justification: We strongly follow the algorithmic description in [ and any variations for the practical implementation are discussed in Appendix C We report all used hyperparameters
in Appendix C.T
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution is a specific model and empirical evaluation, it may be necessary to either make possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how replicate the results, access to a hosted model (e.g., in the case of a large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) the contribution is primarily a new algorithm, the paper should make clear how reproduce that algorithm. (b) If the contribution is primarily the architecture clearly and fully.
model architecture, the paper should describe
(c) the contribution a new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset instructions for how to construct the dataset).
20

---

(d)
We recognize that reproducibility may be tricky in some cases, in which case authors are welcome describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should be possible for other researchers to have some path to reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [Yes]
Justification: An implementation of our code is appended in the supplemental material. The datasets we used are available in an open access repository at /bbtops://datadryaa org/
stash/Catasse//oli 50615/0rdy .cnp5hqps
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please the NeurlPS code and data submission guidelines (https://nips.ce cc/
Soblic//gides/Conn /osddiicguuudss//uuuusssssiiiiii
for more details.
While we encourage the release of code and data, we understand that this might not be possible, so "No" an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (c.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (https
ptaiss.cc/uublicguuidees http:///guuieeee/oeuuuubiiiiiiia
ssw.iioiccoyyoccooooooooo for more details.
The authors should provide instructions on data access and preparation, including how access the raw data, preprocessed data, intermediate data, and generated data,
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible supplemental material (appended the paper) is recommended, but including URLs to data and code is permitted.
6. Experimental Setting/eetails
Question: Does the paper specify all the training and test details (c.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification: Section 5 and Appendix specify all of the details about the setting and hyperparameters and relevant other algorithms.
Guidelines:
The answer NA means that the paper does include experiments.
The experimental setting should be presented in the core paper to a level detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, supplemental material.
7. Experiment Statistical Significance
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer:
[Yes]
Justification:
We report mean and standard error which we deem sufficient for the claims we are making.
21

---

Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, or statistical significance tests, least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g.. Normally distributed errors).
It should be clear whether the error bar is the standard deviation or the standard error of the mean.
is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CL, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that out of range (e.g. negative error rates).
If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed reproduce the experiments?
Question:
Answer: [Yes]
Justification: We report the computational resources available and the runtimes experi- ments in Appendix C.4
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well as estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported didn't 'tttt make it into the paper).
paper (e.g., preliminary or failed experiments that
9. Code Of Ethics
Question: Does the research conducted the paper conform, in every respect, with the NeurlPS Code of Ethics httppe///horrpp..cc///alll//eees
Answer: [Yes]
Justification: Since this is a primarily theoretical work in nature we do not violate the concerns listed in the Code of Ethics.
Guidelines:
The answer NA means that the authors have not reviewed the NeurlPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., there special consid- eration due to laws or regulations in their jurisdiction).
10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative socictal impacts of the work performed?
22

---

Answer: [NA]
Justification: As this is a theoretical paper in nature, the societal impacts of this paper are somewhat limited in scope.
Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact or why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g.. disinformation, generating fake profiles, surveillance), fairesss considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and tied to particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification: As this is mainly theoretical work in nature, it is not quite applicable to this work.
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors
should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Are the creators or original owners of assets (c.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [Yes]
Justification: Open-source code and environments all listed in the section and relevant authors are cited when comparing to their benchmarks. The code provided was written by the authors.
Guidelines:
23

---

The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package dataset.
The authors should state which version of the asset is used and, if possible, include URL.
The name of the license (e.g.. CC-BY 4.0) should be included for each asset. For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswi thcode com/ datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that re-packaged, both the original license and the license of the derived asset (if it has changed) should provided.
If this information is not available online, the authors are encouraged to reach out to the asset's creators.
13. New Assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification:
We do not provide any new assets.
Guidelines:
The answer NA means that the paper does release assets.
Researchers should communicate the details the dataset/code/mooel as part their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset is used.
At submission time, remember anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsourcing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification:
We do not do any research with human subjects or crowdsourcing.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then much detail as possible should be included in the main paper.
According to the NeurlPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: We do not do any research with human subjects or crowdsourcing.

---

Guidelines:
The answer NA means that the paper does not involve crowdsoureing nor research with
human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent)
may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and expect authors to adhere to the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such the institution conducting the review.
25


Reviews:
[{"review_id": "U8yDzFx8gn", "reviewer": "Reviewer_BR1J", "summary": "The paper presents an algorithm called MaxIteration for addressing the challenges of RL in large or infinite state spaces. The core idea is to compete with a max-following policy, which at each state selects the action of the constituent policy with the highest value. The MaxIteration algorithm is efficient, requiring only access to an empirical risk minimization (ERM) oracle for value function approximation of the constituent policies, without needing the value functions themselves.", "questions": "1. Are there any specific cases where the algorithm's performance might degrade?\n2. How does the algorithm deal with non-stationary environments or changing dynamics?", "limitations": "Please see the above comments.", "rating": 5, "confidence": 2, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "1. The algorithm is computationally efficient, scaling well with large state spaces.\n2. The paper provides a solid theoretical foundation with proofs of the algorithm's effectiveness.\n3. It improves upon existing policies without needing to explore the entire state space.\n4. The algorithm's performance is validated by experiments on robotic simulation tasks.", "weaknesses": "1. The algorithm assumes access to an ERM oracle, which might not be practical in all scenarios.\n2. While its efficiency in simulation tasks, the algorithm might be complex to implement in real-world systems.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Dear Reviewer BR1J, thank you for your feedback on our work and highlighting the value of our theoretically motivated empirical algorithm.\n\n**Weaknesses**\n   > The algorithm assumes access to an ERM oracle, which might not be practical in all scenarios.\n\nMany machine learning problems are known to be computationally hard in the worst case, but Empirical Risk Minimization (ERM) has still proven to be a useful framework in practice. For instance, the machine learning community has made great strides in solving supervised learning problems using neural networks over the past 10 years.\nOur oracle assumption can be thought of as providing us the guarantee that we can learn an approximate value function well in such a batch-ERM setting. That means, we are reducing the problem of learning an approximate max-following policy to a simpler supervised learning problem over a given distribution. In other words, our goal with this work is to provide guarantees under the assumption that in practice ERM is easy and neural networks do what neural networks do.\n\n > While its efficiency in simulation tasks, the algorithm might be complex to implement in real-world systems.\n\nWe agree that one of the main challenges of implementing RL algorithms on real-world systems is the required sample complexity. However, we would like to highlight that our work is an attempt at reducing the required number of samples to obtain good policies. Our experimental results use only around $80$ trajectories while common on-policy RL algorithms require several thousand [Mendez et al. 2022].\n\n**Questions**\n   >  Are there any specific cases where the algorithm's performance might degrade?\n\nWe provably cannot do worse than the constituent policies with our approach which gives us a baseline for our algorithm's worst-case performance. Intuitively, we can think of it this way: if it is worse to switch between policies, we can always resort to using only a single constituent policy. Exactly for this reason, as we experimentally show, there are cases where MaxIteration also cannot do drastically better and ultimately performs similarly to one of the base constituent policies themselves. This is also the case in Figure $1b$.\n\n   >  How does the algorithm deal with non-stationary environments or changing dynamics?\n    \nThis is a very intriguing question and we thank the reviewer for bringing it up. Seeing what happens when the performance of a constituent policy changes due to changes in the environment is a very interesting idea. In general, we believe that it is possible to obtain efficient routines for such settings. However, this would require redefining the setting as well as some of the other definitions (and likely changing the algorithm). For the current manuscript we believe that this question is out of scope but it is an excellent direction for future work we would like to pursue.", "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": "", "extra_scores": {}}, {"review_id": "2LSLy4gxT0", "reviewer": "Reviewer_Z6cc", "summary": "This paper presents an approach to enabling Reinforcement Learning (RL) by improving the process of generating an optimal policy. Their method assumes that there is access to a particular class of Markov Decision Process (MDP). The intuition is having a collection of bases determined as constituent policies. Under some theoretically supported assumptions, the policy learning process they propose guarantees consistently obtaining a policy that is at least as good as the best constituent policy and potentially better. The method relies on an algorithm that generates policies from the max-following class. The authors tested their framework with a practical version of such an algorithm (MaxIteration) in 16 robotic tasks. An essential aspect of their method is that it relies on heuristics to create the collection of constituent policies.", "questions": "- What are Policy 0 and Policy 1 in Figure 1?\n- How do you explain the tasks where all the methodologies had a very low success rate?", "limitations": "The authors addressed their method's main limitation: the need for an oracle for the methodology to hold. They claimed that they will address this concern in the future.", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "This paper presents a structured theory consolidated over the definition of a policy function class called max-following. The authors provided a practical algorithm that can generate policies belonging to that class. They proved their proficiency through robotic tasks, compared to an offline RL method called Implicit Q-Learning (IQL).", "weaknesses": "This class falls under a set of observations provided by the authors that are necessary for the theory to hold. Also, the bases of constituent policies rely on heuristics. That could restrict the potential application of their training method. \n\nI couldn't find the explanation of Policy 0 and Policy 1 in Figure 3. This figure could be more apparent, as understanding your baselines is essential.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Dear Reviewer Z$6$cc, thank you so much for your feedback on our paper and for highlighting the practical nature of our theoretically-grounded algorithm. \n\n**Weaknesses**\n> We are unsure what \"this class falls under a set of observations provided by the authors that are necessary for the theory to hold” means. Would you be willing to clarify a bit more?\n\nOne interpretation of this statement may be that our observations from section $4$ are necessary for our theory to hold. This would be incorrect as we simply provide the observations to clarify the properties of our max-following and approximate max-following approach. These are \\textit{not} assumptions needed in order for our algorithm and theoretical results to hold, and are rather meant for our reader to gain intuition into some of the definitions we provided. The main assumption our paper makes is access to an ERM oracle. \n\n> It is also unclear to us what it means that the bases of our constituent policies rely on heuristics. We would appreciate clarification on this point as well.\n\nThe constituent policies are not chosen based on heuristics, and are rather chosen based upon access to some pre-existing class of policies. We do not make assumptions about the properties of these policies, beyond the assumption that a regression oracle is able to give us reasonable approximations to their value functions. We hope that in many realistic settings there are policies that are pre-trained such that they are skilled in one domain but not necessarily trained to be good at other tasks. Thus, we can compose them well, but skill-specific pre-training is not necessary for our theoretical results to hold.\n\n  >  I couldn't find the explanation of Policy 0 and Policy 1 in Figure 3. This figure could be more apparent, as understanding your baselines is essential.\n\nWe appreciate this pointer. For the camera ready version, we will update the caption of the Figure to include a description of the policies.\nPolicies $0$ and $1$ correspond to the pre-trained policies using IQL on the intial tasks above the arrow in each graph. That is, in the left most subfigure of Figure $3$, Policy $0$ corresponds to the policy of picking and placing a dumbbell, whereas Policy $1$ corresponds to the policy of moving a box into the trashcan. The MaxIteration algorithm enables the robot move a dumbbell into the trashcan without needing the robot to train separately on that task by reusing the earlier existing policies.\n\n**Questions**\n  \n> What are Policy 0 and Policy 1 in Figure 1?\n\nIn our figure $1a$, the policies correspond to moving left or right and in $1b$ correspond to moving right, left, or up. If the review is referring to Figure $3$, we refer to the previous response.\n\n> How do you explain the tasks where all the methodologies had a very low success rate?\n\nNote that in the experimental setting, the initial policies (i.e. policies 0 and 1) are pre-trained to solve tasks distinct from the task that we test them on. Thus, we expect the pre-trained policies to be bad at the test task. Our algorithm only guarantees that we are at least as good as the best individual policy. In some cases, we see that combining policies is not sufficient to achieve success. That is because the tasks we chose are robotics tasks with highly complex dynamics and the dynamics of moving a plate versus a dumbbell using a robotic arm differ quite a bit. In such cases, simply switching between the two policies is insufficient to solve the task. However, this opens up interesting directions for future work such as including minor policy update steps to the learning process without requiring state-space dependence.", "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": "", "extra_scores": {}}, {"review_id": "Cv2LYZBK6Y", "reviewer": "Reviewer_Qu2b", "summary": "The paper considers the setting in which several good policies are available for some Markov Decision Process, and the agent has to learn how to combine them in a way that allows to achieve higher performance than following a single of the constituent policies. This problem is quite wide and a large number of methods exist to combine policies, with varying assumptions and properties. This paper proposes a method that can realistically be implemented, by considering that per-policy value functions can be learned for an ever-increasing horizon $h$, and then the action to execute in the environment is the one executed by the policy that has the largest value in the current state and current horizon.\n\nThe novel aspect of the contribution seems to be the reliance on $h$ and the iterative nature of the algorithm. In MDPs with a finite time horizon, we have a finite amount of $h$ values, so a finite amount of value functions to learn. Combined with the fixed amount of constituent policies, this leads to an algorithm whose complexity scales well even to very large state-spaces, because the size of the state space does not intervene in the compute requirements of the algorithm.\n\nThe proposed method is discussed from a theoretical perspective, and promising empirical results are provided. The experiments consider complicated robotic tasks, with an interesting setting and motivation for this work: the constituent policies are almost-optimal policies for various tasks, and the new policy to learn from a combination of the existing ones is learned against a new task. So, this work seems to be applicable to multi-task RL.", "questions": "Given the average-low clarity of the paper, I may have mis-understood several parts of the contribution. I expect the authors to disagree with some of the remarks written above. I would welcome to be corrected, and for the authors to take the opportunity to improve the paper given the possible ways it can be mis-understood.", "limitations": "The paper does not seem to have potential negative societal issues, and its scientific limitations are well-discussed.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "The proposed method seems sound, easily to implement (provided that the paper is made clearer) and to lead to impressive empirical results. The assumptions and limitations of the approach are well-discussed, which helps deciding whether it would apply well on some specific problem.", "weaknesses": "While the contribution seems of high quality, the paper lacks clarity and intuition, which may make it difficult to reproduce.\n\n- Examples of oracles for the value functions should be given, to better indicate to people whether the oracle can be a value function learned on another task, or obtained from rollouts, or requires a simulator. The oracle is an important part of the algorithm, as it is queried $K$ times per horizon step and its output is directly used to perform an argmax operation (the result of the oracle does not seem to be distilled to some learned function)\n- The paper should be a bit more explicit about how to produce the $\\mu_h$ distributions and the fact that this requires resetting the environment and performing actions in it. Not every environment is resettable at will by the agent, and executing all these actions requires an online setting.\n- The core of the paper is the use of approximate max-following policies, defined in Definition 2.3. The definition is very dry and the reader has to carefully look at the notations to understand where everything comes from. For such an important definition, an intuition and maybe an example would have been very useful. Later in the paper (Figure 2), examples of environments and corresponding max-following policies are used in some argument, but without explaining what a max-following policy is. Thus, the definition is very dry, yet at the core of important arguments in the paper.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Dear Reviewer Qu$2$b, thank you so much for highlighting the scaling dependence of our algorithm/its ability to work in large state spaces well and for relating it to our empirical results and the broader multi-task RL area. \n\n**Weaknesses**\n> Examples of oracles for the value functions should be given\n    \nIn practice, the oracle can be implemented using an arbitrary function approximator such as a neural network. The input distribution of the oracle is approximated by rolling out the max-following policy to some time step $h$ and then rolling out a constituent policy up to the horizon of the environment. This can happen either in a simulator or on a real-world system. The collected data is then used to fit the neural network. The learned neural network is the output of the oracle. See Appendix C for additional detail on the procedure. For additional formal clarification of the oracle, see response to weakness $2$.\n\n>The paper should be a bit more explicit about how to produce the \n distributions and the fact that this requires resetting the environment and performing actions in it.\n \nWe thank the reviewer for pointing out the lack of clarity in how the $\\mu_h$ distributions are defined and sampled. We provide some explanation below, and will add clarification to the paper as well. \n\n- We first want to highlight that sampling from $\\mu_h$ does not require that the agent can reset the environment at will. We only require what is typically required in the episodic setting -- that the agent explores for an episode of $H$ steps, where $H$ is finite and fixed across all of training. After these $H$ steps, the agent is then reset to a state sampled from the distribution over starting states.  \n- The distributions $\\mu_h$ are (informally) defined as follows: at iteration $h \\in [H]$ of our algorithm, the agent has already learned a good approximate max-following policy for the first $h$ steps of the episode. The distribution $\\mu_h$ is the distribution over states visited by the agent at step $h$ if it begins from a state drawn from the starting state distribution and then follows the approximate max-following policy it has learned thus far for $h$ steps.\n- That means to sample from $\\mu_h$, the oracle can simply run the approximate max-following policy for $h$ steps to arrive at a state $s_h$, which is a sample from $\\mu_h$. It can then do whatever it likes for the remainder of the episode, and so does not need to reset at arbitrary time steps.\n- In practice, since the oracle needs to produce a good approximation of the value function $V_h^k$ at time $h$ for policy $\\pi^k$ on states sampled from $\\mu_h$, we should think of it as using the remainder of the episode to obtain an unbiased estimate of the expectation of $V_h^k$ on the distribution $\\mu_h$. That is, once it has sampled a state $s_h$ by running the approximate max-following policy for $h$ steps, it just executes policy $\\pi^k$ for the remainder of the episode. The accumulated reward obtained by following policy $\\pi^k$ from state $s_h$ for steps $h$ through $H$ gives the oracle an unbiased estimate of $\\mathbb{E}_{s_h \\sim \\mu_h}[V^k_h(s_h)]$. To implement our oracle assumption, we could use many such unbiased estimates as training data to train a neural network, to learn a good approximate value function for $\\pi^k$ at time $h$ on distribution $\\mu_h$.\n\n>The core of the paper is the use of approximate max-following policies, defined in Definition 2.3. The definition is very dry and the reader has to carefully look at the notations to understand where everything comes from.\n\nThank you for the feedback on the readability of Definition 2.3. First, as we start explaining in line 134 and following, a \"max-following policy is defined as a policy that at every step follows the action of the [constituent] policy with the highest value in that state.\" With **approximate** max-following policies one can run into issues arising from the fact that value functions are not perfectly accurate anymore. We will add some additional motivating intuition leading up to the technical definition 2.3 similar to that of Definition 2.1. The purpose of our observations in section $4$ is to provide the intuition for max-following and approximate max-following. For instance, imagine a scenario where two of the value functions are very close to each other for some state. Now, due to noise introduced from approximation it might look as if the function with the true lower value actually has the higher of the two values (see Observation 4.6). As outlined in section $4$, accounting for this noise in our benchmark requires comparing the learned policy to a class of policies (the class of approximate max-following policies) rather than a single baseline policy, and so the technicality of Definition 2.3 is unfortunately necessary. If the reviewer thinks it would improve readability, we would be happy to move Section 4 before Section 3, where we present our algorithm, so that the reader can have these examples in mind before we present our main results. \n\n**Questions**\n\nWe are extremely grateful for this reviewer's thorough feedback and attention to detail and we hope to be able to incorporate much of the advice provided to build a better paper. We hope to be able to use the discussion period to clarify some of the details surrounding our oracle assumption both in theory and in practice and work on improving the exposition/clarity of our definitions and examples to help create a better paper.", "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": "", "extra_scores": {}}]

Author rebuttal:
First and foremost, we would like to thank all the reviewers for their time and feedback on our paper. We thank reviewers BR1J and Z6cc for highlighting the usefulness of our theoretically motivated but practically employable algorithm. We also thank reviewer Qu2b for highlighting the simplicity of our algorithm and the strong words about our empirical results.


Given the common questions around our oracle assumption, we would like to make a clarifying statement up front. Many machine learning problems are known to be computationally hard in the worst case, but Empirical Risk Minimization (ERM) has still proven to be a useful framework in practice. For instance, the machine learning community has made great strides in solving supervised learning problems using neural networks over the past 10 years.
Our oracle assumption can be thought of as providing us the guarantee that we can learn an approximate value function well in such a batch-ERM setting. That means, we are reducing the problem of learning an approximate max-following policy to a simpler supervised learning problem over a given distribution. In other words, our goal with this work is to provide guarantees under the assumption that in practice ERM is easy and neural networks do what neural networks do.

Meta-review: This paper considers the setting in which several good policies are available for some MDP, and an agent has to learn how to combine them to achieve higher performance than following a single of the constituent policies. The core idea behind the proposed algorithm is to use with a max-following policy, which at each state selects the action of the constituent policy with the highest value. The algorithm's efficiency is demonstrated both theoretically and empirically.
Decision: Accept (poster)