Year: 2021

Abstract:
We study efficient algorithms for reinforcement learning in Markov decision processes, whose complexity is independent of the number of states. This formulation succinctly captures large scale problems, but is also known to be computationally hard in its general form. Previous approaches attempt to circumvent the computational hardness by assuming structure in either transition function or the value function, or by relaxing the solution guarantee to a local optimality condition. We consider the methodology of boosting, borrowed from supervised learning, for converting weak learners into an effective policy. The notion of weak learning we study is that of sampled-based approximate optimization of linear functions over policies. Under this assumption of weak learnability, we give an efficient algorithm that is capable of improving the accuracy of such weak learning methods iteratively. We prove sample complexity and running time bounds on our method, that are polynomial in the natural parameters of the problem: approximation guarantee, discount factor, distribution mismatch and number of actions. In particular, our bound does not explicitly depend on the number of states. A technical difficulty in applying previous boosting results, is that the value function over policy space is not convex. We show how to use a non-convex variant of the Frank-Wolfe method, coupled with recent advances in gradient boosting that allow incorporating a weak learner with multiplicative approximation guarantee, to overcome the non-convexity and attain global optimality guarantees.

heading: 1 INTRODUCTION
text: The field of reinforcement learning, formally modelled as learning in Markov decision processes (MDP), models the mechanism of learning from rewards, as opposed to examples. Although the case of tabular MDPs is well understood, the main difficulty in applying RL to practice is the size of the state space.
Various techniques have been suggested and applied to cope with very large MDPs. The most common of which is function approximation of either the value or the transition function of the underlying MDP, many times using deep neural networks. Training deep neural networks in the supervised learning model is known to be computationally hard. Therefore reinforcement learning with neural function approximation is also computationally hard in general, and for this reason lacks provable guarantees.
This challenge of finding efficient and provable algorithms for MDPs with large state space is the focus of our study. Previous approaches can be categorized in terms of the structural assumptions made on the MDP to circumvent the computational hardness. Some studies focus on structured dynamics, whereas others on structured value function or policy classes w.r.t. to the dynamics.
In this paper we study another methodology to derive provable algorithms for reinforcement learning: ensemble methods for aggregating weak or approximate algorithms into substantially more accurate solutions. Our method can be thought of as extending the methodology of boosting from supervised learning (Schapire & Freund, 2012) to reinforcement learning. Interestingly, however, our resulting aggregation of weak learners is not linear.
In order to circumvent the computational hardness of solving general MDPs with function approximation, we assumes access to a weak learner: an efficient sample-based procedure that is capable
of generating an approximate solution to any linear optimization objective over the space of policies. We describe an algorithm that iteratively calls this procedure on carefully constructed new objectives, and aggregates the solution into a single policy. We prove that after sufficiently many iterations, our resulting policy is provably near-optimal.

heading: 1.1 CHALLENGES AND TECHNIQUES
text: Reinforcement learning is quite different from supervised learning and several difficulties have to be circumvented for boosting to work. Amongst the challenges that the reinforcement learning setting presents, consider the following,
(a) The value function is not a convex or concave function of the policy. This is true even in the tabular case, and even more so if we use a parameterized policy class.
(b) The transition matrix is unknown, or prohibitively large to manipulate for large state spaces. This means that even evaluation of a policy cannot be exact, and can only be computed approximately.
(c) It is unrealistic to expect a weak learner that attains near-optimal value for a given linear objective over the policy class. At most one can hope for a multiplicative and/or additive approximation of the overall value.
Our approach overcomes these challenges by applied several new as well as recently developed techniques. To overcome the nonconvexity of the value function, we use a novel variant of the Frank-Wolfe optimization algorithm that simultaneously delivers on two guarantees. First, it finds a first order stationary point with near-optimal rate. Secondly, if the objective happens to admit a certain gradient domination property, an important generalization of convexity, it also guarantees near optimal value. The application of the nonconvex Frank-Wolfe method is justified due to previous recent investigation of the policy gradient algorithm (Agarwal et al., 2019; 2020a), which identified conditions under which the value function is gradient dominated.
The second information-theoretic challenge of the unknown transition function is overcome by careful algorithmic design: our boosting algorithm requires only samples of the transitions and rewards. These are obtained by rollouts on the MDP.
The third challenge is perhaps the most difficult to overcome. Thus far, the use of the Frank-Wolfe method in reinforcement learning did not include a multiplicative approximation, which is critical for our application. Luckily, recent work in the area of online convex optimization (Hazan & Singh, 2021) studies boosting with a multiplicative weak learner. We make critical use of this new technique which includes a non-linear aggregation (using a 2-layer neural network) of the weak learners. This aspect is perhaps of general interest to boosting algorithm design, which is mostly based on linear aggregation.

heading: 1.2 OUR CONTRIBUTIONS
text: Our main contribution is a novel efficient boosting algorithm for reinforcement learning. The input to this algorithm is a weak learning method capable of approximately optimizing a linear function over a certain policy class.
The output of the algorithm is a policy which does not belong to the original class considered. It is rather a non-linear aggregation of policies from the original class, according to a two-layer neural network. This is a result of the two-tier structure of our algorithm: an outer loop of non-convex Frank-Wolfe method, and an inner loop of online convex optimization boosting. The final policy comes with provable guarantees against the class of all possible policies.
Our algorithm and guarantees come in four flavors, depending on the mode of accessing the MDP (two options), and the boosting methodology for the inner online convex optimization problem (two options).
It is important to point out that we study the question from an optimization perspective, and hence, assume the availability of an efficient exploration scheme – either via access to a reset distribution that has some overlap with the state distribution of the optimal policy, or constraining the policy
class to policies that explore sufficiently. Such considerations also arise when reducing reinforcement learning to a sequence of supervised learning problems, e.g. Conservative Policy Iteration (Kakade & Langford, 2002) assumes the former. One contribution we make here is to quantitatively differentiate between these two modes of exploration in terms of the rates of convergence they enable for the boosting setting.

