Convergence Rates for Stochastic Approximation on a Boundary

We analyze the behavior of projected stochastic gradient descent focusing on the case where the optimum is on the boundary of the constraint set and the gradient does not vanish at the optimum. Here iterates may in expectation make progress against the objective at each step. When this and an appropriate moment condition on noise holds, we prove that the convergence rate to the optimum of the constrained stochastic gradient descent will be different and typically be faster than the unconstrained stochastic gradient descent algorithm. Our results argue that the concentration around the optimum is exponentially distributed rather than normally distributed, which typically determines the limiting convergence in the unconstrained case. The methods that we develop rely on a geometric ergodicity proof. This extends a result on Markov chains by Hajek (1982) to the area of stochastic approximation algorithms. As examples, we show how the results apply to linear programming and tabular reinforcement learning.


Introduction.
We analyze the behavior of stochastic gradient descent focusing on the case where the optimum is on the boundary of the constraint set and the gradient does not vanish at the optimum. For a projected stochastic gradient descent algorithm, when the expected value of the objective decreases on each iteration, we will show that a constrained stochastic gradient descent algorithm has a different rate of convergence that would be anticipated by standard results for stochastic gradient descent.
General convergence rates are known for (projected) stochastic gradient descent with a convex objective function. Here to obtain an -approximation of the optimum, we require O( −2 ) iterations [26; 27; 6]. Such results can be improved to require O( −1 ) iterations when the objective function is strongly convex [26; 27; 6]; however, even in this case, the distance to the optimum will still be of order O( −2 ). Moreover, there are commonly applied functions such as linear or piecewise linear objectives which are not strongly convex. Thus standard results would suggest O( −2 ) iterations are required to obtain an -approximation of the optimizer. In this paper, we argue that a stochastic approximation procedure can achieve the faster rate of O( −1 ).
In our main result, we consider a constrained stochastic gradient descent algorithm minimizing f (x) with iterates {x t } ∞ t=0 belong to a constraint set X and with a learning rate of the form 1/t γ with γ ∈ [0, 1]. If the optimum is on the boundary then we can expect the algorithm to make progress against its objective in proportion to the learning rate. This is Condition C1. Further we assume sub-exponential noise. This is Condition C2. When Condition C1 and C2 hold then we prove that This result is more formally stated in Theorem 1 and, specifically, Corollary 1. An exponential concentration bounds is also given. Taking γ = 1, we see that an -approximation of the optimum requires O( −1 ) iterations. The conditions required for Theorem 1 are generic. Thus the results are not intended to be applicable to any one particular stochastic gradient descent algorithm, nor do we place specific design restrictions on the algorithm. What the result emphasizes is that a different convergence rate may hold for a broad class of stochastic gradient descent algorithms when there are constraints.   Figure 1a): When the objective is unconstrained the density of the location of iterates is well approximated by a normal distribution with variance σ 2 = O(α), where α is the step size of the algorithm. The distance to the optimum is O(α 1/2 ). Figure 1b): When the value of x is constrained to the positive orthant, the distribution of iterates away for zero are now well approximated by an exponential distribution with rate λ = O(α −1 ). So for step size α, the distant to the optimum is O(α). This paper proves that the exponential decay holds more generally for constrained stochastic approximation procedures with time-dependent learning rates. This differs and may well be faster than the well established convergence rates of stochastic gradient descent in the unconstrained case.
The high-level intuition for this behavior in a stochastic gradient algorithm is as follows. Consider a projected stochastic gradient descent algorithm with a small but fixed learning rate (cf. Section 3 for a formal definition). When the optimum is in the interior of the constraint set, the progress of the algorithm will slow as the iterates approaches the minimizer in a manner that is roughly proportional to the distance to the optimum. In this regime, the process behaves in a manner that is similar to an Ornstein-Uhlenbeck (OU) process [23]. An OU process is known to have a normal distribution as its limiting stationary distributions. This stationary distribution determines convergence to the optimum [8]. If we consider the same iterates but instead these are now projected to belong to a polytope then, assuming that the optimum is on the boundary, the resulting process behaves in a manner that is approximated by a reflected Brownian motion [19; 20]. When the gradient is non-zero on the boundary, it is well known that a reflected Brownian motion with negative drift has an exponential distribution as its stationary distribution [15]. The normal and exponential distributions found have a very different concentration in probability. Thus we can anticipate a different convergence behavior. In particular, for the one-dimensional case, simple calculations using Kingman's bound [16] indicate that the distance from the optimum should be within of the optimum in O( −1 ) steps for a projected stochastic gradient descent algorithm. The argument of Kingman also indicates that an exponential Lyapunov function might be more appropriate than the standard expansion and interpolation methods used for the convergence analysis of stochastic gradient descent. The aim of this paper is to rigorously confirm this for stochastic approximation algorithms.
The proof method that we develop uses a martingale argument first described by Hajek [14] for Markov chains. The Lyapunov function bounds of [14] and also [3] are commonly employed to give exponential tail bounds for a stationary Markov processes. These are often applied in the analysis of queueing networks. Here we adapt this analysis and apply it to stochastic gradient descent. To the best of our knowledge this is the first paper to apply this approach to gain concentration bounds in the context of stochastic approximation.
Above, we discuss our results for projected stochastic gradient descent; however, the results hold more broadly. In particular, the main result (Theorem 1) requires a condition on the progress of algorithm and constraints on the noise induced by the gradient descent steps. Thus the results in Theorem 1 are not specific to any one algorithm. Instead they give general conditions for exponential concentration of measure to hold for a stochastic approximation procedure. For this reason, any constrained stochastic approximation procedure may enjoy faster convergence rates than those achieved by the corresponding unconstrained algorithm.
However, it is also important to identify scenarios when these assumptions are known to hold. In Theorem 2, we prove a convergence result for projected stochastic gradient descent when applied to a linear program. Here we show that when the set of constraints are known but the costs in the objective are unknown then the assumptions of Theorem 1 are satisfied and we can expect a faster convergence rate.
Finally as an application, we apply our results to tabular reinforcement learning. We consider a discounted Markov Decision Process (MDP) where the state transition function is known but the reward function is unknown. Algorithms such as Q-learning are well known to require O( −2 ) iterations to reach an -approximation of the optimal value function. It is well known that a MDP can be characterized as a linear program: either in a primal formulation that calculates the value function; or in a dual formulation that gives the occupancy measure of the MDP. We apply projected stochastic gradient descent to the dual linear programming formulation of the MDP. This can be thought of as a relatively simple policy gradient algorithm. Here we prove a gap dependent bound which requires O( −1 ) to find an -approximation of the optimal occupancy measure. This policy gradient algorithm is faster than the rate of convergence that would be achieved for instance by Q-learning. Certainly, bespoke algorithms exist in recent reinforcement learning literature [33; 35]; however, it is striking that with a relatively simple change -to optimize over the policy's occupancy measure-a standard projected gradient descent yields a faster algorithm.
Other other applications and extensions of our results would be possible. We have not considered different forms of averaging gradients which would likely yield a faster convergence rate. We assume a somewhat canonical choice of variance in gradient steps. (See Condition C2.) It is possible to investigate the dependence on the moment generating function of the gradient. This may be applicable, for instance, in online reinforcement learning. Further, there may be different formulations of the exponential martingale argument given in Section 4. For instance, it is possible to prove similar results using the Martingale approach of Kingman [17].
The remainder of the paper is organized as follows. In Section 2, we review relevant literature. In Section 3, we introduce the basic model, notation and algorithms that we consider. In Section 4, we present our main result: Theorem 1. Theorem 1 gives an exponential concentration bound for any stochastic approximation procedure satisfying two conditions, C1 and C2. We also provide a simpler formulation of the main result, namely, Corollary 1. In Section 5 and specifically in Theorem 2, we apply our results to linear programs. In Section 6, we then apply Theorem 2 to solve a tabular reinforcement learning problem. The proof of Theorem 1 is contained in Section 7. Further results from Section 5 and Section 6 are proved in Section 8.

