Fast Policy Learning through Imitation and Reinforcement

INTRODUCTION

Reinforcement learning (RL) has emerged as a promising technique to tackle complex sequential decision problems. When empowered with deep neural networks, RL has demonstrated impressive performance in a range of synthetic domains (Mnih et al.,, 2013; Silver et al.,, 2017). However, one of the major drawbacks of RL is the enormous number of interactions required to learn a policy. This can lead to prohibitive cost and slow convergence when applied to real-world problems, such as those found in robotics (Pan et al.,, 2017).

Imitation learning (IL) has been proposed as an alternate strategy for faster policy learning that works by leveraging additional information provided through expert demonstrations (Pomerleau,, 1989; Schaal,, 1999). However, despite significant recent breakthroughs in our understanding of imitation learning (Ross et al.,, 2011; Cheng and Boots,, 2018), the performance of IL is still highly dependent on the quality of the expert policy. When only a suboptimal expert is available, policies learned with standard IL can be inferior to the policies learned by tackling the RL problem directly with approaches such as policy gradients.

Several recent attempts have endeavored to combine RL and IL (Ross and Bagnell,, 2014; Chang et al.,, 2015; Nair et al.,, 2017; Rajeswaran et al.,, 2017; Sun et al.,, 2018). These approaches incorporate the cost information of the RL problem into the imitation process, so the learned policy can both improve faster than their RL-counterparts and outperform the suboptimal expert policy. Despite reports of improved empirical performance, the theoretical understanding of these combined algorithms are still fairly limited (Rajeswaran et al.,, 2017; Sun et al.,, 2018). Furthermore, some of these algorithms have requirements that can be difficult to satisfy in practice, such as state resetting (Ross and Bagnell,, 2014; Chang et al.,, 2015).

In this paper, we aim to provide an algorithm that combines the best aspects of RL and IL. We accomplish this by first formulating first-order RL and IL algorithms in a common mirror descent framework, and show that these algorithms can be viewed as a single approach that only differs in the choice of first-order oracle. On the basis of this new insight, we address the difficulty of combining IL and RL with a simple, randomized algorithm, named loki (Locally Optimal search after $K$-step Imitation). As its name suggests, loki operates in two phases: picking $K$ randomly, it first performs $K$ steps of online IL and then improves the policy with a policy gradient method afterwards. Compared with previous methods that aim to combine RL and IL, loki is extremely straightforward to implement. Furthermore, it has stronger theoretical guarantees: by properly randomizing $K$, loki performs as if directly running policy gradient steps with the expert policy as the initial condition. Thus, not only can loki improve faster than common RL methods, but it can also significantly outperform a suboptimal expert. This is in contrast to previous methods, such as AggreVatTe (Ross and Bagnell,, 2014), which generally cannot learn a policy that is better than a one-step improvement over the expert policy. In addition to these theoretical contributions, we validate the performance of loki in multiple simulated environments. The empirical results corroborate our theoretical findings.

PROBLEM DEFINITION

We generally will not deal with the objective function in (1) directly. Instead, we consider a surrogate problem

By the performance difference lemma below (Kakade and Langford,, 2002), it is easy to see that solving (2) is equivalent to solving (1).

(Kakade and Langford,, 2002) Let $\pi$ and $\pi^{\prime}$ be two policies and $A_{\pi^{\prime}}(s,a)=Q_{\pi^{\prime}}(s,a)-V_{\pi^{\prime}}(s)$ be the (dis)advantage function with respect to running $\pi^{\prime}$. Then it holds that

FIRST-ORDER RL AND IL

We formulate both first-order RL and IL methods within a single mirror descent framework (Nemirovski et al.,, 2009), which includes common update rules (Sutton et al.,, 2000; Kakade,, 2002; Peters and Schaal,, 2008; Peters et al.,, 2010; Rawlik et al.,, 2012; Silver et al.,, 2014; Schulman et al., 2015b, ; Ross et al.,, 2011; Sun et al.,, 2017). We show that policy updates based on RL and IL mainly differ in first-order stochastic oracles used, as summarized in Table 1.

