CONTINUOUS DEEP Q-LEARNING IN OPTIMAL CONTROL PROBLEMS: NORMALIZED ADVANTAGE FUNCTIONS ANALYSIS
Year: 2021

Abstract:
One of the most effective continuous deep reinforcement learning algorithms is normalized advantage functions (NAF). The main idea of NAF consists in the approximation of the Q-function by functions quadratic with respect to the action variable. This idea allows to apply the algorithm to continuous reinforcement learning problems, but on the other hand, it brings up the question of classes of problems in which this approximation is acceptable. The presented paper describes one such class. We consider reinforcement learning problems obtained by the discretization of certain optimal control problems. Based on the idea of NAF, we present a new family of quadratic functions and prove its suitable approximation properties. Taking these properties into account, we provide several ways to improve NAF. The experimental results confirm the efficiency of our improvements.

heading: 1 INTRODUCTION
text: The standard reinforcement learning (RL) setup consists of an agent interacting with an environment (Sutton & Barto, 2018). At each step of the interaction, the agent determines an action based on its policy and its current state, gets a reward, and makes a transition to the next state. An aim of the agent is to learn the policy that maximizes the sum of rewards.
Q-learning (Watkins & Dayan, 1992) is one of the most widespread algorithms for solving RL problems. According to this algorithm, the optimal action-value function (Q-function) is being found as a solution of the Bellman optimality equation. After the learning, the agent can act optimally by the learned Q-function. Initially, the Q-learning algorithm was applied for solving RL problems with finite state and action spaces. In this case, the Q-function can be represented by a finite table. For the case of a large or continuous state space, Q-learning has recently been extended to Deep Q-learning algorithm (Mnih et al., 2015) that allows to look for the approximate Q-function in the class of neural networks by means of the stochastic gradient descent. Deep Q-learning and its modifications have shown the efficiency for a range of challenging tasks (Wang et al., 2016; van Hasselt et al., 2016; Schaul et al., 2016; Hessel et al., 2018), however, note that this algorithm can not be directly applied for solving RL problems with continuous action spaces. The reason is that Deep Q-learning involves a maximizing of an approximate Q-function by the action variable on each step of the learning, which is a complex problem for continuous action spaces. Among various approaches to overcome this problem (Lillicrap et al., 2016; Haarnoja et al., 2017; Kalashnikov et al., 2018; Lim et al., 2019; Ryu et al., 2020; Lutter et al., 2021), we focus on an idea of the normalized advantage functions (NAF) algorithm (Gu et al., 2016). This idea consists in the approximation of the Q-function by functions quadratic with respect to the action variable. It allows to get the maximum quite fast and precisely and solve some challenging control problems (Gu et al., 2017; Dong et al., 2018; Ikemoto & Ushio, 2021), but on the other hand, it brings up the question of classes of RL problems in which this approximation is acceptable. The presented paper describes one of the possible answers to this question.
Note that the class of LQR problems (Bradtke et al., 1994) has the Q-functions quadratic with respect to the action variable. However, this class, being quite special, is not suitable for the description of complex controlled processes. In the paper, we consider a wider (in some sense) class of RL prob-
lems. We consider RL problems which are obtained by the discretization of certain optimal control problems (Bardi & Dolcetta, 1997). The rationale for the consideration of such RL problems is that a lot of RL problems with continuous action spaces arise from control problems for mechanical or robotic systems (Lillicrap et al., 2016; Gu et al., 2016; Haarnoja et al., 2017; Gu et al., 2017; Kalashnikov et al., 2018), whose dynamic are, in fact, described by ordinary differential equations.
For the considered class of problems, based on the idea of NAF, we present a new family of quadratic functions and prove that, first, this family is sufficiently rich to approximately solve the Bellman optimality equation (Theorem 1), and second, any sufficiently accurate solution of the Bellman optimality equation allows to approximately obtain the optimal policy in the corresponding optimal control problem (Theorem 2). Moreover, we prove that it is impossible to get the same results for the original family of functions from Gu et al. (2016) (Theorem 3). From the obtained theoretical statements, we get some additional knowledge about the Q-function approximation by our family of quadratic functions and also provide several ways to use this knowledge in order to improve NAF. The experimental results confirm the efficiency of our improvements.