Literature Review.
We now review relevant literature. We review results on the rate of convergence of stochastic gradient descent. We review the martingale approach that we use to establish exponential tail bound. We discuss its typical usage for establishing exponential ergodicity in Markov chains. We discuss the changes required to adapt these arguments to time-dependent stochastic approximation. We review results on constrained stochastic approximation. We apply our results to linear programs with unknown costs. So we briefly review probabilistic concentration results in this setting. We apply our results to reinforcement learning. We review the linear programming approach to dynamic programming and discuss related results in reinforcement learning.

Lyapunov Bounds.
A key ingredient of our analysis is an exponential tail bound acheived using a geometric Lyanpunov function argument. We note that such arguments are commonly employed in order to establish the exponential ergodicity of a Markov chain. For instance, see [25,Chapter 15]. Specifically, Hajek [14] provides a proof that converts a linear drift condition into an exponential Martingale that can then be used to gain fast convergence rates for ergodic Markov chains. Extending this argument to stochastic approximation is one of the key contributions of this paper. The argument of Hajek can be thought of as an extension of the Martingale bound of Kingman for the G/G/1 queue [17]. Indeed it is possible to derive a different version of the proof of the given in this paper using the argument of Kingman; however, the approach of Hajek [14] is cleaner and so we do not peruse this Kingman proof here [17]. There are alternative arguments for achieving an exponential tail bound using a Lyapuov function with linear drift [3]. However, these arguments can apply to time-inhomogeneous Markov chains, and so are not applicable in our context.
As discussed in the introduction, many of these bounds have typically been applied in the context of queueing networks. This because many queueing processes can be viewed as random walks chains constrained to belong to a polytope region. Here it is broadly known that a linear negative drift with constraints leads to an exponential distribution bounds [15]. There are results connecting the limit behavior of stochastic approximation procedures with constrained random walks and diffusions [19]. Nonetheless, the concentration results proven here are, to the best of our knowledge, new in the context of stochastic approximation.
Stochastic Approximation and Stochastic Gradient Descent. Due to its applicability in machine learning, there is now a vast literature on stochastic gradient descent [5]. The argument used originally by Robbins-Monro [30] as well as more recent approaches used in online convex optimization [37] tend to focus on interpolating the (Euclidean) distance to the optimum. This contrasts the exponential Lyapunov approach discussed above.
As discussed in the introduction, the rate of convergence of a stochastic gradient descent procedure on a convex objective (either with or without projection) is well known to be within O(1/ √ t) of the optimum after t-iterations the algorithm. If it is further assumed that the objective function is strongly convex then this rate of convergence can be improved to be O(1/t) [27; 26; 6]. These results are standard and hold for projected stochastic gradient descent.
The convergence of stochastic approximation algorithms on constrained regions is given in detail in the text of Kushner and Clark [18]. See also [19]. The geometric approach taken in this paper is influenced by the early work on projected stochastic gradient descent [12]. See also [1,Chapter 3]. Convergence rates for constrained stochastic approximation algorithms are considered by Buche and Kushner [7]. Here the authors note that analysis typically applied to analyze unconstrained stochastic approximation does not readily apply to the constrained case, and a diffusion analysis is conducted with results depending on which constraints of the optimization are active. Large deviations analysis is a further method used to better understand boundary behavior in stochastic approximation with constraints [10]. These results [10; 7] concern deviations around a rate of convergence of the order O(1/ √ t), whereas we are interested in establishing conditions for a faster O(1/t) rate of convergence.
Linear Programs and Markov Decision Processes. In this article, we apply our results to linear programs and then to solve Markov decision processes which in both cases have unknown random costs. This gives two examples where it is possible to apply the results of this paper.
The study of stochastic linear programs is common within operations research. We refer to Prekopa [29], Birge and Louveaux [4] and Shapiro et al. [32] as standard textbooks that cover both theory as well as variety of linear and non-linear programming examples where stochastic perturbations in their coefficients can occur. We provide concentration results for our stochastic gradient descent algorithm at the optimum. The work of [11] focuses on concentration of probability for linear programs with random objectives.
A Markov decision process can be characterized as a linear program [24]. Schweitzer and Seidmann [31] provides a modern formulation of a Markov decision process as a linear program. This is an extended approach and popularized as a method for approximate dynamic program [9]. Such linear programs can be characterized in either primal or dual form. The dual form can be more tractable for specific problem classes for example in scheduling [28]. In our case, this dual form is most convenient.
As an example of our results, we consider tabular reinforcement learning. Here we consider a finite state finite action Markov decision process where costs are unknown and must be estimated by sampling. In our case, we assume that the dynamics of the system are known. There are multiple tabular reinforcement learning algorithms, the most well known being Q-learning [36]. Q-learning requires O( −2 ) samples for an approximation [22]. General minimax lower-bounds require O( −2 ) samples for a approximation of the optimal policy [13]. Minimax results consider the best performance on worse case problem. However, problem specific convergence rates can improve these bounds by allowing dependence on gap between the optimal policy and a sub-optimal policy. (This is similar to bandit algorithms where regret bounds are typically O(log T ) but the minimax regret is typical O( √ T ) [21].) For a recent analysis and bound for gap-dependent bound for tabular RL see [33].