We begin by defining the iterative rule to update policies. We assume that the learner’s policy $\pi$ is parametrized by some $\theta\in\Theta$, where $\Theta$ is a closed and convex set, and that the learner has access to a family of strictly convex functions $\mathcal{R}$.

To update the policy, in the $n$th iteration, the learner receives a vector $g_{n}$ from a first-order oracle, picks $R_{n}\in\mathcal{R}$, and then performs a mirror descent step:

where $P_{n,g_{n}}$ is a prox-map defined as

$\eta_{n}$ is the step size, and $D_{R_{n}}$ is the Bregman divergence associated with $R_{n}$ (Bregman,, 1967): $D_{R_{n}}(\theta||\theta_{n})\coloneqq R_{n}(\theta)-R_{n}(\theta_{n})-\langle\nabla R_{n}(\theta_{n}),\theta-\theta_{n}\rangle$.

By choosing proper $R_{n}$, the mirror descent framework in (4) covers most RL and IL algorithms. Common choices of $R_{n}$ include negative entropy (Peters et al.,, 2010; Rawlik et al.,, 2012), $\frac{1}{2}\|\theta\|_{2}^{2}$ (Sutton et al.,, 2000; Silver et al.,, 2014), and $\frac{1}{2}\theta^{\top}F(\theta_{n})\theta$ with $F(\theta_{n})$ as the Fisher information matrix (Kakade,, 2002; Peters and Schaal,, 2008; Schulman et al., 2015a, ).

2 FIRST-ORDER ORACLES

A standard approach to RL is to treat (1) as a stochastic nonconvex optimization problem. In this case, $g_{n}$ in mirror descent (4) is an estimate of the policy gradient $\nabla_{\theta}J(\pi)$ (Williams,, 1992; Sutton et al.,, 2000).

For deterministic policies, we replace the expectation as evaluation (as it is the expectation over a Dirac delta function, i.e. $a=\pi(s)$) and use the chain rule:

Substituting (7) or (8) back into (3.2.1), we get the equation for stochastic policy gradient (Sutton et al.,, 2000) or deterministic policy gradient (Silver et al.,, 2014). Note that the above equations require the exact knowledge, or an unbiased estimate, of $A_{\pi}$. In practice, these terms are further approximated using function approximators, leading to biased gradient estimators (Konda and Tsitsiklis,, 2000; Schulman et al., 2015b, ; Mnih et al.,, 2016).

2.2 Imitation Gradients

Rather than solving the stochastic nonconvex optimization directly, online IL solves an online learning problem with per-round cost in the $n$th iteration defined as

By Lemma 1, this implies $J(\pi_{n})\leq J(\pi^{*})+\frac{C_{\pi^{*}}}{1-\gamma}l_{n}(\pi_{n})$. Namely, in the $n$th iteration, online IL attempts to minimize an online upper-bound of $J(\pi_{n})$.

First-order online IL methods operate by updating policies with mirror descent (4) with $g_{n}$ as an estimate of

Similarly, we can turn DAgger into a first-order method, which we call DAggereD, by using $g_{n}$ as an estimate of the first-order oracle

THEORETICAL COMPARISON

With the first-order oracles defined, we now compare the performance and properties of performing mirror descent with policy gradient or imitation gradient. We will see that while both approaches share the same update rule in (4), the generated policies have different behaviors: using policy gradient generates a monotonically improving policy sequence, whereas using imitation gradient generates a policy sequence that improves on average. Although the techniques used in this section are not completely new in the optimization literature, we specialize the results to compare performance and to motivate loki in the next section. The proofs of this section are included in Appendix B.

We analyze the performance of policy gradients with standard techniques from nonconvex analysis.

where the expectation is due to randomness of sampling $g_{n}$, and $\hat{\nabla}_{\theta}J(\pi_{n})\coloneqq\frac{1}{\eta_{n}}\left(\theta_{n}-P_{n,\nabla_{\theta}J(\pi_{n})}(\theta_{n})\right)$. is a gradient surrogate.

