Stochastic Gradient Descent with Dependent Data for Offline Reinforcement Learning
This work addresses offline reinforcement learning for policy evaluation and learning, providing theoretical convergence guarantees that match online methods, but it is incremental as it builds on existing stochastic optimization and RL frameworks.
The paper tackles offline reinforcement learning by formulating policy evaluation as a stochastic optimization problem and solving it with approximate stochastic gradient descent (aSGD) using time-dependent data, achieving $ ilde O(1/t)$ convergence for strongly convex loss functions independent of the discount factor $γ$, and combining this with policy iteration to learn optimal policies with complexity $ ilde O(ε^{-2}(1-γ)^{-5})$, matching classic online RL algorithms like Q-learning.
In reinforcement learning (RL), offline learning decoupled learning from data collection and is useful in dealing with exploration-exploitation tradeoff and enables data reuse in many applications. In this work, we study two offline learning tasks: policy evaluation and policy learning. For policy evaluation, we formulate it as a stochastic optimization problem and show that it can be solved using approximate stochastic gradient descent (aSGD) with time-dependent data. We show aSGD achieves $\tilde O(1/t)$ convergence when the loss function is strongly convex and the rate is independent of the discount factor $γ$. This result can be extended to include algorithms making approximately contractive iterations such as TD(0). The policy evaluation algorithm is then combined with the policy iteration algorithm to learn the optimal policy. To achieve an $ε$ accuracy, the complexity of the algorithm is $\tilde O(ε^{-2}(1-γ)^{-5})$, which matches the complexity bound for classic online RL algorithms such as Q-learning.