On the Analysis of Model-Free Methods for the Linear Quadratic Regulator

doi:10.1007/s40305-024-00546-z

Abstract

Abstract: Many reinforcement learning methods achieve great success in practice but lack theoretical foundation. In this paper, we study the convergence analysis of the model-free methods for the Linear Quadratic Regulator by treating the underlying system as a black box. The global linear convergence properties and sample complexities are established for several popular algorithms such as the temporal differences (TD)-learning method, the policy gradient algorithm, and the actor-critic (AC) algorithm. Our analysis shows that the actor-critic algorithm can reduce the sample complexity compared with the policy gradient algorithm. Although our analysis is still preliminary, it still explains the benefit of AC algorithm in a certain sense.

Key words: Linear Quadratic Regulator, TD-learning, The policy gradient algorithm, The actor-critic algorithm, Convergence

CLC Number:

Ze-Yu Jin, Johann Michael Schmitt, Zai-Wen Wen. On the Analysis of Model-Free Methods for the Linear Quadratic Regulator[J]. Journal of the Operations Research Society of China, 2026, 14(2): 364-396.

TrendMD

Add to citation manager EndNote|Reference Manager|ProCite|BibTeX|RefWorks

URL: https://www.jorsc.shu.edu.cn/EN/10.1007/s40305-024-00546-z

https://www.jorsc.shu.edu.cn/EN/Y2026/V14/I2/364

References

