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

Expand
  • 1 School of Mathematical Sciences, Peking University, Beijing 100871, China;
    2 Beijing International Center for Mathematical Research, Peking University, Beijing 100871, China

Received date: 2023-02-14

  Revised date: 2024-03-24

  Online published: 2026-07-06

Supported by

This work was supported in part by the National Natural Science Foundation of China (No.12331010).

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.

Cite this article

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 . DOI: 10.1007/s40305-024-00546-z

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)
Options
Outlines

/