Model and Notation
This section acts as a brief recap of a number of well-known optimization formulations. We define the projected stochastic gradient descent as an algorithm to solve these problems. We also determine conditions that we place on learning rates for such algorithms. We define linear programs and Markov decision processes as special cases of our optimization formulation which we will later analyze as example applications.
Basic Notation. We apply the convention that Z + = {n : n = 0, 1, 2, ...} and R + = {x : x ≥ 0}. We apply the convention that (implied) multiplication has precedence over division, i.e. 2a/3b = Optimization Notation. We let X denote a closed bounded convex subset of R d . For a function f : X → R, we consider the minimization We let X be the set of minimizers of the above optimization. We let Π X (x) denote the projection of x onto the set X . That is Π X (x) := argmin y∈X ||x−y|| 2 , where ||·|| denotes the Euclidean norm. We let d(x, X ) denote the distance from the point to its projection. That is d(x, X ) := min y∈X ||x−y||.
We let F be the gap between the maximum and minimum of f (x) on X , that is Stochastic Gradient Descent with Constraints. We consider stochastic iterative procedures for solving the optimization (1). A standard algorithm for this problem is projected stochastic gradient descent. Projected stochastic gradient descent is a randomized procedure for optimizing the objective (1) when random estimates of the gradient of f (x) are available. Specifically, the sequence {x t } ∞ t=0 obeys the iteration where, for each t ∈ Z + , α t is a positive real number and c t is a random variable such that (More formally we let F t be the σ-field generated by (c 1 , x 1 , ..., c t−1 , x t ) and {F t } t≥0 is its associated filtration.) When f (x) is convex and the sequence α t obeys the condition then d(x t , X ) → 0 as t → ∞ [19]. Sequences typically considered take the form α t = a/(b + t) γ for a, b > 0 and γ ∈ [0, 1]. Instead of condition (3) in this paper, we will assume that {α t } t≥0 is a deterministic non-increasing sequence such that We do not necessarily assume that α t → 0 as we later wish to consider the case of small but constant step sizes. The above condition is satisfied by any sequence of the form α t = a/(b + t) γ for a, b > 0 and γ ∈ [0, 1]. (Note that for any sequence satisfying (3) it holds that lim inf t→∞ (α t − α t+1 )/α t = 0.) The results in the paper are not specific to Projected stochastic gradient descent. In general, our results consider a random sequence {x t } ∞ t=0 adapted to a filtration {F t } ∞ t=0 with x t ∈ X for each t ∈ Z + . The distance between successive terms is determined by the sequence . We refer to any such algorithm as a constrained stochastic gradient descent algorithm. Projected stochastic gradient descent is one specific example of a constrained stochastic gradient descent algorithm.
Linear Programming Notation. We will be interested in the special case where X is a polytope. That is X = {x ∈ R d : Hx ≤ b} for a matrix H ∈ R p×d and a vector b ∈ R p . We assume that the objective f is linear. That is f (x) =c x for a constant vectorc ∈ R d . Thus the above optimization is a linear program: We let E be the set of extreme points of the set X . The set E is finite for any polytope and the optimum of a linear program is alway achieved at an extreme point [2]. We let E be the set of extreme points in X .
Markov Decision Process Notation. A Markov Decision Process (MDP) is a stochastic process (S t : t ∈ Z + ) defined on a set of states S. The states visited are determined by actions (A t : t ∈ Z + ) defined on the set of actions A. Specifically, the transitions to the next state S t+1 is determined by the current state S t , the action A t and an independent identically distributed random variable We let P (s |s, a) = P(S t+1 = s |S t = s, A t = a) . We assume that the set of states, S, and actions, A, are both finite. For each state and action pair (S t , A t ), there is a real-valued cost Costs can be positive or negative. We assume that the costs are bounded by c max < ∞ that is |c(s, a)| ≤ c max for all s ∈ S and a ∈ A. A policy is a function, π : S → A, that selects an action for each state. Specifically under policy π, Note that under a policy π the process (S t : t ∈ Z + ) is a Markov chain. We let E π s0 [·] be the expectation of the Markov chain S under policy π conditional on the initial state S 0 = s 0 . We let P denote the set of policies, which is the set of functions from X to A.
A discounted MDP has the objective to minimize the discounted costs of a MDP: where the discount factor β is such that β ∈ (0, 1).