[1] Abbasi-Yadkori, Y., Szepesvári, C.: Regret bounds for the adaptive control of linear quadratic systems. In: Proceedings of the 24th Annual Conference on Learning Theory, pp. 1–26(2011)
[2] Bhandari, J., Russo, D., Singal, R.: A finite time analysis of temporal difference learning with linear function approximation. In: Conference on Learning Theory, pp. 1691–1692(2018)
[3] Bhatnagar, S., Precup, D., Silver, D., Sutton, R.S., Maei, H.R., Szepesvári, C.: Convergent temporaldifference learning with arbitrary smooth function approximation. In: Advances in Neural Information Processing Systems, pp. 1204–1212(2009)
[4] Borkar, V.S., Meyn, S.P.: The ode method for convergence of stochastic approximation and reinforcement learning. SIAM J. Control Optim. 38(2), 447–469(2000)
[5] Bradtke, S.J.: Reinforcement learning applied to linear quadratic regulation. In: Advances in Neural Information Processing Systems, pp. 295–302(1993)
[6] Bradtke, S.J., Barto, A.G.: Linear least-squares algorithms for temporal difference learning. Mach. Learn. 22(1–3), 33–57(1996)
[7] Dai, B., Shaw, A., Li, L., Xiao, L., He, N., Liu, Z., Chen, J., Song, L.: SBEED: convergent reinforcement learning with nonlinear function approximation. In: International Conference on Machine Learning, pp. 1125–1134(2018)
[8] Dean, S., Mania, H., Matni, N., Recht, B., Tu, S.: Regret bounds for robust adaptive control of the linear quadratic regulator. In: Advances in Neural Information Processing Systems, pp. 4188–4197(2018)
[9] Dean, Sarah, Mania, Horia, Matni, Nikolai, Recht, Benjamin, Stephen, Tu.: On the sample complexity of the linear quadratic regulator. Found. Comput. Math. 20(4), 633–679(2020)
[10] Faradonbeh, M.K.S., Tewari, A., Michailidis, G.: Randomized algorithms for data-driven stabilization of stochastic linear systems. In: 2019 IEEE Data Science Workshop, pp. 170–174(2019). https://doi. org/10.1109/DSW.2019.8755578
[11] Fazel, M., Ge, R., Kakade, S., Mesbahi, M.: Global convergence of policy gradient methods for the linear quadratic regulator. In: International Conference on Machine Learning, pp. 1467–1476(2018)
[12] Konda, V.R., Tsitsiklis, J.N.: Actor-critic algorithms. In: Advances in Neural Information Processing Systems, pp. 1008–1014(2000)
[13] Krauth, K., Tu, S., Recht, B.: Finite-time analysis of approximate policy iteration for the linear quadratic regulator. arXiv:1905.12842(2019)
[14] Lazaric, A., Ghavamzadeh, M., Munos, R.: Finite-sample analysis of LSTD (2010). http://researchers. lille.inria.fr/~munos/papers/files/lstd-icml2010.pdf
[15] Liu, B., Liu, J., Ghavamzadeh, M., Mahadevan, S., Petrik, M.: Finite-sample analysis of proximal gradient td algorithms. In: 31st Conference on Uncertainty in Artificial Intelligence, pp. 504–513. Citeseer (2015)
[16] Luo, Y., Yang, Z., Wang, Z., Kolar, M.: Natural actor-critic converges globally for hierarchical linear quadratic regulator. arXiv:1912.06875(2019)
[17] Malik, D., Pananjady, A., Bhatia, K., Khamaru, K., Bartlett, P., Wainwright, M.: Derivative-free methods for policy optimization: Guarantees for linear quadratic systems. In: The 22nd International Conference on Artificial Intelligence and Statistics, pp. 2916–2925(2019)
[18] Mnih, V., Kavukcuoglu, K., Silver, D., Rusu, A.A., Veness, J., Bellemare, M.G., Graves, A., Riedmiller, M., Fidjeland, A.K., Ostrovski, G., et al.: Human-level control through deep reinforcement learning. Nature 518(7540), 529(2015)
[19] Preiss, J.A., Arnold, S.M.R., Wei, C.-Y., Kloft, M.: Analyzing the variance of policy gradient estimators for the linear-quadratic regulator. arXiv:1910.01249(2019)
[20] Sutton, R.S., Maei, H.R., Precup, D., Bhatnagar, S., Silver, D., Szepesvári, C., Wiewiora, E.: Fast gradient-descent methods for temporal-difference learning with linear function approximation. In: Proceedings of the 26th Annual International Conference on Machine Learning, pp. 993–1000. ACM (2009)
[21] Sutton, R.S.: Learning to predict by the methods of temporal differences. Mach. Learn. 3(1), 9–44(1988)
[22] Sutton, R.S., Barto, A.G.: Reinforcement Learning: An Introduction. MIT Press, Cambridge (2018)
[23] Sutton, R.S., Mcallester, D., Singh, S., Mansour, Y.: Policy gradient methods for reinforcement learning with function approximation. Adv. Neural Inf. Process. Syst. 12, 1057–1063(1999)
[24] Todorov, E.: Optimal control theory. In: Bayesian Brain: Probabilistic Approaches to Neural Coding, pp. 268–298(2006)
[25] Tsitsiklis, J.N., Van Roy, B.: Analysis of temporal-difference learning with function approximation. In: Advances in Neural Information Processing Systems, pp. 1075–1081(1997)
[26] Tu, S., Recht, B.: Least-squares temporal difference learning for the linear quadratic regulator. In: International Conference on Machine Learning, pp. 5005–5014(2018)
[27] Watkins, C.J.C.H., Dayan, P.: Q-learning. Mach. Learn. 8(3–4), 279–292(1992)
[28] Williams, Ronald J.: Simple statistical gradient-following algorithms for connectionist reinforcement learning. Mach. Learn. 8(3–4), 229–256(1992)
[29] Yaghmaie, F.A., Gustafsson, F.: Using reinforcement learning for model-free linear quadratic control with process and measurement noises. In: 2019 IEEE 58th Conference on Decision and Control, pp. 6510–6517. IEEE (2019)
[30] Yang, Z., Chen, Y., Hong, M., Wang, Z.: Provably global convergence of actor-critic: a case for linear quadratic regulator with ergodic cost. Adv. Neural Inf. Process. Syst. 32, 796(2019)
[31] Zhang, K., Koppel, A., Zhu, H., Basar, T.: Global convergence of policy gradient methods to (almost) locally optimal policies. arXiv:1906.08383(2019)
[32] Zou, S., Xu, T., Liang, Y.: Finite-sample analysis for SARSA with linear function approximation. In: Advances in Neural Information Processing Systems, pp. 8668–8678(2019)