betaFeedback

WorksComputer Science

Efficient Variance-Aware Reinforcement Learning in Time-Inhomogeneous Linear MDPs

Abstract

We study variance-dependent reinforcement learning in episodic time-inhomogeneous linear Markov decision processes (MDPs) with feature dimension dd, horizon HH, and KK episodes. While recent works have established variance-dependent regret with O~(1)\tilde{O}(1) deterministic-regime overhead for linear mixture MDPs (Zhao et al., 2023) and worst-case nearly minimax optimal regret O~(dH3K+d7H8)\tilde{O}(d\sqrt{H^3 K} + d^7 H^8) for linear MDPs (He et al., 2023),, existing variance-aware analyses for linear MDPs (Li and Sun, 2023; Huang et al., 2023) rely on a coarse concentration step whose resulting regret guarantees retain a polynomial O~(K1/4)\tilde{O}(K^{1/4}) additive term even in deterministic environments. We propose VA-LSVI-UCB++, a computationally efficient algorithm that achieves the variance-dependent regret bound O~(dHmin⁡{VarK∗,VarKπ}+d5H4)\tilde{O}(d\sqrt{H\min\{\mathrm{Var}_K^*,\mathrm{Var}_K^π\}}+d^5H^4), where VarK∗\mathrm{Var}_K^* and VarKπ\mathrm{Var}_K^π denote the cumulative conditional variances of the optimal value function and the played policies' value functions along the realized trajectory. Our result adapts to the minimum of the two realized trajectory variances, recovers the worst-case minimax optimal leading term O~(dH3K)\tilde{O}(d\sqrt{H^3 K}), and collapses to O~(d5H4)\tilde{O}(d^5 H^4) in deterministic environments, free of polynomial-in-KK dependency. At the core of our analysis is a simultaneous three-way reference-advantage decomposition for the optimistic, pessimistic, and squared value function estimators coupled with variance self-bounding and Freedman-type value-difference arguments, which tightens the pessimistic and second-moment confidence radii by a factor of O~(dH)\tilde{O}(d H) and removes the inverse-variance-floor blowup.

Introduction

Designing statistically and computationally efficient algorithms for reinforcement learning (RL) with function approximation is a central problem in modern statistical learning theory. To handle large or continuous state spaces, a major line of research studies Markov decision processes (MDPs) equipped with linear structure, most notably linear mixture MDPs ([26, 17, 3, 41, 40, 39]), where the transition kernel is a linear combination of basis transition models Ph(s′∣s,a)=⟨ϕ(s′∣s,a),θh∗⟩P_h(s' \mid s,a)=\langle\phi(s' \mid s,a),\theta_h^*\rangle, and linear MDPs ([30, 20, 2] (Hu et al. 2022; He et al. 2023)), where both the transition kernel Ph(s′∣s,a)=⟨ϕ(s,a),dθh(s′)⟩P_h(s' \mid s,a)=\langle\phi(s,a),d\theta_h(s')\rangle and the reward function are linear in a known dd-dimensional state-action feature map ϕ(s,a)\phi(s,a) with unknown signed measures θh(⋅)\theta_h(\cdot) over the state space S\mathcal{S}.

While worst-case minimax regret bounds quantify algorithm performance in the hardest environment instances, practical RL environments often exhibit low or even zero transition stochasticity. This observation has motivated a surge of interest in variance-dependent (or second-order) regret bounds ([32, 41, 37, 21, 39, 16, 43, 10] (Zhou and Gu 2022; Li and Sun 2023)), which scale with the transition variance rather than the worst-case horizon bound and ideally interpolate between the O~(K)\widetilde{O}(\sqrt{K}) minimax rate in stochastic regimes and O~(1)\widetilde{O}(1) (polylogarithmic in KK) regret in deterministic regimes. For time-homogeneous linear mixture MDPs under ∑h=1Hrh≤1\sum_{h=1}^{H}r_h\leq1, Zhao et al. [39] proposed UCRL-AVE, achieving a variance-dependent regret of O~(dVar⁡K∗+d2)\widetilde{O}(d\sqrt{\operatorname{Var}^{*}_{K}}+d^2) without prior knowledge of the transition variances.