heading: 2 BACKGROUND
text: The standard reinforcement learning (RL) setup consists of an agent interacting with an environment (Sutton & Barto, 2018). This interaction is described by a Markov Decision Process (MDP), which is a tuple (S,U ,P,R, ρ0, γ), where S is a state space, U is an action space, P(s′|s, u) is a transition distribution, R(s, u) is a reward function, ρ0(s) is an initial state distribution, and γ ∈ [0, 1] is a discount factor. An aim of the agent is to learn its optimal policy µ∗(s) that maximizes the value
J(µ) = E [ ∞∑
i=0
γiR(si, ui) | s0 ∼ ρ0(s0), ui = µ(si), si+1 ∼ P(si+1|si, ui), i = 0, 1, 2, . . . ] .
In the general statement of reinforcement learning problems, a policy of the agent can be stochastic, however, within this paper, we assume that the policy is deterministic.
One of the most effective algorithms for solving RL problems is Q-learning (Watkins & Dayan, 1992). According to this algorithm, the agent explores the environment and looks for the optimal action-value function (Q-function)
Q∗(s, u) = sup µ E [ ∞∑ i=0 γiR(si, ui) | s0 = s, u0 = u,
si+1 ∼ P(si+1|si, ui), ui+1 = µ(si+1), i = 0, 1, 2, . . . ] .
as a solution of the Bellman optimality equation Q∗(s, u) = E [ R(s, u) + γmax
u′∈U Q∗(s
′, u′) | s′ ∼ P (s′|s, u) ] .
In other words, the agent solves the following minimization problem:
sup s∈S,u∈U ∣∣∣Q(s, u)− E[R(s, u) + γmax u′∈U Q(s′, u′) | s′ ∼ P(s′|s, u) ]∣∣∣→ inf Q . (1)
If the agent knows the function Q∗(s, a), it can act optimally by the greedy policy µ∗(s) ∈ argmaxu∈U Q∗(s, u).
Initially, the Q-learning algorithm was applied for solving RL problems with finite state and action spaces. In this case, the Q-function is represented by a finite table and problem (1) is finitedimensional. For the case of a large or continuous state space, Q-learning has recently been extended to Deep Q-learning algorithm (Mnih et al., 2015) that allows to look for the approximate Q-function in the class of neural networks Q(x, u|θQ), where θQ is the parameter vector of the neural network. During the learning, the experiences (si, ui, ri, si+1) are stored in the buffer D and simultaneously the parameter vector θQ is updated by means of the stochastic gradient descent minimizing the loss function
L(θQ) = E [ (Q(s, u|θQ)− y)2 | (s, u, r, s′) ∼ U(D) ] , y = r + γmax
u′∈U Q(s′, u′|θQ). (2)
where U(D) is the uniform distribution on D. Deep Q-learning and its modifications are effective for a range of challenging tasks (Wang et al., 2016; van Hasselt et al., 2016; Schaul et al., 2016; Hessel et al., 2018), however, note that this algorithm can not be directly applied for solving RL problems with continuous action spaces. The reason is that Deep Q-learning involves the maximizing in (2) on each step of the learning, which is a complex problem for continuous U . Among various approaches to overcome this problem (Lillicrap et al., 2016; Haarnoja et al., 2017; Kalashnikov et al., 2018; Lim et al., 2019; Ryu et al., 2020; Lutter et al., 2021), we focus on an idea of the normalized advantage functions (NAF) algorithm (Gu et al., 2016). This idea consists in the approximation of the Q-function by the following quadratic with respect to u functions:
Q(s, u|θQ) = V (s|θV ) +A(s, u|θA),
A(s, u|θA) = −1 2 (u− µ(s|θµ))TP (s|θP )(u− µ(s|θµ)),
(3)
where V (s|θV ), µ(s|θµ), and P (s|θP ) are neural networks with parameters θV , θµ, and θP , respectively; P (s|θP ) is a positive-definite square matrix for each s and θP ; θA = {θµ, θP } and θQ = {θA, θV }. Under the condition µ(s|θµ) ∈ U, (4) it allows to get the maximum and argmaximum values directly by values of V (s|θV ) and µ(s|θµ):
max u∈U Q(s, u|θQ) = V (s|θV ), Argmax u∈U Q(s, u|θQ) = µ(s|θµ), (5)
but on the other hand, it brings up the question of classes of RL problems in which quadratic approximations is acceptable. Below, we describes one such class.

