Offline Reinforcement Learning: Tutorial, Review, and Perspectives on Open Problems — part 2/12

Cleaned-text code points [14685, 29399). Bibliography omitted here; source.md includes it.

One of the most direct ways to optimize the RL objective in Equation 1 is to directly estimate its gradient. In this case, we typically assume that the policy is parameterized by a parameter vector θ \theta , and therefore given by π θ ​ ( 𝐚 t | 𝐬 t ) \pi_{\theta}(\mathbf{a}_{t}|\mathbf{s}_{t}) . For example, θ \theta might denote the weights of a deep network that outputs the logits for the (discrete) actions 𝐚 t \mathbf{a}_{t} . In this case, we can express the gradient of the objective with respect to θ \theta as: ∇ θ J ​ ( π θ ) = 𝔼 τ ∼ p π θ ​ ( τ ) ​ [ ∑ t = 0 H γ t ​ ∇ θ ​ log ⁡ π θ ​ ( 𝐚 t | 𝐬 t ) ​ ( ∑ t ′ = t H γ t ′ − t ​ r ​ ( 𝐬 t ′ , 𝐚 t ′ ) − b ⁡ ( 𝐬 t ) ) ⏟ return estimate ​ A ^ ​ ( 𝐬 t , 𝐚 t ) ] , \nabla_{\theta}J(\pi_{\theta})\!=\!\mathbb{E}_{\tau\sim p_{\pi_{\theta}}(\tau)}\left[\!\sum_{t=0}^{H}\right.\gamma^{t}\nabla_{\theta}\log\pi_{\theta}(\mathbf{a}_{t}|\mathbf{s}_{t})\underbrace{\left(\sum_{t^{\prime}=t}^{H}\gamma^{t^{\prime}-t}r(\mathbf{s}_{t^{\prime}},\mathbf{a}_{t^{\prime}})-b(\mathbf{s}_{t})\right)}_{\text{return estimate }\hat{A}(\mathbf{s}_{t},\mathbf{a}_{t})}\left.\vphantom{\sum_{t=0}^{H}}\!\right], (2) where the return estimator A ^ ​ ( 𝐬 t , 𝐚 t ) \hat{A}(\mathbf{s}_{t},\mathbf{a}_{t}) can itself be learned as a separate neural network critic , as discussed below, or it can simply be estimated with Monte Carlo samples, in which case we simply generate samples from p π θ ​ ( τ ) p_{\pi_{\theta}}(\tau) , and then sum up the rewards over the time steps of the sampled trajectory. The baseline b ⁡ ( 𝐬 t ) b(\mathbf{s}_{t}) can be estimated as the average reward over the sampled trajectories, or by using a value function estimator V ⁡ ( 𝐬 t ) V(\mathbf{s}_{t}) , which we discuss in the dynamic programming section. We can equivalently write this gradient expression as an expectation with respect to d t π ​ ( 𝐬 t ) d^{\pi}_{t}(\mathbf{s}_{t}) as ∇ θ J ​ ( π θ ) = ∑ t = 0 H 𝔼 𝐬 t ∼ d t π ​ ( 𝐬 t ) , 𝐚 t ∼ π θ ​ ( 𝐚 t | 𝐬 t ) ​ [ γ t ​ ∇ θ ​ log ⁡ π θ ​ ( 𝐚 t | 𝐬 t ) ​ A ^ ​ ( 𝐬 t , 𝐚 t ) ] . \nabla_{\theta}J(\pi_{\theta})\!=\!\sum_{t=0}^{H}\mathbb{E}_{\mathbf{s}_{t}\sim d^{\pi}_{t}(\mathbf{s}_{t}),\mathbf{a}_{t}\sim\pi_{\theta}(\mathbf{a}_{t}|\mathbf{s}_{t})}\left[\gamma^{t}\nabla_{\theta}\log\pi_{\theta}(\mathbf{a}_{t}|\mathbf{s}_{t})\hat{A}(\mathbf{s}_{t},\mathbf{a}_{t})\right]. A common modification is to drop the γ t \gamma^{t} term in front of the gradient, which approximates an average reward setting ( Thomas,, 2014 ) . Dropping this term and adopting an infinite-horizon formulation, we can further rewrite the policy gradient as expectation under d π ​ ( 𝐬 ) d^{\pi}(\mathbf{s}) as ∇ θ J ​ ( π θ ) = 1 1 − γ ​ 𝔼 𝐬 ∼ d π ​ ( 𝐬 t ) , 𝐚 ∼ π θ ​ ( 𝐚 | 𝐬 ) ​ [ ∇ θ ​ log ​ π θ ​ ( 𝐚 | 𝐬 ) ​ A ^ ​ ( 𝐬 , 𝐚 ) ] . \nabla_{\theta}J(\pi_{\theta})\!=\!\frac{1}{1-\gamma}\mathbb{E}_{\mathbf{s}\sim d^{\pi}(\mathbf{s}_{t}),\mathbf{a}\sim\pi_{\theta}(\mathbf{a}|\mathbf{s})}\left[\nabla_{\theta}\log\pi_{\theta}(\mathbf{a}|\mathbf{s})\hat{A}(\mathbf{s},\mathbf{a})\right]. The constant scaling term 1 1 − γ \frac{1}{1-\gamma} is often disregarded. This infinite-horizon formulation is often convenient to work with for analyzing and deriving policy gradient methods. For a full derivation of this gradient, we refer the reader to prior work ( Sutton et al.,, 2000 ; Kakade,, 2002 ; Schulman et al.,, 2015 ) . We can summarize a basic Monte Carlo policy gradient algorithm as follows:

