Title: ONLINE BELLMAN RESIDUE MINIMIZATION VIA SAD-DLE POINT OPTIMIZATION

Abstract: We study the problem of Bellman residual minimization with nonlinear function approximation in general. Based on a nonconvex saddle point formulation of Bellman residual minimization via Fenchel duality, we propose an online first-order algorithm with two-timescale learning rates. Using tools from stochastic approximation, we establish the convergence of our problem by approximating the dynamics of the iterates using two ordinary differential equations. Moreover, as a byproduct, we establish a finite-time convergence result under the assumption that the dual problem can be solved up to some error. Finally, numerical experiments are provided to back up our theory.

1. INTRODUCTION:

Reinforcement learning (RL) (Sutton & Barto, 1998) studies the problem of sequential decision making under uncertainty. In these problems, an agent aims to make optimal decisions by interacting with the environment, which is modeled as a Markov Decision Process (MDP). Thanks to the recent advancement of deep learning, reinforcement learning has demonstrated extraordinary empirical success in solving complicated decision making problems, such as the game of Go (Silver et al., 2016; 2017) , navigation (Banino et al., 2018) , and dialogue systems (Li et al., 2016) .

However, when nonlinear function approximation such as neural networks are utilized, theoretical analysis of RL algorithms becomes intractable as it involves solving a highly nonconvex statistical optimization problems. Whereas in the tabular case or in the case with linear function approximation, using tools for convex optimization and linear regression, the statistical and computational properties of the reinforcement learning algorithms are well-understood under these settings. In consequence, although RL algorithms with nonlinear function approximation great empirical success, their theoretical understanding lags behind, which makes it difficult to design RL methods in a principled fashion.

Moreover, from a statistical perspective, with nonlinear function approximation, RL methods such as fitted value iteration (Munos & Szepesvári, 2008) , fitted Q-iteration (Antos et al., 2008a) , and Bellman residual minimization Antos et al. (2008b) can be cast as nonlinear regression problems. Using nonparametric regression tools, statistical properties of batch RL methods with nonlinear function approximation are established (Farahmand et al., 2016) . However, when it comes to computational properties, due to the fundamental hardness of nonconvex optimization, theoretical understanding of the convergence of RL methods remains less explored, which is contrast to the case with linear function approximation, where the convergence of online algorithms based on temporal-difference (TD) learning are well studied.

In this work, we we make the first attempt to study an online algorithm for Bellman residual minimization, with nonlinear function approximation. In the batch form, Bellman residual minimization is formulated as a bilevel optimization, which cannot be solved with computational efficiency. To tackle this problem, we formulate the Bellman residual itself as the optimal value of another maximization problem. In this way, Bellman residual minimization becomes a saddle point problem, where the value function is the primal variable, and the dual variable tracks the TD-error of the primal variable. By also parametrizing the dual variable using a parametrized function class, we propose a primal-dual subgradient method which is an online first-order method for Bellman residue minimization.

Furthermore, since the saddle-point problem is not convex-concave, the order between the inner maximization and outer minimization problems plays a significant role. Similar to the batch algorithm, ideally we would fix the primal variable and solve the inner maximization problem to its global optima, and then updated the primal variable. However, in the online setting, this approach is not tractable. To achieve computational efficiency, we apply the two-timescale updates to the primal and dual variables. Specifically, we update the primal and dual variables using two sets of learning rates, where the learning rate of the dual variable is much larger than that of the primal variable. Using stochastic approximation (Borkar, 2008; Kushner & Yin, 2003) , two-timescale updating rules ensures that we could safely fix the primal variable when studying the convergence of the dual variable. In this case, the dual variable converges to a local maximum of the inner maximization problem. Moreover, the dynamics of the iterates are characterized by two ordinary differential equations (ODE) running at different timescales.

Our contributions are three-fold. First, we formulate the problem of Bellman residual minimization as a nonconvex saddle point problem, for which we propose an online first-order algorithm using two-timescale learning rates. Second, using stochastic approximation, we show that the online algorithm converges almost surely to the asymptotically equilibria of an ODE. Third, assuming the existence of an optimization oracle which solves the dual problem up to some error, we show that the stochastic gradient method in the primal step converges to a stationary point of the squared Bellman residual up to some fundamental error.

Related Work. The statistical properties of Bellman residual minimization is studied in Antos et al. (2008b) ; Maillard et al. (2010); Farahmand et al. (2016) for policy evaluation, where the problem is solved using least-squares regression under the batch setting. Moreover, in these work, Bellman residue minimization is an intermediate step of least-squares policy iteration Lagoudakis & Parr (2003) . These work are not comparable to our work since our study an online algorithm for Bellman residue minimization and its convergence.

In addition, our work is related to the line of research on the online algorithms for policy evaluation with function approximation. Most existing work focus on linear function approximation. Specifically, Tsitsiklis & Van Roy (1997) study the convergence of the on-policy TD(λ) algorithm based on temporal-difference (TD) error. To handle off-policy sampling, Maei et al. (2010); Sutton et al. (2009; 2016) ; Yu (2015) ; Hallak & Mannor (2017) propose various TD-learning methods with convergence guarantees. Utilizing two-timescale stochastic approximation in Borkar (2008) and strong convexity, they establish global convergence results for the proposed methods. The finite-sample analysis of these methods are recently established in Dalal et al. (2017b; a) . More related works are Liu et al. (2015) ; Du et al. (2017) , which formulate minization of the mean-squared projected Bellman error as a saddle point problem using Fenchel duality. However, since they consider linear function approximation, the corresponding saddle point problem is convex-concave, whereas our objective is nonconvex. When it comes to nonlinear function approximation, to the best of our knowledge, the only convergent algorithm is the nonlinear-GTD algorithm proposed in Bhatnagar et al. (2009) . Their algorithm depends on the Hessian of the value function, and thus might be costly in practice.

Moreover, it is worth noting that Dai et al. (2017b) apply the same saddle point formulation to soft Qlearning. However, they consider a batch algorithm with the assumption that the inner maximization can be solved to the global optima. Due to nonconvexity, this assumption could stringent. Furthermore, Chen & Wang (2016) ; Wang (2017) propose primal-duality of reinforcement learning based on the Lagrangian duality of linear programming for MDP (Puterman, 2014) . These work establish convergence results in the tabular case. Applying neural networks to the same duality formulation, Dai et al. (2017a); Cho & Wang (2017) propose variants of the actor-critic algorithms (Konda & Tsitsiklis, 2000) , which does not have convergence guarantees.

Notation. We use the following notations throughout this paper. For any vector x ∈ R n , we use x 2 and x ∞ to denote the Euclidean norm and the ∞ -norm of x, respectively. For a finite set M, we use |M| to denote its cardinality. We denote by P(M) the set of all probability measures on M and we write B(M) for the set of all bounded functions defined on M. For a function f ∈ B(M), we define the ∞ -norm of f as f ∞ = sup x∈M |f (x)|. Moreover, for any probability measure µ ∈ P(M), we write f µ for the 2 -norm with respect to µ, i.e.,

f µ = [ M |f (x)| 2 dµ(x)] 1/2 . Finally, we use [n] to denote the set of integers {1, • • • , n}.

2. VALUE FUNCTION ESTIMATION IN RL:

In this section, we introduce some background on reinforcement learning that will be used in the presentation our main results.

In reinforcement learning, the environment is often modeled as a Markov decision process (MDP) denoted by a tuple (S, A, P, r, γ), where S is the set of states, A is the set of all possible actions, P : S × A → P(S) is the Markov transition kernel, r : S × A → R is the reward function, and γ ∈ (0, 1) is the discount factor. More specifically, an agent interacts with the MDP sequentially in the following way. At the t-th step for any t ≥ 0, suppose the MDP is at state s t ∈ S and the agent selects an action a t ∈ A; then, the agent observes reward r(s t , a t ) and the MDP evolves to the next state s t+1 ∼ P (• | s t , a t ). Here P (• | s, a) is the probability distribution of the next state when taking action a at state s. The discounted cumulative reward is defined as R = t≥0 γ t • r(s t , a t ).