heading: 3 PROBLEM STATEMENT
text: In this section, we consider a certain class of optimal control problems and show that discrete approximations of these problems can be formalized as RL problems.
Consider the following optimal control problem: it is required to maximize the functional J(u(·)) = σ(x(T ))− ∫ T 0 ( q(t, x(t)) + u(t)T r(t, x(t))u(t) ) dt, (6)
over all u(·), where x(·) is the solution (Filippov, 1988, §1) of the differential equation
d dt x(t) = f(t, x(t)) + g(t, x(t))u(t), t ∈ [0, T ], (7)
under the initial condition x(0) = z. (8)
Here t is the time variable, T > 0 is the terminal instant of time, x(t) ∈ Rn is the current state vector, u(t) ∈ U is the current control action vector forming the measurable function u(·), U ⊂ Rm is the nonempty compact set, z ∈ Rn is the fixed initial state vector, f(t, x) ∈ Rn, g(t, x) ∈ Rn×m, q(t, x) ∈ R, r(t, x) ∈ Rm×m, (t, x) ∈ [0, T ] × Rn are continuous with respect to t and continuously differentiable with respect to x functions, r(t, x) is the positive-definite matrix for each (t, x) ∈ [0, T ]×Rn, and σ(x) ∈ R, x ∈ Rn is the continuous function. We assume that there exists a constant cfg > 0 such that
∥f(t, x) + g(t, x)u∥ ≤ (1 + ∥x∥)cfg, (t, x) ∈ [0, T ]× Rn, u ∈ U. (9)
Note that, under these conditions, for each function u(·), there exists a unique solution x(·) of equation (7) under the initial condition (8) (Filippov, 1988, §1).
Define the value function in optimal control problem (6), (7) by
V∗(t∗, x∗) = sup u(·)
( σ(x(T ))− ∫ T t∗ ( q(t, x(t))+u(t)T r(t, x(t))u(t) ) dt ) , (t∗, x∗) ∈ [0, T ]×Rn,
(10)
where, for each u(·), x(·) is the solution of equation (7) on the interval [t∗, T ] under the initial condition x(t∗) = x∗.
Define the sets S = { (t, x) ∈ [0, T ]× Rn : ∥x∥ ≤ (1 + ∥z∥)ecfgt − 1 } , S(t) = { x ∈ Rn : (t, x) ∈ S } . (11)
Let k ∈ N, ∆tk = T/k, and ti = i∆tk, i ∈ 0, k. Consider the corresponding discrete optimal control problem: it is required to maximize the function
Jk(u0, u1, . . . uk−1) = σ(xk)−∆tk k−1∑ i=0 ( q(ti, xi) + u T i r(ti, xi)ui ) , (12)
over all ui ∈ U , i ∈ 0, k − 1, where (x0, x1, . . . , xk) is defined by
x0 = z, xi+1 = xi + (f(ti, xi) + g(ti, xi)ui)∆tk, i ∈ 0, k − 1. (13)
Let us show that problem (12), (13) can be formalized as the RL problem. First, we define the state and actions spaces, the initial state distribution, and the discount factor as follows:
S = ∪ki=0 ( {ti} × S(ti) ) ∪ sT , U = U, ρ0(s0) = δ(s0 = (0, z)), γ = 1. (14)
Here sT is some fictional terminal state, δ is Dirac delta distribution. Next, for every i ∈ 0, k − 1, x ∈ S(ti), and u ∈ U , we define the transition distribution and the reward function by
P(s′|s = (ti, x), u) = δ(s′ = (ti+1, x′)), R(s = (ti, x), u) = − ( q(ti, x) + u T r(ti, x)u ) ∆tk,
(15) where x′ = x + (f(ti, x) + g(ti, x)u)∆tk. Taking into account (9) and (11), one can prove the inclusion (ti+1, x′) ∈ S. Hence, the transition distribution P is well-defined. For i = k, we set
P(s′|s = (tk, x), u) = δ(s′ = sT ), R(s = (tk, x), u) = σ(x), x ∈ S(tk), u ∈ U. (16)
In order to make dynamical processes (13) formally infinite, we put
P(s′|sT , u) = δ(s′ = sT ), R(sT , u) = 0, u ∈ U. (17)
Thus, we define MDP which describes the RL problem corresponding to problem (12), (13). Next, we show that such RL problems is suitable for using quadratic approximations of the Q-function.

