References
- R. Bellman, Dynamic programming, Science 153(3731) (1966), pp. 34–37. doi: 10.1126/science.153.3731.34
- D.P. Bertsekas, D.P. Bertsekas, D.P. Bertsekas, and D.P. Bertsekas, Dynamic Programming and Optimal Control, Vol. 1, Athena Scientific, Belmont, MA, 1995.
- C. Derman, Finite State Markov Decision Processes, Academic Press, New York, 1970.
- J. Fearnley, Exponential lower bounds for policy iteration, in Proceedings of the Thirty-Seventh International Colloquium on Automata, Languages, and Programming, Springer, 2010, pp. 551–562.
- J. Filar and K. Vrieze, Competitive Markov Decision Processes, Springer Science & Business Media, New York, 2012.
- O. Friedmann, An exponential lower bound for the parity game strategy improvement algorithm as we know it, in Proceedings of the Twenty-Fourth Annual IEEE Symposium on Logic in Computer Science (LICS 2009), IEEE Computer Society Press, 2009, pp. 145–156.
- T.D. Hansen, P.B. Miltersen, and U. Zwick, Strategy iteration is strongly polynomial for 2-player turn-based stochastic games with a constant discount factor, J. ACM 60(1) (2013), pp. 1:1–1:16. ISSN 0004-5411. doi: 10.1145/2432622.2432623
- R.A Howard, Dynamic Programming and Markov Processes, MIT Press, Cambridge, 1960.
- M. Jurdziński and R. Savani, A simple p-matrix linear complementarity problem for discounted games, in Logic and Theory of Algorithms, A. Beckmann, C. Dimitracopoulos, and B. Löwe, eds., Springer, Berlin, 2008, pp. 283–293. ISBN 978-3-540-69407-6.
- A. Neyman, S. Sorin, and S. Sorin, Stochastic Games and Applications, Vol. 570, Springer Science & Business Media, New York, 2003.
- I. Post and Y. Ye, The simplex method is strongly polynomial for deterministic Markov decision processes, Proceedings of the Twenty-Fourth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA'13, Philadelphia, PA, 2013. Society for Industrial and Applied Mathematics, pp. 1465–1473. ISBN 978-1-611972-51-1.
- M.L. Puterman, Markov Decision Processes: Discrete Stochastic Dynamic Programming, John Wiley & Sons, New York, 2014.
- S.S. Rao, R. Chandrasekaran, and K.P.K. Nair, Algorithms for discounted stochastic games, J. Optim. Theory Appl. 11(6) (1973), pp. 627–637. doi: 10.1007/BF00935562
- B. Scherrer, Improved and generalized upper bounds on the complexity of policy iteration, in Proceedings of the Twenty-Seventh Conference on Advances in Neural Information Processing Systems, 2013, pp. 386–394.
- L.S. Shapley, Stochastic games, Proc. Natl. Acad. Sci. USA 39(10) (1953), pp. 1095–1100. doi: 10.1073/pnas.39.10.1953
- D. Silver, A. Huang, C. J. Maddison, A. Guez, L. Sifre, G. van den Driessche, J. Schrittwieser, I. Antonoglou, V. Panneershelvam, M. Lanctot, S. Dieleman, D. Grewe, J. Nham, N. Kalchbrenner, I. Sutskever, T. Lillicrap, M. Leach, K. Kavukcuoglu, T. Graepel, and D. Hassabis, Mastering the game of go with deep neural networks and tree search, Nature 529(7587) (2016), pp. 484–489. doi: 10.1038/nature16961
- Y. Ye, A new complexity result on solving the Markov decision problem, Math. Oper. Res. 30(3) (2005), pp. 733–749. doi: 10.1287/moor.1050.0149
- Y. Ye, The simplex and policy-iteration methods are strongly polynomial for the Markov decision problem with a fixed discount rate, Math. Oper. Res. 36(4) (2011), pp. 593–603. ISSN 0364765X, 15265471. doi: 10.1287/moor.1110.0516