In addition, a policy π : S → P(A) specifies a rule of taking actions. Specifically, π(a|s) is the probability of selecting action a at state s under policy π. We note that π induces a Markov chain on S × A with transition probability p(s , a | s, a) = π(a | s ) • P (s | s, a). We define the (action) value function of policy π as Q π (s, a) = E(R | s 0 = s, a 0 = a, π), which is the expected value of the discounted cumulative reward when the agent takes action a at state s, and follows policy π afterwards. Moreover, we define the optimal value function Q * : S × A → R by letting Q * (s, a) = sup π Q π (s, a) for all (s, a) ∈ S × A, where the supremum is taken over all possible policies. By definition, Q * (s, a) is the largest reward obtainable by the agent when starting from (s, a). It is well-known that Q π and Q * are the unique fixed points of the Bellman evaluation operator T π and the Bellman optimality operator T * , respectively. Specifically, Bellman operators T π : B(S ×A) → B(S × A) and T * : B(S × A) → B(S × A) are defined respectively by

(T π Q)(s, a) =r(s, a) + γ • E Q(s t+1 , a t+1 ) s t = s, a t = a, a t+1 ∼ π(• | s t+1 ) ,

(2.1)

(T * Q)(s, a) =r(s, a) + γ • E max a∈A Q(s t+1 , a) s t = s, a t = a , (2.2)

where s t+1 ∼ P (• | s t , a t ). The problems of estimating Q π and Q * are usually referred to as policy evaluation and optimal control, respectively. Both of these problems lie at the core of reinforcement learning. Specifically, policy evaluation is the pivotal step of dynamic programming methods. Moreover, estimating Q * by applying the Bellman optimality operator in (2.2) repeatedly gives the classical Q-learning algorithm (Watkins & Dayan, 1992) , based on which a number of new algorithms are developed.

In this work, we propose a saddle framework for stochastic fixed-point problems in general.

3. A SADDLE POINT FORMULATION OF BELLMAN RESIDUE MINIMIZATION:

In this section, we formulate the problem of estimating the value functions introduced in §2 as saddle point optimization problems. Before going into the details, we first introduce a standard assumption on the MDP.

Assumption 3.1 (MDP Regularity). The MDP (S, A, P, r, γ) satisfies the following conditions.

(i). The action space A is a finite set, and there exists a constant R max > 0 such that |r(s, a)| ≤ R max for any (s, a) ∈ S × A.

(ii). For policy evaluation problem, we assume that the Markov chain on S × A induced by policy π has a stationary distribution d π ∈ P(S × A). For estimating Q * , we consider the off-policy setting where we collect data using a behavioral policy π b : S → A. Moreover, we assume that π b induces a stationary distribution d π b over S × A. Moreover, we assume that it is possible to draw i.i.d. samples from d π and d π b .

The first condition in Assumption 3.1 ensures that both Q * and Q π are bounded by R max /(1 -γ).

The stationary distributions d π and d π b in the second condition is are the natural measures to evaluate the error of estimating Q π and Q * . This condition holds if the Markov chains induced by π and π b are irreducible and aperiodic. Moreover, when these two Markov chains possess the rapid mixing property, the observations are nearly independent, which justifies the assumption of i.i.d. sampling from d π and d π b .

In the following, we first focus on estimating Q * ; the results for Q π can be similarly obtained by replacing T * by T π in (2.1). To simplify the notation, we denote d π b by ρ. When the capacity of S is large, to estimate Q * efficiently, we estimate Q * using a parametrized function class

F = {Q θ : S × A → R, θ ∈ R d },

where θ is the parameter. Then the problem is reduced to finding a parameter

θ ∈ R d such that Q θ is close to Q * . Since Q * is unknown, it is impossible to minimize the mean-squared error Q θ -Q * 2 ρ . Since Q * is the unique fixed point of T * , a direct idea is to minimize the mean-squared Bellman residual minimize θ∈R d J(θ) = Q θ -T * Q θ 2 ρ = E (s,a)∼ρ [Q θ (s, a) -(T * Q θ )(s, a)] 2 .

(3.1) via (stochastic) subgradient descent. By definition, the subgradient of J(θ) is

∇ θ J(θ) = E (s,a)∼ρ [Q θ (s, a) -(T * Q θ )(s, a)] • (∇ θ Q θ )(s, a) -[∇ θ (T * Q θ )](s, a) , (3.2)

where ∇ θ (T * Q θ )(s, a) is the subgradient of T * Q θ (s, a) with respect to θ, which is given by

EQUATION

where a = argmax b∈A Q θ (s t+1 , b). Although combining (3.2) and (3.3) yields the closed form of ∇J(θ), there exists a fundamental challenge when applying gradient-based methods to (3.1). Specifically, notice that both (T * Q θ )(s, a) and (∇ θ T * Q θ )(s, a) involves conditional expectation given (s, a) ∈ S × A, and these two terms are multiplied are together in ∇ θ J(θ) in (3.2). Thus, to construct an unbiased estimator of ∇ θ J(θ), given an observation (s, a) ∼ ρ, we need to draw two independent samples from P (• | s, a) to ensure that the estimators of (T * Q θ )(s, a) and (∇ θ T * Q θ )(s, a) constructed respectively using these two samples are conditionally independent given (s, a). Such an issue is called the "double sampling" problem in reinforcement learning literature (Baird et al., 1995) .

To resolve this issue, inspired by the saddle point formulation of soft Q-learning in Dai et al. (2017b) , we formulate the objective function J(θ) as

J(θ) = maximize µ∈B(S×A) E ρ -1/2 • [µ(s, a)] 2 + [Q θ (s, a) -(T * Q θ )(s, a)] • µ(s, a) , (3.4)

where the maximization is taken over all functions µ : S × A → R. In particular, for any fixed θ, the solution of the optimization problem in 