Proposition 1 shows that monotonic improvement can be made under proper smoothness assumptions if the step size is small and noise is comparably small with the gradient size. However, the final policy’s performance is sensitive to the initial condition $J(\pi_{0})$, which can be poor for a randomly initialized policy.

Proposition 1 also suggests that the size of the gradient $\|\hat{\nabla}_{\theta}J(\pi_{n})\|^{2}$ does not converge to zero on average. Instead, it converges to a size proportional to the sampling noise of policy gradient estimates due to the linear dependency of $\frac{2\eta_{n}}{\alpha_{n}}\|\nabla_{\theta}J(\pi_{n})-g_{n}\|_{*}^{2}$ on $\eta_{n}$. This phenomenon is also mentioned by Ghadimi et al., (2016). We note that this pessimistic result is because the prox-map (5) is nonlinear in $g_{n}$ for general $R_{n}$ and $\Theta$. However, when $R_{n}$ is quadratic and $\Theta$ is unconstrained, the convergence of $\|\hat{\nabla}_{\theta}J(\pi_{n})\|^{2}$ to zero on average can be guaranteed (see Appendix B.1 for a discussion).

2 IMITATION GRADIENTS

While applying mirror descent with a policy gradient can generate a monotonically improving policy sequence, applying the same algorithm with an imitation gradient yields a different behavior. The result is summarized below, which is a restatement of (Ross and Bagnell,, 2014, Theorem 2.1), but is specialized for mirror descent.

where the expectation is due to randomness of sampling $g_{n}$, $\epsilon_{\text{class}}=\sup_{\{\pi_{n}\}}\inf_{\pi\in\Pi}\frac{1}{N}\sum_{n=1}^{N}l_{n}(\pi)$ and $\epsilon_{\text{regret}}=\frac{G^{2}(\log N+1)}{2\hat{\sigma}N}$.

Proposition 2 is based on the assumption that $l_{n}$ is strongly convex, which can be verified for certain problems (Cheng and Boots,, 2018). Consequently, Proposition 2 shows that the performance of the policy sequence on average can converge close to the expert’s performance $J(\pi^{*})$, with additional error that is proportional to $\epsilon_{\text{class}}$ and $\epsilon_{\text{regret}}$.

Finally, we note that updating policies with imitation gradients does not necessarily generate a monotonically improving policy sequence, even for deterministic problems; whether the policy improves monotonically is completely problem dependent (Cheng and Boots,, 2018). Without going into details, we can see this by comparing policy gradient in (3.2.1) and the special case of imitation gradient in (12). By Lemma 3, we see that

IMITATE-THEN-REINFORCE

To combine the benefits from RL and IL, we propose a simple randomized algorithm loki: first perform $K$ steps of mirror descent with imitation gradient and then switch to policy gradient for the rest of the steps. Despite the algorithm’s simplicity, we show that, when $K$ is appropriately randomized, running loki has similar performance to performing policy gradient steps directly from the expert policy.

The algorithm loki is summarized in Algorithm 1. The algorithm is composed of two phases: an imitation phase and a reinforcement phase. In addition to learning rates, loki receives three hyperparameters ($d$, $N_{m}$, $N_{M}$) which determine the probability of random switching at time $K$. As shown in the next section, these three hyperparameters can be selected fairly simply.

Before learning, loki first randomly samples a number $K\in[N_{m},N_{M}]$ according to the prescribed probability distribution (15). Then it performs $K$ steps of mirror descent with imitation gradient. In our implementation, we set

After the imitation phase, loki switches to the reinforcement phase. At this point, the policy $\pi_{K}$ is much closer to the expert policy than the initial policy $\pi_{0}$. In addition, an estimate of $A_{\pi_{K}}$ is also available. Because the learner’s policies were applied to collect data in the previous online imitation phase, $A_{\pi_{n}}$ can already be updated accordingly, for example, by minimizing TD error. Compared with other warm-start techniques, loki can learn both the policy and the advantage estimator in the imitation phase.

2 ANALYSIS