For additional details on standard on-policy policy gradient methods, we refer the reader to prior work ( Sutton et al.,, 2000 ; Kakade,, 2002 ; Schulman et al.,, 2015 ) .

#### Approximate dynamic programming.

Another way to optimize the reinforcement learning objective is to observe that, if we can accurately estimate a state or state-action value function , it is easy to then recover a near-optimal policy. A value function provides an estimate of the expected cumulative reward that will be obtained by following some policy π ⁡ ( 𝐚 t | 𝐬 t ) \pi(\mathbf{a}_{t}|\mathbf{s}_{t}) when starting from a given state 𝐬 t \mathbf{s}_{t} , in the case of the state-value function V π ​ ( 𝐬 t ) V^{\pi}(\mathbf{s}_{t}) , or when starting from a state-action tuple ( 𝐬 t , 𝐚 t ) (\mathbf{s}_{t},\mathbf{a}_{t}) , in the case of the state-action value function Q π ​ ( 𝐬 t , 𝐚 t ) Q^{\pi}(\mathbf{s}_{t},\mathbf{a}_{t}) . We can define these value functions as: V π ​ ( 𝐬 t ) \displaystyle V^{\pi}(\mathbf{s}_{t}) = 𝔼 τ ∼ p π ​ ( τ | 𝐬 t ) ​ [ ∑ t ′ = t H γ t ′ − t ​ r ​ ( 𝐬 t , 𝐚 t ) ] \displaystyle=\mathbb{E}_{\tau\sim p_{\pi}(\tau|\mathbf{s}_{t})}\left[\sum_{t^{\prime}=t}^{H}\gamma^{t^{\prime}-t}r(\mathbf{s}_{t},\mathbf{a}_{t})\right] Q π ​ ( 𝐬 t , 𝐚 t ) \displaystyle Q^{\pi}(\mathbf{s}_{t},\mathbf{a}_{t}) = 𝔼 τ ∼ p π ​ ( τ | 𝐬 t , 𝐚 t ) ​ [ ∑ t ′ = t H γ t ′ − t ​ r ​ ( 𝐬 t , 𝐚 t ) ] . \displaystyle=\mathbb{E}_{\tau\sim p_{\pi}(\tau|\mathbf{s}_{t},\mathbf{a}_{t})}\left[\sum_{t^{\prime}=t}^{H}\gamma^{t^{\prime}-t}r(\mathbf{s}_{t},\mathbf{a}_{t})\right]. From this, we can derive recursive definitions for these value functions, which are given as V π ​ ( 𝐬 t ) \displaystyle V^{\pi}(\mathbf{s}_{t}) = 𝔼 𝐚 t ∼ π ⁡ ( 𝐚 t | 𝐬 t ) ​ [ Q π ​ ( 𝐬 t , 𝐚 t ) ] \displaystyle=\mathbb{E}_{\mathbf{a}_{t}\sim\pi(\mathbf{a}_{t}|\mathbf{s}_{t})}\left[Q^{\pi}(\mathbf{s}_{t},\mathbf{a}_{t})\right] Q π ​ ( 𝐬 t , 𝐚 t ) \displaystyle Q^{\pi}(\mathbf{s}_{t},\mathbf{a}_{t}) = r ⁡ ( 𝐬 t , 𝐚 t ) + γ ​ 𝔼 𝐬 t + 1 ∼ T ⁡ ( 𝐬 t + 1 | 𝐬 t , 𝐚 t ) ​ [ V π ​ ( 𝐬 t + 1 ) ] . \displaystyle=r(\mathbf{s}_{t},\mathbf{a}_{t})+\gamma\mathbb{E}_{\mathbf{s}_{t+1}\sim T(\mathbf{s}_{t+1}|\mathbf{s}_{t},\mathbf{a}_{t})}\left[V^{\pi}(\mathbf{s}_{t+1})\right]. We can combine these two equations to express the Q π ​ ( 𝐬 t , 𝐚 t ) Q^{\pi}(\mathbf{s}_{t},\mathbf{a}_{t}) in terms of Q π ​ ( 𝐬 t + 1 , 𝐚 t + 1 ) Q^{\pi}(\mathbf{s}_{t+1},\mathbf{a}_{t+1}) : Q π ​ ( 𝐬 t , 𝐚 t ) \displaystyle Q^{\pi}(\mathbf{s}_{t},\mathbf{a}_{t}) = r ( 𝐬 t , 𝐚 t ) + γ 𝔼 𝐬 t + 1 ∼ T ⁡ ( 𝐬 t + 1 | 𝐬 t , 𝐚 t ) , 𝐚 t + 1 ∼ π ⁡ ( 𝐚 t + 1 | 𝐬 t + 1 ) [ Q π ( 𝐬 t + 1 , 𝐚 t + 1 ) ) ] . \displaystyle=r(\mathbf{s}_{t},\mathbf{a}_{t})+\gamma\mathbb{E}_{\mathbf{s}_{t+1}\sim T(\mathbf{s}_{t+1}|\mathbf{s}_{t},\mathbf{a}_{t}),\mathbf{a}_{t+1}\sim\pi(\mathbf{a}_{t+1}|\mathbf{s}_{t+1})}\left[Q^{\pi}(\mathbf{s}_{t+1},\mathbf{a}_{t+1}))\right]. (3) We can also express these in terms of the Bellman operator for the policy π \pi , which we denote ℬ π \mathcal{B}^{\pi} . For example, Equation ( 3 ) can be written as Q → π = ℬ π ​ Q → π \vec{Q}^{\pi}=\mathcal{B}^{\pi}\vec{Q}^{\pi} , where Q → π \vec{Q}^{\pi} denotes the Q-function Q π Q^{\pi} represented as a vector of length | 𝒮 | × | 𝒜 | |\mathcal{S}|\times|\mathcal{A}| . Before moving on to deriving learning algorithms based on these definitions, we briefly discuss some properties of the Bellman operator. This Bellman operator has a unique fixed point that corresponds to the true Q-function for the policy π ⁡ ( 𝐚 | 𝐬 ) \pi(\mathbf{a}|\mathbf{s}) , which can be obtained by repeating the iteration Q → k + 1 π = ℬ π ​ Q → k π \vec{Q}^{\pi}_{k+1}=\mathcal{B}^{\pi}\vec{Q}^{\pi}_{k} , and it can be shown that lim k → ∞ Q → k π = Q → π \lim_{k\rightarrow\infty}\vec{Q}^{\pi}_{k}=\vec{Q}^{\pi} , which obeys Equation ( 3 ) ( Sutton and Barto,, 1998 ) . The proof for this follows from the observation that ℬ π \mathcal{B}^{\pi} is a contraction in the ℓ ∞ \ell_{\infty} norm ( Lagoudakis and Parr,, 2003 ) .