(3.4) is δ θ (s, a) = Q θ (s, a)-(T * Q θ )(s,

EQUATION

where (s, a) ∼ ρ and s ∼ P (• | s, a) is the next state given (s, a). Here θ and ω can be viewed as the primal and dual variables respectively. The gradients of L(θ, ω) with respect to θ and ω are given by

∇ θ L(θ, ω) = E s,a,s µ ω (s, a) • ∇ θ Q θ (s, a) -γ • ∇ θ Q θ (s , a ) , (3.6) ∇ ω L(θ, ω) = E s,a,s ∇ ω µ ω (s, a) • Q θ (s, a) -R(s, a) -γ • max b∈A Q θ (s , b) -µ ω (s, a) , (3.7)

where a in (3.6) satisfies that a = argmax b∈A Q θ (s , b). From (3.6) and (3.7), replacing ∇ θ L(θ, ω) and ∇ ω L(θ, ω) by the stochastic gradients based on one observation (s, a, s ), we establish an stochasitc subgradient algorithm, whose details are given in Algorithm 1. Since the saddle point problem (3.5) is nonconvex, in the algorithm we project the iterates onto compact sets Θ ⊆ R d and Ω ⊆ R p respectively. Moreover, notice that ideally we would like to solve the inner maximization problem in (3.5) for fixed θ. To achieve such a goal in an online fashion, we perform the primal and dual steps in different paces. Specifically, the learning rates α t and β t satisfy β t /α t → ∞ as t goes to infinity. Using results from stochastic approximation (Borkar, 2008; Kushner & Yin, 2003) , such a condition on the learning rates ensures that the dual iterates {ω t } t≥0 asymptotically track the sequence {argmax ω∈R p L(θ t , ω)} t≥0 , thus justifying our algorithm.

Algorithm 1 A Primal-Dual Algorithm for Q-Learning

Input: Initial parameter estimates θ 0 ∈ R d and ω 0 ∈ R p , primal and dual learning rates

{α t , β t } t≥0 . for t = 0, 1, 2, . . . until convergence do Sample (s t , a t ) ∼ ρ, observe reward r(s t , a t ) and the next state s t . Let a t = argmax a∈A Q θt (s t , a).

Update the parameters by

ω t+1 ← Π Ω ω t + β t • ∇ ω µ ωt (s t , a t ) • Q θt (s t , a t ) -r(s t , a t ) -γ • Q θt (s t , a t ) -µ ωt (s t , a t ) , (3.8) θ t+1 ← Π Θ θ t -α t • µ ωt (s t , a t ) • ∇ θ Q θt (s t , a t ) -γ • ∇ θ Q θt (s t , a t ) .

(3.9)

end for:

Furthermore, for policy evaluation, we replace T * by T π in (3.4) to obtain Finally, it is worth noting that, various saddle point formulations of Bellman residual minimization are proposed to avoid the issue of double sampling (Antos et al., 2008b; Farahmand et al., 2016; Dai et al., 2017b) . Our formulation is the same as the one for soft Q-learning in Dai et al. (2017b) , and is equivalent to that in Antos et al. (2008b); Farahmand et al. (2016) for policy evaluation. All of these work are batch algorithms, with the assumption that the global optima of the inner maximization can be reached. Whereas we propose an online first-order algorithm with nonlinear function approximation. Moreover, our analysis utilize tools from stochastic approximation of iterative algorithms (Borkar, 2008; Kushner & Yin, 2003) , which is significantly different from their theory. .

min θ∈R d max ω∈R p E s,a,s ,a -1/2 • [µ ω (s, a)] 2 + Q θ (s, a) -r(s, a) -γ • Q θ (s , a ) • µ ω (s,

4. THEORETICAL RESULTS:

In this section, we lay out the theoretical results. For ease of presentation, we focus on the estimation of Q * while our theory can be easily adapted to the policy evaluation problem. We first state the assumption on function class

F = {Q θ : θ ∈ R d }.

Assumption 4.1. Here we assume that, for any (s, a)

∈ S × A, Q θ (s, a) is a differentiable func- tion of θ such that |Q θ (s, a)| ≤ Q max ∇ θ Q θ (s, a) 2 ≤ G max , and that ∇ θ Q θ (s, a) is Lipschitz continuous in θ, where Q max ≥ R max /(1 -γ) and G max > 0 are two constants.

Here our assumption on F allows nonlinear function approximation of the value function in general. Moreover, we only consider bounded value functions since Q * is bounded by R max /(1 -γ).

Moreover, we assume that ∇ θ Q θ (s, a) is bounded and Lipschitz continuous for regularity. This assumption can be readily satisfied if θ is restricted to a compact subset of R d .

In addition, we assume that G = {µ ω : ω ∈ R p } is a class of linear functions as follows.

Assumption 4.2. We assume that µ ω (s, a) = ω φ(s, a) for any ω ∈ R p , where φ : S × A → R p is a feature mapping such that φ(s, a) is uniformly bounded for any s ∈ S, a ∈ A. Furthermore, we assume that there exists a constant

σ min > 0 such that E (s,a)∼ρ [φ(s, a)φ(s, a) ] σ min • I p .

Here we assume the dual function is linear for the purpose of theoretical analysis. In this case, the inner maximization problem max ω L(θ, ω) has a unique solution

ω(θ) = E (s,a)∼ρ [φ(s, a)φ(s, a) ] -1 E (s,a)∼ρ φ(s, a) • [Q θ (s, a) -(T * Q θ )(s, a)] (4.1) for any θ ∈ R d . Thus, µ(θ) is the minimizer of Q θ -T * Q θ -µ ω(θ) 2 ρ , i.e., µ ω(θ)

is the best approximation of the TD-error using function class G. It is possible to extend our result to nonlinear µ ω following the analysis in Heusel et al. (2017) under stronger assumptions. In addition, we note that most online TD-learning algorithms uses linear function approximation. Moreover, it is shown in Tsitsiklis & Van Roy (1997) that TD-learning with nonlinear function approximation may fail to converge. To the best of our knowledge, for nonlinear function approximation, the nonlinear GTD algorithm in Bhatnagar et al. (2009) is the only convergent online algorithm. However, their focus solely on policy evaluation, and their approach depends on the Hessian ∇ 2 θ V θ . As a comparison, our method also consider nonlinear function approximation and can be applied to both policy evaluation and optimal control. Now we are ready to present the convergence result for Algorithm 1. Theorem 4.3. We assume the learning rates {α t , β t } t≥0 in (3.8) and (3.9) satisfy

t≥0 α t = t≥0 β t = ∞, t≥0 α 2 t + β 2 t < ∞, lim t→∞ α t /β t = 0. (4.2)

In addition, let Θ ⊆ R d and Ω ⊆ R p be the Euclidean balls with radius R θ and R ω respectively. For function L(θ, ω) defined in (3.5), we define

K = θ ∈ Θ : ∇ θ L(θ, ω)| ω=ω(θ) = 0 ∪ θ ∈ ∂Θ : ∇ θ L(θ, ω)| ω=ω(θ) = λθ for some λ ≥ 0 . (4.3)

Then under Assumptions 3.1, 4.1, and 4.2, the iterates {(θ t , ω t )} t≥0 created by Algorithm 1 converges almost surely to the set {[θ * , ω(θ * )], θ * ∈ K}.

In addition to the Robbins-Monro condition, (Robbins et al., 1951 ), the learning rates in (4.2) also satisfies lim t→∞ α t /β t = 0. Intuitively, this means that the sequence {ω t } t≥1 tracks {ω(θ t )} t≥1 asymptotically. In other words, (4.2) enables our online algorithm to approximately solve the inner maximization problem max ω L(θ, ω) with θ fixed. Using two-timescale stochastic approximation (Borkar, 2008; Kushner & Yin, 2003) , when studying the convergence {θ t } t≥0 , we could replace ω t in (3.9) by ω(θ t ). In this case, using ODE approximation, {θ t } t≥0 converges almost surely to K in (4.3), which is the asymptotically stable equilibria of the projected ODE θ = ∇ θ L(θ, ω)| ω=ω(θ) +ξ θ , where ξ θ (t) is the correction term caused by projection onto Θ.

Furthermore, even when Θ is sufficiently large such that {(ω t , θ t )} t≥0 converges to [ω(θ * ), θ * ] with ∇ θ L[θ * , ω(θ * )] = 0, due to the error of function approximation, θ * is not a stationary point of J(•). Specifically, let δ θ = Q θ -T * Q θ be the TD-error. Then, by (3.6) we have

∇ θ J(θ * ) = E (s,a)∼ρ [∇ θ δ θ * (s, a) • δ θ * (s, a)] = E (s,a)∼ρ ∇ θ δ θ * (s, a) • [δ θ * (s, a) -µ ω(θ * ) (s, a)] . (4.4)

Since µ ω(θ * ) is the best approximator of δ θ * within G, θ * is in a neighborhood of a stationary point of J(•) if the function approximation error is small.

To see error incurred in estimating the TD-error reflects the fundamental limit of our method, we also provide a finite-time analysis provided that there exists an optimization oracle which approximately solves the inner maximization problem in (3.1). Assumption 4.4 (Optimization Oracle). We assume that there exists an optimization oracle that returns a bounded function µ θ ∈ B(S × A) when queried by any θ ∈ R d . Moreover, we assume that |µ θ (s, a)| ≤ 2Q max for any (s, a) ∈ S × A, and there exists a constant > 0 such that

µ θ -δ θ 2 ρ ≤ ε.

Here we assume that the estimator µ θ for δ θ is bounded by 2Q max since δ θ is bounded by 2R max /(1 -γ) under Assumption 3.1. Moreover, in light of Algorithm 1, ε can be viewed as the estimation error of the TD-error using {µ ω , ω ∈ Ω}, i.e., sup θ∈Θ inf ω∈Ω δ θ -µ ω ρ . Now we update {θ t } t≥0 by

θ t+1 ← θ t -α t • µ θt (s t , a t ) • ∇ θ Q θt (s t , a t ) -γ • ∇ θ Q θt (s t , a t ) , (4.5)

where s t is the next state given (s t , a t ) ∼ ρ, and a t = argmax a∈A Q θt (s t , a). The following theorem shows that any limit point of {θ t } t≥0 is in the vicinity of a stationary point of J(•) with error proportional to ε. Theorem 4.5. Assume that the learning rates {α t } t≥0 in (4.5) satisfy t≥0 α t = ∞ and t≥0 α 2 t < ∞. Under Assumptions 3.1, 4.1, and 4.4, with probability one, we have

lim sup t≥0 ∇ θ J(θ t ) 2 ≤ 8G max • ε.

To understand this theorem, first notice that the update direction in (4.5) is a noisy version of

E (s,a)∼ρ [ µ θt (s, a) • ∇ θ δ θt (s, a)],

which is a biased estimate of ∇ θ J(θ t ). Moreover, under Assumptions 4.1 and 4.4, such a bias can be bounded by 8G max • ε. Due to this bias in gradient estimation, {θ t } t≥1 can only enter a neighborhood of a stationary point. In addition, for Algorithm 1 with G being the class of linear functions, the optimization oracle outputs µ ω(θ) = φ ω(θ) for any θ ∈ Θ. Applying Cauchy-Schwarz inequality to (4.4), we have ∇J(θ * ) 2 ≤ 2G max • δ θ * -µ ω(θ * ) ρ . Thus, Theorems 4.3 and 4.5 yield consistent results, which implies that the error incurred by estimating the TD-error using function class G leads to unavoidable error of our approach.

5. EXPERIMENTS:

To justify our proposed method for estimating value function, we compare it with the classical deep Q-network (DQN) on several control tasks from the OpenAI Gym (Brockman et al., 2016) . For a fair comparison, we use the codes from OpenAI Baselines (Dhariwal et al., 2017) for DQN, and use the same parametrization for both our method and DQN. The parameters are fine-tuned for each task to achieve the state-of-art performance. We run the algorithms with 5 random seeds and report the average rewards with 50% confidence intervals. Figure 1 (a)-(c ) illustrates the empirical comparison results for the environments CartPole-v0, MountainCar-v0 and Pendulum-v0. We can see that in all these tasks, our method achieves the equivalent performance to DQN. The experiment settings are as follows.

• CartPole-v0. For both methods, we set the learning rate for Q-network, i.e. α t , as 10 -3

with batch size 32. The Q-network is a one-layer network with 30 hidden nodes. The µ-network's learning rate and structure are the same as the Q-network.

• Pendulum-v0. For both methods, we set α t as 10 -4 with batch size 1000. The Q-network is a two-layer network with 40 hidden nodes for each layer. The learning rate and structure of the µ-network are the same as Q-network.

• MountainCar-v0. For both methods, we set α t as 10 -4 with batch size 1000. The Qnetwork is a two-layer network with 20 hidden nodes for each layer. The learning rate for the µ-network, i.e. β t , is also 10 -4 with the same structure as Q-network.

As is shown in Theorem 4.3, we require lim t→∞ α t /β t = 0 to guarantee the solution of inner maximization problem max ω L(θ, ω) asymptotically. To justify this theoretical result, we test our method on CartPole-v0 with different setting of α t and β t . The results are illustrated in Figure 1-(d) .

We set α t /β t as 100, 1, and 0.01, respectively. As the learning rate ratio α t /β t deceases, the reward increases faster and become more stable around the solution. From Case I, when α t /β t is too big, our method cannot guarantee the solution of control task, which is in accordance with Theorem 4.3.

6. CONCLUSION:

In this work, we propose an online first-order algorithm for the problem of Bellman residual minimization with nonlinear function approximation in general. Our algorithm is motivated by a duality formulation. Moreover, we establish the convergence of our problem by via ODE approximation, utilizing tools from stochastic approximation. In addition, we also establish a finite-time convergence result under the assumption of a computational oracle. Finally, numerical experiments are provided to back up our theory. shown in these plots, our method achieves the equivalent performance to the classical DQN. In addition, in (d) we show the performances of our method for CartPole-v0 under different learning rates. For Case I, we set α t = 10 -2 , β t = 1e -4 with α t /β t = 100. For Case II, we set α t = 10 -4 , β t = 10 -4 with α t /β t = 1. For Case III, we set α t = 10 -4 , β t = 10 -2 with α t /β t = 0.01.

The figure shows that α t /β t → 0 is critical for our method to work, which agrees with the theory.

A ALGORITHMS FOR POLICY EVALUATION AND SOFT Q-LEARNING:

For policy evaluation, we replace T * in (3.4) by the Bellman evaluation operator T π , which yields a saddle point problem

min θ∈R d max ω∈R p L π (θ, ω) = E s,a,s ,a -1/2 • [µ ω (s, a)] 2 + Q θ (s, a) -r(s, a) -γ • Q θ (s , a ) • µ ω (s, a) , (A.1)

where (s, a) ∼ ρ, s ∼ P (• | s, a) is the next state given (s, a), and a ∼ π(• | s ). The gradients of L π (θ, ω) with respect to θ and ω are given by

∇ θ L π (θ, ω) = E s,a,s ,a µ ω (s, a) • ∇ θ Q θ (s, a) -γ • ∇ θ Q θ (s , a ) , ∇ ω L π (θ, ω) = E s,a,s ,a ∇ ω µ ω (s, a) • Q θ (s, a) -R(s, a) -γ • Q θ (s , a ) -µ ω (s, a) .

Therefore, replacing the primal and dual gradients by their unbiased estimates, we obtain Algorithm 2.

Algorithm 

ω t+1 ← Π Ω ω t + β t • ∇ ω µ ωt (s t , a t ) • Q θt (s t , a t ) -r(s t , a t ) -γ • Q θt (s t , a ) -µ ωt (s t , a t ) , θ t+1 ← Π Θ θ t -α t • µ ωt (s t , a t ) • ∇ θ Q θt (s t , a t ) -γ • ∇ θ Q θt (s t , a ) .

Furthermore, soft Q-learning is proposed Haarnoja et al. (2017) based on the maximum entropy principle. This problem aims to find the fixed point of the soft Bellman operator T defined by

(T Q)(s, a) = r(s, a) + γ • E τ • log a∈A exp[Q(s t+1 , a)/τ ] s t = s, a t = a , (A.2)

where τ > 0 is the temperature parameter. By definition, T can be seen as a smooth approximation of the Bellman optimality operator, where the max function in (2.2) is replaced by the softmax function, where parameter τ controls the approximation error. It is known that T also admits a unique fixed point, denoted by Q : S × A → R. To estimate Q with function approximation, similar to (3.5) and (A.1), we consider the saddle point problem min θ∈R d max ω∈R p L (θ, ω), where L (θ, ω) is given by

L (θ, ω) = E s,a,s -1/2 • [µ ω (s, a)] 2 + Q θ (s, a) -r(s, a) -γ • τ • log a∈A exp[Q θ (s , a)/τ ] • µ ω (s, a) ,

where (s, a) ∼ ρ and s ∼ P (• | s, a). Here ρ is the stationary distribution on S × A induced by the behavioral policy π b . By direct computation, the gradients of L (θ, ω) with respect to θ and ω are given by

∇ θ L (θ, ω) = E s,a,s ,a µ ω (s, a) • ∇ θ Q θ (s, a) -γ • a∈A ν θ (s , a) • ∇Q θ (s , a) , ∇ ω L (θ, ω) = E s,a,s ,a ∇ ω µ ω (s, a) • Q θ (s, a) -R(s, a) -γ • τ • log a∈A exp[Q θ (s , a)/τ ] -µ ω (s, a) ,

where we define ν θ : S × A → [0, 1] by

ν θ (s, a) = exp[Q θ (s, a)/τ ] a ∈A exp[Q θ (s, a)/τ ] , ∀(s, a) ∈ S × A, ∀θ ∈ R d .

Thus, we obtain a stochastic gradient algorithm for estimating Q , which is stated in Algorithm 3. 

t = Q θt (s t , a t ) -r(s t , a t ) -γ • τ • log{ a∈A exp[Q θt (s t , a)/τ ]}.

Update the parameters by

ω t+1 ← Π Ω ω t + β t • ∇ ω µ ωt (s t , a t ) • δ t -µ ωt (s t , a t ) , θ t+1 ← Π Θ θ t -α t • µ ωt (s t , a t ) • ∇ θ Q θt (s t , a t ) -γ • ∇ θ Q θt (s t , a t ) .

end for

B PROOFS OF THE MAIN RESULTS:

B.1 PROOF OF THEOREM 4.3

Proof. The proof of this theorem consists of two steps, where we consider the faster and slower timescales seperately.

Step 1. Faster timescale. We first consider the convergence of {θ t , ω t } t≥1 in the faster timescale.

Using ODE approximation, we will show that the sequence of dual variables {ω t } t≥0 generated from (3.8) tracks the solution of the inner maximization problem, i.e., argmax ω L(θ t , ω). To begin with, for notational simplicity, we define φ t = φ(s t , a t ),

δ t = Q θt (s t , a t ) -r(s t , a t ) -γ • Q θt (s t , a t ), A t = ∇ θ Q θt (s t , a t ) -γ • ∇ θ Q θt (s t , a t ), (B.1)

for all t ≥ 0, where a t = argmax a∈A Q θt (s t , a). Then the updating rules in Algorithms 1 reduce to

ω t+1 ← Π Ω ω t + β t • (δ t -φ t ω t ) • φ t , θ t+1 ← Π Θ θ t -α t • φ t ω t • A t , (B.2)

where {α t , β t } t≥0 are the learning rates, and Π Θ is the projection operator. Moreover, we define F t = σ({s τ , a τ , r(s τ , a τ ), s τ } τ ≤t ) as the σ-algebra generated by the history until time t. Thus, θ t and ω t are F t-1 -measurable for any t ≥ 1. Furthermore, for any θ ∈ R d and ω ∈ R p , we define

h(θ, ω) = E (s,a)∼ρ φ(s, a) • [Q θ (s, a) -(T * Q θ )(s, a) -φ(s, a) ω] , (B.3) g(θ, ω) = E (s,a)∼ρ φ(s, a) ω • ∇ θ Q θ (s, a) -[∇ θ (T * Q θ )](s, a) . (B.4)

Then by definition, we have

E[δ t -φ t ω t )•φ t | F t-1 ] = h(θ t , ω t ) and E[φ t ω t •A t | F t-1 ] = g(θ t , ω t )

for any t ≥ 1, which implies that {ζ t } t≥1 and {η t } t≥1 defined by

ζ t = (δ t -φ t ω t ) • φ t -h(θ t , ω t ), η t = φ t ω t • A t -g(θ t , ω t ) (B.5)

are two martingale difference sequence with respect to filtration {F t } t≥1 . Moreover, we define C Θ (θ) as the outer normal cone of Θ at θ ∈ Θ, and define C Ω (ω) for Ω similarly.

Thus, (B.2) can be written as

θ t+1 ω t+1 = Π Θ×Ω θ t ω t -β t • α t /β t • A t • φ t ω t φ t φ t ω t -δ t • φ t = θ t ω t -β t • α t /β t • A t • φ t ω t φ t φ t ω t -δ t • φ t + ξ θ t ξ ω t , (B.6)

where Π Θ×Ω is the projection onto product set Θ × Ω = {(u, v) : u ∈ Θ, v ∈ Ω}, and ζ θ t and ζ ω t in (B.5) are the correction terms induced by projection. Thus, by definition, we have ξ θ t ∈ -C Θ (θ t+1 ) and ξ ω t ∈ -C Ω (ω t+1 ), respectively. Furthermore, under Assumption 4.1, both Q θ (s, a), ∇ θ Q θ (s, a), and φ(s, a) are bounded, which implies that there exist a constant

C > 0 such that E[ ζ t 2 2 + η t 2 2 | F t-1 ] ≤ C for all t ≥ 1.

Under review as a conference paper at ICLR 2019

Moreover, let M T = T t=1 β t • (ξ θ t , ξ ω t ) ∈ R d+p for any T ≥ 1. Since t≥1 β 2 t < ∞, {M T } T ≥1

is a square-integrable martingale sequence. Moreover, by the Martingale convergence theorem (Proposition VII-2-3(c) on page 149 of Neveu (1975) ), {M T } T ≥1 converges almost surely. Thus, for any > 0, by Doob's martingale inequality Doob (1953), we have

P sup N ≥T M N -M T ≥ ≤ sup N ≥T E[ M N -M T 2 2 ] 2 ≤ 2C 2 t≥T β 2 t 2

, which converges to zero as T goes to infinity. Furthermore, recall that, under the two-timescale assumption of the learning rates, we have α t /β t → 0 as t goes to infinity, which implies that

lim t→∞ α t /β t • A t • φ t ω t = 0.

Now we apply the Kushner-Clark lemma (Kushner & Clark, 1978 , see also Theorem D.2 in §D for details) to sequence {(θ t , ω t ) } t≥1 , which implies that the asymptotic behavior of {(θ t , ω t )} t≥1 is characterized by the projected ODE

θ = 0 + ξ θ , ω = h(θ, ω) + ξ ω , (B.7)

where h is defined in (B.3), and ξ θ and ξ ω satisfy ξ θ (t) ∈ -C Θ (θ(t)) and ξ ω (t) ∈ -C Θ (ω(t)) for any t ≥ 0. Specifically, sequence {(θ t , ω t ) } t≥1 converges almost surely to the set of asymptotically stable equilibria of the projected ODE in (B.7), which is given by

(θ * , ω * ) : θ * ∈ Θ, h(θ * , ω * ) ∈ C Ω (ω * ) . (B.8)

Recall that Ω is the Euclidean ball in R p with radius R ω . Thus, the boundary of Ω, ∂Ω, is {ω :

ω 2 = R ω }. For any ω ∈ ∂Ω, the outer normal cone is C Ω (ω) = {λ • ω : λ ≥ 0}.

In the sequel, we show that, for any

(θ * , ω * ) in the equilibria in (B.8), ω * is in the interior of Ω, i.e., ω * 2 < R ω . This implies that {(θ t , ω t )} t≥1 converges almost surely to {(θ * , ω * ) : θ * ∈ Θ, h(θ * , ω * ) = 0}.

Then, by definition, we have h[θ, ω(θ)] = 0 for any θ ∈ R d , which implies that ω(θ) is the unique maximizer of max ω∈R p L(θ, ω) since L(θ, ω) is a strictly concave quadratic function of ω and h(θ, ω) = ∇ ω L(θ, ω). Moreover, since φ(s, a) 2 is bounded for any (s, a) ∈ S × A and the eigenvalues of E (s,a)∼ρ [φ(s, a)φ(s, a) ] are at least σ min > 0, by norm inequality, we have

ω(θ) 2 ≤ 2Q max /σ min • sup (s,a) φ(s, a) 2 .

(B.9) Thus, if R ω is larger than the right-hand side of (B.9), ω(θ) is in the interior of Ω for any θ ∈ Θ.

Now we assume to the contrary that ω * ∈ ∂Ω. By (B.8), there exists λ > 0 such that

λ • ω * = h(θ * , ω * ) = E (s,a)∼ρ [φ(s, a)φ(s, a) ] • [ω(θ * ) -ω * ], (B.10)

where the second equality follows from (B.3) and (4.1). For the right-hand side of (B.10), we have

[ω(θ * ) -ω * ] • E (s,a)∼ρ [φ(s, a)φ(s, a) ] • [ω(θ * ) -ω * ] ≥ c min • ω * -ω(θ * ) 2 2 > 0. (B.11) However, since ω(θ * ) is in the interior of Ω, we have λ • ω(θ * ) -ω * , ω * = λ • ω * 2 • ω(θ * ) 2 -λ • ω * 2 2 < 0. (B.12)

Thus, the contradiction between (B.11) and (B.12) implies that our assumption that ω * ∈ ∂Ω is not true, i.e., ω * is in the interior of Ω. In this case, C Ω (ω * ) is an empty set. Thus the asymptotically stable equilibria of the ODE in (B.7) are given by

(θ * , ω * ) : θ * ∈ Θ, h(θ * , ω * ) = 0 = [θ * , ω(θ * )] : θ * ∈ Θ . (B.13)

This implies that, in the faster timescale, we could fix the primal parameter at θ ∈ Θ, and the dual variable converges to ω(θ), which is the unique solution of the dual optimization problem max ω L(θ, ω). In other words, using two timescale updates, we essentially solve the dual problem for each θ.

Step 2. Slower timescale. Note that (B.13) cannot characterize the asymptotic behavior of the primal variable. Now we proceed to establish a finer characterization of the asymptotic behavior of {θ t , ω t } t≥1 by looking into the slower timescale. For ease of presentation, let E t = σ(θ τ , τ ≤ t) be the σ-field generated by {θ τ , τ ≤ t}. In addition, we define

ψ (1) t = -φ t ω t • A t + E[φ t ω t • A t | E t ] ψ (2) t = -E[φ t ω t • A t | E t ] + g[θ t , ω(θ t )], (B.14)

where function g is defined in (B.4), A t and φ t are defined in (B.1). It holds that {ψ

(1)

t } t≥1 is a martingale difference sequence. Note that by the definition of g, we have

E[φ t ω(θ t ) • A t | E t ] = g[θ t , ω(θ t )].

Using the notation in (B.14), the primal update in (B.2) can be written as

θ t+1 = Π Θ θ t -α t • g[θ t , ω(θ t )] + α t • ψ (1) t + α t • ψ (2) t . (B.15)

As shown in the first step of the proof, ω(θ t ) -θ t converges to zero as t goes to infinity. Moreover, under Assumption 4.1, both ∇ θ Q θ (s, a) and φ(s, a) are bounded. By Cauchy-Schwarz inequality,

ψ (2) t 2 = E{φ t [ω(θ t ) -ω t ] • A t | E t } 2 ≤ sup (s,a) φ(s, a) 2 • sup (s,a) ∇ θ Q θ (s, a) 2 • E[ ω(θ t ) -ω t 2 | E t ],

which converges to zero almost surely. Besides, the boundedness of ∇ θ Q θ (s, a) and φ(s, a) also implies that there exist a constant

C > 0 such that E[ ψ (1) t 2 2 | E t ] ≤ C for all t ≥ 1.

Furthermore, we define

W T = T t=1 α t • ψ (1) t ∈ R d for any T ≥ 1. Since t≥1 α 2 t < ∞, {W T } T ≥1

is a square-integrable martingale sequence, which converges almost surely by the Martingale convergence theorem (Neveu, 1975) . Moreover, Doob's martingale inequality (Doob, 1953) implies that lim

T →∞ P sup N ≥T W N -W T ≥ ≤ lim T →∞ sup N ≥T E[ W N -W T 2 2 ] 2 ≤ lim T →∞ 2C 2 t≥T α 2 t 2 = 0.

To apply the Kushner-Clark lemma, we additionally need to verify that function ḡ(θ) = g[θ, ω(θ)] is a continuous. To see this, note that ω(θ) defined in (4.1) is a continuous function, and g(θ, ω) in (B.4) is continuous in both θ and ω.

Finally, applying by the Kushner-Clark lemma (Kushner & Clark, 1978) to sequence {θ t } t≥1 , it holds that {θ t } t≥1 converges almost surely to the set of asymptotically stable equilibria of the ODE B.16) where C Θ (θ) is the outer normal cone of Θ. Since Θ is a Euclidean ball with radius R θ , if θ is on the boundary of Θ, i.e., θ 2 = R θ , we have C Θ (θ) = {λ • θ, λ ≥ 0}. Thus, for any asymptotically stable equilibrium θ * of (B.16), if θ * is in the interior of Θ, i.e., θ < R θ , we have ḡ(θ * ) = 0. Additionally, if θ * 2 = R max , we have ḡ(θ * ) ∈ C Θ (θ * ), which implies that there exists λ > 0 such that ḡ(θ * ) = λ • θ * . Therefore, we conclude the proof of Theorem 4.3.