An Exponential Lyapunov Bound
When the slope of the objective function does not go to zero as we approach the boundary, we can anticipate that a stochastic gradient descent algorithm will expect to always make progress towards minimizing its objective proportional to the learning rate α t , except perhaps at the optimum or at points within a small region of the optimum. More precisely, we can expect a constrained stochastic gradient descent sequence {x t } ∞ t=0 to satisfy the condition for some δ > 0 and some B > 0. We also place some bounds on the size of the change in f (x t ). Specifically, we assume that there exists a constant η > 0 and a random variable Y such that Condition (C1) need not hold for all projected gradient descent algorithms and problem instances. Nonetheless, the condition is reasonable as one might expect a stochastic gradient descent algorithm to make progress against its objective when away from a point with zero gradient. The Condition (C2) is a reasonably mild assumption. For example, in projected stochastic gradient descent, this amounts to assuming that the magnitude of gradient estimates ||c t || have a moment generating function, and thus a sub-exponential tail. (See Lemma 7 for a verification of this claim.) Shortly we will estaiblish the conditions (C1) and (C2) when applying projected stochastic gradient descent to linear program. However, for now we leave (C1) and (C2) as general conditions that can be satisfied by a constrained stochastic gradient descent algorithm.
Below we present our main convergence result. In essence, the result establishes that once the sum t s=1 α s is sufficiently large the error of a constrained stochastic gradient descent is of the order of α t . Theorem 1. When Condition (C1) and (C2) are satisfied by a constrained stochastic gradient descent algorithm, there exist positive constants E, G, H such that for any n with t/2 n > 1 We can interpret the above result as follows. (When reading the above result, it is best to consider the parameter n = 1. Though for faster decaying learning rates, e.g. α t = 1/t, a different choice of n is required to obtain the best bound.) In (5), we see that the probability that f (x t ) − f (x ) is above z can be split into two terms. The first term accounts for the time it takes for the initial condition to be forgotten and for the process f (x t ) to approach the value f (x ). Notice if step sizes α t are kept constant then this term decays exponentially fast. Following this, the second term, accounts for excursions in the process away from f (x ). These excursions exhibit a behavior that is analogous to a G/G/1 queue [17] and has a tail behavior that is exponentially distributed. Notice this is different from typical behavior of an Ornstein-Uhlenbeck process (which we would typically associate with constant step-size stochastic gradient descent) which is know to have a normally distributed stationary distribution.
From (6), we see that once the dependence on initial state of the system has been accounted for then the process f (x t ) will be within a factor of α t of the optimum. In particular, for step sizes of the form α t = 1/t γ , we have that This final observation is confirmed in the following corollary. and for time independent constants I, J and K.
It is worth remarking that Theorem 1 and Corollary 1 hold for any algorithm for which the generic conditions (C1) and (C2) hold. Thus the results are not intended to applicable to any one particular stochastic gradient descent algorithm, nor do we place specific design restrictions on the algorithm. Moreover, it is not necessary to verify these conditions in order to implement any algorithm. The result emphasizes that a convergence rate may hold for a broad class of stochastic gradient descent algorithms when there are constraints. This convergence may well be faster than that anticipated by the well established convergence in the unconstrained case.
In the proof of Theorem 1 and Corollary 1, we did not specify the stochastic approximation procedure used nor did we explore settings where the key Conditions C1 and C2 hold. The aim of this section is to provide a concrete example where we prove that Conditions C1 and C2 hold and thus Theorem 1 and Corollary 1 apply. Here we consider a linear program where the cost function that we wish to minimize must be sampled and where the constraints of the optimization are deterministic. We consider the projected stochastic gradient descent algorithm where the costs sampled are batched. When the batch size is sufficiently large and assuming the sample would cost a reasonably light tailed then it is possible to verify the Conditions C1 and C2. Thus in this case, we prove that projected stochastic gradient descent has a faster convergence rate than (unconstrained) stochastic gradient descent.
As discussed in Section 3, we are interested in solving a linear program of the form where X = {x ∈ R d : Hx ≤ b} is a bounded polytope. We suppose that the constraint set X is deterministic and known, however, the cost vectorc is unknown but can be sampled. Specifically, t ∈ Z + , we let c i t , i = 1, ..., B be independent sub-Gaussian random vectors in R d , with meanc that is for i = 1, ..., B and t ∈ Z + , and there exists a constant λ > 0 such that We think of the set of costs (c i t : i = 1, ..., B) as a batch which we then average in order to make a stochastic gradient descent step. That is, we let and then apply projected stochastic gradient descent We can prove that the conditions of Theorem 1 are satisfied for linear programs. From this we obtain the following results.
Theorem 2. For the projected stochastic gradient descent (11) applied to a linear program (9) with learning rates of the form and where I, J and K are time independent constants.
To prove Theorem 2, we must show that the premise of Theorem 1 is satisfied. Specifically, we must prove that projected stochastic gradient descent makes constant progress against its objective.
The key ingredient that we require in order to prove is a lemma, which shows that the angle between a sub-optimal point and the closest optimal point is always bounded away from zero. Indeed, although we prove this results for polytope regions it is reasonable to expect that the angle between a suboptimal point and the optimum might be bounded below for a wide variety of optimization problems, beyond linear programs.
There are a large number of linear programs for specific problems where the above analysis applied. However, we now focus in this section on the example of solving discounted Markov decision processes using the results from the last section. Here we use a linear programming approach to prove the convergence of a simple policy gradient algorithm. Here we considered a Markov decision process where the dynamics of the system are known but the costs accrude are unknown.
Here we look to optimize a Markov decision process through sampling these costs. We define a Markov decision process in Section 3. It is well known that a Markov decision process can be formulated as a linear program, where the primal form of this linear program solves for the optimal value function and the dual form finds the optimal occupancy measure. (See the appendix, Section A.1, for a brief discussion on this.) In this linear programming formula, this dual problem takes the form: Here (ξ(s) : s ∈ S) is a positive vector. We assume that the dynamics as given by (P (s |s, a) : a ∈ A, s, s ∈ S) are known but costs are unknown and must be sampled, then above we have a linear program with an unknown objective and known constraints. For this reason we can apply the analysis developed in the last section.
Here we assume that we are able to sample costsc = (c(s, a) : s ∈ S, a ∈ A) where the states and actions as distributed according to some predetermined probability distribution π = (π(s, a) : a ∈ A, s ∈ S). There are a number of ways of sampling the cost vector c t for each t. The most straight-forward is as follows. For each t, the cost c t = (c t (s, a) : s ∈ S, a ∈ A) is assumed as follows. We take IID samples (s i t , a i t ), i = 1, ..., B with distribution π = (π(s, a) : s ∈ S, a ∈ A) where π(s, a) > 0 for all s ∈ S and a ∈ A. We then define We can think of this method of observing costs as x experience reply. In experience reply a policy is followed and states and actions are observed according to some distribution π. As samples come from a Markov process, these samples are stored in memory and resampled independently at random. The costs observed would then be approximated by the above dynamics. We consider the projected gradient descent Here the projection above is on to the constraint set of the dual problem: x(s, a)P (s |s, a), ∀s ∈ S .
Given the description above the following result is a direct consequence of Corollary 1. and for time independent constants I, J and K.
The fastest convergence rate that can be obtained above is when γ = 1. We note that this rate of convergence is faster than would typically be observed when applying a tabular reinforcement learning algorithm such as Q-learning. The rate of convergence of Q-learning is known to be of the order of t −1/2 . We note however that the constant K given in the above bound depends on the structure of the polytope X . Thus our bound (13) is an instance dependent bound rather than a minimax bound which would typically be applied to gain a bound across all problem instances.
Although we will focus on the above sampling, we now breifly discuss other methods where costs can be sampled. The above sampling mimics the behaviour where there is a policy that visits each state and action with distribution π(s, a) and then by storing in memory the states and actions visited by the policy we can independently draw from the list of state and actions visited. This method of achieving a batch of (approximately) independent samples is know as experience replay. Another approach would apply to episodic environments. Here we assumed that the MDP terminates in a finite expected time and the MDP can then be restarted from some fixed state s 0 ∈ S. Under this assumption, the costs reached under a fixed policy over successive episodes are independent. We would consider B episodes and apply the average cost achieved per episode. It is also possible that a sequence of state action cost triples is sampled directly from a fixed policy. Further, a particular choice is where the costs are sampled directly from the current policy choice as indicated by x.