We now present the theoretical properties of loki. The analysis is composed of two steps. First, we show the performance of $J(\pi_{K})$ in Theorem 1, a generalization of Proposition 2 to consider the effects of non-uniform random sampling. Next, combining Theorem 1 and Proposition 1, we show the performance of loki in Theorem 2. The proofs are given in Appendix C.

Let $d\geq 0$, $N_{m}\geq 1$, and $N_{M}\geq 2N_{m}$. Let $K\in[N_{m},N_{M}]$ be a discrete random variable such that

where the expectation is due to sampling $K$ and $g_{n}$, $\Delta=\frac{C_{\pi^{*}}}{1-\gamma}\left(\epsilon^{w}_{\text{class}}+2^{-d}\hat{\sigma}D_{\mathcal{R}}+G^{2}C_{N_{M}}/\hat{\sigma}N_{M}\right)$, $D_{\mathcal{R}}=\sup_{R\in\mathcal{R}}\sup_{\pi,\pi^{\prime}\in\Pi}D_{R}(\pi^{\prime}||\pi)$, $\epsilon^{w}_{\text{class}}\coloneqq\sup_{\{w_{n}\},\{\pi_{n}\}}\inf_{\pi\in\Pi}\frac{\sum_{n=1}^{N}w_{n}l_{n}(\pi)}{\sum_{n=1}^{N}w_{n}}$, and

In summary, due to the sublinear convergence rate of IL, $N_{M}$ does not need to be large (say less than 100) as long as $N_{M}\gg d$; on the other hand, due to the $2^{d}$ factor, $d$ is also small (say less than $5$) as long as it is large enough to cancel out the effects of $D_{\mathcal{R}}$. Finally, we note that, like Proposition 2, Theorem 1 encourages using larger step sizes, which can further boost the convergence of the policy in the imitation phase of loki.

Given Proposition 1 and Theorem 1, now it is fairly easy to understand the performance of loki.

where the expectation is due to sampling $g_{n}$ and $K$.

Firstly, Theorem 2 shows that $\pi_{N}$ can perform better than the expect policy $\pi^{*}$, and, in fact, it converges to a locally optimal policy on average under the same assumption as in Proposition 1. Compare with to running policy gradient steps directly from the expert policy, running loki introduces an additional gap $O(\Delta+K\|\hat{\nabla}_{\theta}J(\pi)\|^{2})$. However, as discussed previously, $\Delta$ and $K\leq N_{M}\ll N$ are reasonably small, for usual $N$ in RL. Therefore, performing loki almost has the same effect as using the expert policy as the initial condition, which is the best we can hope for when having access to an expert policy.

We can also compare loki with performing usual policy gradient updates from a randomly initialized policy. The performance difference can be easily shown as $O(J(\pi^{*})-J(\pi_{0})+\Delta+K\|\hat{\nabla}_{\theta}J(\pi)\|^{2})$. Therefore, if performing $K$ steps of policy gradient from $\pi_{0}$ gives a policy with performance worse than $J(\pi^{*})+\Delta$, then loki is favorable.

RELATED WORK

Under the same assumption in Proposition 2, running slols generates a policy sequence, with randomness due to sampling $g_{n}$, satisfying

In fact, the performance in Theorem 3 is actually a lower bound of Theorem 3 in (Chang et al.,, 2015).The main difference is due to technicalities. In Chang et al., (2015), $\epsilon^{\lambda}_{\text{class}}$ is compared with a time-varying policy. Theorem 3 says that on average $\pi_{n}$ has performance between the expert policy $J(\pi^{*})$ and the intermediate cost $J_{\pi_{n}}^{*}$, as long as $\epsilon^{\lambda}_{\text{class}}$ is small (i.e., there exists a single policy in $\Pi$ that is better than the expert policy or the local improvement from any policy in $\Pi$). However, due to the presence of $\epsilon^{\lambda}_{\text{class}}$, despite $J_{\pi_{n}}^{*}\leq J(\pi_{n})$, it is not guaranteed that $J_{\pi_{n}}^{*}\leq J(\pi^{*})$. As in Chang et al., (2015), either lols or slols can necessarily perform on average better than the expert policy $\pi^{*}$. Finally, we note that recently both Nair et al., (2017) and Rajeswaran et al., (2017) propose a scheme similar to slols, but with the AggreVaTe(D) gradient computed using offline batch data collected by the expert policy. However, there is no theoretical analysis of this algorithm’s performance.