EQUATION

B.2 PROOF OF THEOREM 4.5:

Proof. In the sequel, to simplify the notation, we use C to denote absolute constant, whose value might change from line to line. In addition, for any θ ∈ R d , we define B.17) where δ θ = Q θ -T * Q θ is the TD-error, and µ θ is the output of the optimization oracle for query θ.

EQUATION

Note that θ t in (4.5) is updated in the direction of an unbiased estimate of ∇J(θ t ). To simplify the notation, we let

ζ t = µ θt (s t , a t ) • ∇ θ Q θt (s t , a t ) -∇ θ Q θt (s t , a t ) -∇ θ J(θ t ), (B.18)

where ∇ θ J(θ t ) is defined in (B.17), a t = argmax a∈A Q θt (s t , a). Then the update rule in (4.5) can be written as θ t+1 = θ t -α t Moreover, note that the gradient of J(θ) can be written as

∇ θ J(θ) = E (s,a)∼ρ [δ θ (s, a)•∇ θ δ θ (s, a)].

By the definition of the TD-error, under Assumption 4.1, δ θ and ∇ θ δ θ are bounded by 2Q max and 2G max on S × A respectively. Moreover, since ∇ θ δ θ is Lipschitz in θ, there exists a constant L > 0 such that ∇ θ J(θ) is L-Lipschitz. Thus, we have

