2019

Dynamic Programming Principles for Mean-Field Controls with Learning

Gu, Haotian, Guo, Xin, Wei, Xiaoli et al.

Understand

Dynamic programming principle (DPP) is fundamental for control and optimization, including Markov decision problems (MDPs), reinforcement learning (RL), and more recently mean-field controls (MFCs).

However, in the learning framework of MFCs, DPP has not been rigorously established, despite its critical importance for algorithm designs.
In this paper, we first present a simple example in MFCs with learning where DPP fails with a mis-specified Q function; and then propose the correct form of Q function in an appropriate space for MFCs with learning.
This particular form of Q function is different from the classical one and is called the IQ function.

Built on

Djete MF, Possamaï D, Tan X (2019) McKean-Vlasov optimal control: the dynamic programming principle. arXiv preprint arXiv:1907.08860
Original
1907
Earlier work this paper cites.
Carmona R, Laurière M, Tan Z (2019a) Linear-quadratic mean-field reinforcement learning: convergence of policy gradient methods. arXiv preprint arXiv:1910.04295
Original
1910
Earlier work this paper cites.
Carmona R, Laurière M, Tan Z (2019b) Model-free mean-field reinforcement learning: mean-field MDP and mean-field Q-learning. arXiv preprint arXiv:1910.12802
Original
1910
Earlier work this paper cites.
Motte M, Pham H (2019) Mean-field Markov decision processes with common noise and open-loop controls. To appear in Annals of Applied Probability, arXiv preprint arXiv:1912.07883
Original
1912
Earlier work this paper cites.
Bellman R (1957) A Markovian decision process. Journal of Mathematics and Mechanics 679–684
1957
Earlier work this paper cites.
McKean H (1969) Propagation of chaos for a class of non-linear parabolic equations. lecture series in differential equations 7. Stochastic Differential Equations 41–57
1969
Earlier work this paper cites.
Bertsekas DP, Shreve SE (1978) Stochastic optimal control, volume 139 of mathematics in science and engineering
1978
Earlier work this paper cites.
Watkins CJ (1989) Learning From Delayed Rewards. PhD thesis, King’s College, Cambridge
1989
Earlier work this paper cites.
Watkins CJ, Dayan P (1992) Q-learning. Machine Learning 8(3-4):279–292
1992
Earlier work this paper cites.
Bertsekas DP, Tsitsiklis JN (1996) Neuro-Dynamic Programming , volume 5 (Athena Scientific Belmont, MA)
1996
Earlier work this paper cites.
Dearden R, Friedman N, Russell S (1998) Bayesian Q-learning. AAAI/IAAI , 761–768
1998
Earlier work this paper cites.
Doya K (2000) Reinforcement learning in continuous time and space. Neural Computation 12(1):219–245
2000
Earlier work this paper cites.
Konda VR, Tsitsiklis JN (2000) Actor-critic algorithms. Advances in Neural Information Processing Systems , 1008–1014
2000
Earlier work this paper cites.
Doya K, Samejima K, Katagiri Ki, Kawato M (2002) Multiple model-based reinforcement learning. Neural computation 14(6):1347–1369
2002
Earlier work this paper cites.
Gibbs AL, Su FE (2002) On choosing and bounding probability metrics. International statistical review 70(3):419–435
2002
Earlier work this paper cites.
Even-Dar E, Mansour Y, Bartlett P (2003) Learning rates for Q-learning. Journal of machine learning Research 5(1)
2003
Earlier work this paper cites.

Similar