Proof of Theorem 1 and Corollary 1
In this section, we prove our main result, Theorem 1, as well as Corollary 1, which is a simplified version of Theorem 1.
The following is a brief outline of the proofs of Theorem 1 and Corollary 1. The proof of Theorem 1 uses Lemma 1, Lemma 2 and Proposition 1, which are stated below. Lemma 1, although not critical to our analysis, simplifies the drift condition C1 by eliminating some additional terms and boundary effects. Lemma 2, on-the-other-hand, is a key component of our proof. It converts the linear drift condition C1 into an exponential bound which we then iteratively expand. The lemma extends Theorem 2.3 from Hajek [14] by allowing for adaptive time dependent step sizes. Proposition 1 applies standard moment generating function inequalities to the results found in Lemma 2. After Proposition 1 is proven the proof of Theorem 1 is essentially complete. We simply need to translate results back to the notation of our original formulation. Corollary 1 follows after carefully bounding some of the series stated in Theorem 1. For the learning rates considered, cleaner bounds are obtained in Corollary 1. (Three other generic, technical lemmas with standard proofs are required. These are proven in Section A.2 of the appendix. ) We now proceed with the steps outlined above. We let where α t satisfies (4). First we simplify the above conditions C1 and C2 to give the Lyapunov conditions (18) and (19) stated below.
Lemma 1. Given Conditions C1 and C2 hold, there exists a constant t 0 such that the sequence of random variables (L t : t ≥ t 0 ) satisfies and Proof. Applying the definition of L t and the drift condition C1 gives Since (α t − α t+1 )/α t → 0, there exists a constant t 0 such that (α t − α t+1 )/α t < δ/2B for all t ≥ t 0 . This gives the first drift condition (18). For the second condition, for t ≥ t 0 with t 0 as just defined: Taking Z = Y + δ/2, it is clear that condition (19) holds for Z as an immediate consequence of the boundedness condition on Y in C2. Now given (19) holds, we will convert the drift condition (18) into a exponential bound and then iterate to give the bound below.
. Thus, on the event {L t ≥ 0} the following holds: In the first equality above, we apply a Taylor expansion. In the first inequality we apply (18) and (19) above, and also recall that α t is decreasing. In the final inequality, we applied the standard bound 1 + x ≤ e x . We note that ρ t as define above satisfies ρ t < 1 whenever α t < δ/ηE. We note that E is finite since by assumption E[e ηα0Z ] < ∞. Also from the expansion given in (20), it is clear that E is positive. The bound (21) holds on the event {L t ≥ 0}. Now notice ≤ ρ t e ηLt + D .
The first inequality applies the above bound (21) and the second inequality applies the boundedness condition (19). Taking expectations above gives By induction, we have as required.
The following is a technical lemma proven in the appendix that we will require for Proposition 1 below. Moreover, if α t , t ∈ Z + satisfies the learning rate condition (4) then min s= t/2 n ,...,t t k=s α k t k=s α 2 k ≥ G n α t (23) for some positive constant G and for n ∈ N such that t/2 n > 1.
With the moment generating function bound in Lemma 2 and the above lemma, we can bound the tail probabilities and expectation of L t . Proposition 1. For any sequence satisfying (4), there exists a constant H such that Proof. We apply Lemma 2 with t 1 = t/2 n which gives We let η be such that 0 ≤ η ≤ min t1≤s≤t t k=s α k δ 2 t k=s α 2 k E . Notice, for such η, it holds that Applying this to (24) gives In the 2nd inequality above we note that α k ≥ α t for all k ≤ t. In the 3rd inequality, we note that the summation over τ are terms from a geometric series, so we upper bound this by the appropriate infinite sum. By Lemma 3, we see that for a constant G > 0. In particular, we take η = δG n /2Eα t . Thus, the bound (25) becomes Noting that L t1 ≤ max x∈X f (x) − min x∈X f (x) + α 0 B = F + α 0 B, by the definition of F in (2). We simplify the above expression as follows Above we define H := De . Notice if t is such that F + α 0 B − t s= t/2 n α s δ 2 ≤ 0, then the above inequality (26) can be bounded by as required.
With Proposition 1 in place we can translate our result back into our original notation and prove Theorem 1.
We now prove Corollary 1 as a consequence of Theorem 1. This involves carefully bounding the terms in Theorem 1.
Proof of Corollary 1. First we consider the case γ ∈ [0, 1), after we will consider the case where γ = 1.
When γ ∈ [0, 1) we take n = 1 in Theorem 1. Notice that then applied to the above bound, we have that t s= t/2 n α s δ 2 ≥ α 0 B + F , Thus applying bound (5) from Theorem 1 for t ≥ t 0 , with t 0 as define above and n = 1, we see that Integrating the above bound then gives Now suppose that γ = 1 then the analogous bound to (27) is We see that if we chose n such that holds. Thus is we choose n as above and t 0 = 1 then, again applying (5) from Theorem 1, we have the bound Thus we see that the bound (12) holds with I := H + 1 and J := δG n /2E. Integrating the above bound then gives Thus we see that (13) holds with K := B + 2E(1 + H)/δG n .