J(θ) ≤ J(θ t ) -∇ θ J(θ t ), θ t+1 -θ t + L/2 • θ t+1 -θ t 2 2 ≤ J(π θt ) -α t • ∇ θ J(θ t ), ∇J(θ t ) + ζ t + α 2 t • L/2 • ∇J(θ t ) + ζ t 2 2 . (B.19)

Taking conditional expectation on both sides of (B.19) given F t , since ζ t is centered with finite variance, we obtain that

E[J(θ t+1 ) | G t ] ≤ J(θ t ) -α t • ∇ θ J(θ t ), ∇J(θ t ) -α 2 t • L/2 • ∇ θ J(θ t ) 2 2 -C • α 2 t , (B.20)

where C > 0 is an absolute constant. Note that ∇J(θ) is a biased estimate of ∇ θ J(θ). Under Assumptions 4.1 and 4.4, the bias can be bounded via Cauchy-Schwarz inequality:

∇ θ J(θ) -∇J(θ) 2 = E (s,a)∼ρ ∇ θ δ θ (s, a) • [δ θ (s, a) -µ θ (s, a)] 2 ≤ E (s,a)∼ρ ∇ θ δ θ (s, a) 2 • δ θ -µ θ ρ ≤ 2G max • ε, (B.21)

where ε is the error of the optimization oracle in Assumption 4.4. We denote ∇J(θ t ) -∇ θ J(θ t ) by ψ t hereafter to simplify the notation. Moreover, by Cauchy-Schwarz inequality, we have