Based on these definitions, we can derive two commonly used algorithms based on dynamic programming: Q-learning and actor-critic methods. To derive Q-learning, we express the policy implicitly in terms of the Q-function, as π ⁡ ( 𝐚 t | 𝐬 t ) = δ ⁡ ( 𝐚 t = arg ⁡ max ⁡ Q ⁡ ( 𝐬 t , 𝐚 t ) ) \pi(\mathbf{a}_{t}|\mathbf{s}_{t})=\delta(\mathbf{a}_{t}=\arg\max Q(\mathbf{s}_{t},\mathbf{a}_{t})) , and only learn the Q-function Q ⁡ ( 𝐬 t , 𝐚 t ) Q(\mathbf{s}_{t},\mathbf{a}_{t}) . By substituting this (implicit) policy into the above dynamic programming equation, we obtain the following condition on the optimal Q-function: Q ⋆ ​ ( 𝐬 t , 𝐚 t ) = r ⁡ ( 𝐬 t , 𝐚 t ) + γ ​ 𝔼 𝐬 t + 1 ∼ T ⁡ ( 𝐬 t + 1 | 𝐬 t , 𝐚 t ) ​ [ max 𝐚 t + 1 ⁡ Q ⋆ ​ ( 𝐬 t + 1 , 𝐚 t + 1 ) ] . Q^{\star}(\mathbf{s}_{t},\mathbf{a}_{t})=r(\mathbf{s}_{t},\mathbf{a}_{t})+\gamma\mathbb{E}_{\mathbf{s}_{t+1}\sim T(\mathbf{s}_{t+1}|\mathbf{s}_{t},\mathbf{a}_{t})}\left[\max_{\mathbf{a}_{t+1}}Q^{\star}(\mathbf{s}_{t+1},\mathbf{a}_{t+1})\right]. (4) We can again express this as Q → = ℬ ⋆ ​ Q → \vec{Q}=\mathcal{B}^{\star}\vec{Q} in vector notation, where ℬ ⋆ \mathcal{B}^{\star} now refers to the Bellman optimality operator. Note however that this operator is not linear, due to the maximization on the right-hand side in Equation ( 4 ). To turn this equation into a learning algorithm, we can minimize the difference between the left-hand side and right-hand side of this equation with respect to the parameters of a parametric Q-function estimator with parameters ϕ \phi , Q ϕ ​ ( 𝐬 t , 𝐚 t ) Q_{\phi}(\mathbf{s}_{t},\mathbf{a}_{t}) . There are a number of variants of this Q-learning procedure, including variants that fully minimize the difference between the left-hand side and right-hand side of the above equation at each iteration, commonly referred to as fitted Q-iteration ( Ernst et al.,, 2005 ; Riedmiller,, 2005 ) , and variants that take a single gradient step, such as the original Q-learning method ( Watkins and Dayan,, 1992 ) . The commonly used variant in deep reinforcement learning is a kind of hybrid of these two methods, employing a replay buffer ( Lin,, 1992 ) and taking gradient steps on the Bellman error objective concurrently with data collection ( Mnih et al.,, 2013 ) . We write out a general recipe for Q-learning methods in Algorithm 2 .

