2017

Learning-based Control of Unknown Linear Systems with Thompson Sampling

Ouyang, Yi, Gagrani, Mukul, Jain, Rahul

Understand

We propose a Thompson sampling-based learning algorithm for the Linear Quadratic (LQ) control problem with unknown system parameters.

The algorithm is called Thompson sampling with dynamic episodes (TSDE) where two stopping criteria determine the lengths of the dynamic episodes in Thompson sampling.
The first stopping criterion controls the growth rate of episode length.
The second stopping criterion is triggered when the determinant of the sample covariance matrix is less than half of the previous value.

Built on

W. R. Thompson, “On the likelihood that one unknown probability exceeds another in view of the evidence of two samples,” Biometrika
1933
Earlier work this paper cites.
J. Sternby, “On consistency for the method of least squares using martingale theory,” IEEE Transactions on Automatic Control
1977
Earlier work this paper cites.
A. Becker, P. Kumar, and C.-Z. Wei, “Adaptive control with the stochastic approximation algorithm: Geometry and convergence,” IEEE Transactions on Automatic Control
1985
Earlier work this paper cites.
T. L. Lai and H. Robbins, “Asymptotically efficient adaptive allocation rules,” Advances in applied mathematics
1985
Earlier work this paper cites.
H.-F. Chen and L. Guo, “Convergence rate of least-squares identification and adaptive control for stochastic systems,” International Journal of Control
1986
Earlier work this paper cites.
Prentice-Hall, Inc., 1989
S. Sastry and M. Bodson, Adaptive control: stability, convergence, and robustness · 1989
Earlier work this paper cites.
Prentice-Hall, Inc., 1989
K. Narendra and A. Annaswamy, Stable adaptive systems · 1989
Earlier work this paper cites.
Addison-Wesley Longman Publishing Co., Inc., 1994
K. J. Astrom and B. Wittenmark, Adaptive Control · 1994
Earlier work this paper cites.
L. Guo, “Self-convergence of weighted least-squares with applications to stochastic adaptive control,” IEEE Transactions on Automatic Control
1996
Earlier work this paper cites.
M. C. Campi and P. Kumar, “Adaptive linear quadratic gaussian control: the cost-biased approach revisited,” SIAM Journal on Control and Optimization
1998
Earlier work this paper cites.

Similar

Cambridge university press, 2006
N. Cesa-Bianchi and G. Lugosi, Prediction, learning, and games · 2006
Cited alongside, same era.
V. Dani, T. P. Hayes, and S. M. Kakade, “Stochastic linear optimization under bandit feedback.,” in COLT
2008
Cited alongside, same era.
S. L. Scott, “A modern bayesian look at the multi-armed bandit,” Applied Stochastic Models in Business and Industry
2010
Cited alongside, same era.
Y. Abbasi-Yadkori and C. Szepesvári, “Regret bounds for the adaptive control of linear quadratic systems,” in Proceedings of the 24th Annual Conference on Learning Theory
2011
Cited alongside, same era.
O. Chapelle and L. Li, “An empirical evaluation of thompson sampling,” in NIPS
2011
Cited alongside, same era.
M. Ibrahimi, A. Javanmard, and B. V. Roy, “Efficient reinforcement learning for high dimensional linear quadratic systems,” in Advances in Neural Information Processing Systems (NIPS)
2012
Cited alongside, same era.
S. Agrawal and N. Goyal, “Analysis of thompson sampling for the multi-armed bandit problem,” in Conference on Learning Theory
2012
Cited alongside, same era.
E. Kaufmann, N. Korda, and R. Munos, “Thompson sampling: An asymptotically optimal finite-time analysis,” in International Conference on Algorithmic Learning Theory
2012
Cited alongside, same era.
S. Agrawal and N. Goyal, “Thompson sampling for contextual bandits with linear payoffs.,” in ICML (3)
2013
Cited alongside, same era.
I. Osband, D. Russo, and B. Van Roy, “(More) efficient reinforcement learning via posterior sampling,” in NIPS
2013
Cited alongside, same era.
available at: www.cs.cmu.edu/ gautamd/Files/maxGaussians.pdf
Original
G. Dasarathy, “A simple probability trick for bounding the expected maximum of n random variables,”
Cited in the paper.

Then

Courier Corporation, 2014
G. C. Goodwin and K. S. Sin, Adaptive filtering prediction and control · 2014
Later among the works it cites.
D. Russo and B. Van Roy, “Learning to optimize via posterior sampling,” Mathematics of Operations Research
2014
Later among the works it cites.
SIAM Classics, 2015
P. R. Kumar and P. Varaiya, Stochastic systems: Estimation, identification, and adaptive control · 2015
Later among the works it cites.
Y. Abbasi-Yadkori and C. Szepesvári, “Bayesian optimal control of smoothly parameterized systems.,” in UAI
2015
Later among the works it cites.
A. Gopalan and S. Mannor, “Thompson sampling for learning parameterized markov decision processes,” in COLT
2015
Later among the works it cites.
I. Osband and B. Van Roy, “Posterior sampling for reinforcement learning without episodes,” arXiv preprint arXiv:1608.02731
Original
2016
Later among the works it cites.
D. Russo, B. Van Roy, A. Kazerouni, and I. Osband, “A tutorial on thompson sampling,” arXiv preprint arXiv:1707.02038
Original
2017
Closest in time.
M. Abeille and A. Lazaric, “Thompson sampling for linear-quadratic control problems,” arXiv preprint arXiv:1703.08972
Original
2017
Closest in time.
M. J. Kim, “Thompson sampling for stochastic control: The finite parameter case,” IEEE Transactions on Automatic Control
2017
Closest in time.

Beyond the bibliography

alphaXiv searches the wider corpus for related work and actual follow-ups.

Open on alphaXiv

alphaXiv is searching for related work…

Reading the bibliography…