heading: 1.3 RELATED WORK
text: To cope with prohibitively large MDPs, the method of choice to approximate the policy and transition space are deep neural networks, dubbed “deep reinforcement learning". Deep RL gave rise to beyond human performance in games such as Go, protein folding, as well as near-human level autonomous driving. In terms of provable methods for deep RL, there are two main lines of work. The first is a robust analysis of the policy gradient algorithm (Agarwal et al., 2019; 2020a). Importantly, the gradient domination property of the value function established in this work is needed in order to achieve global convergence guarantees of our boosting method.
The other line of work for provable approaches is policy iteration, which uses a restricted policy class, making incremental updates, such as Conservative Policy Iteration (CPI) (Kakade & Langford, 2002; Scherrer & Geist, 2014), and Policy Search by Dynamic Programming (PSDP)(Bagnell et al., 2003).
Our boosting approach for provable deep RL builds on the vast literature of boosting for supervised learning (Schapire & Freund, 2012), and recently online learning (Leistner et al., 2009; Chen et al., 2012; 2014; Beygelzimer et al., 2015; Jung et al., 2017; Jung & Tewari, 2018). One of the crucial techniques important for our application is the extension of boosting to the online convex optimization setting, with bandit information (Brukhim & Hazan, 2021), and critically with a multiplicative weak learner (Hazan & Singh, 2021). This latter technique implies a non-linear aggregation of the weak learners. Non-linear boosting was only recently investigated in the context of classification (Alon et al., 2020), where it was shown to potentially enable significantly more efficient boosting.
Perhaps the closest work to ours is boosting in the context of control of dynamical systems (Agarwal et al., 2020b). However, this work critically requires knowledge of the underlying dynamics (transitions), which we do not, and cannot cope with a multiplicative approximate weak learner.
The Frank-Wolfe algorithm is extensively used in machine learning, see e.g. (Jaggi, 2013), references therein, and recent progress in stochastic Frank-Wolfe methods (Hassani et al., 2017; Mokhtari et al., 2018; Chen et al., 2018; Xie et al., 2019). Recent literature has applied a variant of this algorithm to reinforcement learning in the context of state space exploration (Hazan et al., 2019).

heading: 2 PRELIMINARIES
text: Optimization. We say that a differentiable function f : K 7→ R over some domain K is L-smooth with respect to some norm ‖ · ‖∗ if for every x, y ∈ K we have
∣∣f(y)− f(x)−∇f(x)>(y − x)∣∣ ≤ L 2 ‖x− y‖2∗.
For constrained optimization (such as over ∆A), the projection Γ : R|A| → ∆A of a point x to onto a domain ∆A is
Γ[x] = arg min y∈∆A
‖x− y‖.
An important generalization of convex function we use henceforth is that of gradient domination, Definition 1 (Gradient Domination). A function f : K → R is said to be (κ, τ,K1,K2)-locally gradient dominated (around K1 by K2) if for all x ∈ K1, it holds that
max y∈K f(y)− f(x) ≤ κ× max y∈K2
{ ∇f(x)>(y − x) } + τ.
Markov decision process. An infinite-horizon discounted Markov Decision Process (MDP)M = (S,A, P, r, γ, d0) is specified by: a state space S, an action space A, a transition model P where P (s′|s, a) denotes the probability of immediately transitioning to state s′ upon taking action a at state s, a reward function r : S ×A→ [0, 1] where r(s, a) is the immediate reward associated with taking action a at state s, a discount factor γ ∈ [0, 1); a starting state distribution d0 over S. For any infinite-length state-action sequence (hereafter, called a trajectory), we assign the following value
V (τ = (s0, a0, s1, a1, . . . )) = ∞∑ t=0 γtr(st, at).
The agent interacts with the MDP through the choice of stochastic policy π : S → ∆A it executes, where ∆A denotes the probability simplex over A. The execution of such a policy induces a distribution over trajectories τ = (s0, a0, . . . ) as
P (τ |π) = d0(s0) ∞∏ t=0 (P (st+1|st, at)π(at|st)). (1)
Using this description we can associate a state V π(s) and state-action Qπ(s, a) value function with any policy π. For an arbitrary distrbution d over S, define:
Qπ(s) = E [ ∞∑ t=0 γtr(st, at) ∣∣∣ π, s0 = s, a0 = a],
V π(s) = Ea∼π(·|s) [Qπ(s, a)|π, s] , V πd = Es0∼d [V π(s)|π] . Here the expectation is with respect to the randomness of the trajectory induced by π in M . When convenient, we shall use V π to denote V πd0 , and V ∗ to denote maxπ V π .
Similarly, to any policy π, one may ascribe a (discounted) state-visitation distribution dπ = dπd0 .
dπd (s) = (1− γ) ∞∑ t=0 γt ∑ τ :st=s P (τ |π, s0 ∼ d)
Modes of Accessing the MDP. We henceforth consider two modes of accessing the MDP, that are standard in the reinforcement learning literature, and provide different results for each.
The first natural access model is called the episodic rollout setting. This mode of interaction allows us to execute a policy, stop and restart at any point, and do this multiple times.
Another interaction model we consider is called rollout with ν-restarts. This is similar to the episodic setting, but here the agent may draw from the MDP a trajectory seeded with an initial state distribution ν 6= d0. This interaction model was considered in prior work on policy optimization Kakade & Langford (2002); Agarwal et al. (2019). The motivation for this model is two-fold: first, ν can be used to incorporate priors (or domain knowledge) about the state coverage of the optimal policy; second, ν provides a mechanism to incorporate exploration into policy optimization procedures.

heading: 3 SETTING: POLICY AGGREGATION AND WEAK LEARNING
text: Our boosting algorithms henceforth call upon weak learners to generate weak policies, and aggregate these policies in a way that guarantees eventual convergence to optimality. In this section we formalize both components.

heading: 3.1 POLICY AGGREGATION
text: For a base class of policies ΠW , our algorithm incrementally builds a more expressive policy class by aggregating base policies via both linear combinations and non-linear transformations. In effect, the algorithm produces a finite-width depth-2 circuit over some subset of the base policy class. We start with the simpler linear aggregation.
Definition 2 (Function Aggregation). Given some N0 ∈ Z+, w ∈ RN0 , (f1, . . . fN0) ∈ (S → R|A|)⊗N0 , we define f = ∑N0 n=1 wnfn to be the unique function f : S → RA for which simultaneously for all s ∈ S, it holds
f(s) = N0∑ n=1 wnf(s).
Next, the projection operation below may be viewed as a non-linear activation, such as ReLU, in deep learning terms. Note that the projection of any function from S to R|A| produces a policy, i.e. a mapping from states to distributions over actions.
Definition 3 (Policy Projection). Given a function f : S → R|A|, define a projected policy π = Γ[f ] to be a policy such that simultaneously for all s ∈ S, it holds that π(·|s) = Γ [f(s)] .
The next definition defines the class of functions represented by circuits of depth 1 over a base policy class. Note that these function do not necessarily represent policies since they take an affine (vs. convex) combination of policies.
Definition 4 (Shrub). For an arbitrary base policy class Π ⊆ S → ∆A, define (Π, N) to be a set such that λ ∈ Λ(Π, N) if and only if there exists N0 ≤ N,w ∈ RN0 , (π1, . . . πN0) ∈ Π⊗N0 such that λ = ∑N0 n=1 wnπn.
The final definition describes the set of possible outputs of the boosting procedure.
Definition 5 (Policy Tree). For an arbitrary base policy class Π ⊆ S → ∆A, define (Π, N, T ) to be a policy class such that π ∈ (Π, N, T ) if and only if there exists T0 ≤ T,w ∈ ∆T0 , (λ1, . . . λT0) ∈ (Π, N)⊗T0 such that π = ∑T0 t=1 wtΓ[λt].
It is important that the policy that the boosting algorithm outputs can be evaluated efficiently. In the appendix we show it is indeed the case (see Lemma 15).