EXPERIMENTS

We evaluate loki on several robotic control tasks from OpenAI Gym (Brockman et al.,, 2016) with the DART physics engine (Lee et al.,, 2018)The environments are defined in DartEnv, hosted at https://github.com/DartEnv. and compare it with several baselines: trpo (Schulman et al., 2015a, ), trpo from expert, DAggereD (the first-order version of DAgger (Ross et al.,, 2011) in (13)), slols (Section 6), and thor (Sun et al.,, 2018).

We consider the following tasks. In all tasks, the discount factor of the RL problem is set to $\gamma=0.99$. The details of each task are specified in Table A in Appendix A.

This is a classic control problem, and its goal is to swing up an pendulum and to keep it balanced in a upright posture. The difficulty of this task is that the pendulum cannot be swung up directly due to a torque limit.

The goal of these tasks (Hopper, 2D Walker, and 3D Walker) is to control a walker to move forward as quickly as possible without falling down. In Hopper, the walker is a monoped, which is subjected to significant contact discontinuities, whereas the walkers in the other tasks are bipeds. In 2D Walker, the agent is constrained to a plane to simplify balancing.

In the Reacher task, a 5-DOF (degrees-of-freedom) arm is controlled to reach a random target position in 3D space. The reward consists of the negative distance to the target point from the finger tip plus a control magnitude penalty. The actions correspond to the torques applied to the $5$ joints.

2 ALGORITHMS

We compare five algorithms (loki, trpo, DAggereD, thor, slols) and the idealistic setup of performing policy gradient steps directly from the expert policy (Ideal). To facilitate a fair comparison, all the algorithms are implemented based on a publicly available trpo implementation (Dhariwal et al.,, 2017). Furthermore, they share the same parameters except for those that are unique to each algorithm as listed in Table A in Appendix A. The experimental results averaged across $25$ random seeds are reported in Section 7.3.

The same sub-optimal expert is used by all algorithms (loki, DAggereD, slols, and thor). It is obtained by running trpo and stopping it before convergence. The estimate of the expert value function $V_{\pi^{*}}$ (required by slols and thor) is learned by minimizing the sum of squared TD(0) error on a large separately collected set of demonstrations of this expert. The final explained variance for all the tasks is more than $0.97$ (see Appendix A).

The on-policy advantage $A_{\pi_{n}}$ in the first-order oracles for trpo, slols, and loki (in the reinforcement phase) is implemented using an on-policy value function estimator and Generalized Advantage Estimator (GAE) (Schulman et al., 2015b, ). For DAggereD and the imitation phase of loki, the first-order oracle is calculated using (14). For slols, we use the estimate $A_{\pi^{*}}(s_{t},a_{t})\approx c(s_{t},a_{t})+\gamma\hat{V}_{\pi^{*}}(s_{t+1})-\hat{V}_{\pi^{*}}(s_{t})$. And for thor, $A_{\pi_{n},t}^{H,\pi^{*}}$ of the truncated-horizon problem is approximated by Monte-Carlo samples with an on-policy value function baseline estimated by regressing on these Monte-Carlo samples. Therefore, for all methods, an on-policy component is used in constructing the first-order oracle. The exponential weighting in GAE is $0.98$; the mixing coefficient $\lambda$ in slols is $0.5$; $N_{M}$ in loki is reported in Table A in Appendix A, and $N_{m}=\left\lfloor\frac{1}{2}N_{M}\right\rfloor$, and $d=3$.