Fleming WH, Soner HM (2006) Controlled Markov processes and viscosity solutions , volume 25 (Springer Science & Business Media)
2006
Cited alongside, same era.
Huang M, Malhamé RP, Caines PE (2006) Large population stochastic dynamic games: closed-loop McKean-Vlasov systems and the Nash certainty equivalence principle. Communications in Information & Systems 6(3):221–252
2006
Cited alongside, same era.
Lasry JM, Lions PL (2007) Mean field games. Japanese Journal of Mathematics 2(1):229–260
2007
Cited alongside, same era.
Villani C (2009) Optimal transport: old and new , volume 338 (Springer)
2009
Cited alongside, same era.
Wunder M, Littman ML, Babes M (2010) Classes of multiagent Q-learning dynamics with epsilon-greedy exploration. Proceedings of the 27th International Conference on Machine Learning , 1167–1174 (Citeseer)
2010
Cited alongside, same era.
Andersson D, Djehiche B (2011) A maximum principle for SDEs of mean-field type. Applied Mathematics & Optimization 63(3):341–356
2011
Cited alongside, same era.
Buckdahn R, Djehiche B, Li J (2011) A general stochastic maximum principle for SDEs of mean-field type. Applied Mathematics & Optimization 64(2):197–216
2011
Cited alongside, same era.
Bensoussan A, Frehse J, Yam P (2013) Mean Field Games and Mean Field Type Control Theory , volume 101 (Springer)
2013
Cited alongside, same era.
El-Tantawy S, Abdulhai B, Abdelgawad H (2013) Multiagent reinforcement learning for integrated network of adaptive traffic signal controllers (MARLIN-ATSC): Methodology and large-scale application on downtown Toronto. IEEE Transactions on Intelligent Transportation Systems 14(3):1140–1150
2013
Cited alongside, same era.
Garnier J, Papanicolaou G, Yang TW (2013) Large deviations for a mean field model of systemic risk. SIAM Journal on Financial Mathematics 4(1):151–184
2013
Cited alongside, same era.
Mannor S, Tsitsiklis JN (2013) Algorithmic aspects of mean–variance optimization in Markov decision processes. European Journal of Operational Research 231(3):645–653
2013
Cited alongside, same era.
Laurière M, Pironneau O (2014) Dynamic programming for mean-field type control. Comptes Rendus Mathematique 352(9):707–713
2014
Cited alongside, same era.

Then

Mnih V, Kavukcuoglu K, Silver D, Rusu AA, Veness J, Bellemare MG, Graves A, Riedmiller M, Fidjeland AK, Ostrovski G, Petersen S, Beattie C, Sadik A, Antonoglou I, King H, Kumaran D, Wierstra D, Legg S, Hassabis D (2015) Human-level control through deep reinforcement learning. Nature 518(7540):529–533
2015
Later among the works it cites.
Pham H, Wei X (2016) Discrete time McKean–Vlasov control problem: a dynamic programming approach. Applied Mathematics & Optimization 74(3):487–506
2016
Later among the works it cites.
Shalev-Shwartz S, Shammah S, Shashua A (2016) Safe, multi-agent, reinforcement learning for autonomous driving. arXiv preprint arXiv:1610.03295
Original
2016
Later among the works it cites.
Silver D, Huang A, Maddison CJ, Guez A, Sifre L, Van Den Driessche G, Schrittwieser J, Antonoglou I, Panneershelvam V, Lanctot M (2016) Mastering the game of go with deep neural networks and tree search. Nature 529(7587):484
2016
Later among the works it cites.
Lacker D (2017) Limit theory for controlled McKean–Vlasov dynamics. SIAM Journal on Control and Optimization 55(3):1641–1672
2017
Later among the works it cites.
Nuño G (2017) Optimal social policies in mean field games. Applied Mathematics & Optimization 76(1):29–57
2017
Later among the works it cites.
Carmona R, Delarue F (2018) Probabilistic Theory of Mean Field Games with Applications I-II (Springer)
2018
Later among the works it cites.
Jin J, Song C, Li H, Gai K, Wang J, Zhang W (2018) Real-time bidding with multi-agent reinforcement learning in display advertising. Proceedings of the 27th ACM International Conference on Information and Knowledge Management , 2193–2201
2018
Later among the works it cites.
Sutton RS, Barto AG (2018) Reinforcement Learning: An Introduction (MIT press)
2018
Later among the works it cites.
Guo X, Hu A, Xu R, Zhang J (2019) Learning mean-field games. Advances in Neural Information Processing Systems , 4966–4976
2019
Closest in time.
Li M, Qin Z, Jiao Y, Yang Y, Wang J, Wang C, Wu G, Ye J (2019) Efficient ridesharing order dispatching with mean field multi-agent reinforcement learning. The World Wide Web Conference , 983–994
2019
Closest in time.
Vinyals O, Babuschkin I, Chung J, Mathieu M, Jaderberg M, Czarnecki WM, Dudzik A, Huang A, Georgiev P, Powell R (2019) Alphastar: Mastering the real-time strategy game starcraft II. DeepMind Blog 2
2019
Closest in time.
Aïd R, Basei M, Pham H (2020) A McKean–Vlasov approach to distributed electricity generation development. Mathematical Methods of Operations Research 91(2):269–310
2020
Closest in time.
Wang L, Yang Z, Wang Z (2020) Breaking the curse of many agents: Provable mean embedding Q-iteration for mean-field reinforcement learning. International Conference on Machine Learning , 10092–10103 (PMLR)
2020
Closest in time.
Gu H, Guo X, Wei X, Xu R (2021) Mean-field controls with Q-learning for cooperative MARL: convergence and complexity analysis. SIAM Journal on Mathematics of Data Science 3(4):1168–1196
2021
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…