heading: 3.2 MODELS OF WEAK LEARNING
text: We consider two types of weak learners, and give different end results based on the different assumptions: weak supervised and weak online learners. In the discussion below, let πr be a uniformly random policy, i.e. ∀(s, a) ∈ S ×A, πr(a|s) = 1/|A|.
Supervised Learning. The natural way to define weak learning is an algorithm whose performance is always slight better than that of random policy, one that chooses an action uniformly at random at any given state. However, in general no learner can outperform a random learner over all label distributions (this is called the “no free lunch" theorem). This motivates the literature on agnostic boosting (Kanade & Kalai, 2009; Brukhim et al., 2020; Hazan & Singh, 2021) that defines a weak learner as one that can approximate the best policy in a given policy class. Definition 6 (Weak Supervised Learner). Let α ∈ (0, 1). Consider a class L of linear loss functions ` : RA → R, and D a family of distributions that are supported over S × L, policy classes ΠW ,Π. A weak supervised learning algorithm, for every ε, δ > 0, given m(ε, δ) samples Dm from any distribution D ∈ D outputs a policyW(Dm) ∈ ΠW such that with probability 1− δ,
E(s,`)∼D [ `(W(Dm)) ] ≥ α max
π∗∈Π E(s,`)∼D
[ `(π∗(s)) ] + (1− α)E(s,`)∼D [ `(πr(s)) ] − ε.
Note that the weak learner outputs a policy in ΠW which is approximately competitive against the class Π. As an additional relaxation, instead of requiring that the weak learning guarantee holds for all distributions, in our setup, it will be sufficient that the weak learning assumption holds over natural distributions. We define these below. Hereafter, we refer to (ΠW , N, T ) as for N,T = O(poly(|A|, (1− γ)−1, ε−1, α−1, log δ−1)) specified later. Assumption 1 (Weak Supervised Learning). The booster has access to a weak supervised learning oracle (Definition 6) over the policy class Π, for some α ∈ (0, 1). Furthermore, the weak learning condition holds only for a class of natural distributions D – D ∈ D if and only if there exists some π ∈ such that
DS(s) = ∫ ` D(s, `)dµ(`) = dπ(s).
In particular, while a natural distribution may have arbitrary distribution over labels, its marginal distribution over states must be realizable as the state distribution of some policy in over the MDP M . Therefore, the complexity of weak learning adapts to the complexity of the MDP itself. As an extreme example, in stochastic contextual bandits where policies do not affect the distribution of states (say d0), it is sufficient that the weak learning condition holds with respect to all couplings of a single distribution d0.
Online Learning. The second model of weak learning we consider requires a stronger assumption, but will give us better sample and oracle complexity bounds henceforth. Definition 7 (Weak Online Learner). Let α ∈ (0, 1). Consider a class L of linear loss functions ` : RA → R. A weak online learning algorithm, for every M > 0, incrementally for each timestep computes a policyWm ∈ ΠW and then observes the state-loss pair (s, `t) ∈ S × L such that
M∑ m=1 `m(Wm(sm)) ≥ α max π∗∈Π M∑ m=1 `m(π ∗(sm)) + (1− α) M∑ m=1 `m(πr(sm))−RW(M).
Assumption 2 (Weak Online Learning). The booster has access to a weak online learning oracle (Definition 7) over the policy class Π, for some α ∈ (0, 1). Remark 8. A similar remark about natural distributions applies to the online weak learner. In particular, it is sufficient the guarantee in 7 holds for arbitrary sequence of loss functions with high probability over the sampling of the state from dπ for some π ∈ . Although stronger than supervised weak learning, this oracle can be interpreted as a relaxation of the online weak learning oracle considered in (Brukhim et al., 2020; Brukhim & Hazan, 2021; Hazan & Singh, 2021). A similar model of hybrid adversarial-stochastic online learning was considered in (Rakhlin et al., 2011; Lazaric & Munos, 2009; Beygelzimer et al., 2011). In particular, it is known (Lazaric & Munos, 2009) that unlike online learning, the capacity of a hypothesis class for this model is governed by its VC dimension (vs. Littlestone dimension).

heading: 4 ALGORITHM & MAIN RESULTS
text: In this section we describe our RL boosting algorithm. Here we focus on the case where a supervised weak learning is provided. The online weak learners variant of our result is detailed in the appendix. We next define several definitions and algorithmic subroutines required for our method.
The Extension Operator. The extension operator (Hazan & Singh, 2021) operate overs functions and modifies their value outside and near the boundary of the convex set ∆A to aid the boosting algorithm.
FG,β [f ](x) = min y∈∆A
{ f(y) +G min
z∈∆A ‖y − z‖+ 1 2β ‖x− y‖2 } To state the results, we need the following definitions. The first generalizes the policy completeness notion from (Scherrer & Geist, 2014). It may be seen as the policy-equivalent analogue of inherent bellman error (Munos & Szepesvári, 2008). Intuitively, it measures the degree to which a policy in Π can best approximate the bellman operator in an average sense with respect to the state distribution induced by a policy from . Definition 9 (Policy Completeness). For any initial state distribution µ, define
Eµ( ,Π) = max π∈ min π∗∈Π Es∼dπµ [ max a∈A Qπ(s, a)−Qπ(s, ·)>π∗(·|s) ] .
The following notion of the distribution mismatch coefficient is often useful to characterize the exploration problem faced by policy optimization algorithms. Definition 10 (Distribution Mismatch). Let π∗ = arg maxπ V π , and ν a fixed initial state distribution (see section 2). Define the following distribution mismatch coefficients:1
C∞( ) = max π∈ ∥∥∥∥dπ∗dπ ∥∥∥∥ ∞ , D∞ = ∥∥∥∥dπ∗ν ∥∥∥∥ ∞ .

heading: 4.1 RL BOOSTING VIA WEAK SUPERVISED LEARNING
text: We give the main RL boosting algorithm, assuming supervised weak learners. We use a simple sub-routine for choosing a step size, provided in the appendix.
Algorithm 1 RL Boosting via Weak Supervised Learning 1: Input parameters T,N,M,P, µ. Initialize a policy π0 ∈ ΠW arbitrarily. 2: for t = 1 to T do 3: Set ρt,0 to be an arbitrary policy in ΠW . 4: for n = 1 to N do 5: Execute πt−1 for M episodes with initial state distribution µ via Algorithm 2, to get
Dt,n = {(si, Q̂i)mi=1}.
6: Modify Dt,n to produce a new dataset D′t,n = {(si, fi)}mi=1, such that for all i ∈ [m]:
fi = −∇FG,β [−Q̂i](ρt,n(·|si))
. 7: Let At,n be the policy chosen by the weak learning oracle when given data set D′t,n. 8: Update ρt,n = (1− η2,n)ρt,n−1 + η2,nα At,n − η2,n ( 1 α − 1 ) πr.
9: end for 10: Declare π′t = Γ [ρt,N ]. 11: Choose η1,t = min{1, 2C∞t } if µ = d0 else η1,t = StepChooser(πt−1, π ′ t, µ, P ). 12: Update πt = (1− η1,t)πt−1 + η1,tπ′t. 13: end for 14: Output π̄=πT if µ = d0 else output πt−1 with the smallest ηt.
1For brevity, We use the shorthand C∞ where clear from context.
Theorem 11. Algorithm 1 samples T (MN +P ) episodes of length Õ( 11−γ ) with probability 1− δ. In the episodic model, for T = O (
C2∞ (1−γ)3ε
) ,N = ( 16|A|C∞ (1−γ)2α )2 ,M = m ( (1−γ)2αε C∞|A| , δ NT ) ,µ = d0,

heading: P = 0, with probability 1− δ,
text: V ∗ − V π ≤ C∞ E( ,Π) 1− γ + ε.
In the ν-reset model, for T = 8D 2 ∞ (1−γ)6ε2 , N = ( 16|A|D∞ (1−γ)3α )2 , P = Õ( 200|A| 2D2∞ (1−γ)6ε2 ), M =
m (
(1−γ)3αε 8|A|D∞ , δ 2NT
) ,µ = ν, with probability 1− δ,
V ∗ − V π ≤ D∞ Eν( ,Π) (1− γ)2 + ε.

heading: 4.2 TRAJECTORY SAMPLER
text: In Algorithm 2 we describe an episodic sampling procedure, that is used in our sample-based RL boosting algorithms described above. For a fixed initial state distribution µ, and any given policy π, we apply the following sampling procedure: start at an initial state s0 ∼ µ, and continue to act thereafter in the MDP according to any policy π, until termination. With this process, it is straightforward to both sample from the state visitation distribution s ∼ dπ , and to obtain unbiased samples of Qπ(s, ·); see Algorithm 2 for the detailed process.
Algorithm 2 Trajectory Sampler: s ∼ dπ , unbiased estimate of Qπs 1: Sample state s0 ∼ µ, and action a′ ∼ U(A) uniformly. 2: Sample s ∼ dπ as follows: at every timestep h, with probability γ, act according to π; else,
accept sh as the sample and proceed to Step 3. 3: Take action a′ at state sh, then continue to execute π, and use a termination probability of 1−γ.
Upon termination, set R(sh, a′) as the undiscounted sum of rewards from time h onwards. 4: Define the vector Q̂πsh , such that for all a ∈ A, Q̂πsh(a) = |A| ·R(sh, a
′) · Ia=a′ . 5: return (sh, Q̂πsh).

heading: 5 ANALYSIS – PROOF SKETCH
text: We sketch the high-level ideas of the proof of our main result, stated in Theorem 11, and refer the reader to the appendix for the formal proof. Throughout the analysis, we use the notation ∇πV π to denote the gradient of the value function with respect to the |S| × |A|-sized representation of the policy π, namely the functional gradient of V π .
We establish an equivalence between the outlined algorithm and an abstraction of the Frank-Wolfe algorithm (Algorithm D) from optimization theory. This variant of the Frank-Wolfe (FW) algorithm operates over non-convex and gradient dominated functions to obtain the following novel convergence guarantees. We establish the necessary gradient domination results from the policy completeness results. Theorem 12. Let f : K → R be L-smooth in some norm ‖ · ‖∗, H-bounded, and the diameter of K in ‖ · ‖∗ be D. Then, for a ( 0,K2)-linear optimization oracle, the output x̄ of Algorithm D satisfies
max u∈K2
∇f(x̄)>(u− x̄) ≤ √ 2HLD2
T + 3 + 0.
Furthermore, if f is (κ, τ,K1,K2)-locally gradient-dominated and x0, . . . xT ∈ K1, then it holds
max x∗∈K
f(x∗)− f(x̄) ≤ 2κ 2 max{LD2, H}
T + τ + κ 0.
The Frank-Wolfe algorithm utilizes an inner gradient optimization oracle as a subroutine. To implement this oracle using approximate optimizers, we utilize yet another variant of the FW method as “internal-boosting” for the weak learners (by employing an adapted analysis of Theorem 13).

heading: 5.1 INTERNAL-BOOSTING WEAK LEARNERS
text: We utilize a variant of the Frank-Wolfe method as a form “internal-boosting” for the weak learners, by employing an adapted analysis of previous work that is stated below.
Note that Q̂π(s, ·) produced by Algorithm 2 satisfies ‖Q̂π(s, ·)‖ = |A|1−γ . We can now borrow the following result on boosting for statistical learning from (Hazan & Singh, 2021), specializing the decision set to be ∆A. Let Dt be the distribution induced by the trajectory sampler in round t.
Theorem 13 ((Hazan & Singh, 2021)). Let β = √
1 αN , and η2,n = min{ 2 n , 1}. Then, for any t, π ′ t
produced by Algorithm 1 satisfies with probability 1− δ that
max π∈Π
E(s,Q)∼Dt [ Q>π(s) ] − E(s,Q)∼Dt [ Q>π′t(s) ] ≤ 2|A|
(1− γ)α ( 2√ N + ε )

heading: 5.2 FROM WEAK LEARNING TO LINEAR OPTIMIZATION
text: In the following Lemma, we give an important observation which allows us to re-state the guarantee in the previous subsection in terms of linear optimization over functional gradients. Lemma 14. Applying Algorithm 2 for any given policy π, yields an unbiased estimate of the gradient, such that for any π′,
(∇πV πµ )>π′ = 1
1− γ E (s,Q̂π(s,·))∼D
[ Q̂π(s, ·)>π′(·|s) ] , (2)
where π′(·|s) ∈ ∆A, and D is the distribution induced on the outputs of Algorithm 2, for a given policy π and initial state distribution µ.
Proof. Recall ∇πV π denotes the gradient with respect to the |S| × |A|-sized representation of the policy π – the functional gradient. Then, using the policy gradient theorem (Williams, 1992; Sutton et al., 2000), it is given by,
∂V πµ ∂π(a|s) = 1 1− γ dπµ(s)Q π(s, a). (3)
The following sources of randomness are at play in the sampling algorithm (Algorithm 2): the distribution dπ (which encompasses the discount-factor-based random termination, the transition probability, and the stochasticity of π), and the uniform sampling over A. For a fixed s, π, denote by Qπs as the distribution over Q̂π(s, ·) ∈ RA, induced by all the aforementioned randomness sources. To conclude the claim, observe that by construction
EQπ(s,·)[Q̂π(s, ·)|π, s] = Qπ(s, ·). (4)

heading: 6 CONCLUSIONS
text: Building on recent advances in boosting for online convex optimization and bandits, we have described a boosting algorithm for reinforcement learning over large state spaces with provable guarantees. We see this as a first attempt at using a tried-and-tested methodology from supervised learning in RL, and many challenges remain.
First and foremost, our notion of weak learner optimizes a linear function over policy space. A more natural weak learner would be an RL agent with multiplicative optimality guarantee, and it would be interesting to extend our methodology to this notion of weak learnability.
Another important aspect that is not discussed in our paper is that of state-space exploration. Potentially boosting can be combined with state-space exploration techniques to give stronger guarantees independent of distribution mismatch C∞, D∞ factors.
Finally, a feature of our method is that it produces nonlinear aggregations of weak learners as per a two layer neural network. Are simpler aggregations with provable guarantees possible?

heading: A APPENDIX
text: It is important that the policy that the boosting algorithm outputs can be evaluated efficiently. Towards that end, we give the following claim.
Claim 15. For any π ∈ (Π, N, T ), π(·|s) for any s ∈ S can be evaluated using TN base policy evaluations and O(T × (NA+A logA)) arithmetic and logical operations.
Proof. Since π ∈ (Π, N, T ), it is composed of TN base policies. Producing each aggregated function takes NA additions and multiplications; there are T of these. Each projection takes time equivalent to sorting |A| numbers, due to a water-filling algorithm (Duchi et al., 2008); these are also T in number. The final linear transformation takes an additional TA operations.

heading: B STEP-SIZE SUBROUTINE
text: Below we give an algorithm for choosing step sizes used in both of the RL boosting methods (for online, and supervised, weak learners).
Algorithm 3 StepChooser(πt−1, π′t, µ, P ) 1: Execute πt−1 for P episodes with initial state distribution µ via Algorithm 2, to get
D = {(si, Q̂i)Pi=1}.
2: For any policy π, let Ĝπ = 1P ∑P p=1 Q̂i > π(·|si). 3: Return
η1,t = clip[0,1]
( (1− γ)2
2
( Ĝπ ′ t − Ĝπt−1 ))

heading: C RL BOOSTING VIA WEAK ONLINE LEARNING
text: Algorithm 4 RL Boosting via Weak Online Learning 1: Initialize a policy π0 ∈ ΠW arbitrarily. 2: for t = 1 to T do 3: Initialize online weak learnersW1, . . .WN . 4: for m = 1 to M do 5: Execute πt−1 once with initial state distribution µ via Algorithm 2, to get (st,m, Q̂t,m). 6: Choose ρt,m,0 ∈ ΠW arbitrarily. 7: for n = 1 to N do 8: Set ρt,m,n = (1− η2,n)ρt,m,n−1 + η2,nα W n − η2,n ( 1 α − 1 ) πr.
9: end for 10: Pass to eachWn the following loss linear ft,m,n:
ft,m,n = −∇FG,β [−Q̂t,m](ρt,m,n(·|si))
11: end for 12: Declare π′t = 1 M ∑M m=1 Γ [ρt,m,N ]. 13: Choose η1,t = min{1, 2C∞( )t } if µ = d0 else set η1,t = StepChooser(πt−1, π ′ t, µ, P ). 14: Update πt = (1− η1,t)πt−1 + η1,tπ′t. 15: end for 16: Output π̄= πT if µ = d0 else output πt−1 with the smallest ηt.
Theorem 16. Algorithm 4 samples T (M +P ) episodes of length 11−γ log T (M+P ) δ with probability 1−δ. In the episodic model, Algorithm 4 guarantees as long as T = 16C 2 ∞( ) (1−γ)3ε ,N = ( 16|A|C∞( ) (1−γ)2α )2 ,
M = max {
1000|A|2C2∞( ) (1−γ)4ε2α2 log 2 Tδ, 8|A|C∞( )RW(M)(1−γ)2αε } ,µ = d0, we have with probability 1− δ
V ∗ − V π ≤ C∞( ) E( ,Π) 1− γ + ε
In the ν-reset model, Algorithm 1 guarantees as long as T = 100D 2 ∞ (1−γ)6ε2 , N = ( 20|A|D∞ (1−γ)3α )2 ,
P = 250D2∞|A| 2
(1−γ)6ε2 log 2 T δ , M = max {( 40|A|D∞ (1−γ)3αε log T δ )2 , 10|A|D∞RW(M)(1−γ)3αε } ,µ = ν, we have with
probability 1− δ
V ∗ − V π ≤ D∞ Eν( ,Π) (1− γ)2 + ε
If RW(M) = √ M log |W| for some measure of weak learning complexity |W|, the algorithm
samples Õ ( C4∞( )|A|
2 log |W| (1−γ)7α2ε3
) episodes in the episodic model, and Õ ( D4∞|A|
2 log |W| (1−γ)12α2ε4
) in the ν-
reset model.

heading: D NON-CONVEX FRANK-WOLFE
text: In this section, we give an abstract high-level procedural template that the previously introduced RL boosters operate in. This is based on a variant of the Frank-Wolfe optimization technique, adapted to non-convex and gradient dominated function classes (see Definition 1).
The Frank-Wolfe (FW) method assumes oracle access to a black-box linear optimizer, denoted O, and utilizes it by iteratively making oracle calls with modified objectives, in order to solve the harder task of convex optimization. Analogously, boosting algorithms often assume oracle access to a ”weak” learner, which are utilized by iteratively making oracle calls with modified objective, in order to obtain a ”strong” learner, with boosted performance. In the RL setting, the objective is in fact non-convex, but exhibits gradient domination. By adapting Frank-Wolfe technique to this setting, we will in subsequent section obtain guarantees for the algorithms given in Section 4.
Setting. Denote by O a black-box oracle to an ( 0,K2)-approximate linear optimizer over a convex set K ⊆ Rd such that for any given v ∈ Rd, we have
v>O(v) ≥ max u∈K2 v>u− 0.
Algorithm 5 Non-convex Frank-Wolfe 1: Input: T > 0, objective f , linear optimization oracle O 2: Choose x0 arbitrarily. 3: for t = 1, . . . , T do 4: Call zt = O(∇t−1), where ∇t−1 = ∇f(xt−1). 5: Choose ηt = min{1, 2κt } in the gradient-dominated case, else choose ηt so that
|LD2ηt −∇>t−1(zt − xt−1)| ≤ .
6: Set xt = (1− ηt)xt−1 + ηtzt. 7: end for 8: return x̄ = xT in the gradient-dominated case, else xt−1 with the smallest ηt.
Theorem 17. Let f : K → R be L-smooth in some norm ‖ · ‖∗, H-bounded, and the diameter of K in ‖ · ‖∗ be D. Then, for a ( 0,K2)-linear optimization oracle, the output x̄ of Algorithm D satisfies
max u∈K2
∇f(x̄)>(u− x̄) ≤ √ 2HLD2
T + 3 + 0.
Furthermore, if f is (κ, τ,K1,K2)-locally gradient-dominated and x0, . . . xT ∈ K1, then it holds
max x∗∈K
f(x∗)− f(x̄) ≤ 2κ 2 max{LD2, H}
T + τ + κ 0.

heading: E ANALYSIS FOR BOOSTING WITH SUPERVISED LEARNING (PROOF OF
text: THEOREM 11)
Theorem (Formal version of Theorem 11). Algorithm 1 samples T (MN + P ) episodes of length 1
1−γ log T (MN+P ) δ with probability 1− δ. In the episodic model, Algorithm 1 guarantees as long as T = 16C2∞( ) (1−γ)3ε , N = ( 16|A|C∞( ) (1−γ)2α )2 , M = m ( (1−γ)2αε 8C∞( )|A| , δ NT ) ,µ = d0, we have with probability 1− δ V ∗ − V π ≤ C∞( )
E( ,Π) 1− γ + ε
In the ν-reset model, Algorithm 1 guarantees as long as T = 8D 2 ∞ (1−γ)6ε2 , N = ( 16|A|D∞ (1−γ)3α )2 , P = 200|A|2D2∞ (1−γ)6ε2 log 2TN δ , M = m ( (1−γ)3αε 8|A|D∞ , δ 2NT ) ,µ = ν, we have with probability 1− δ
V ∗ − V π ≤ D∞ Eν( ,Π) (1− γ)2 + ε
Ifm(ε, δ) = log |W|ε2 log 1 δ for some measure of weak learning complexity |W|, the algorithm samples Õ ( C6∞( )|A|
4 log |W| (1−γ)11α4ε5
) episodes in the episodic model, and Õ ( D6∞|A|
4 log |W| (1−γ)18α4ε6
) in the ν-reset model.
Proof of Theorem 11. The broad scheme here is to utilize an equivalence between Algorithm 1 and Algorithm D on the function V π (or V πν in the ν-reset model), to which Theorem 17 applies.
To this end, firstly, note V π is 11−γ -bounded. Define a norm ‖ · ‖∞,1 : R |S|×|A| → R as ‖x‖1,∞ = maxs∈S ∑ a∈A |xs,a|. Further, observe that for any policy π : S → ∆A, ‖π‖∞,1 = 1. The following lemma specifies the smoothness of V π in this norm.
Lemma 18. V π is 2γ(1−γ)3 -smooth in the ‖ · ‖∞,1 norm.
To be able to interpret Algorithm 1 as an instantiation of the algorithmic template Algorithm D presents, we advance two claims: one, the step-size choices of the two algorithms conincide; two, π′t (Line 3-10) serves as an approximate linear optimizers for ∇V πt−1 . Together, these imply that the iterates produced by the two algorithms conincide. The first of these, which provides a value of to use in the statement of Theorem 17, is established below.
Claim 19. Upon every invocation of StepChooser, the output η1,t satisfies with probability 1−δ∣∣∣∣ 2η1,t(1− γ)3 − (∇V πt−1µ )>(π′t − πt−1) ∣∣∣∣ ≤ 16|A|(1− γ)2√P log 1δ
Next, we move onto the linear optimization equivalence. Indeed, Claim 20 demonstrates that π′t serves a linear optimizer over gradients of the function V π; the suboptimality specifies 0.
Claim 20. Let β = √
1 αN , and η2,n = min{ 2 n , 1}. Then, for any t, π ′ t produced by Algorithm 1
satisfies with probability 1− δ
max π∈Π
(∇V πt−1µ )>(π − π′t) ≤ 2|A|
(1− γ)2α ( 2√ N + εW ) Finally, observe that it is by construction that πt ∈ . Therefore, in terms of the previous section, K is the class of all policies, K1 = , K2 = Π. In the episodic model, we wish to invoke the second part of Theorem 17. The next lemma establishes gradient-domination properties of V π to support this.
Lemma 21. V π is ( C∞( ), 11−γC∞( )E(Π, ), ,Π ) -gradient dominated, i.e. for any π ∈ :
V ∗ − V π ≤ C∞( ) ( 1
1− γ E(Π, ) + max π′∈Π (∇V π)>(π′ − π)
)
Deriving κ, τ from the above lemma along with 0 from Claim 20 and from Claim 19, as a consequence of the second part of Theorem 17, we have with probability 1−NTδ
V ∗ − V π̄ ≤ C∞( ) E( ,Π) 1− γ + 4C2∞( ) (1− γ)3T + 4|A|C∞( ) (1− γ)2α √ N + 2|A|C∞( ) (1− γ)2α εW .
Similarly, in the ν-reset model, the first part of Theorem 17 provides a local-optimality guarantee for V πν . Lemma 22 provides a bound on the function-value gap (on V
π) provided such local-optimality conditions.
Lemma 22. For any π ∈ , we have
V ∗ − V π ≤ 1 1− γ D∞
( 1
1− γ Eν(Π, ) + max π′∈Π (∇V πν )>(π′ − π)
)
Again, using the bound on maxπ′∈Π(∇V π̄ν )>(π′ − π̄) Theorem 17 provides, we have that with probability 1− 2NTδ
V ∗ − V π̄ ≤ D∞Eν( ,Π) (1− γ)2 + 2D∞ (1− γ)3 √ T + 2|A|D∞ (1− γ)3α ( 2√ N + εW ) + 48|A|D∞ (1− γ)3 √ P log 1 δ

heading: F ANALYSIS FOR BOOSTING WITH ONLINE LEARNING (PROOF OF
text: THEOREM 16)
Proof of Theorem 16. Similar to the proof of Theorem 11, we establish an equivalence between Algorithm 1 and Algorithm D on the function V π (or V πν in the ν-reset model), to which Theorem 17 applies provided smoothness (see Lemma 18).
Indeed, Claim 23 demonstrates π′t serves a linear optimizer over gradients of the function V π , and provides a bound on 0. Claim 19 ensures that that the step size choices (and hence iterates) of the two algorithms coincide. As before, observe that it is by construction that πt ∈ . Claim 23. Let β = √
1 αN , and η2,n = min{ 2 n , 1}. Then, for any t, π ′ t produced by Algorithm 4
satisfies with probability 1− δ
max π∈Π
(∇V πt−1µ )>(π − π′t) ≤ 2|A|
(1− γ)2α ( 2√ N + RW(M) M + √ 16 log δ−1 M )
In the episodic model, one may combine the second part of Theorem 17, which provides a bound on function-value gap for gradient dominated functions, which Lemma 21 guarantees, to conclude with probability 1− Tδ
V ∗ − V π̄ ≤ C∞( )E( ,Π) 1− γ + 4C2∞( ) (1− γ)3T + 4|A|C∞( ) (1− γ)2α √ N + 2|A|C∞( ) (1− γ)2α RW(M) M + 8|A|C∞( ) log δ−1 (1− γ)2α √ M .
Similarly, in the ν-reset model, Lemma 22 provides a bound on the function-value gap provided local-optimality conditions, which the first part of Theorem 17 provides for. Again, with probability 1− Tδ
V ∗ − V π̄ ≤ D∞Eν( ,Π) (1− γ)2 + 2D∞ (1− γ)3 ( 1√ T + |A| α ( 2√ N + RW(M) M + 4 log δ−1√ M ) + 24|A|√ P log 1 δ )

heading: G PROOFS OF SUPPORTING CLAIMS
text: G.1 NON-CONVEX FRANK-WOLFE METHOD (THEOREM 17)
Proof of Theorem 17. Non-convex case. Note that for any timestep t, it holds due to smoothness that
f(xt) = f(xt−1 + ηt(zt − xt−1))
≥ f(xt−1) + ηt∇>t−1(zt − xt−1)− η2t L
2 D2
= f(xt−1)− 1 2LD2 ( LD2ηt −∇>t−1(zt − xt−1) )2 + (∇>t−1(zt − xt−1))2 2LD2
Using the step-size definition to bound on the middle term, and telescoping this inequality over function-value differences across successive iterates, we have
min t
(∇>t−1(zt − xt−1))2 ≤ 1
T T∑ t=1 (∇>t−1(zt − xt−1))2 ≤ 2LD2H T + 2
Let t′ = arg mint ηt and t ∗ = arg mint(∇>t−1(zt − xt−1))2. Then
∇>t′−1(zt′ − xt′−1) ≤ LD2ηt′ + ≤ LD2ηt∗ + ≤ ∇>t∗−1(zt∗ − xt∗−1) + 2 ≤ √ 2LD2H
T + 2 + 2
To conclude the claim for the non-convex part, observe √ a+ b ≤ √ a+ √ b for a, b > 0, and that since zt′ = O(∇t′−1), it follows by oracle definition that max u∈K2 ∇>t′−1u ≤ ∇>t′−1zt′ + 0.
Gradient-Dominated Case. Define x∗ = arg maxx∈K f(x) and ht = f(x∗)− f(xt).
ht ≤ ht−1 − ηt∇>t−1(zt − xt−1) + η2t L
2 D2 smoothness
≤ ht−1 − ηt max y∈K2
ηt∇>t−1(y − xt−1) + η2t L
2 D2 + ηt 0 oracle
≤ ht−1 − ηt κ (f(x∗)− f(xt−1)) + η2t L 2 D2 + ηt
( 0 + τ
κ
) gradient domination
= (
1− ηt κ
) ht−1 + η 2 t L
2 D2 + ηt
( 0 + τ
κ ) The theorem now follows from the following claim.
Claim 24. Let C ≥ 1. Let gt be a H-bounded positive sequence such that gt ≤ (
1− σt C
) gt−1 + σ 2 tD + σtE.
Then choosing σt = min{1, 2Ct } implies gt ≤ 2C2 max{2D,H} t + CE.
G.2 SMOOTHNESS OF VALUE FUNCTION (LEMMA 18)
Proof of Lemma 18. Consider any two policies π, π′. Using the Performance Difference Lemma (Lemma 3.2 in (Agarwal et al., 2019), e.g.) and Equation 2, we have
|V π ′ − V π −∇V π(π′ − π)|
= 1 1− γ ∣∣Es∼dπ′ [Qπ(·|s)>(π′(·|s)− π(·|s)]− Es∼dπ [Qπ(·|s)>(π′(·|s)− π(·|s)]∣∣
≤ 1 (1− γ)2 ‖dπ ′ − dπ‖1‖π′ − π‖∞,1
The last inequality uses the fact that maxs,aQπ(s, a) ≤ 11−γ . It suffices to show ‖d π′ − dπ‖1 ≤ γ1−γ ‖π ′ − π‖∞,1. To establish this, consider the Markov operator Pπ(s′|s) =∑
a∈A P (s ′|s, a)π(a|s) induced by a policy π on MDP M . For any distribution d supported on
S, we have
‖(Pπ ′ − Pπ)d‖1 = ∑ s′ ∣∣∣∣∣∑ s,a P (s′|s, a)d(s)(π′(a|s)− π(a|s) ∣∣∣∣∣ ≤ ∑ s′ P (s′|s, a)‖d‖1‖π′ − π‖∞,1 ≤ ‖π′ − π‖∞,1
Using sub-additivity of the l1 norm and applying the above observation t times, we have for any t
‖((Pπ ′ )t − (Pπ)t)d‖1 ≤ t‖π′ − π‖∞,1.
Finally, observe that
‖dπ ′ − dπ‖1 ≤ (1− γ) ∞∑ t=0 γt‖((Pπ ′ )t − (Pπ)t)d0‖1
≤ ‖π′ − π‖∞,1(1− γ) ∞∑ t=0 tγt = γ 1− γ ‖π′ − π‖∞,1
G.3 STEP-SIZE GUARANTEE (CLAIM 19)
Proof of Claim 19. Let D be the distribution induced by Algorithm 2 upon being given πt−1. Due to Lemma 14, it suffices to demonstrate that for any π ∈ {π′t, πt−1} the following claim holds with probability 1 − δ2 . The claim in turn follows from Hoeffding’s inequality, while noting Q̂πt−1(s, ·) is |A|1−γ -bounded in the l∞ norm.∣∣∣Ĝπ − E
(s,Q̂πt−1 (s,·))∼D
[ Q̂πt−1(s, ·)>π(·|s) ]∣∣∣ ≤ 8|A| (1− γ) √ P log 1 2δ
G.4 GRADIENT DOMINATION (LEMMA 21 AND LEMMA 22)
Proof of Lemma 21. Invoking Lemma 4.1 from (Agarwal et al., 2019) with µ = d0, we have V ∗ − V π ≤ ∥∥∥∥dπ∗dπ ∥∥∥∥ ∞ max π0 (∇V π)>(π0 − π)
≤ C∞( )(max π0 (∇V π)>π0 −max π′∈Π (∇V π)>π′ + max π′∈Π (∇V π)>(π′ − π))
Finally, with the aid of Equation 2, observe that
max π0 (∇V π)>π0 −max π′∈Π (∇V π)>π′ = min π′∈Π
1
1− γ Es∼dπ [ max a Qπ(s, a)−Qπ(·|s)>π′ ]
≤ 1 1− γ E(Π, )
Proof of Lemma 22. Invoking Lemma 4.1 from (Agarwal et al., 2019) with µ = ν, we have
V ∗ − V π ≤ 1 1− γ ∥∥∥∥dπ∗ν ∥∥∥∥ ∞ max π0 (∇V πν )>(π0 − π)
≤ 1 1− γ D∞(max π0 (∇V πν )>π0 −max π′∈Π (∇V πν )>π′ + max π′∈Π (∇V πν )>(π′ − π))
Again, with the aid of Equation 2, observe that
max π0 (∇V πν )>π0 −max π′∈Π (∇V πν )>π′ = min π′∈Π
1
1− γ Es∼dπν [ max a Qπ(s, a)−Qπ(·|s)>π′ ]
≤ 1 1− γ Eν(Π, )
G.5 SUPERVISED LINEAR OPTIMIZATION GUARANTEES (CLAIM 20)
Proof of Claim 20. The subroutine presented in lines 3-10 (which culminate in π′t) is an instantiation of Algorithm 3 from (Hazan & Singh, 2021), specializing the decision set to be ∆A. To note the equivalence, note that in (Hazan & Singh, 2021) the algorithm is stated assuming that the center-ofmass of the decision set is at the origin (after a coordinate transform); correspondingly, the update rule in Algorithm 1 can be written as
(ρt,n − πr) = (1− η2,n)(ρt,n−1 − πr) + η2,n α (At,n − πr).
For any state s, πr(·|s) = 1A1|A| corresponds to the center-of-masss of ∆A. Finally, note that maximizing f>x over x ∈ K is equivalent to minimizing (−f)>x over the same domain. Therefore, we can borrow the following result on boosting for statistical learning from (Hazan & Singh, 2021) (Theorem 13). Note that Q̂π(s, ·) produced by Algorithm 2 satisfies ‖Q̂π(s, ·)‖ = |A|1−γ . Let Dt be the distribution induced by the trajectory sampler in round t.
Theorem 25 ((Hazan & Singh, 2021)). Let β = √
1 αN , and η2,n = min{ 2 n , 1}. Then, for any t, π ′ t
produced by Algorithm 1 satisfies with probability 1− δ that
max π∈Π
E(s,Q)∼Dt [ Q>π(s) ] − E(s,Q)∼Dt [ Q>π′t(s) ] ≤ 2|A|
(1− γ)α ( 2√ N + ε ) Lemma 14 allows us to restate the guarantees in the previous subsection in terms of linear optimization over functional gradients. The conclusion thus follows immediately by combining Lemma 14 and Theorem 25.
G.6 ONLINE LINEAR OPTIMIZATION GUARANTEES (CLAIM 23)
Proof of Claim 23. In a similar vein to the proof of Claim 20, here we state the a result on boosting for online convex optimization (OCO) from (Hazan & Singh, 2021) (Theorem 6), the counterpart of Theorem 13 for the online weak learning case.
Theorem 26 ((Hazan & Singh, 2021)). Let β = √
1 αN , and η2,n = min{ 2 n , 1}. Then, for any t,
Γ[ρt,m,N ] produced by Algorithm 4 satisfies
max π∈Π M∑ m=1 [ Q̂>t,mπ(st,m) ] − M∑ m=1 [ Q̂>t,mΓ[ρt,m,N ](st,m) ] ≤ 2|A| (1− γ)α ( 2M√ N +RW(M) )
Next we invoke online-to-batch conversions. Note that in Algorithm 4, (st,m, Q̂t,m) for any fixed t is sampled i.i.d. from the same distribution. Therefore, we can apply online-to-batch results, i.e. Theorem 9.5 in (Hazan, 2019), on Theorem 26 to get
max π∈Π
E(s,Q)∼Dt [ Q>π(s) ] −E(s,Q)∼Dt [ Q>π′t(s) ] ≤ 2|A|
(1− γ)α ( 2√ N + RW(M) M + √ 16 log δ−1 M ) We finally invoke Lemma 14.
G.7 REMAINING PROOFS (CLAIM 24)
Proof of Claim 24. Let T ∗ = arg maxt{t : t ≤ 2C}. For any t ≤ T ∗, we have σt = 1 and gt ≤ H ≤ 2C 2H t . For t ≥ T ∗, we proceed by induction. The base case (t = T ∗) is true by the previous display. Now, assume gt−1 ≤ 2C 2 max{2D,H} t−1 + CE for some t > T ∗.
gt ≤ (
1− 2 t
)( 2C2 max{2D,H}
t− 1 + CE
) + 4C2D
t2 +
2CE
t ≤ CE + 2C2 max{2D,H} ( 1
t− 1
( 1− 2
t
) + 1
t2 ) = CE + 2C2 max{2D,H} t
2 − 2t+ t− 1 t2(t− 1)
≤ CE + 2C2 max{2D,H} t(t− 1) t2(t− 1)

Review summaries:
In this paper, the authors study boosting in RL, i.e., how to convert weak learners into effective policies. The authors provide an algorithm that improves the accuracy of the weak learners iteratively, and the sample complexity and running time do not explicitly depend on the number of states.   In order to overcome the non-convexity of the value function (with respect to the policy space), the authors use a non-convex variant of the Frank-Wolfe method together with recent advances in gradient boosting. 

This paper proposes a new approach for solving RL problems with sample complexity independent of the number of states. Rather than imposing structural assumptions, the authors consider access to weak learners and propose a way to combine these weak learners effectively to generate a near optimal policy. The sample complexity result is competitive and does not depend on the number of states, under the assumption of access to weak learners.