Proof of Theorem 2 and Theorem 3
Theorem 2 and Theorem 3 show how Theorem 1 and Corollary 1 can be applied in the case of linear programming and dynamic programming. The proof of Theorem 2 is an application of Theorem 1. As such, we are required to show that the conditions of Theorem 1 as satisfied. Specifically we must prove that Conditions C1 and C2 hold. The moment generating function bound in Condition C2 follows in a reasonably straightforward manner when random costs have a sub-Gaussian tail behavior. However, Condition C1 requires a more careful analysis. Here we give a geometric argument which proves that there is a non-zero angle between any sub-optimal point in X and the nearest optimal point in X . This is Lemma 5. (Note that Lemma 5 holds for linear programs, though may hold for many other convex optimization problems.) We then provide an perturbation analysis of this result in Corollary 2. We then apply a series of probabilistic bounds to this in Proposition 2. The results from Proposition 2 can then be collected together to verify that Conditions C1 and C2 hold and thus we prove Theorem 2.
The proof of Theorem 3 relies of the linear programming formulation of a Markov decision process and thus Theorem 3 follows immediately from Theorem 2.
The following result bounds the angle between optimal and sub-optimal points for a polytope. (Indeed other constrain sets X would satisfy this result and thus would potentially be amenable to our analysis.) Lemma 4. If X is a bounded polytope and X = argmin x∈Xc x.
Then there exists a constant K > 0 such that for x the projection of x onto X .
Proof. We assume without loss of generality thatc x = 0 and ||c|| = 1. Let E be the extreme points of X . Let E be the extreme points in X . Then let E := E \ E and X is the convex closure of E . Let a := min x∈X c x and D := max x ∈X ,x ∈X ||x − x ||. We will show we can take K := a/D.
For all x ∈ X \ X , x must be a convex combination of a point in X and a point in X . Specially, for x 0 ∈ X and x 1 ∈ X and p ∈ (0, 1]. Then, as required, The first inequality above uses the fact that x is closest to x. The equality applies (28). Then finally, we apply the definitions of a, D and K.
The following lemma is a deterministic version of the result that we want. Here we provide a geometric argument which shows that if we apply a projected gradient descent algorithm with the deterministic cost vectorc then we always make progress that is proportional to step size against the objective.
Proof. The proof follows by a geometric argument. To help with this we refer the reader to Figure  2. Now, let y = x + αc.
Let x be the projection of x onto X = argmin x∈Xc x. By Lemma 4, Let y be the projection of y onto the line segment between x and x . By convexity, y ∈ X . Also, by (29), y = x . To see this notice that ||y − x|| = α||c|| by definition, where as Thus since y is closer to x ∈ X than x . So the projection, y , cannot equal x . Further, by Lemma 4c Note that because y is the projection of y onto the line between x and x we have that (Note that the left and right are both ||x − y || cos θ where θ is the angle between x , x and y . See Figure 5.) Combining (31), (32), and (33) gives Also by Pythagoras' Theorem, ||x − y || 2 = ||y − y || 2 + ||y − x|| 2 . Thus, Since ||y −ŷ|| ≤ ||y − y ||, we have Sincec (y − x) ≤ −α||c|| 2 , it must be that Thus we see that (30) holds.
Lemma 5 shows that projected gradient descent will make constant progress on a linear program when the objective function is known. Of course there is some room for error in this estimate. The corollary below gives such a bound.
for some constant p > 0.
Proof. The argument here follows from the proof of Lemma 5 and we reuse the notation given there. Notice thatc The first inequality above applies the Cauchy-Schwartz inequality and Lemma 5. The second follows since projections reduce distances and we apply (35) recalling that y := x − αc. The final inequality follows from assumptions on δ in (35).
The following is a fairly standard bound on sub-Gaussian random variables. Similar bounds can be found in texts such as Vershynin [34]. A proof of Lemma 6 can be found in Appendix B.
Lemma 6. Given that the costsc i t are sub-Gaussian, it holds that for all δ > 0 The following proposition applies Lemma 6 to Corollary 2. So that we have a bound on the expected drift of our stochastic gradient descent algorithm.
There exist a batch size B such that Thus when (38) holds progress against the linear programming objective is guarenteed. We now seek to bound the error when (38) does not hold. Applying the Cauchy-Schwarz Inequality, From this upper-bound, observe that the errors are determined by the fluctuations in c t . Further, notice that the left-hand side of (38) equals α t ||c t −c||. Given these two observations, we analyze the term E ||c t || · I ||c t −c|| ≥ δ||c|| .
This term bounds the error inc x t+1 −c x t when (38) does not hold. Notice that by the Triangle Inequality We now bound the two terms (39) and (40). We can bound (39) using Lemma 6 We can bound (40) with Lemma 6 also. Specifically, We can the combine the above inequalities Since p is positive and independent of B it should be clear that for B sufficiently large we can choose p > 0.
The proof of Theorem 2 is now immediate.
Proof of Theorem 2. By Proposition 2, it holds that wheneverc x t −c x ≥ 2α||c|| 2 . In otherwords, Condition C1 of Theorem 1 is satisfied with δ = 2||c|| and B = p ||c||. Further we show that the moment generating function condition on increments, C2, is satisfied.
Thus in the context of condition C1 we can take Y =c c t . Notice by the sub-Gaussian assumption on costs (10), Thus we see that the moment generating function condition C2 is also satisfied. Since Condition C1 and C2 hold Theorem applies (as well as corollary). Thus theorem holds.