∇ θ J(θ t ), ∇J(θ t ) = ∇ θ J(θ t ), ∇ θ J(θ t ) -ψ t ≥ ∇ θ J(θ t ) 2 2 -∇ θ J(θ t ) 2 • ψ t 2 . (B.22)

Similarly, for ∇ θ J(θ t ) 2 2 , we obtain that 

∇J(θ t ) 2 2 ≤ ∇ θ J(θ t ) 2 2 + ψ t 2 2 + 2 • ∇ θ J(θ t ) 2 • ψ t 2 . (B.

E[J(θ t+1 ) | F t ] ≤ J(θ t ) + C • α 2 t -α t • (1 -α t • L/2) • ∇ θ J(θ t ) 2 2 + α t • (1 + α t • L) • ∇ θ J(θ t ) 2 • ψ t 2 ≤ J(θ t ) + C • α 2 t -α t • (1 -α t • L/2) • ∇ θ J(θ t ) 2 2 + α t • 2(1 + α t • L) • G max • ε • ∇ θ J(θ t ) 2 . (B.24)

Since t≥0 α 2 t < ∞, α t converges to zero as t goes to infinity. When t is sufficiently large such that 4α t • L < 1, (B.24) implies that

E[J(θ t+1 ) | F t ] ≤ J(θ t ) -α t /2 • ∇ θ J(θ t ) 2 2 + 4α t • G max • ε • ∇ θ J(θ t ) 2 + C • α 2 t = J(θ t ) -α t /2 • ∇ θ J(θ t ) 2 • ∇ θ J(θ t ) 2 -8G max • ε + C • α 2 t . (B.25)

Furthermore, since J(θ) is a nonnegative function and t≥1 α 2 t < ∞, by (B.25) we have

t≥0 α t • ∇ θ J(θ t ) 2 • ∇ θ J(θ t ) 2 -8G max • ε < ∞. (B.26)

In the sequel, we show by contradiction that every limit point θ * of {θ t } t≥1 satisfies that ∇ θ J(θ * ) 2 ≤ 8G max • ε. Let ν > 0 be an arbitrary number. We first show that {t : ∇ θ J(θ t ) 2 < 8G max • ε + ν} is an infinite set. Suppose this is false, then there exists an integer t 0 such that ∇

θ J(θ t ) 2 ≥ 8G max • ε + ν for all t ≥ t 0 . Since t≥0 α t = ∞, we have t≥t0 α t • ∇ θ J(θ t ) 2 • ∇ θ J(θ t ) 2 -8G max • ε ≥ t≥t0 α t • ν • (8G max • ε + ν) = ∞,

which contradicts (B.26). Thus, there are infinite θ t 's satisfying ∇ θ J(θ t ) 2 ≤ 8G max + ν. Since ν can be arbitrarily small, this implies which, combined with (B.27) , establishes the theorem.

lim inf t≥0 ∇ θ J(θ t ) 2 ≤ 8G max • ε. (B.27) Let ε b = 8G max • ε. It remains to show that lim sup t≥0 ∇ θ J(θ t ) 2 ≤ ε b ,

Suppose this argument does not hold, then for any ν > 0, there exists ε > 0 such that ∇ θ J(θ t ) 2 ≥ δ b + 2ν for infinitely many t. Moreover, for this particular ν, ∇ θ J(θ t ) 2 ≤ δ b + ν also holds for infinitely many t. We define index sets N 1 and N 2 by

N 1 = {θ t : ∇ θ J(θ t ) 2 ≥ δ b + 2ν}, N 2 = {θ t : ∇ θ J(θ t ) 2 ≤ δ b + ν},

which are two disjoint and closed sets by the continuity of ∇ θ J(θ) 2 . Moreover, we define

D(N 1 , N 2 ) = inf θ∈N1 inf θ ∈N2 θ -θ 2 , (B.28)

which is a positive number since N 1 and N 2 are disjoint. In addition, since both N 1 and N 2 are infinite sets, there exists an index set I ⊆ N such that the subsequence {θ t } t∈I of {θ t } t≥0 crosses N 1 and N 2 infinitely often. That is, there exists two sequences {s i } i≥1 and {t i } i≥1 ⊆ N such that {θ t } t∈I = i≥1 {θ si , θ si+1 , . . . , θ ti-1 }. Furthermore, we have {θ si } i≥1 ⊆ N 1 , {θ ti } i≥1 ⊆ N 2 , and

δ b + ε ≤ ∇ θ J(θ ) 2 ≤ δ b + 2ε for all ∈ ∪ i≥1 {s i + 1, . . . , t i -1}.

Hence, by triangle inequality, we have

t∈I θ t+1 -θ t 2 = ∞ i=1 ti-1 =si θ +1 -θ 2 ≥ ∞ i=1 θ ti -θ si 2 ≥ ∞ i=1 D(N 1 , N 2 ) = ∞, (B.29)

where D(N 1 , N 2 ) > 0 is defined in (B.28). Moreover, by (B.26), we have

∞ > t∈I α t • ∇ θ J(θ t ) 2 • ∇ θ J(θ t ) 2 -δ b ≥ t∈I α t • (δ b + ν) • ν,

which further implies that t∈I α t < ∞. However, by the update rule in (4.5), under Assumption 4.1, it holds that θ t+1 -θ t 2 ≤ α t • 2Q max • G max , where we use the boundedness of µ θ (s, a) and

∇ θ Q θ (s, a). Thus, it holds that t∈I θ t+1 -θ t 2 ≤ 2Q max • G max t∈I α t < ∞,

which contradicts (B.29). This contradiction implies that lim sup t≥0 ∇ θ J(θ t ) 2 ≤ ε b . Therefore, we conclude the proof of Theorem 4.5.

C STATISTICAL ERROR:

In this section, using tools from nonparametric regression, we establish the statistical error of our saddle point formulation in (3.5). To this end, we assume that the state space S is a closed compact subset of the Euclidean space R m and let H be the Sobolev space W k (R m ) restricted on S. In addition, we define

H A = Q ∈ B(S × A) : Q(•, a) ∈ H, ∀a ∈ A , Q H = a∈A Q(•, a) 2 W k 1/2

for any Q ∈ H A , where • W k is the Sobolev norm.

We consider the Bellman residual minimization problem with function class H A based on n i.i.d. observations {(s i , a i , s i )}, where (s i , a i ) ∼ ρ and s i is the next state. Replacing the loss function in (3.5) by its sample-based counterpart, we define

L n (Q, µ) = n i=1 -1/2 • [µ(s i , a i )] 2 + Q(s i , a i ) -r(s i , a i ) -γ • max a i ∈A Q(s i , a i ) • µ(s i , a i ) (C.1) = 1 2 • n i=1 Q(s i , a i ) -r(s i , a i ) -γ • max a i ∈A Q(s i , a i ) 2 -Q(s i , a i ) -µ(s i , a i ) -r(s i , a i ) -γ • max a i ∈A Q(s i , a i ) 2 .

Hence, if we denote Q -µ in (C.1) by h ∈ H A , L n (Q, µ) becomes

L n (Q, h) = 1 2 • n i=1 Q(s i , a i ) -r(s i , a i ) -γ • max a i ∈A Q(s i , a i ) 2 -h(s i , a i ) -r(s i , a i ) -γ • max a i ∈A Q(s i , a i ) 2 . (C.2)

Therefore, the sample-based sample-based functional optimization problem

min Q∈H A max h∈H A L n (Q, h) -λ µ • h H + λ Q • Q H (C.3)

reduces to the batch Bellman Residual Minimization algorithm studied in Antos et al. (2008b); Farahmand et al. (2009; 2016) . Here λ µ and λ Q in (C.3) are two positive regularization parameters, and we adopt regularization to avoid overfitting. Moreover, since µ = Q -h, the optimization problem in (C.3) is equivalent to

min Q∈H A max µ∈H A L n (Q, h) -λ µ • Q -µ H + λ Q • Q H . (C.4)

Let ( Q, µ) be the solution of (C.4). Using the theoretical result in Farahmand et al. (2009; 2016) , we obtain the statistical rate of Q, which is stated in the following theorem. Theorem C.1. Besides Assumption 3.1, we further make the following assumptions.

(a). The Sobolev space W k (R m ) satisfies that 2k > m.

(b). We assume that any Q ∈ H A satisfies that |Q(s, a)| ≤ Q max with Q max ≥ R max /(1 -γ).

Moreover, H A contains the optimal value function Q * .

(c). For any Q ∈ H A , there exists positive constants K 1 and K 2 such that

T * Q H ≤ K 1 + K 2 • Q H .

Moreover, let α = m/(2k). We set the regularization parameters in (C.4) to be 1+α) .