Classic Q-learning can be derived as the limiting case where the buffer size is 1, and we take G = 1 G=1 gradient steps and collect S = 1 S=1 transition samples per iteration, while classic fitted Q-iteration runs the inner gradient descent phase to convergence (i.e., G = ∞ G=\infty ), and uses a buffer size equal to the number of sampling steps S S . Note that many modern implementations also employ a target network , where the target value r i + γ ​ max 𝐚 ′ ​ Q ϕ k ​ ( 𝐬 ′ , 𝐚 ′ ) r_{i}+\gamma\max_{\mathbf{a}^{\prime}}Q_{\phi_{k}}(\mathbf{s}^{\prime},\mathbf{a}^{\prime}) actually uses ϕ L \phi_{L} , where L L is a lagged iteration (e.g., the last k k that is a multiple of 1000). Note that these approximations violate the assumptions under which Q-learning algorithms can be proven to converge. However, recent work suggests that high-capacity function approximators, which correspond to a very large set 𝒬 \mathcal{Q} , generally do tend to make this method convergent in practice, yielding a Q-function that is close to Q → π \vec{Q}^{\pi} ( Fu et al.,, 2019 ; Van Hasselt et al.,, 2018 ) .

#### Actor-critic algorithms.

Actor-critic algorithms combine the basic ideas from policy gradients and approximate dynamic programming. Such algorithms employ both a parameterized policy and a parameterized value function, and use the value function to provide a better estimate of A ^ ​ ( 𝐬 , 𝐚 ) \hat{A}(\mathbf{s},\mathbf{a}) for policy gradient calculation. There are a number of different variants of actor-critic methods, including on-policy variants that directly estimate V π ​ ( 𝐬 ) V^{\pi}(\mathbf{s}) ( Konda and Tsitsiklis,, 2000 ) , and off-policy variants that estimate Q π ​ ( 𝐬 , 𝐚 ) Q^{\pi}(\mathbf{s},\mathbf{a}) via a parameterized state-action value function Q ϕ π ​ ( 𝐬 , 𝐚 ) Q^{\pi}_{\phi}(\mathbf{s},\mathbf{a}) ( Haarnoja et al.,, 2018 ; Haarnoja et al.,, 2017 ; Heess et al.,, 2015 ) . We will focus on the latter class of algorithms, since they can be extended to the offline setting. The basic design of such an algorithm is a straightforward combination of the ideas in dynamic programming and policy gradients. Unlike Q-learning, which directly attempts to learn the optimal Q-function, actor-critic methods aim to learn the Q-function corresponding to the current parameterized policy π θ ​ ( 𝐚 | 𝐬 ) \pi_{\theta}(\mathbf{a}|\mathbf{s}) , which must obey the equation Q π ​ ( 𝐬 t , 𝐚 t ) = r ⁡ ( 𝐬 t , 𝐚 t ) + γ ​ 𝔼 𝐬 t + 1 ∼ T ⁡ ( 𝐬 t + 1 | 𝐬 t , 𝐚 t ) , 𝐚 t + 1 ∼ π θ ​ ( 𝐚 t + 1 | 𝐬 t + 1 ) ​ [ Q π ​ ( 𝐬 t + 1 , 𝐚 t + 1 ) ] . Q^{\pi}(\mathbf{s}_{t},\mathbf{a}_{t})=r(\mathbf{s}_{t},\mathbf{a}_{t})+\gamma\mathbb{E}_{\mathbf{s}_{t+1}\sim T(\mathbf{s}_{t+1}|\mathbf{s}_{t},\mathbf{a}_{t}),\mathbf{a}_{t+1}\sim\pi_{\theta}(\mathbf{a}_{t+1}|\mathbf{s}_{t+1})}\left[Q^{\pi}(\mathbf{s}_{t+1},\mathbf{a}_{t+1})\right]. As before, this equation can be expressed in vector form in terms of the Bellman operator for the policy, Q → π = ℬ π ​ Q → π \vec{Q}^{\pi}=\mathcal{B}^{\pi}\vec{Q}^{\pi} , where Q → π \vec{Q}^{\pi} denotes the Q-function Q π Q^{\pi} represented as a vector of length | 𝒮 | × | 𝒜 | |\mathcal{S}|\times|\mathcal{A}| . We can now instantiate a complete algorithm based on this idea, shown in Algorithm 3 .

