Sample Complexity of Asynchronous Q-Learning: Sharper Analysis and Variance Reduction
By Gen Li, Yuting Wei, Yuejie Chi, Yuantao Gu, Yuxin Chen. 2020
145 citations recorded by the source corpus.
Asynchronous Q-learning aims to learn the optimal action-value function (or Q-function) of a Markov decision process (MDP), based on a single trajectory of Markovian samples induced by a behavior policy. Focusing on a <inline-formula> <tex-math notation="LaTeX">$\gamma $ </tex-math></inline-formula>-discounted MDP with state space <inline-formula> <tex-math notation="LaTeX">$\mathcal {S}$ </tex-math></inline-formula> and action space <inline-formula> <tex-math notation="LaTeX">$\mathcal {A}$ </tex-math></inline-formula>, we demonstrate that the <inline-formula> <tex-math notation="LaTeX">$\ell _{\infty }$ </tex-math></inline-formula>-based sample complexity of classical asynchronous Q-learning — namely, the number of samples needed to yield an entrywise <inline-formula> <tex-math notation="LaTeX">$\varepsilon $ </tex-math></inline-formula>-accurate estimate of the Q-function — is at most on the order of <inline-formula> <tex-math notation="LaTeX">$\frac {1}{ \mu _{\mathsf {min}}(1-\gamma)^{5}\varepsilon ^{2}}+ \frac { t_{\mathsf {mix}}}{ \mu _{\mathsf {min}}(1-\gamma)}$ </tex-math></inline-formula> up to some logarithmic factor, provided that a proper constant learning rate is adopted. Here, <inline-formula> <tex-math notation="LaTeX">$t_{\mathsf {mix}}$ </tex-math></inline-formula> and <inline-formula> <tex-math notation="LaTeX">$\mu _{\mathsf {min}}$ </tex-math></inline-formula> denote respectively the mixing time and the minimum state-action occupancy probability of the sample trajectory. The first term of this bound matches the sample complexity in the synchronous case with independent samples drawn from the stationary distribution of the trajectory. The second term reflects the cost taken for the empirical distribution of the Markovian trajectory to reach a steady state, which is incurred at the very beginning and becomes amortized as the algorithm runs. Encouragingly, the above bound improves upon the state-of-the-art result by a factor of at least <inline-formula> <tex-math notation="LaTeX">$|\mathcal {S}||\mathcal {A}|$ </tex-math></inline-formula> for all scenarios, and by a factor of at least <inline-formula> <tex-math notation="LaTeX">$t_{\mathsf {mix}}|\mathcal {S}||\mathcal {A}|$ </tex-math></inline-formula> for any sufficiently small accuracy level <inline-formula> <tex-math notation="LaTeX">$\varepsilon $ </tex-math></inline-formula>. Further, we demonstrate that the scaling on the effective horizon <inline-formula> <tex-math notation="LaTeX">$\frac {1}{1-\gamma }$ </tex-math></inline-formula> can be improved by means of variance reduction.
Subfields: Artificial Intelligence, Atomic and Molecular Physics, and Optics
How researchers see this paper
The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.
In Artificial Intelligence
In Atomic and Molecular Physics, and Optics
Citations in the corpus
- Variational Bayesian Reinforcement Learning with Regret Bounds (2018, background): “L of the known information theoretic lower bound of Ω( L The update rule we derive is similar to that used in ‘soft’ Q-learning (so-called since the ‘hard’ max is replaced with a soft-max) [6, 16, 18, 30, 47].”
- Reinforcement Learning for Selective Key Applications in Power Systems: Recent Advances and Future Challenges (2021, methodology): “For classical RL algorithms, such as Q -learning, the sample complexity depends on the size of the state and action spaces; the larger the state and action spaces are, the more data are generally needed to find a near-optimal policy [25], [189].”
- Near-Optimal Offline Reinforcement Learning via Double Variance Reduction (2021, methodology): “, 2017) and policy optimization problems (Sidford et al., 2018b,a; Yang & Wang, 2019; Wainwright, 2019; Sidford et al., 2020; Li et al., 2020; Zhang et al., 2020).”
- Is Pessimism Provably Efficient for Offline RL? (2020, background): “…Fan et al., 2020; Xie and Jiang, 2020a;b; Jiang and Huang, 2020; Uehara et al., 2020; Duan et al., 2020; Yin et al., 2020; Qu and Wierman, 2020; Li et al., 2020; Liao et al., 2020; Nachum and Dai, 2020; Yang et al., 2020a; Zhang et al., 2020a;b), we require no assumptions on the “uniform…”