From a statistical perspective, however, linear MDPs are substantially more challenging to analyze than linear mixture MDPs. In linear mixture MDPs, for any next-stage value function Vk,h+1V_{k,h+1}, the integrated feature vector ϕVk,h+1(s,a)=∑s′∈Sϕ(s′∣s,a)Vk,h+1(s′)\phi_{V_{k,h+1}}(s,a)=\sum_{s'\in\mathcal{S}}\phi(s'\mid s,a)V_{k,h+1}(s') is explicitly computable by the learner, and the regression target parameter θh∗∈Rd\theta_h^*\in\mathbb{R}^d is fixed and independent of Vk,h+1V_{k,h+1}. Exploiting this fixed-target structure, Zhao et al. [39] directly applied self-normalized martingale concentration to the single target vector θh∗\theta_h^* without requiring an ϵ\epsilon-net covering over the value function class. In contrast, in linear MDPs, the feature vector ϕ(shi,ahi)\phi(s_h^i,a_h^i) is fixed while the true Bellman backup parameter wh(Vk,h+1)=∫SVk,h+1(s′)dθh(s′)w_h(V_{k,h+1})=\int_{\mathcal{S}}V_{k,h+1}(s')d\theta_h(s') depends on the random, data-dependent value function Vk,h+1V_{k,h+1} constructed from later stages. This statistical dependency breaks martingale adaptedness and necessitates a uniform convergence (ϵ\epsilon-net covering) argument over the value function class ([20]). Because the optimistic value function class has log-covering number O~(d2)\widetilde{O}(d^2) (or O~(d3H)\widetilde{O}(d^3H) under rare-switching updates), naive uniform convergence inflates the confidence radius by d\sqrt{d}, leading to the suboptimal O~(d3H4K)\widetilde{O}(\sqrt{d^3H^4K}) regret of LSVI-UCB ([20]).

Recently, He et al. (2023) (concurrently with Agarwal et al. [2]) resolved the worst-case minimax optimality for linear MDPs by proposing LSVI-UCB++, which attains O~(dH3K+d7H8)\widetilde{O}(d\sqrt{H^3K}+d^7H^8) regret via variance-weighted ridge regression, reference-advantage decomposition Vk,h+1=Vh+1∗+(Vk,h+1−Vh+1∗)V_{k,h+1}=V^*_{h+1}+(V_{k,h+1}-V^*_{h+1}), pointwise monotonic value updates, and rare-switching policy updates. Yet, despite employing variance-weighted regression, the guarantee of LSVI-UCB++ is purely worst-case and does not exploit low or zero transition variance: even in a deterministic linear MDP where all transition variances vanish, the regret bound of He et al. (2023) remains O~(dH3K+d7H8)\widetilde{O}(d\sqrt{H^3K}+d^7H^8). Specifically, the analysis of He et al. (2023) relies on (i) a coarse, variance-oblivious concentration bound over the full function classes with initial confidence radius scaling inversely with the variance floor σmin⁡\sigma_{\min} (with σmin⁡=H\sigma_{\min}=\sqrt{H} used in the coarse analysis, yielding large radii βˉ=O~(d3H2)\bar{\beta}=\widetilde{O}(\sqrt{d^3H^2}) and β~=O~(d3H2)\widetilde{\beta}=\widetilde{O}(\sqrt{d^3H^2}) for the pessimistic and second-moment estimators), and (ii) Azuma–Hoeffding inequalities on the transition martingale differences of Vk,h+1−Vh+1πkV_{k,h+1}-V^{\pi_k}_{h+1} and Vk,h+1−V~k,h+1V_{k,h+1}-\widetilde{V}_{k,h+1} that inject unconditional H3K\sqrt{H^3K} and H5K\sqrt{H^5K} terms. Subsequent works by Li and Sun (2023) (VARA) and Huang et al. [16] (HEAVY-LSVI-UCB) replaced the Azuma–Hoeffding step with Freedman-type arguments to obtain variance-aware leading terms O~(dHKσ∗)\widetilde{O}(d\sqrt{HK\sigma^*}) and O~(dHKγ∗)\widetilde{O}(d\sqrt{HK\gamma^*}) (where G∗,V∗G^{*},\mathcal{V}^{*} denote expected occupancy-measure variances), but both still retained the coarse first-stage confidence radius β0=O~(Hd3H/σmin⁡)\beta_{0}=\widetilde{O}(H\sqrt{d^{3}H}/\sigma_{\min}) (and Hβ0=O~(H2d3H/σmin⁡)H\beta_{0}=\widetilde{O}(H^{2}\sqrt{d^{3}H}/\sigma_{\min}) for the second-moment target); trading off σmin⁡∝K−1/4\sigma_{\min}\propto K^{-1/4} in their regret upper bounds leaves an unconditional O~(K1/4)\widetilde{O}(K^{1/4}) polynomial additive term even in deterministic MDPs. Thus, a natural question remains open:

Can we design a computationally efficient algorithm for linear MDPs that achieves\textit{Can we design a computationally efficient algorithm for linear MDPs that achieves}
variance-dependent regret adapting to the realized trajectory variance min⁡{Var⁡K∗,Var⁡Kπ} with a\textit{variance-dependent regret adapting to the realized trajectory variance }\min\{\operatorname{Var}_{K}^{*},\operatorname{Var}_{K}^{\pi}\}\textit{ with a}
K-independent (up to polylogarithmic factors) lower-order remainder?\textit{\(K\)-independent (up to polylogarithmic factors) lower-order remainder?}

Main contributions. In this paper, we answer the open question above affirmatively by proposing VA-LSVI-UCB++ (Algorithm 1), a computationally efficient algorithm for episodic time-inhomogeneous linear MDPs. A detailed comparison with prior results for time-inhomogeneous MDPs is provided in Table 1 (with a companion comparison for time-homogeneous horizon-free RL in Appendix § 12 and Table 2). Our main contributions are summarized as follows:

References

  1. [1]Abbasi-Yadkori, Y., Pál, D. and Szepesvári, C. (2011). Improved algorithms for linear stochastic bandits. In Advances in Neural Information Processing Systems, volume 24, pages 2312–2320.
  2. [2]Agarwal, A., Jin, Y. and Zhang, T. (2023). VOQL: Towards optimal regret in model-free RL with nonlinear function approximation. In Proceedings of the 36th Annual Conference on Learning Theory, pages 987–1063.arxiv.org/abs/2212.06069
  3. [3]Ayoub, A., Jia, Z., Szepesvári, C., Wang, M. and Yang, L. F. (2020). Model-based reinforcement learning with value-targeted regression. In Proceedings of the 37th International Conference on Machine Learning, pages 463–474.arxiv.org/abs/2006.01107
  4. [4]Azar, M. G., Munos, R. and Kappen, H. J. (2013). Minimax PAC bounds on the sample complexity of reinforcement learning with a generative model. Machine Learning, 91 325–349.DOI
  5. [5]Azar, M. G., Osband, I. and Munos, R. (2017). Minimax regret bounds for reinforcement learning. In Proceedings of the 34th International Conference on Machine Learning, pages 263–272.arxiv.org/abs/1703.05449
  6. [6]Beygelzimer, A., Langford, J., Li, L., Reyzin, L. and Schapire, R. (2011). Contextual bandit algorithms with supervised learning guarantees. In Proceedings of the 14th International Conference on Artificial Intelligence and Statistics, pages 19–26.
  7. [7]Chen, L., Jafarnia-Jahromi, M., Jain, R. and Luo, H. (2021). Implicit finite-horizon approximation and efficient optimal algorithms for stochastic shortest path. In Advances in Neural Information Processing Systems, volume 34, pages 10849–10861.arxiv.org/abs/2106.08377
  8. [8]Chen, L., Jain, R. and Luo, H. (2022). Improved no-regret algorithms for stochastic shortest path with linear MDP. In Proceedings of the 39th International Conference on Machine Learning, pages 3204–3245.arxiv.org/abs/2112.09859
  9. [9]Dann, C., Jiang, N., Krishnamurthy, A., Agarwal, A., Langford, J. and Schapire, R. E. (2018). On oracle-efficient PAC RL with rich observations. In Advances in Neural Information Processing Systems, volume 31.arxiv.org/abs/1803.00606
  10. [10]Foster, D. J., Block, A. and Misra, D. (2024). Is behavior cloning all you need? Understanding horizon in imitation learning. In Advances in Neural Information Processing Systems, volume 37.arxiv.org/abs/2407.15007
  11. [11]Freedman, D. A. (1975). On tail probabilities for martingales. The Annals of Probability, 3 100–118.DOI
  12. [16]Huang, J., Zhong, H., Wang, L. and Yang, L. F. (2023). Tackling heavy-tailed rewards in reinforcement learning with function approximation: Minimax optimal and instance-dependent regret bounds. In Advances in Neural Information Processing Systems, volume 36, pages 56576–56588.arxiv.org/abs/2306.06836
  13. [17]Jia, Z., Yang, L. F., Szepesvári, C. and Wang, M. (2020). Model-based reinforcement learning with value-targeted regression. In Proceedings of the 2nd Conference on Learning for Dynamics and Control, pages 666–686.
  14. [18]Jiang, N., Krishnamurthy, A., Agarwal, A., Langford, J. and Schapire, R. E. (2017). Contextual decision processes with low Bellman rank are PAC-learnable. In Proceedings of the 34th International Conference on Machine Learning, pages 1704–1713.arxiv.org/abs/1610.09512
  15. [19]Jin, C., Allen-Zhu, Z., Bubeck, S. and Jordan, M. I. (2018). Is Q-learning provably efficient? In Advances in Neural Information Processing Systems, volume 31.
  16. [20]Jin, C., Yang, Z., Wang, Z. and Jordan, M. I. (2020). Probably efficient reinforcement learning with linear function approximation. In Proceedings of the 33rd Annual Conference on Learning Theory, pages 2137–2143.arxiv.org/abs/1907.05388
  17. [21]Kim, Y., Yang, I. and Jun, K.-S. (2022). Improved regret analysis for variance-adaptive linear bandits and horizon-free linear mixture MDPs. In Advances in Neural Information Processing Systems, volume 35, pages 1060–1072.arxiv.org/abs/2111.03289
  18. [22]Kirschner, J. and Krause, A. (2018). Information directed sampling and bandits with heteroscedastic noise. In Proceedings of the 31st Annual Conference on Learning Theory, pages 358–384.arxiv.org/abs/1801.09667
  19. [23]Lattimore, T. and Hutter, M. (2012). PAC bounds for discounted MDPs. In Proceedings of the 23rd International Conference on Algorithmic Learning Theory, pages 320–334.arxiv.org/abs/1202.3890
  20. [26]Modi, A., Jiang, N., Tewari, A. and Singh, S. (2020). Sample complexity of reinforcement learning using linearly combined model ensembles. In Proceedings of the 23rd International Conference on Artificial Intelligence and Statistics, pages 2010–2020.arxiv.org/abs/1910.10597
  21. [27]Wagenmaker, A. J., Chen, Y., Simchowitz, M., Du, S. S. and Jamieson, K. (2022). First-order regret in reinforcement learning with linear function approximation: A robust estimation approach. In Proceedings of the 39th International Conference on Machine Learning, pages 22384–22429.arxiv.org/abs/2112.03432
  22. [28]Wang, R., Du, S. S., Yang, L. F. and Kakade, S. M. (2020). Is long horizon RL more difficult than short horizon RL? In Advances in Neural Information Processing Systems, volume 33, pages 9075–9085.arxiv.org/abs/2005.00527
  23. [29]Wang, T., Zhou, D. and Gu, Q. (2021). Provably efficient reinforcement learning with linear function approximation under adaptivity constraints. In Advances in Neural Information Processing Systems, volume 34, pages 13524–13536.arxiv.org/abs/2101.02195
  24. [30]Yang, L. F. and Wang, M. (2019). Sample-optimal parametric Q-learning using linearly additive features. In Proceedings of the 36th International Conference on Machine Learning, pages 6995–7004.arxiv.org/abs/1902.04779
  25. [31]Zanette, A., Brandfonbrener, D., Brunskill, E., Pirotta, M. and Lazaric, A. (2020a). Frequentist regret bounds for randomized least-squares value iteration. In Proceedings of the 23rd International Conference on Artificial Intelligence and Statistics, pages 1954–1964.arxiv.org/abs/1911.00567
  26. [32]Zanette, A. and Brunskill, E. (2019). Tighter problem-dependent regret bounds in reinforcement learning without domain knowledge using value function bounds. In Proceedings of the 36th International Conference on Machine Learning, pages 7304–7312.arxiv.org/abs/1901.00210
  27. [33]Zanette, A., Lazaric, A., Kochenderfer, M. and Brunskill, E. (2020b). Learning near optimal policies with low inherent Bellman error. In Proceedings of the 37th International Conference on Machine Learning, pages 10978–10989.arxiv.org/abs/2003.00153
  28. [34]Zhang, Z., Ji, X. and Du, S. S. (2021a). Is reinforcement learning more difficult than bandits? A near-optimal algorithm escaping the curse of horizon. In Proceedings of the 34th Annual Conference on Learning Theory, pages 4528–4531.
  29. [35]Zhang, Z., Ji, X. and Du, S. S. (2022). Horizon-free reinforcement learning in polynomial time: The power of stationary policies. In Proceedings of the 35th Annual Conference on Learning Theory, pages 3858–3904.arxiv.org/abs/2203.12922
  30. [36]Zhang, Z., Lee, J. D., Chen, Y. and Du, S. S. (2024). Horizon-free regret for linear Markov decision processes. In Proceedings of the 12th International Conference on Learning Representations.arxiv.org/abs/2403.10738
  31. [37]Zhang, Z., Yang, J., Ji, X. and Du, S. S. (2021b). Improved variance-aware confidence sets for linear bandits and linear mixture MDP. In Advances in Neural Information Processing Systems, volume 34, pages 4342–4355.
  32. [38]Zhang, Z., Zhou, Y. and Ji, X. (2020). Almost optimal model-free reinforcement learning via reference-advantage decomposition. In Advances in Neural Information Processing Systems, volume 33, pages 15198–15207.
  33. [39]Zhao, H., He, J., Zhou, D., Zhang, T. and Gu, Q. (2023). Variance-dependent regret bounds for linear bandits and reinforcement learning: Adaptivity and computational efficiency. In Proceedings of the 36th Annual Conference on Learning Theory, pages 4977–5020.
  34. [40]Zhou, D. and Gu, Q. (2022). Computationally efficient horizon-free reinforcement learning for linear mixture MDPs. In Advances in Neural Information Processing Systems, volume 35, pages 36337–36349.
  35. [41]Zhou, D., Gu, Q. and Szepesvári, C. (2021a). Nearly minimax optimal reinforcement learning for linear mixture Markov decision processes. In Proceedings of the 34th Annual Conference on Learning Theory, pages 4532–4576.
  36. [43]Zhou, R., Zhang, Z. and Du, S. S. (2023). Sharp variance-dependent bounds in reinforcement learning: Best of both worlds in stochastic and deterministic environments. In Proceedings of the 40th International Conference on Machine Learning, pages 42878–42914.

Paper details

vlnc:W_pjsjnk3y
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 0

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Computer Science

Gemini 4 Argon (bare), Gemini 4 Carbon, GPT-6 Astra (bare)

View statement
Looking for related papers…
Contents