λ µ = λ Q = n • Q * 2 H -1/(

Let ( Q, µ) be the solution of (C.4). Then for any η ∈ (0, 1), we have

Q -Q * 2 ρ ≤ n -1/(1+α) (1 -γ) 2 • C 1 (Q * , K 1 , K 2 ) • log(1/η) + C 2 (Q * , K 1 , K 2 )

with probability at least 1 -η, where we define

C 1 (Q * , K 1 , K 2 ) = C • (K 1 + K 2 2 ) • Q * 2α/(1+α) H and C 2 (Q * , K 1 , K 2 ) = C • K 2 1 • (1 + Q * -2/(1+α) H

) for some absolute constant C > 0.

Proof. The proof follows from the results in Farahmand et al. (2009; 2016) . Note that the functional optimization problems in (C.4) and (C.3) are equivalent. Applying Theorem 11 in Farahmand et al. (2016) to the problem in (C.3), we obtain that

Q -T * Q 2 ρ ≤ n -1/(1+α) • C 1 (Q * , K 1 , K 2 ) • log(1/η) + C 2 (Q * , K 1 , K 2 ) (C.5)

with probability at least 1 -η. In addition, since Q * is the unique fixed point of T * , by triangle inequality, we have

Q -Q * ρ ≤ Q -T * Q ρ + T * Q -T * Q * ρ ≤ Q -T * Q ρ + γ • Q -Q * ρ ,

where the last inequality holds since T * is γ-contractive. Thus it holds that

Q -Q * ρ ≤ (1 - γ) -1 • Q -T * Q ρ .

Therefore, by (C.5), we obtain that

Q -Q * 2 ρ ≤ (1 -γ) -2 • Q -T * Q 2 ρ ≤ n -1/(1+α) • (1 -γ) -2 • C 1 (Q * , K 1 , K 2 ) • log(1/η) + C 2 (Q * , K 1 , K 2 ) ,

which concludes the proof of Theorem C.1.

D KUSHNER-CLARK LEMMA:

We state here the well-known Kushner-Clark Lemma (Kushner & Clark, 1978; Metivier & Priouret, 1984; Prasad et al., 2014) in the sequel.

Let Γ be an operator that projects a vector onto a compact set X ⊆ R N . Define a vector Γ(•) as

Γ[h(x)] = lim 0<η→0 Γ[x + ηh(x)] -x η ,

for any x ∈ X and with h : X → R N continuous. Consider the following recursion in N dimensions Assumption D.1. We make the following assumptions:

• h(•) is a continuous R N -valued function.

• The sequence {β t }, t ≥ 0 is a bounded random sequence with β t → 0 almost surely as t → ∞.

• The stepsizes γ t , t ≥ 0 satisfy γ t → 0 as t → ∞ and t γ t = ∞.

• The sequence ξ t , t ≥ 0 satisfies for any > 0 Then the Kushner-Clark Lemma says the following.

Theorem D.2. Under Assumption D.1, suppose that the ODE (D.2) has a compact set K * as its set of asymptotically stable equilibria. Then x t in (D.1) converges almost surely to K * as t → ∞.

:



Figures and Tables:

a), which is known as the temporal-difference (TD) error in the literature. Moreover, we parametrize µ in (3.4) using function class G = {µ ω : S × A → R, ω ∈ R p }. Then combining (3.1) and (3.4), we formulate Bellman residual minimization as a stochastic saddle point problem