heading: 4 QUADRATIC APPROXIMATIONS OF THE Q-FUNCTION
text: Denote by Q the family of functions Q such that
Q(t, x, u) = V (t, x) +A(t, x, u), (t, x, u) ∈ [0, T )× Rn × U, (18)
where A(t, x, u) = −(u− µ̃(t, x))TP (t, x)(u− µ̃(t, x))
+(µ(t, x)− µ̃(t, x))TP (t, x)(µ(t, x)− µ̃(t, x))
µ(t, x) ∈ argmin u′∈U
(u′ − µ̃(t, x))TP (t, x)(u′ − µ̃(t, x)).
(19)
Here V (t, x), µ̃(t, x), and P (t, x) are continuous functions; P (t, x) is a positive-definite square matrix for each (t, x) ∈ [0, T )× Rn. Note that, functions Q from the family Q satisfy the equalities
max u∈U Q(t, x, u) = V (t, x), Argmax u∈U Q(t, x, u) = µ(t, x), (20)
as well as (see (5)) quadratic functions from family (3). However, these function families are different. The difference is that we do not assume the inclusion µ̃(t, x) ∈ U as opposed to assumption (4). The theorems below establish a connection between the optimal control problem (6)–(8) and minimization problems (1) for MDP (14)–(17).
Theorem 1. Let the value function V∗(t, x) be continuously differentiable. Then, for every ε > 0, there exists k∗ > 0 such that, for every k ≥ k∗, the function Q ∈ Q defined by (18) and (19) where
V (t, x) = V∗(t, x), P (t, x) = r(t, x)∆tk, µ̃(t, x) = 1
2 r−1(t, x)gT (t, x)∇xV∗(t, x) (21)
satisfies the inequality∣∣Q(ti, x, u) + (q(ti, x) + uT r(ti, x)u)∆tk −max u′∈U Q(ti+1, x ′, u′) ∣∣ ≤ ε∆tk, x′ = x+ ( f(ti, x) + g(ti, x)u ) ∆tk, u ∈ U, x ∈ S(ti), i ∈ 0, k − 1,
(22)
where we assume Q(tk, x′, u′) = σ(x′).
Theorem 2. Let the value function V∗(t, x) be continuously differentiable. Let ε > 0 and k∗ > 0 be defined according to Theorem 1. Take k ≥ k∗ and suppose that a function Q ∈ Q satisfies inequality (22). Then the following estimate holds:
Jk(u0, u1, . . . uk−1) ≥ sup u(·) J(u(·))− 3Tε, (23)
where the function Jk(u0, u1, . . . uk−1) is defined by (12) with ui = µ(ti, xi), i ∈ 0, k − 1 and the function µ(t, x) is defined by Q according to (18) and (19).
Thus, Theorem 1 shows that the function family Q is sufficiently rich to contain approximate solutions of problem (1) with a predetermined accuracy and Theorem 2 establishes that all such approximate solutions contained in Q allow to get the policy, which approximately provides the optimal result in optimal control problem (6)–(8).
Note that the similar results can be obtained for the wider class of optimal control problems (see Appendix B). However, in this case, we need to consider another form of the function A(t, x, u). Within the presented paper, we focus on class (6)–(8), because, firstly. this class seems quite general and important for applications and, secondly, the function A(t, x, u), corresponding to this class, has the quite simple (quadratic) form.
Now, let us consider the original family of functions from Gu et al. (2016). Denote by QNAF the family of functions Q such that
Q(t, x, u) = V (t, x)− (u− µ(t, x))TP (t, x)(u− µ(t, x)), (t, x, u) ∈ [0, T )× Rn × U, (24)
where V (t, x), µ(t, x), and P (t, x) are continuous functions; P (t, x) is a positive-definite square matrix for each (t, x) ∈ [0, T )×Rn; µ(t, x) ∈ U for each (t, x) ∈ [0, T )×Rn. The theorem below establishes that if we take the family QNAF instant of Q, then Theorem 1 can not be proved even in the simplest cases of optimal control problem (6)–(8).
Theorem 3. Let n = m = 1, T = 1, U = [−1, 1], f(t, x) = q(t, x) = 0, g(t, x) = r(t, x) = 1, σ(x) = −x2, and z = 2. Then, for every k ≥ 4 and Q ∈ QNAF , there exist i ∈ 0, k − 1, x ∈ S(ti), and u ∈ U such that∣∣Q(ti, x, u) + u2∆tk −max
u′∈U Q(ti+1, x
′, u′) ∣∣ > ∆tk/8, x′ = x+ u∆tk,
where we assume Q(tk, x′, u′) = −(x′)2. Proofs of the theorems are given in the Appendix A.

