Oracle-Efficient Reinforcement Learning for Max Value Ensembles

Authors: marcel  hussing
michael  kearns
aaron  roth
bela  sengupta
jessica  sorrell
Venue: NeurIPS_cc_2024_Conference
Published: 2024-05-15 03:14:50

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.

Main paper: 
 introduction: 
 Computationally efficient RL algorithms are known for simple environments with small state spaces such as tabular Markov decision processes (MDPs) [Kearns and Singh, 2002, Brafman and Tennenholtz, 2002] , but practical applications often require dealing with large or even infinite state spaces. 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 [Jaksch et al., 2010 , Lattimore and Hutter, 2012 , Du et al., 2019 , Domingues et al., 2021] . 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., 2021 , Peer et al., 2021 , Chen et al., 2021 , Hiraoka et al., 2022] , which assume access to multiple 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 a 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 et al., 2020 , Liu et al., 2023 , 2024] . These works instead aim to learn a policy competitive with a maxaggregation 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 max-aggregation 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 is to learn a policy competitive with a similar but incomparable benchmark to that of Cheng et al. [2020] under comparatively weak assumptions. We give an efficient algorithm for learning a policy competitive with a max-following policy (Definition 2.1), assuming the learner has access to a 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-following 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 5.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, it was recently shown by [Golowich et al., 2024] that learning an optimal policy in a particular family of block MDPs is computationally intractable under reasonable cryptographic assumptions, even when the learner has access to a 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 a policy that competes with max-following, a regression oracle is in fact sufficient. We leave open the interesting question of whether such an oracle is necessary.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 1, Theorem 3.1). We consider the episodic RL setting in which the learner interacts with its environment for episodes of a fixed length H. The algorithm incrementally constructs an improved policy over H iterations, learning an improved policy for step h ∈ [H] of the episode at iteration h. This incremental approach allows the algorithm to 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.Because 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 a superset of the class of maxfollowing policies and contains all policies that at each state follow the action of some constituent policy with near-maximum value at that state. In 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. [2022] , Hussing et al. [2023] . We demonstrate that in all cases, the max-following policy we find is at least as good as the constituent policies and in several cases outperforms it significantly.As discussed above, our work is related to a recent line of research learning a max-aggregation policy [Cheng et al., 2020 , Liu et al., 2023 , 2024] , which can be viewed as a one-step look-ahead max-following policy and is incomparable to the class of max-following policies (see the appendix of Cheng et al. [2020] for example MDPs demonstrating this fact). 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 Liu et al. [ , 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 5 for additional discussion).The boosting approach to policy ensembling of Brukhim et al. [2022] 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.There are other lines of work on policy improvement, which consider improving upon a single base policy and therefore do not address the challenge of ensembling [Sun et al., 2017 , Schulman et al., 2015 , Chang et al., 2015] . Barreto et al. [2017 Barreto et al. [ , 2020]] , Alegre 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. [2022] 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 state-dependent 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 a meaningful benchmark. [Song et al., 2023] provide a survey of a variety of more complex techniques to ensemble policies, mainly from a practical perspective.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 1.1summary sections provide an overview of our theoretical and experimental results. We then proceed to explain the setup in our preliminaries 2 and provide our main theoretical results 3 immediately after. We also provide our experimental 5 results at the end of the paper.Guidelines:• The answer NA means that the abstract and introduction do not include the claims made in the paper. • The abstract and/or introduction should clearly state the claims made, including the contributions made in 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 to other settings. • It is fine to include aspirational goals as motivation as long as it is clear that these goals are not attained by the paper. 