After receiving an update direction $g_{n}$ from the first-order oracle, a KL-divergence-based trust region is specified. This is equivalent to setting the strictly convex function $R_{n}$ in mirror descent to $\frac{1}{2}\theta^{\top}F(\theta_{n})\theta$ and choosing a proper learning rate. In our experiments, a larger KL-divergence limit ($0.1$) is selected for imitation gradient (14) (in DAggereD and in the imitation phase of loki), and a smaller one ($0.01$) is set for all other algorithms. This decision follows the guideline provided by the theoretical analysis in Section 3.2.2 and is because of the low variance in calculating the gradient of (14). Empirically, we observe using the larger KL-divergence limit with policy gradient led to high variance and instability.

3 EXPERIMENTAL RESULTS

We report the performance of these algorithms on various tasks in Figure 1. The performance is measured by the accumulated rewards, which are directly provided by OpenAI Gym.

We first establish the performance of two baselines, which represent standard RL (trpo) and standard IL (DAggereD). trpo is able to achieve considerable and almost monotonic improvement from a randomly initialized policy. DAggereD reaches the performance of the suboptimal policy in a relatively very small number of iterations, e.g. 15 iterations in 2D Walker, in which the suboptimal policy to imitate is trpo at iteration 100. However, it fails to outperform the suboptimal expert.

Then, we evaluate the proposed algorithm loki and Ideal, the performance of which we wish to achieve in theory. loki consistently enjoys the best of both trpo and DAggereD: it improves as fast as DAggereD at the beginning, keeps improving, and then finally matches the performance of Ideal after transitioning into the reinforcement phase. Interestingly, the on-policy value function learned, though not used, in the imitation phase helps loki transition from imitation phase to reinforcement phase smoothly.

Lastly, we compare loki to the two other baselines (slols and thor) that combine RL and IL. loki outperforms these two baselines by a considerably large margin in Hopper, 2D Walker, and 3D Walker; but surprisingly, the performance of slols and thor are inferior even to trpo on these tasks. The main reason is that the first-order oracles of both methods is based on an estimated expert value function $\hat{V}_{\pi^{*}}$. As $\hat{V}_{\pi^{*}}$ is only regressed on the data collected by running the expert policy, large covariate shift error could happen if the dimension of the state and action spaces are high, or if the uncontrolled system is complex or unstable. For example, in the low-dimensional Pendulum task and the simple Reacher task, the expert value function can generalize better. As a result, in these two cases, lols and thor achieve super-expert performance. However, in more complex tasks, where the effects of covariant shift amplifies exponentially with the dimension of the state space, thor and slols start to suffer from the inaccuracy of $\hat{V}_{\pi^{*}}$, as illustrated in the 2D Walker and 3D Walker tasks.

CONCLUSION

We present a simple, elegant algorithm, loki, that combines the best properties of RL and IL. Theoretically, we show that, by randomizing the switching time, loki can perform as if running policy gradient steps directly from the expert policy. Empirically, loki demonstrates superior performance compared with the expert policy and more complicated algorithms that attempt to combine RL and IL.

This work was supported in part by NSF NRI Award 1637758, NSF CAREER Award 1750483, and NSF Graduate Research Fellowship under Grant No. 2015207631.

References

Appendix A Task Details

The expert value estimator $\hat{V}_{\pi^{*}}$ needed by slols and thor were trained on a large set of samples (50 times the number of samples used in each batch in the later policy learning), and the final average TD error are: Pendulum ($0.972$), Hopper ($0.989$), 2D Walker ($0.975$), 3D Walker ($0.983$), and Reacher ($0.973$), measured in terms of explained variance, which is defined as 1- (variance of error / variance of prediction).

Appendix B Proof of Section 4

To prove Proposition 1, we first prove a useful Lemma 2.

where $\eta$ satisfies that $-\alpha\eta+\frac{\beta\eta^{2}}{2}\leq 0$. Then it holds

where $H=\frac{1}{\eta}(x-P_{h,\eta}(x))$. In particular, if $\|\cdot\|=\|\cdot\|_{W}$ for some positive definite matrix $W$, $R$ is quadratic, and $\mathcal{K}$ is Euclidean space,