heading: 5 EXPERIMENTS
text: We consider four examples of optimal control problems (6)–(8) described in Table 1, where
σ1(x) = −x21 − x22, σ2(x) = −|x1| − 0.1|x2|, σ3(x) = −|x1 − 4| − |x2| − |x3 − 0.75π|
σ3(x) = −x21 − x22 − (x3 − 2)2 − (x4 − 2)2
Van der Pol oscillator is a famous model of a non-conservative oscillator with non-linear damping. The aim of the control is to stabilize the oscillator at the terminal time.
Pendulum is a traditional problem for testing control algorithms. The aim of the control is the stabilization of the pendulum in the top position at the terminal time.
Dubins car is a quite famous model which describes a motion of the point particle moving at a constant speed on the plane. The problem is to find a control providing the closeness of the motion with a target point at the terminal time.
A target problem is an optimal control problem presented in Munos (2006). The dynamic system describes a hand holding a spring to which is attached a mass. It is required to control the hand such that the mass achieve the target point at the terminal time.

heading: 5.1 BOUNDED NAF
text: First, we modify NAF algorithm, proposed in Gu et al. (2016), based on the function family Q. Note that, the considered examples have U = [α, β]m. Denote tanhα,β(ν) = α+(1+tanh(ν))(β−α)/2, ν ∈ Rm, α, β ∈ Rm, where tanh is the hyperbolic tangent for each coordinate. Then, according to (18) and (19), we can use the following approximation of the Q-function, within NAF algorithm:
Q(t, x, u|θQ) = V (t, x|θV ) +A(t, x, u|θA),
A(t, x, u|θA) = − ( u− µ̃(t, x|θµ̃) )2 P (t, x|θP )
+ ( tanhα,β(µ̃(t, x|θµ̃))− µ̃(t, x|θµ̃) )2 P (t, x|θP ),
where V (t, x|θV ), µ̃(t, x|θµ̃), and P (t, x|θP ) are neural networks with parameters θV , θµ̃, and θP , respectively; P (t, x|θP ) is a positive-definite square matrix for each (t, x) and θP ; θA = {θµ̃, θP } and θQ = {θA, θV }. To be short, we call this algorithm Bounded NAF (BNAF), because it is essential for our modification of NAF that the set U is bounded.
Note that, we can also use the function clipα,β(ν) = max{α,min{β, ν}}, ν ∈ Rm, α, β ∈ Rm instead of the function tanhα,β . According to (19), it is more correct, however our experiments show that the learning results are slightly better with tanhα,β (see Appendix C). A possible reason for this is that the function clipα,β is not smooth.

heading: 5.2 REWARD-BASED BNAF
text: If we know the function r(t, x), then, according to Theorem 1, we can use the function r(t, x)∆tk instead of the neural network P (t, x|θP ) to reduce the number of learning parameters. This variant of BNAF is called Reward-based BNAF (RB-BNAF).

heading: 5.3 GRADIENT-BASED BNAF
text: If we also know the function g(t, x), then, according to the Theorem 1, we can use the function
µ̃(t, x|θV ) = 1 2 r−1(t, x)gT (t, x)∇xV (t, x|θV )
instead of the neural network µ̃(t, x|θµ̃). It also reduces the number of learning parameters. This variant of BNAF is called Gradient-based BNAF (GB-BNAF).