preliminaries: 
 We consider an episodic fixed-horizon Markov decision process (MDP) [Puterman, 1994] which we formalize as a tuple M = (S, A, R, P, µ 0 , H) where S is the set of states, A the set of actions, R is a reward function, P the transition dynamics, µ 0 a distribution over starting states and H the horizon [Sutton and Barto, 2018] .[N ] will denote the set {0, ..., N -1}. In the beginning, an initial state s 0 is sampled from µ 0 . At any time h ∈ [H], the agent is in some state s h ∈ S and chooses an action a h ∈ A based on a function π h mapping from states to distributions over actions Π : S → ∆(A). As a consequence, the agent traverses to a new next state s h+1 sampled from P (•|s h , a h ) and obtains a reward R(s h , a h ). Without loss of generality, we assume that rewards bounded within [0, 1]. The sequence of functions π h used by the agent is referred to as its policy, and is denoted π = {π h } h∈ [H] . A trajectory is the sequence of (state, action) pairs taken by the agent over an episode of length H, and is denoted τ = {(s h , a h )} h∈ [H] . We will use the notation τ ∼ π(µ 0 ) to refer to sampling a trajectory by first sampling a starting state s 0 ∼ µ 0 , and then executing policy π from s 0 .The goal of the learner is to maximize the expected cumulative reward Es 0∼µ0,P [ H-1 t=0 R(s t , a t )] over episodes of length H. We further define the value function as the expected cumulative return of following some policy π from some state s as V π (s) = Es 0∼µ0,P [ H-1 t=0 R(s t , a t )|π, s 0 = s]. Due to the finite horizon of the episodic setting, we will also need to refer to the expected cumulative reward from state s under policy π from time h ∈ [H]. We denote this time-specific value function byV π h (s) = EP [ H-1 t=h R(s t , a t )|π, s h = s].Finally, the key object of interest is a max-following policy. Given access to a set of k arbitrarily defined policies Π k = {π k } K k=1 and their respective value functions which we denote by the shorthand V π k = V k , 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-following policy class). Fix a set of policies Π k for a common MDP M and an episode length H. The class of max-following policies Π k max is definedΠ k max = {π : ∀h ∈ [H], ∀s ∈ S, π h (s) = π k * (s) for some k * ∈ argmax k∈[K] V k h (s)}Note that for any collection of constituent policies Π k 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 to Observation 4.5 for an example demonstrating this fact.We V π h ← O π (α, µ, h) such that Es∼µ[( V π h (s) -V π h (s)) 2 ] ≤ α. We use the notation O π α = O π (α, •, •) to denote O πwith fixed accuracy parameter α. We will also use the shorthandO k = O π k .Looking ahead to Section 3, we note that for every distribution µ on which Algorithm 1 queries an oracle, µ is not only efficiently samplable, but samplable by executing an explicitly constructed policy π samp for h steps in MDP M, starting from µ 0 . Thus, for any distribution µ, policy π k , and time h for which we query O k , we could efficiently obtain an unbiased estimate of Es∼µ[V k h (s)] by following a known π samp for h steps from µ 0 , and then switching to π k for the remainder of the episode. We mention this to highlight that our 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 Es∼µ[V k h (s)] into an approximation V k h with small squared error with respect to µ. Lastly, we define our benchmark class of policies. Given a set of constituent policies Π k , our benchmark defines for each state and time a set of permissible actions: any action taken by a policy π t ∈ Π k for which the value V t h (s) is sufficiently close to the maximum value max k∈[K] V k h (s). The class of approximate max-following policies is then any policy that exclusively takes permissible actions. We refer the reader to Section 4 for further explanation of this benchmark. Definition 2.3 (Approximate max-following policies). We define a set of β-good policies at state s ∈ S and time h ∈ [H], selected from a set Π k , as follows.T β,h (s) = {π ∈ Π k : V π h (s) ≥ max k∈[K] V k h (s) -β}.Then we define the set of approximate max-following policies for Π k to beΠ k * β = {π : ∀h ∈ [H], ∀s ∈ S, π h (s) = π t h (s) for some π t ∈ T β,h (s)}.3 The MaxIteration learning algorithmIn this section, we introduce our algorithm for learning an approximate max-following policy, MaxIteration (Algorithm 1. This algorithm learns a good approximation of a max-following policy at step h, assuming access to a good approximation of a max-following policy for all previous steps.For the first step (h = 0), the algorithm learns a good approximation V k 0 for all constituent policies π k on the starting distribution µ 0 . These approximate value functions can in turn be used to define the first action taken by the approximate max-following policy, namely π0 (s) = π argmax k V k 0 (s) (s). Following π0 (s) from µ 0 generates a samplable distribution over states µ 1 (s) = Es 0∼µ0 [P (s|s 0 , π0 (s 0 ))], and so our oracle assumption allows us to obtain good estimates V k 1 with respect to µ 1 for all π k . We can then define the second action of the approximate max-following policy, and so on, for all H steps. Notice that sampling from µ h 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 µ h are (informally) defined as follows: at iteration h ∈ [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 µ 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. That means to sample from µ 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 µ h . 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 k h at time h for policy π k on states sampled from µ h , one should think of it as using the remainder of the episode to obtain an unbiased estimate of the expectation of V k h on the distribution µ 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 π k for the remainder of the episode. The accumulated reward obtained by following policy π k from state s h for steps h through H gives the oracle an unbiased estimate ofEs h ∼µ h [V k h (s h )].To implement this oracle assumption, one could use many such unbiased estimates as training data to train a neural network, to learn a good approximate value function for π k at time h on distribution µ h .Algorithm 1 MaxIteration M α (Π k ) 1: for h ∈ [H] do 2: for k ∈ [K] do 3:let µ h be the distribution sampled by executing the following procedure: 4: sample a starting state s 0 ∼ µ 0 5:for i ∈ [h] do 6: s i+1 ∼ P ( • | s i , π argmax k V k i (si) (s i )) 7:end for 8:output s h 9:V k h ← O k α (µ h , h) 10:end for 11: end for 12: return policy π= {π h } h∈[H] where πh (s) = π argmax k∈[K] V k h (s) (s)Theorem 3.1. For any ε ∈ (0, 1], any MDP M with starting state distribution µ 0 , any episode length H, and anyK policies Π k defined on M, let α ∈ Θ( ε 3 KH 4 ) and β ∈ Θ( ε H ). Then MaxIteration M α (Π k ) makes O(HK) oracle queries and outputs π such that E s0∼µ0 V π (s 0 ) ≥ min π∈Π k * β E s0∼µ0 [V π (s 0 )] -O(ε). Proof. For all h ∈ [H], k ∈ [K], let V k h denote the approximate value function obtained from O k α (µ h , h) in Algorithm 1.We then define, for every h ∈ [H], the set of states for which some approximate value function V k h (s) has large absolute error (B h ) and the set of bad trajectories(B τ ) that pass through a state in B h for any h ∈ [H] : B h = {s ∈ S : ∃k ∈ [K] s.t. | V k h (s) -V k h (s)| ≥ ε 2H } and B τ = {{(s h , a h )} h∈[H] : ∃h ∈ [H] s.t. s h ∈ B h }.We will show that there exists an approximate max-following policy π ∈ Π k * β such that for any trajectoryτ ′ ̸ ∈ B τ , Pr τ ∼π(µ0) [τ = τ ′ ] = Pr τ ∼π(µ0) [τ = τ ′ ].We then bound the probability Pr τ ∼π(µ0) [τ ∈ B τ ], and the contribution to Es 0∼µ0 [V π (s 0 )] from these trajectories, proving the claim.Let V k * h (s) denote the value of the policy that π follows at time h and state s. From the definition of the bad set B h and the setting ofβ ∈ Θ( ε H ), for any state s ̸ ∈ B h , V k * h (s) ≥ V k * h (s) -ε 2H ≥ max k∈[K] V k h (s) -ε 2H ≥ max k∈[K] V k h (s) -β.In other words, if a state s is not bad at time h, then πh (s) = π k h (s) for a policy π k that has value V k h (s) within β of the true max value max k∈[K] V k h (s). It then follows from the definition of the class of approximate max-following policies Π k * β (Definition 2.3) that there exists some π ∈ Π k * β such that for all h ∈ [H], for all s ̸ ∈ B h , πh (s) = π h (s).For any trajectory τ ′ , Pr τ ∼π(µ0) [τ = τ ′ ] = Pr µ0 [s 0 ] • H-1 h=0 P (s h+1 |s h , πh (s h )). Then for any trajectory τ ′ ̸ ∈ B τ , Pr τ ∼π(µ0) [τ = τ ′ ] = Pr τ ∼π(µ0) [τ = τ ′ ],and thereforeE τ ∼π(µ0) H-1 h=0 R(s h , a h ) | τ ̸ ∈ B τ = E τ ∼π(µ0) H-1 h=0 R(s h , a h ) | τ ̸ ∈ B τFor τ ∈ B τ , we have lower and upper-bounds Eτ∼π(µ 0 ) [H-1 h=0 R(s h , a h ) | τ ∈ B τ ] ≥ 0 and Eτ∼π(µ 0) [ H-1 h=0 R(s h , a h ) | τ ∈ B τ ] ≤ H.We can then write:E s 0 ∼µ 0 V π (s0) = E τ ∼π(µ 0 ) H-1 h=0 R(s h , a h ) | τ ̸ ∈ Bτ • Pr τ ∼π(µ 0 ) [τ ̸ ∈ Bτ ] + E τ ∼π(µ 0 ) H-1 h=0 R(s h , a h ) | τ ∈ Bτ • Pr τ ∼π(µ 0 ) [τ ∈ Bτ ] ≥ E τ ∼π(µ 0 ) H-1 h=0 R(s h , a h ) | τ ̸ ∈ Bτ • Pr τ ∼π(µ 0 ) [τ ̸ ∈ Bτ ] = E τ ∼π(µ 0 ) H-1 h=0 R(s h , a h ) | τ ̸ ∈ Bτ • Pr τ ∼π(µ 0 ) [τ ̸ ∈ Bτ ] ≥ E τ ∼π(µ 0 ) H-1 h=0 R(s h , a h ) -H • Pr τ ∼π(µ 0 )[τ ∈ Bτ ] (using law of total probability and upper bound on rewards)≥ minπ∈Π k * β E s 0 ∼µ 0 [V π (s0)] -H • Pr τ ∼π(µ 0 ) [τ ∈ Bτ ].It remains to upper-bound Pr τ ∼π(µ0) [τ ∈ B τ ]. We have already arguedPr τ ∼π(µ0) [τ ∈ B τ ] = Pr τ ∼π(µ0) [τ ∈ B τ ]. Observing that Pr τ ∼π(µ0) [τ ∈ B τ ] ≤ H-1 h=0 Pr τ ∼π(µ0) [s h ∈ B h ], it is sufficient to show Pr τ ∼π(µ0) [s h ∈ B h ] ∈ O( ε H 2 ) to prove the claim. For all h ∈ [H], let µ h (s) = Pr τ ∼π(µ0) [s h = s],and note that this is the distribution supplied to the oracle at iteration h of Algorithm 1. It follows from our oracle assumption (Definition 2.2) that for all k ∈ [K],Es h ∼µ h [( V k (s h ) -V k (s h )) 2 ] < α. We apply Markov's inequality to conclude that for all k ∈ [K], Pr s h ∼µ h [| V k h (s h ) -V k h (s h )| ≥ ε 2H ] < 4αH 2 ε 2 ∈ O( ε KH 2 ).Union bounding over the K constituent policies gives Prs h ∼µ h [s h ∈ B h ] ∈ O( ε H 2 ), from the definition of B h . Union bounding over the trajectory length H, we then havePr τ ∼π(µ0) [τ ∈ B τ ] ∈ O( ε H ). It follows that E s0∼µ0 V π (s 0 ) ≥ min π∈Π k * β E s0∼µ0 [V π (s 0 )] -O(ε),completing the proof.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 no 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 a separate "Limitations" section in their paper.• The paper should point out 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 on a few datasets or with a few runs. In general, empirical results often depend on implicit assumptions, which should be articulated. • The authors should reflect on the factors that influence the performance of the approach.For example, a facial recognition algorithm may perform poorly when image resolution is low or images are taken in low lighting. Or a speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to 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 fairness. • While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, a worse outcome might be that reviewers discover limitations that aren't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an important role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations. 
theory assumptions and proofs: 
 Question: For each theoretical result, does the paper provide the full set of assumptions and a complete (and correct) proof?Answer: [Yes] Justification: We provide extensive discussion of our setting and preliminaries 2 and corresponding proofs of theorems 3 about the nature of our assumptions about the oracle and definitions and also about how they compare with corresponding theoretical works in the literature.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 crossreferenced. • 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 if they appear in the supplemental material, the authors are encouraged to provide a short proof sketch to provide intuition. • Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material. • Theorems and Lemmas that the proof relies upon should be properly referenced. 
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-following policies. Lemma 4.1 (Worst approximate max-following policy competes with best fixed policy). For any ε ∈ (0, 1] and any episode length H, let β ∈ Θ( ε H ). Then for any MDP M with starting state distribution µ 0 , and any K policies Π k defined on M, It is an immediate corollary of Theorem 3.1 and Lemma 4.1 that the policy learned by Algorithm 1 competes with the best constituent policy. Corollary 4.2. For any ε ∈ (0, 1], any MDP M with starting state distribution µ 0 , any episode length H, and any K policies Π k defined on M, let α ∈ Θ( ε 3 KH 4 ), and let π denote the policy output bymin π∈Π k * β E s0∼µ0 V π (s 0 ) ≥ max k∈[K] E s0∼µ0 V k (s 0 ) -O(ε).MaxIteration M α (Π k ). Then E s0∼µ0 V π (s 0 ) ≥ max k∈[K] E s0∼µ0 V k (s 0 ) -O(ε).We provide diagrams of MDPs as examples for the observations that we make below. States in S are denoted by the labels on the nodes. Actions in A are indicated by arrows from given states with deterministic transition dynamics and the rewards R(s, a) are labeled over the corresponding arrows.Arrows may be omitted for transitions that are self-loops with reward 0. Observation 4.3. The worst approximate max-following policy can be arbitrarily better than the best constituent policy.Consider in Figure 1a two policies on this MDP: π 0 (s) = right and π 1 (s) = left, for all s ∈ S. Note that for any episode length H ≥ 2, for all k ∈ {0, 1}, max s∈S V k (s) = 2. For any β < 1, Π k * β comprises policies π such that π(s 0 ) = right, π(s 2 ) = left, and π(s 1 ) ∈ {right, left}. Therefore for any episode length H, and state s ∈ S, min π∈Π k * β V π (s) = 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 H. Observation 4.4. A max-following policy cannot always compete with an optimal policy.In Figure 1b , consider policies π 0 (s) = right, π 1 (s) = left, and π 2 (s) = up, for all s ∈ S. At state s 2 , π 0 is the only policy with non-zero value. Thus, any max-following policy will take action right from s 2 , receiving reward ε and then reward 0 for the remainder of the episode. Given a starting state distribution supported entirely on s 2 , for any episode length H ≥ 3, the optimal policy will obtain cumulative reward H -2, whereas any max-following policy will only obtain reward ε. Observation 4.5. Different max-following policies may have different expected cumulative reward.We again consider Figure 1b , but suppose now the starting state distribution is supported entirely on s 0 . For all k ∈ [3], V k (s 0 ) = 0 and so a max-following policy may take any action from s 0 . A max-following policy that always takes actions left or up from s 0 will only ever obtain cumulative reward 0, but a max-following policy that takes action right will move to s 1 and (so long as more than one step remains in the episode) will then take action up and move to state s 4 , where it will stay to obtain cumulative reward H -2.If the value functions of constituent policies are exactly known, it 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 max-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 an obstacle to learning a max-following policy.In Figure 2a , we again consider policies π 0 (s) = right and π 1 (s) = left for all states s ∈ S, color coding the actions taken by π 0 with red and π 1 with blue in Figure 2a . For starting state distribution supported entirely on s 0 , a max-following policy π will take action π(s 0 ) = left, π(s 2 ) = right, and π(s 3 ) = left for the remainder of the episode, obtaining reward H -2 + 2ε. However, given only approximate value functions V k with state-wise absolute error bound| V k h (s) -V k h (s)| ≤ εfor all states s and times h, the policy π that takes actionπ k * h (s) for k * = argmax k∈[2]V k h (s) can have much lower expected cumulative reward than a max-following policy. For example if V 0 0 (s 0 ) = ε and V 1 0 (s 0 ) = 0 in our Figure 2a example, then π will have expected return 0. Observation 4.7. A max-following policy'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, 1}. Every action leads to a self-loop (for all a ∈ A, P (s|s, a) = 1) and for a fixed action, rewards are affine functions of the state (e.g. R(s, -1) = 1 -s and R(s, 1) = s). We consider two policies: π 0 (s) = -1 and π 1 (s) = 1 for all s ∈ S. Notice that for episode length H, V 0 (s) = HR(s, -1) and V 1 (s) = HR(s, 1). Since the dynamics keep the state at the same fixed place independent of the action, the max-following policy at state s will simply be the max of 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 a 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-following policy is not of the same parametric class. See Appendix A for further discussion.Question: Does the paper fully disclose all the information needed to reproduce the main experimental 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 1 and any variations for the practical implementation are discussed in Appendix C. We report all used hyperparameters in Appendix C.1. 
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 a 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 to increase performance of a learnable policy [Cheng et al., 2020 , Liu 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 a 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. [2017 Barreto et al. [ , 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., 2023] 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 a 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 et al., 2022] (IQL). This ensures we obtain very strong constituent policies for their respective tasks. After training the constituents, we run MaxIteration and the baselines for a 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 a heuristic version of MaxIteration 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 et al., 2023] to train the MAPS algorithm but were unable to obtain non-trivial return even after a 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 Liu 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 MaxIteration 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 a policy improvement style method on top of the best-performing constituent policy for comparison. Fine-tuning provides a strong baseline in the sense that it 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 MaxIteration. For more details we refer to Appendix C. 1. There are cases where max-following not only increases the return but actually leads to solving a 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 in Appendix C demonstrate that in all cases, MaxIteration is 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, MaxIteration consistently leads to greater return improvement than fine-tuning given the same amount of data. Fine-tuning with substantially more resources would eventually surpass the performance of MaxIteration as MaxIteration is limited to competing with the max-following benchmark which can be suboptimal. 
conclusion: 
 We introduce MaxIteration, an algorithm to efficiently learn a 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 us to learn how to 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 a 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 it seems likely that our oracle assumption is necessary for learning an approximate max-following policy, we leave proving this claim for future work. We also leave consideration of alternative ensembling approaches to future work. Max-value ensembling is sensitive to slight differences in the values between constituent policies whereas, e.g., softmax takes into account the relative 'weighting' of values. In addition, it would be interesting to characterize the amount of improvement we can obtain over our constituent policies or prove conditions under which our approximate max-following policy is competitive with a true max-following policy or the optimal policy. One could also extend this analysis to ensembling methods like softmax and study the nature of guarantees in that setting. 
 
 Appendix: Extending beyond MDPs to the partially observable setting, and to the discounted infinite-horizon setting, would also add richness to the class of problems we could consider.A.1 LQR max-following parametric class vs. constituent policiesmin {ut} ∞ t=0 ∞ t=0 γ t (x T t Qx t + u T t Ru t ) subject to x t+1 = Ax t + Bu t + w t ,To motivate the use of max-following policies in a richer class of MDPs, we consider a traditional control problem with continuous state and action spaces: the discrete linear quadratic regulator. Note that here we analyze the infinite horizon discounted case so that we can analyze the time-invariant value function, but episodic analogues exist. Consider the following setting where γ ∈ [0, 1] is a discount factor, and w t ∼ N (0, σ 2 I). Here, we consider the simple case where Q, R, A = I and B = (1 + ϵ)I. We know that the optimal policy is of the form u = -K * x [Bertsekas, 2012] and we set two policies that are only stable along one component and unstable along the other of the form u 1 = -K 1 x and u 2 = -K 2 x. It is important to note that the value functions of the individual policies and the optimal policies have exact quadratic forms like V (x) = x T P x + q, but the maxfollowing policy is not necessarily within the same parametric class. For example, P 1 is the solution to the Lyapunov equationP 1 = (I + K T 1 K 1 + γ(A -K 1 ) T P 1 (A -K 1 )) and q 1 = γ 1-γ σ 2 tr(P 1 ). A similar formula exists for policy 2.In LQR, for the K 1 , K 2 controllers described above, a max-following policy is able to attain higher value than the individual expert policies that have an unstable direction in one axis. Moreover, we see that the optimal policy is obviously superior to all the other policies, but that a max-following policy is more competitive with it than the other individual expert policies. A max-following policy 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.Lemma 4.1 (Worst approximate max-following policy competes with best fixed policy). For any ε ∈ (0, 1] and any episode length H, let β ∈ Θ( ε H ). Then for any MDP M with starting state distribution µ 0 , and any K policies Π k defined on M,min π∈Π k * β E s0∼µ0 V π (s 0 ) ≥ max k∈[K] E s0∼µ0 V k (s 0 ) -O(ε).Proof. We will prove the claim inductively, showing that for all C ∈ [H], if we run any approximate max-following policy for C steps, and then continue following the policy π k chosen at step C for the rest of the episode, then our expected return is not much worse than if we had followed any fixed π k for the whole episode.Somewhat more formally, recalling the definition of the set of approximate max-following policies s,h) denote the π t ∈ Π k that π follows at state s and time h, we will show that if at some step C ∈ [H] we haveΠ k * β (Definition 2.3), at every time h ∈ [H] and state s ∈ S, a policy π ∈ Π k * β takes action π t h (s) for a π t ∈ Π k such that V t h (s) ≥ max k∈[K] V k h (s) -β. Letting π t(E s0∼µ0,P C h=0 R(s h , π h (s h )) + H-1 h=C+1 R(s h , π t(s C ,C) h (s h )) ≥ max k∈[K] E s0∼µ0 V k (s 0 ) -O( ε(C+1) H ),for all π ∈ Π k * β , then the same holds for C + 1 for all π. In the base case, C = 0, the claimE s0∼µ0,P H-1 h=0 R(s h , π t(s0,0) h (s h )) ≥ max k∈[K] E s0∼µ0 V k (s 0 ) -O( ε H )for all π ∈ Π k * β and all π k ∈ Π k , follows straightforwardly from the definition of Π k * β and setting ofβ ∈ Θ( ε H ), since E s0∼µ0,P H-1 h=0 R(s h , π t(s0,0) h (s h )) = E s0∼µ0 [V π t(s 0 ,0) (s 0 )] ≥ E s0∼µ0 max k∈[K] V k (s 0 ) -O( ε H ) ≥ max k∈[K] E s0∼µ0 V k (s 0 ) -O( ε H ).We now prove the inductive step. We wish to show that if at step C, we have for someπ ∈ Π k * β E s0∼µ0,P C h=0 R(s h , π h (s h )) + H-1 h=C+1 R(s h , π t(s C ,C) h (s h )) ≥ max k∈[K] E s0∼µ0 V k (s) -O( ε(C+1) H ),then continuing to follow π at step C + 1 and following π t(s C+1 ,C+1) thereafter reduces expected return byO( ε H ). Now if π C+1 (s C+1 ) = π t C+1 (s C+1 ) for π t ∈ Π k , it must be the case that V t C+1 (s C+1 ) ≥ max k∈[K] V k C+1 (s C+1 ) -O( ε H ), otherwise π ̸ ∈ Π k * β . It follows that E s0∼µ0,P C+1 h=0 R(s h , π h (s h )) + H-1 h=C+2 R(s h , π t(s C+1 ,C+1) h (s h )) = E s0∼µ0,P C h=0 R(s h , π h (s h )) + V t(s C+1 ,C+1) C+1 (s C+1 ) (by definition of V and π C+1 (s C+1 )) ≥ E s0∼µ0,P C h=0 R(s h , π h (s h )) + max k∈[K] V k C+1 (s C+1 ) -O( ε H ) (from π ∈ Π k * β ) ≥ E s0∼µ0,P C h=0 R(s h , π h (s h )) + V t(s C ,C) C+1 (s C+1 ) -O( ε H ) = E s0∼µ0,P C h=0 R(s h , π h (s h )) + H-1 h=C+1 R(s h , π t(s C ,C) h (s h )) -O( ε H ) (by definition of V ) ≥ max k∈[K] E s0∼µ0 V k (s) -O( ε(C+2) H ) (by inductive hypothesis)and so the claim holds for time C + 1, for any π ∈ Π k * β for which it holds for time C. We showed the base case C = 0 hold for all π ∈ Π k * β , and therefore we haveE s0∼µ0,P C h=0 R(s h , π h (s h )) + H-1 h=C+1 R(s h , π t(s C ,C) h (s h )) ≥ max k∈[K] E s0∼µ0 V k (s) -O( ε(C+1) H ) for all C ∈ [H]. In particular, for C = H -1 we conclude that E s0∼µ0,P C h=0 R(s h , π h (s h )) ≥ max k∈[K] E s0∼µ0 V k (s) -O(ε)and it follows thatmin π∈Π k * β E s0∼µ0 V π (s 0 ) ≥ max k∈[K] E s0∼µ0 V k (s 0 ) -O(ε).For our experiments, we use a 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. β 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 to compare run-times between MaxIteration and IQL. Finally, we use a γ discounting which has been shown to have regularizing effects on the value function updates [Amit et al., 2020] .For IQL, we use the d3rlpy implementations [Seno and Imai, 2022] and code provided by Hussing et al. [2023] .Both algorithms are run for 10, 000 steps initially (to initialize value functions for MaxIteration and to pre-fill the buffer for IQL) before doing updates and then for 50, 000 steps for online training.All neural networks use ReLU [Glorot et al., 2011] Multi-layer perceptrons with 2 layers and a hidden dimension of 256 per layer. We run our MaxIteration algorithm on the DM Control benchmarks [Tunyasuvunakool et al., 2020] similar to the MAPS [Liu et al., 2023] setup. In their setup, the constituent policies correspond to different 3 checkpointed models in one run of the online Soft-Actor critic [Haarnoja et al., 2018] algorithm. As a result, it is generally true that the latest checkpointed model will outperform the previous two checkpoints meaning one constituent policy is 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 to exceed the performance of the constituent policies. Our experiments were conducted using a total of 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 1 hour. A large chunk of the runtime cost stems from executing the simulator.NeurIPS Paper Checklist• 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 a 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 it 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 to 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 submissions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. 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, confidence intervals, or statistical significance tests, at 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. Guidelines:• The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.• If the authors answer No, they should explain the special circumstances that require a deviation from the Code of Ethics. • The authors should make sure to preserve anonymity (e.g., if there is a special consideration due to laws or regulations in their jurisdiction). 10. Broader Impacts Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?• The answer NA means that the paper does not use existing assets.• The authors should cite the original paper that produced the code package or dataset.• The authors should state which version of the asset is used and, if possible, include a 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, paperswithcode.com/datasets has curated licenses for some datasets. Their licensing guide can help determine the license of a dataset. • For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be 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 not release new assets.• Researchers should communicate the details of the dataset/code/model as part of 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. • We recognize that the procedures for this may vary significantly between institutions and locations, and we 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 as the institution conducting the review.38th Conference on Neural Information Processing Systems (NeurIPS 2024). 


Decision: 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.

Reviews: review: paper_summary: paper_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.
strength_weakness: strength_weakness: 1. The algorithm assumes access to an ERM oracle, which might not be practical in all scenarios.
2. While its efficiency in simulation tasks, the algorithm might be complex to implement in real-world systems.
questions: questions: 1. Are there any specific cases where the algorithm's performance might degrade?
2. How does the algorithm deal with non-stationary environments or changing dynamics?
limitations: limitations: Please see the above comments.
paper_summary: paper_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.
strength_weakness: strength_weakness: 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. 

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.
questions: questions: - What are Policy 0 and Policy 1 in Figure 1?
- How do you explain the tasks where all the methodologies had a very low success rate?
limitations: 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.
paper_summary: paper_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.

The 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.

The 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.
strength_weakness: strength_weakness: While the contribution seems of high quality, the paper lacks clarity and intuition, which may make it difficult to reproduce.

- 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)
- 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.
- 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.
questions: 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: limitations: The paper does not seem to have potential negative societal issues, and its scientific limitations are well-discussed.

Comments: title: Answer to Rebuttal
comment: Dear reviewer Z6cc, we are grateful for your feedback and will make several changes in the next iteration of the manuscript. 
* We had hoped to convey that simple heuristic policies can sometimes be useful even when they are not complex, but we see now that there is ambiguity in this statement. We will adjust the abstract as you suggested and point out in the main text that constituent policies can, but must not necessarily, be heuristic. 
* We will also make changes to the caption and text with respect to the description of the policies 0 and 1 including a paragraph similar to what we provided in the rebuttal.

Thank you for engaging in this discussion phase, we greatly appreciate it. We hope you are now more positively disposed to our paper and are happy to discuss further if there are any other points of confusion
Dear authors, thanks for your efforts in clarifying my comments. Here are some clarifications to the questions from my side that didn't appear very clear:

> 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?

I think you understood what I meant, and thanks to your answer, I can now identify that the observations are not necessary conditions (assumptions) on which to base your theoretical results.

> 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.

This part comes from the experimental results that require you to use heuristic-based versions of the algorithm. Thank you for clarifying that this is only related to this part and is not required in the theoretical proof. The confusing part comes from the abstract, where you stated: "One line of research [...] the natural assumption that we are given a collection of heuristic base or constituent policies [...]." I believe this part makes the reader assume that the constituent policies come from heuristics, which is why I commented in the first place. Maybe you can adjust the abstract to clarify the difference.

> Regarding Figure 3

Thank you for explaining and considering my feedback to clarify what Policies 0 and 1 mean. I think improving the details you provided about them would help make your experiments more understandable. Your clarification about this was very helpful in understanding the underperforming tasks in my last question.

Thanks for taking the time to answer all of them; besides what I stated above, I don't have additional comments.