Stochastic Gradient Descent with Dependent Data for Offline
  Reinforcement 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 $\gamma$.
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 $\epsilon$ accuracy, the complexity of the algorithm is $\tilde
O(\epsilon^{-2}(1-\gamma)^{-5})$, which matches the complexity bound for
classic online RL algorithms such as Q-learning.