heading: 5.4 EXPERIMENTAL RESULTS
text: We use the same learning parameters of every our tasks. We apply neural networks with two layers of 256 and 128 rectified linear units (ReLU) and learn their used ADAM with the learning rate lr = 5e−4. We use batch size nbs = 256 and smoothing parameter τ = 1e−3. Also we take ∆t = 0.1. All calculations were performed on a personal computer in a standard way.
We compere NAF, BNAF, RB-BNAF, GB-BNAF algorithms, and DDPG algorithm presented in (Lillicrap et al., 2016). Figure 1 shows learning curves of the algorithms for the considered examples. One can note that GB-BNAF algorithm is the most stable and gets the best performance in all examples. RB-BNAF is also capable to get acceptable results in all examples, although it does not have the same stable learning as GB-BNAF. RB-BNAF algorithm gets worse result than GBBNAF and RB-BNAF in Dubins car (c). NAF demonstrate good results in Van der Pol oscillator (a) and Pendulum (b), however it does not cope with Dubins car (c) and A target problem (d). DDPG algorithm shows poor performance only in A target problem (d).
Thus, taking the presented experiments into account, we can give the following general recommendations. For solving optimal control problems (6)–(8), it is rational to use BNAF, GB-BNAF, and
especially RB-BNAF algorithms along with NAF algorithm. There is a high probability that they will show better results and more stable learning.

heading: 6 RELATED WORKS
text: Many different ways to apply reinforcement learning approaches for solving optimal control problems are investigated (Baird, 1994; Doya, 1995; 2000; Munos, 2006; Tallec et al., 2019; Jeongho Kim, 2020; Lutter et al., 2021). Among them, a time-discretization is perhaps the most obvious and widely used tool (Lillicrap et al., 2016; Gu et al., 2016; Haarnoja et al., 2017; Gu et al., 2017; Kalashnikov et al., 2018). From the theoretical point of view, it is known (Bardi & Dolcetta, 1997, p.388) that solutions of time-discrete optimal control problems converge to a solution of the initial problem as the discretization step tends to zero. In the present paper, we also use the time-discretization and study approximating solutions of Bellman equations and the corresponding greedy politics depending on the discretization step (see Theorem 1 and 2). Other studies of dependencies on the discretization step of reinforcement learning methods can be found in Munos (2006); Tallec et al. (2019).
We focus on the idea from Gu et al. (2016) to expand the Q-learning algorithm to optimal control and reinforcement learning problems with continuous actions. Other approaches for solving such problems are investigated in Lillicrap et al. (2016); Haarnoja et al. (2017); Kalashnikov et al. (2018); Lim et al. (2019); Ryu et al. (2020); Lutter et al. (2021). The paper Lutter et al. (2021) seems the closest to the presented paper. In this paper, the similar optimal control problem and feedback control policy are considered, however, another Bellman equation is used.
Let us also note that the family of functions (18), (19) is included, in some sense, to families of Q-functions considered in Wang et al. (2016); Tallec et al. (2019). It seems expected because more general classes of problems are considered in these papers. Nevertheless, proposed algorithms and results of these papers are very different from presented in this paper.