a) , (3.10) where (s, a) ∼ d π , s ∼ P (• | s, a), and a ∼ π(• | s ). Here d π is the stationary distribution on S × A induced by policy π. Similarly, by computing the gradient of the objective in (3.10), we obtain a stochastic gradient algorithm for policy evaluation.

CartPole-v0 with various α t /β t

Figure1: In (a)-(c) we compare our method and DQN on three classical control tasks. Each plot shows the average reward during training across 5 random runs, with 50% confidence interval. As shown in these plots, our method achieves the equivalent performance to the classical DQN. In addition, in (d) we show the performances of our method for CartPole-v0 under different learning rates. For Case I, we set α t = 10 -2 , β t = 1e -4 with α t /β t = 100. For Case II, we set α t = 10 -4 , β t = 10 -4 with α t /β t = 1. For Case III, we set α t = 10 -4 , β t = 10 -2 with α t /β t = 0.01. The figure shows that α t /β t → 0 is critical for our method to work, which agrees with the theory.

t+1 = Γ x t + γ t [h(x t ) + ξ t + β t ] . (D.1)The ODE associated with (D.1) is given byẋ = Γ[h(x)].(D.2)

Algorithm 3 A Primal-Dual Algorithm for Soft Q-Learning Input: Initial parameter estimates θ 0 ∈ R d and ω 0 ∈ R p , primal and dual stepsizes {α t , β t } t≥0 . for t = 0, 1, 2, . . . until convergence do Sample (s t , a t ) ∼ ρ, observe reward r(s t , a t ) and the next state s t . Sample action a t = b with proabrbility ν θt (s t , b) for any b ∈ A. Compute the TD error δ

Table content: <table/>

• [ ∇J(θ t ) + ζ t ]. By Assumptions 4.1 and 4.2, {ζ t } t≥0 is a sequence of bounded and centered random vectors. Moreover, since both µ θ and ∇ θ Q θ are bounded by Q max and G max on S × A, respectively, ζ t defined in (B.18) is a bounded random variable satisfying ζ t 2 ≤ 4Q max •G max . Let F t be the σ-field generated by {θ j , j ≤ t}. Then we have E(ξ t | F t ) = 0 and E( ξ t 2 | F t ) ≤ C for some constant C > 0.

Table content: <table/>

Peer review (iclr2019):
 The paper studies the behavior of two-timescale stochastic approximation methods in the two fundamental approximate dynamic programming problems of policy evaluation and optimal control. Specifically, the authors pose the problem of Bellman residual minimization as a saddle-point problem and apply stochastic gradient updates for the primal and dual variables, and show that this procedure converges to a certain fixed point under rather general conditions. Notably, the results are claimed to hold even when the objective function is not convex-concave. The authors also highlight that the eventual solution may not necessarily be sensible in general, and also analyze a variant in which the dual variables can be optimized with bounded error in each iteration. In this setup, the main result is showing that the proposed algorithm converges to a neighborhood of the optimal solution of the original problem, and the size of the neighborhood is controlled by the optimization error in the dual objective. I enjoyed reading the paper for the most part: the proposed approach is simple and natural (closely resembling GTD algorithms), and the core technical results seem plausible (although I didn*t have the capacity to check the details this time). I appreciated the openness of the authors to discuss the limitations of their result in Theorem 4.3. The writing is generally good, up to some minor typos. That said, I do have some relatively serious concerns about the nature of some of the results. Specifically, the objective function considered for optimal control seems fundamentally flawed and can be shown to lead to meaningless results even when optimized to zero error. To see this, observe that the objective (3.1) involves an expectation taken under the behavior policy .pi_b which may be arbitrarily far away from the optimal policy. This can lead to easily-seen problems in extreme cases, e.g., when pi_b only visits a recurrent class of states that are not visited at all by the optimal policy, and all rewards are zero in this recurrent class and its neighboring states. Under these conditions, the constant zero function trivially minimizes the Bellman error, even though being a potentially terrible solution. This is a well-known issue with this objective, and it can be solved by making some stronger assumptions on the behavior policy and using importance weighting (as done by, e.g., Antos et al. 2008). Incorporating these elements in the present analysis seems nontrivial, although certainly not impossible. Another concern is that the optimization oracle required for Theorem 4.5 is unrealistically strong, and not just due to computational issues. The problem is that the optimization target for the oracle considered in this theorem is not an observable quantity, but rather an expectation over random variables with unknown distribution (that can only be estimated with an infinite sample size). Making such an assumption effectively eliminates the main technical challenges related to the double sampling issue, so it feels a bit like cheating. In fact, one can use such an assumption to completely circumvent the need for a saddle-point formulation and prove convergence results for Q-learning-style methods directly in a single-timescale SA framework. Right now, this aspect remains hidden due to the writing---the authors should discuss this assumption more honestly in the paper. In order to resolve the above issues, I suggest that the authors limit their presentation to policy evaluation problems where at least some of these technical problems are not present. I believe that a paper focusing only on policy evaluation should have sufficient merit for publication---but then again, rewriting the paper accordingly should be a bit too much to ask for in a conference revision. In either case, I am looking forward to hearing the opinion of the authors on the issues raised above. Detailed comments ================= - pp.1, intro: "the statistical and computational properties of the RL algorithms are well-understood under these settings"---well, let*s just say that *some* of these properties are well understood. E.g., I don*t think that many people would consider "concentrability coefficients" to be really well-understood :) - pp.2, top: "Bellman residue" -> "Bellman residual" (many times in the paper) - pp.2, related work: "our study" -> "we study" - pp.2, bottom: "could stringent" -> "could be stringent" - pp.3, below (2.2): "applying the Bellman optimality operator repeatedly gives the classical Q-learning algorithm"---this is actually value iteration, Q-learning also uses other ideas related to stochastic approximation. Please clarify a bit. - pp.3, above Sec 3: "saddle framework" -> "saddle-point framework" - pp.4, 2nd paragraph: "when the capacity of S is large"---what does this mean? - pp.4, Eq.(3.3): extra .cdot - pp.5, below (3.7): "since the saddle point problem is nonconvex, we project the iterates"---can you explain what this projection has to do with nonconvexity? - pp.5, below (3.7): "such a condition on the learning rates ensures that the dual iterates asymptotically track the sequence [...]"---this is technically only true if the faster-timescale can be first shown to converge at all, which is not trivial! - pp.6, Assumption 4.1: missing comma between Q_max and .|.nabla_.theta....|. It would also be worth noting that this assumption technically excludes neural nets with RELU activations, so I*m not sure if your theory actually applies to the setup in the experiments. - pp.6, below (4.1): "most online TD-learning algorithms uses [sic] linear function approximation"---this is a quite weak argument given that the main contribution of the paper is precisely going beyond these settings; this claim suggests that linear FA methods are OK after all.