A Proofs of Additional Results
A.1 Linear Programming Formulation of MDPs.
In this section, we briefly recall the linear programming formulation of a Markov decision process. In other words, the optimal value function V can be found by solving the following linear program: Here the variables x(s, a) are sometimes referred to as occupancy measures. For a given variable x satisfying the constraints of the dual, we can determine a policy π(a|s) = x(s, a) a ∈A x(s, a ) .
A.2 Proof of Additional Lemma's from Section 4.
Finally, taking a k = α k and a k = α 2 k , we see that (48) holds since α t is decreasing. Thus, from (49), we see that the result (44) holds.
Proof. Notice by Taylor's Theorem, for some y t belonging to the line segment between x t and x t+1 , it holds that Thus we can see that the moment generating function condition (52) holds if we can prove that for some η > 0. The condition (53) is a consequence of (51). Specifically, E[e η||ct|| |F t ] = ∞ 0 P(e η||ct|| > y |F t )dy Thus from (54) we see that (53) holds and thus the required condition (52) holds.
B Additional Lemmas from Section 5 Lemma 6. Given that the costs c i t are sub-Gaussian, it holds that We let N be the 1 2 -net of the sphere S d−1 := {η ∈ R d : η = 1}. (Recall that N is an -net is a subset of S such that all points in S are within of a point in N .) The following bound on the cardinality of N is known To see why (58) holds: let η achieve the maximum in (56) and let η 0 be the point closest to η in N . Then In the first inequality above, we apply the Cauchy-Schwartz Inequality; then we apply the definition of η 0 ; rearranging (59) gives (58), as required. We now achieve the bound (55) as follows: for θ = δ||c||/4λ , The equality (60) follows from (56) and the definition of c t . The inequality (61) applies (58). The inequality (62) is a union bound. Inequality (63) applies the bound on the cardinality of |N | from (57). The inequalities from (63) to (64) applies the sub-Gaussian assumption on costs along with standard moment generating function bounds for sums of independent random variables.