Let $G=\frac{1}{\eta}(x-P_{g,\eta}(x))$. First we show for the special case (i.e. suppose $R(x)=\frac{1}{2}\langle x,Mx\rangle$ for some positive definite matrix $M$, and therefore $G=M^{-1}g$ and $H=M^{-1}h$).

For general setups, we first separate the term into two parts

For the first term, we use the optimality condition

Therefore, we can bound the first term by

On the other hand, for the second term, we first write

This can be proved by Legendre transform:

Because $\frac{1}{\eta}R$ is $\frac{\alpha}{\eta}$-strongly convex with respect to norm $\|\cdot\|$, $\left(\frac{1}{\eta}R\right)^{*}$ is $\frac{\eta}{\alpha}$-smooth with respect to norm $\|\cdot\|_{*}$, we have

which proves (16). Putting everything together, we have

This proves the statement in Proposition 1. We note that, in the above step, the general result of Lemma 2. For the special case Lemma 2, we would recover the usual convergence property of stochastic smooth nonconvex optimization, which shows on average convergence to stationary points in expectation.

B.2 Proof of Proposition 2

We use a well-know result of mirror descent, whose proof can be found e.g. in (Juditsky et al.,, 2011).

Let $\mathcal{K}$ be a convex set. Suppose $R$ is $\alpha$-strongly convex with respect to norm $\|\cdot\|$. Let $g$ be a vector in some Euclidean space and let

Next we prove a lemma of performing online mirror descent with weighted cost. While weighting it not required in proving Proposition 2, it will be useful to prove Theorem 2 later in Appendix C.

Let $f_{n}$ be $\sigma$-strongly convex with respect to some strictly convex function $R_{n}$, i.e.

and let $\{w_{n}\}_{n=1}^{N}$ be a sequence of positive numbers. Consider the update rule

where $g_{n}=\nabla f_{n}(x_{n})$ and $\eta_{n}=\frac{1}{\hat{\sigma}\sum_{m=1}^{n}w_{m}}$. Suppose $\hat{\sigma}\leq\sigma$. Then for all $x^{*}\in\mathcal{K}$, $N\geq M\geq 1$, it holds that

The proof is straight forward by strong convexity of $f_{n}$ and Lemma 3.

Now we use Lemma 4 to prove the final result. It’s easy to see that if $g_{n}$ is an unbiased stochastic estimate of $\nabla f_{n}(x_{n})$ in Lemma 4, then the performance bound would hold in expectation since $x_{n}$ does not depend on $g_{n}$. Finally, by definition of $\epsilon_{\text{class}}$, this concludes the proof.

Appendix C Proof of Section 5

Let $w_{n}=n^{d}$. The proof is similar to the proof of Proposition 2 but with weighted cost. First we use Lemma 1 and bound the series of weighted accumulated loss

Then we bound the right-hand side by using Lemma 4,

which implies $\frac{w_{n}^{2}}{\sum_{m=1}^{n}w_{m}}\leq\frac{(d+1)n^{2d}}{n^{d+1}}\leq(d+1)n^{d-1}.$ Combining these two steps, we see that the weighted accumulated loss on average can be bounded by

Because $N_{M}\geq 2N_{m}$ and $\frac{x}{1-x}\leq 2x$ for $x\leq\frac{1}{2}$, we have

Thus, by the assumption that $\|g_{n}\|_{*}\leq G$ almost surely, the weighted accumulated loss on average has an upper bound

By sampling $K$ according to $w_{s}$, this bound directly translates into the the bound on $J(\pi_{K})$.

C.2 Proof of Theorem 3

For simplicity, we prove the result of deterministic problems. For stochastic problems, the result can be extended to expected performance, similar to the proof of Proposition 2. We first define the online learning problem of applying $g_{n}=\nabla_{\theta}l_{n}^{\lambda}(\pi)|_{\pi=\pi_{n}}$ to update the policy. In the $n$th iteration, we define the per-round cost as

With the strongly convexity assumption and large enough step size, similar to the proof for Proposition 2, we can show that

To relate this to the performance bound, we invoke Lemma 1 and write