For more details, we refer the reader to standard textbooks and prior works ( Sutton and Barto,, 1998 ; Konda and Tsitsiklis,, 2000 ) . Actor-critic algorithms are closely related with another class of methods that frequently arises in dynamic programming, called policy iteration (PI) ( Lagoudakis and Parr,, 2003 ) . Policy iteration consists of two phases: policy evaluation and policy improvement. The policy evaluation phase computes the Q-function for the current policy π \pi , Q π Q^{\pi} , by solving for the fixed point such that Q π = ℬ π ​ Q π Q^{\pi}=\mathcal{B}^{\pi}Q^{\pi} . This can be done via linear programming or solving a system of linear equations, as we will discuss in Section 4 , or via gradient updates, analogously to line 15 in Algorithm 3 . The next policy iterate is then computed in the policy improvement phase, by choosing the action that greedily maximizes the Q-value at each state, such that π k + 1 ​ ( 𝐚 | 𝐬 ) = δ ⁡ ( 𝐚 = arg ⁡ max 𝐚 ​ Q π k ​ ( 𝐬 , 𝐚 ) ) \pi_{k+1}(\mathbf{a}|\mathbf{s})=\delta(\mathbf{a}=\arg\max_{\mathbf{a}}Q^{\pi_{k}}(\mathbf{s},\mathbf{a})) , or by using a gradient based update procedure as is employed in Algorithm 3 on line 24. In the absence of function approximation (e.g., with tabular representations) policy iteration produces a monotonically improving sequence of policies, and converges to the optimal policy. Policy iteration can be obtained as a special case of the generic actor-critic algorithm in Algorithm 3 when we set G Q = ∞ G_{Q}=\infty and G π = ∞ G_{\pi}=\infty , when the buffer 𝒟 \mathcal{D} consists of each and every transition of the MDP.

#### Model-based reinforcement learning.