heading: A APPENDIX
text: Denote H(t, x, s, u) = ⟨f(t, x) + g(t, x)u, s⟩ − q(t, x)− uT r(t, x)u. (25)
Lemma 1. Let the value function V∗(t, x) be continuously differentiable. Then, the following Hamilton-Jacobi-Bellman equation holds:
∂V∗(t, x)
∂t +max u∈U H(t, x,∇xV∗(t, x), u) = 0, (t, x) ∈ (0, T )× Rn.
The proof can be found, for example, in J. Yong. Differential Games: A Concise Introduction. World Scientific, University of Central Florida, 238 USA, 2015. doi: 10.1142/9121.
Proof of Theorem 1. Note that, due to (19), (21), and (25), we have A(t, x, u)/∆tk = H(t, x,∇xV∗(t, x), u)−max
u′∈U H(t, x,∇xV∗(t, x), u′) (26)
for any (t, x, u) ∈ [0, T ]× Rn × U . Due to (9) and (11), we have∥∥f(t, x) + g(t, x)u∥∥ ≤ cfg(1 + ∥z∥)ecfgT := αfg, (t, x) ∈ S, u ∈ U. (27) Let ε > 0. Since V∗(t, x) is continuously differentiable, there exists δ > 0 such that∣∣∣∣V∗(t′, x′)−V∗(t, x)− ∂V∗(t, x)∂t (t′−t)−⟨∇xV (t, x), x′−x⟩
∣∣∣∣ ≤ (|t−t′|+∥x−x′∥) ε1 + αfg (28) for any (t, x), (t′, x′) ∈ S satisfying |t− t′|+ ∥x− x′∥ ≤ δ. Put k∗ = (1 + αfg)T/δ.
Let k ≥ k∗, i ∈ 0, k − 1, x ∈ S(ti), u ∈ U , and x′ = x+(f(ti, x)+ g(ti, x)u)∆tk. Due to (9) and (11), we have (ti+1, x′) ∈ S. Then, from (27) and (28), we derive∣∣∣∣V∗(ti+1, x′)−V∗(ti, x)− ∂V∗(ti, x)∂t ∆tk−⟨∇xV∗(ti, x), f(ti, x)+g(ti, x)u⟩∆tk ∣∣∣∣ ≤ ε∆tk, (29) Next, according to (18), (20), (25), (26), (29), and Lemma 1, we obtain∣∣Q(ti, x, u) + (q(ti, x) + uT r(ti, x)u)∆tk −min
u′ Q(ti+1, x
′, u′) ∣∣
= ∣∣V∗(ti, x) +A(ti, x, u) + (q(ti, x) + uT r(ti, x)u)∆tk − V∗(ti+1, x′)∣∣ ≤ ∣∣∣∣∂V∗(ti, x)∂t + maxu′∈U H(ti, x,∇xV∗(ti, x), u′)
∣∣∣∣∆tk + ε∆tk = ε∆tk. The theorem is proved.
Proof of Theorem 2. Let ε > 0. Define k∗ according to Theorem 1. Let k ≥ k∗. Let Q ∈ Q satisfy (22). Let xi, i ∈ 0, k be defined by (13), where ui ∈ µ(ti, xi). Then, due to (12), (20), and (22), we have
V (0, z)− Jk(u0, . . . , uk−1)
= k−1∑ i=0 ( Q(ti, xi, ui) + ( q(ti, xi) + u T i r(ti, xi)ui ) ∆tk −max u′∈U Q(ti+1, xi+1, u ′) ) ≤ Tε. (30)
Let us define Q∗ ∈ Q according to (21). Let x∗i , i ∈ 0, k be defined by (13), where u∗i ∈ argmaxu∈U Q∗(ti, xi, u). Then, due to the Theorem 1 and (20), we have∣∣V∗(ti, x∗i ) + (q(ti, x∗i ) + (u∗i )T r(ti, x∗i )u∗i )∆tk − V∗(ti+1, x∗i+1)∣∣ ≤ ε∆tk. (31) Note that, according to definition (10) of the value function V∗, we have V∗(tk, x) = σ(x), x ∈ Rn. Then, from (20), (22), and (31), we derive
0 = max u′∈U
Q(tk, x ∗ k, u ′)− σ(x∗k)
≤ k−1∑ i=0 ( max u′∈U Q(ti+1, x ∗ i+1, u ′)−Q(ti, x∗i , u∗i )− ( q(ti, x ∗ i ) + (u ∗ i ) T r(ti, x ∗ i )u ∗ i ) ∆tk ) +V (0, z)
+ k−1∑ i=0 ( V∗(ti, x ∗ i ) + ( q(ti, x ∗ i ) + (u ∗ i ) T r(ti, x ∗ i )u ∗ i ) ∆tk − V∗(ti+1, x∗i+1) ) − V∗(0, z)
≤ 2Tε+ V (0, z)− V∗(0, z). Due to this inequality and inequality (30), we obtain Jk(u0, . . . , uk−1) ≥ V∗(0, z) − 3Tε. Taking into account (6) and (10) we have sup
u(·) J(u(·)) = V∗(0, z). Thus, the theorem is proved.
Proof of Theorem 3. Let k ≥ 4 and Q ∈ QNAF . Let us take i = k − 1 and x = 2. For the sake of brevity, denote V = V (tk−1, 2), µ = µ(tk−1, 2), and P = P (tk−1, 2). Then, in order to prove the theorem, we have to show that
max u∈[−1,1] ∣∣V − (u− µ)2P + u2∆tk + (2 + u∆tk)2∣∣ > ∆tk/8. Arguing by contradiction assume that
max u∈[−1,1] ∣∣V − (u− µ)2P + u2∆tk + (2 + u∆tk)2∣∣ ≤ ∆tk/8. Then, for u = −1, u = 1, and u = 0, we have
−∆tk/8 ≤ V − (1 + µ)2P +∆tk + (2−∆tk)2 ≤ ∆tk/8, (32)
−∆tk/8 ≤ V − (1− µ)2P +∆tk + (2 +∆tk)2 ≤ ∆tk/8, (33) −∆tk/8 ≤ −V + µ2P − 4 ≤ ∆tk/8. (34)
Adding up inequations (32), (33), and twice inequity (34), we derive
−∆tk/2 ≤ 2P − 2∆tk − 2∆t2k ≤ ∆tk/2. (35)
Adding up twice inequations (32), (34), and inequity (35), we obtain
−∆tk ≤ −4µP − 8∆tk ≤ ∆tk.
From this estimate, taking into account (35) and the inequality k ≥ 4, we conclude
µ ≤ −7∆tk 4P ≤ − 7 5 + 4∆tk ≤ −7 6 < −1.
This inequality contradicts the inclusion µ ∈ U = [−1, 1], which should be valid for Q ∈ QNAF .

heading: B APPENDIX
text: Consider the following optimal control problem: it is required to maximize the functional J(u(·)) = σ(x(T ))− ∫ T 0 F 0(t, x(t), u(t))dt,
over all u(·), where x(·) is the solution (Filippov, 1988, §1) of the differential equation
d dt x(t) = F (t, x(t), u(t)), t ∈ [0, T ],
under the initial condition x(0) = z.
Here t is the time variable, T > 0 is the terminal instant of time, x(t) ∈ Rn is the current state vector, u(t) ∈ U is the current control action vector forming the measurable function u(·), U ⊂ Rm is the nonempty compact set, z ∈ Rn is the fixed initial state vector, F (t, x, u) ∈ Rn, F 0(t, x, u) ∈ R, (t, x, u) ∈ [0, T ] × Rn × U are continuous with respect to t and continuously differentiable with respect to x functions, and σ(x) ∈ R, x ∈ Rn is the continuous function. We assume that there exists a constant cfg > 0 such that
∥F (t, x, u)∥ ≤ (1 + ∥x∥)cfg, (t, x) ∈ [0, T ]× Rn, u ∈ U.
Similar to (25), denote H(t, x, s, u) = ⟨F (t, x, u)u, s⟩ − F 0(t, x, u).
Theorem 4. Let the value function V∗(t, x) be continuously differentiable. Then, for every ε > 0, there exists k∗ > 0 such that, for every k ≥ k∗, the function
Q(t, x, u) = V∗(t, x) +A(t, x, u),
A(t, x, u) = H(t, x,∇xV∗(t, x), u)∆tk −max u′∈U
H(t, x,∇xV∗(t, x), u′)∆tk (36)
satisfies the inequality∣∣Q(ti, x, u) + F 0(ti, x, u)∆tk −max u′∈U Q(ti+1, x ′, u′) ∣∣ ≤ ε∆tk, x′ = x+ F (ti, x, u)∆tk, u ∈ U, x ∈ S(ti), i ∈ 0, k − 1, where we assume Q(tk, x′, u′) = σ(x′).
Proof of Theorem 4 can be obtained similar to the proof of Theorem 1.
For the family of q-function (36), based on Theorem 4, one can also prove the result similar to Theorem 2.

heading: C APPENDIX
text: Figure 2 shows learning curves of RB-BNAF and GB-BNAF algorithms with the clip and hyperbolic tangent functions for the considered examples. Note that there are no cases in which algorithms using the clip functions show better performance comparing with the corresponding algorithms using the hyperbolic tangent function. Although the difference does not seem very significant.

Review summaries:
-The authors prove that a discrete approximation of a class of optimal control problems can be recasted as an RL MDP. -The authors prove that the original NAF formulation of the Q-function cannot approximately solve the MDP defined above, and hence propose a new quadratic formulation of the Q-value. They apply their new formulation via Bounded, Reward-based, and Gradient-based BNAF. -The authors evaluate their proposed agent over 4 optimal control environments.