Reinforcement Learning: A Tutorial Survey and Recent Advances

References

• Abounadi J., Bertsekas D., Borkar V. Learning algorithms for Markov decision processes with average cost. SIAM J. Control Optim. (2001) 40:681–698Crossref, Google Scholar
• Abounadi J., Bertsekas D., Borkar V. Stochastic approximations for non-expansive maps: Application to Q-learning algorithms. SIAM J. Control Optim. (2002) 41:1–22Crossref, Google Scholar
• Akar N., Sahin C., Burakowski W., Koch B., Beben A. Reinforcement learning as a means of dynamic aggregate QoS provisioning. Architectures for Quality of Service in the Internet (2003) 2698(Springer, Heidelberg, Germany) 100–114Lecture Notes in Computer ScienceCrossref, Google Scholar
• Arapostathis A., Borkar V., Fernandez-Gaucherand E., Ghosh M., Marcus S. Discrete-time controlled Markov processes with average cost criterion: A survey. SIAM J. Control Optim. (1993) 31:282–344Crossref, Google Scholar
• Baird L. Residual algorithms: Reinforcement learning with function approximation. Proc. 12th Internat. Conf. Machine Learn. (1995) (Morgan Kaufmann, San Francisco) 30–37Crossref, Google Scholar
• Barto A. G., Mahadevan S. Recent advances in hierarchical reinforcement learning. Discrete-Event Dynam. Systems: Theory Appl. (2003) 13:41–77Crossref, Google Scholar
• Barto A. G., Bradtke S. J., Singh S. P. Learning to act using real-time dynamic programming. Artificial Intelligence (1995) 72:81–138Crossref, Google Scholar
• Barto A. G., Sutton R. S., Anderson C. W. Neuronlike elements that can solve difficult learning control problems. IEEE Trans. Systems, Man, Cybernetics (1983) 13:835–846Google Scholar
• Baxter J., Bartlett P. Infinite-horizon policy-gradient estimation. J. Artificial Intelligence (2001) 15:319–350Crossref, Google Scholar
• Bellman R. The theory of dynamic programming. Bull. Amer. Math. Soc. (1954) 60:503–516Crossref, Google Scholar
• Bertsekas D.Dynamic Programming and Optimal Control (1995) (Athena Scientific, Nashua, NH) Google Scholar
• Bertsekas D., Tsitsiklis J.Neuro-Dynamic Programming (1996) (Athena Scientific, Nashua, NH) Google Scholar
• Bhatnagar S., Panigrahi J. R. Actor-critic algorithms for heirarchical Markov decision processes. Automatica (2006) 42:637–644Crossref, Google Scholar
• Borkar V. S. Stochastic approximation with two-time scales. Systems Control Lett. (1997) 29:291–294Crossref, Google Scholar
• Borkar V. S. Asynchronous stochastic approximation. SIAM J. Control Optim. (1998) 36:840–851Crossref, Google Scholar
• Borkar V. S. Q-learning for risk-sensitive control. Math. Oper. Res. (2002) 27:294–311Link, Google Scholar
• Borkar V. S., Meyn S. P. The ODE method for convergence of stochastic approximation and reinforcement learning. SIAM J. Control Optim. (2000) 38:447–469Crossref, Google Scholar
• Borkar V. S., Soumyanath K. A new analog parallel scheme for fixed point computation, Part I: Theory. IEEE Trans. Circuits Systems I: Theory Appl. (1997) 44:351–355Crossref, Google Scholar
• Boutilier C., Dean T., Hanks S. Decision-theoretic planning: Structural assumptions and computational leverage. J. Artificial Intelligence Res. (1999) 11:1–94Crossref, Google Scholar
• Bowling M., Veloso M. Multi-agent learning using a variable learning rate. Artificial Intelligence (2002) 136:215–250Crossref, Google Scholar
• Boyan J. A., Moore A. W., Touretzky D., Mozer M., Hasselmo M. Generalization in reinforcement learning: Safely approximating the value function. Advances in Neural Information Processing Systems (1995) (MIT Press, Cambridge, MA) 369–376Google Scholar
• Bradtke S., Barto A. Linear least-squares algorithms for temporal difference learning. Machine Learn. (1996) 22:33–57Crossref, Google Scholar
• Bradtke S. J., Duff M., Tesauro G., Touretzky D., Leen T. Reinforcement learning methods for continuous-time Markov decision problems. Advances in Neural Information Processing Systems (1995) 7(MIT Press, Cambridge, MA) 393–400Google Scholar
• Burke E. K., Kendall G., Soubeiga E. A tabu-search hyperheuristic for timetabling and rostering. J. Heuristics (2003a) 9:451–470Crossref, Google Scholar
• Burke E., Kendall G., Newall J., Hart E., Ross P., Schulenburg S., Glover F., Kochenberger G. Hyper-heuristics: An emerging direction in modern search technology. Handbook of Meta-heuristics (2003b) (Kluwer Academic Publishers, Boston) 457–474Chapter 16Crossref, Google Scholar
• Cao X.-R., Guo X. A unified approach to Markov decision problems and performance sensitivity analysis with discounted and average criteria. Automatica (2004) 40:1749–1759Crossref, Google Scholar
• Chapman D., Kaelbling L. Input generalization in delayed reinforcement learning. Proc. 12th Internat. Joint Conf. Artificial Intelligence (1991) (Morgan Kaufmann, San Francisco) 726–731Google Scholar
• Crites R., Barto A. Improving elevator performance using reinforcement learning. Proc. Adv. Neural Information Processing Systems (1995) (MIT Press, Cambridge, MA) 1017–1023Google Scholar
• Dai J., Meyn S. P. Stability and convergence of moments for multiclass queuing networks via fluid limits. IEEE Trans. Automatic Control (1995) 40:1889–1904Crossref, Google Scholar
• Darken C., Chang J., Moody J., White D. A., Sofge D. A. Learning rate schedules for faster stochastic gradient search. Neural Networks for Signal Processing 2—Proc. 1992 IEEE Workshop (1992) (IEEE Press, Piscataway, NJ) Crossref, Google Scholar
• Das T. K., Gosavi A., Mahadevan S., Marchalleck N. Solving semi-Markov decision problems using average reward reinforcement learning. Management Sci. (1999) 45:560–574Link, Google Scholar
• Dayan P. The convergence of TD(λ) for general λ. Machine Learn. (1992) 8:341–362Crossref, Google Scholar
• Dean T., Kanazawa K. A model for reasoning about persistence and causation. Computational Intelligence (1989) 5:142–150Crossref, Google Scholar
• Defarias D. P., van Roy B. The linear programming approach to approximate dynamic programming. Oper. Res. (2003) 51:850–865Link, Google Scholar
• Dietterich T. Hierarchical reinforcement learning with the MAXQ value function decomposition. J. Artificial Intelligence Res. (2000) 13:227–303Crossref, Google Scholar
• Evan-Dar E., Mansour Y. Learning rates for Q-learning. J. Machine Learn. Res. (2003) 5:1–25Google Scholar
• Forestier J., Varaiya P. Multilayer control of large Markov chains. IEEE Trans. Automatic Control (1978) 23:298–304Crossref, Google Scholar
• Geibel P., Wysotzki F. Risk-sensitive reinforcement learning applied to control under constraints. J. Artificial Intelligence Res. (2005) 24:81–108Crossref, Google Scholar
• Givan R., Leach S., Dean T. Bounded parameter Markov decision processes. Artificial Intelligence (2000) 122:71–109Crossref, Google Scholar
• Gordon G. Stable function approximation in dynamic programming. (1995) . Technical Report CMU-CS-95-103, Carnegie Mellon University, PittsburghGoogle Scholar
• Gosavi A.Simulation-Based Optimization: Parametric Optimization Techniques and Reinforcement Learning (2003) (Kluwer Academic Publishers, Boston) Crossref, Google Scholar
• Gosavi A. A reinforcement learning algorithm based on policy iteration for average reward: Empirical results with yield management and convergence analysis. Machine Learn. (2004a) 55:5–29Crossref, Google Scholar
• Gosavi A. Reinforcement learning for long-run average cost. Eur. J. Oper. Res. (2004b) 155:654–674Crossref, Google Scholar
• Gosavi A. Boundedness of iterates in Q-learning. Systems Control Lett. (2006) 55:347–349Crossref, Google Scholar
• Gosavi A., Bandla N., Das T. K. A reinforcement learning approach to a single leg airline revenue management problem with multiple fare classes and overbooking. IIE Trans. (2002) 34:729–742Crossref, Google Scholar
• Gosavi A., Das T. K., Sarkar S. A simulation-based learning automata framework for solving semi-Markov decision problems. IIE Trans. (2004) 36:1–11Crossref, Google Scholar
• Grinstead C. M., Snell J. L.Introduction to Probability (1997) (American Mathematical Society, Providence, RI) Google Scholar
• Hastie T., Tibshirani R., Friedman J.The Elements of Statistical Learning (2001) (Springer, New York) Crossref, Google Scholar
• Hauskrecht M. Value-function approximations for partially observable Markov decision processes. J. Artificial Intelligence Res. (2000) 13:33–94Crossref, Google Scholar
• Hirsch M. Convergent activation dynamics in continuous time networks. Neural Networks (1989) 2:331–349Crossref, Google Scholar
• Howard R.Dynamic Programming and Markov Processes (1960) (MIT Press, Cambridge, MA) Google Scholar
• Hu J., Wellman M. P. Nash Q-learning for general-sum stochastic games. J. Machine Learn. Res. (2003) 4:1039–1069Google Scholar
• Jaakola T., Jordan M., Singh S. P. On the convergence of stochastic iterative dynamic programming algorithms. Neural Comput. (1994) 6:1185–1201Crossref, Google Scholar
• Kaelbling L. P., Littman M. L., Cassandra A. R. Planning and acting in partially observable stochastic domains. Artificial Intelligence (1999) 101:99–134Crossref, Google Scholar
• Kaelbling L. P., Littman M. L., Moore A. W. Reinforcement learning: A survey. J. Artificial Intelligence Res. (1996) 4:237–285Crossref, Google Scholar
• Kearns M., Singh S. P. Near-optimal reinforcement learning in polynomial time. Machine Learn. (2002) 49:209–232Crossref, Google Scholar
• Keerthi S., Ravindran B. A tutorial survey of reinforcement learning. Sadhana (1994) 19:851–889Crossref, Google Scholar
• Kimura H., Miyazaki K., Kobayashi S. Reinforcement learning in POMDPs with function approximation. Proc. 14th Internat. Conf. Machine Learn. (1997) (Morgan Kaufmann, San Francisco) 152–160Google Scholar
• Kimura H., Yamamura M., Kobayashi S. Reinforcement learning by stochastic hill climbing on discounted reward. Proc. 12th Internat. Conf. Machine Learn. (1995) Tahoe City, CA(Morgan Kaufmann, San Francisco) 295–303Crossref, Google Scholar
• Konda V. R., Tsitsiklis J. Actor-critic algorithms. Neural Information Processing Systems 12 (2000) (MIT Press, Cambridge, MA) 1008–1014Google Scholar
• Konda V. R., Borkar V. S. Actor-critic type learning algorithms for Markov decision processes. SIAM J. Control Optim. (1999) 38:94–123Crossref, Google Scholar
• Kushner H. J., Clark D. S.Stochastic Approximation Methods for Constrained and Unconstrained Systems (1978) (Springer-Verlag, New York) Crossref, Google Scholar
• Lin Z., Bean J., White C. C. A hybrid genetic/optimization algorithm for finite horizon, partially observed Markov decision process. INFORMS J. Comput. (2004) 16:27–38Link, Google Scholar
• Littman M., Cohen W. W., Hirsch H. Markov games as a framework for multi-agent reinforcement learning. Proc. 11th Internat. Conf. Machine Learn. (1994) New Brunswick, NJ(Morgan Kaufmann, San Francisco) 157–163Crossref, Google Scholar
• Littman M., Brodley C. E., Danyluk A. P. Friend or foe Q-learning in general-sum games. Proc. 18th Internat. Conf. Machine Learn. (2001) Williamston, MA(Morgan Kaufmann, San Francisco) 322–328Google Scholar
• Lovejoy W. A survey of algorithmic methods for partially observable Markov decision processes. Ann. Oper. Res. (1991) 28:47–66Crossref, Google Scholar
• Luce D.Individual Choice Behavior (1959) (John Wiley & Sons, New York) Google Scholar
• Mahadevan S. Average reward reinforcement learning: Foundations, algorithms, and empirical results. Machine Learn. (1996) 22:159–95Crossref, Google Scholar
• Mahadevan S., Maggioni M. Value function approximation using diffusion wavelets and Laplacian eigenfunction. Neural Information Processing Systems (2006) (MIT Press, Cambridge, MA) Google Scholar
• Makar R., Mahadevan S., Ghavamzadeh M. Hierarchical multi-agent reinforcement learning. Proc. 5th Internat. Conf. Autonomous Agents (2001) Montréal(ACM, New York) 246–253Crossref, Google Scholar
• Marbach P., Tsitsiklis J. Simulation-based optimization of Markov reward processes: Implementation issues. Proc. 38th IEEE Conf. Decision and Control (1999) Phoenix, AZ(IEEE, Washington, D.C.) 1769–1774Crossref, Google Scholar
• Monahan G. A survey of partially observable Markov decision processes: Theory, models, and algorithms. Management Sci. (1982) 28:1–16Link, Google Scholar
• Murthy S., Kasif S., Salzberg S. A system for induction of oblique decision trees. J. Artificial Intelligence Res. (1994) 2:1–33Crossref, Google Scholar
• Narendra K. S., Thathachar M. A. L.Learning Automata: An Introduction (1989) (Prentice Hall, Englewood Cliffs, NJ) Google Scholar
• Nareyek A., Resende M. G., de Sousa J. P. Choosing search heuristics by non-stationary reinforcement learning. Metaheuristics: Computer Decision-Making (2003) (Kluwer Academic Publishers, Dordrecht, The Netherlands) 523–544Crossref, Google Scholar
• Ng A., Jordan M., Boutilier C., Goldszmidt M. PEGASUS: A policy search method for large MDPs and POMDPs. Proc. 16th Conf. Uncertainty in Artificial Intelligence (2000) (Morgan Kaufmann, San Mateo, CA) 406–415Google Scholar
• Ormoneit D., Sen S. Kernel-based reinforcement learning. Machine Learn. (2002) 49:161–178Crossref, Google Scholar
• Parr R. Hierarchical control and learning for Markov decision processes. (1998) . Unpublished Ph.D. dissertation, University of California, Berkeley, BerkeleyGoogle Scholar
• Parr R., Russell S. Reinforcement learning with hierarchies of machines. Neural Information Processing Systems (1998) (MIT Press, Cambridge, MA) 1043–1049Google Scholar
• Peng J., Williams R. J. Efficient learning and planning with the dyna framework. Adapt. Behav. (1993) 1:437–454Crossref, Google Scholar
• Pepyne D. L., Looze D. P., Cassandras C. G., Djaferis T. E. Application of Q-learning to elevator dispatching. Proc. 13th Internat. Federation Automatic Control World Congress (1996) San Francisco(Pergamon, San Francisco) Google Scholar
• Peshkin L. Reinforcement learning by policy search. (2001) . Ph.D. thesis, MIT, Cambridge, MAGoogle Scholar
• Pontrandolfo P., Gosavi A., Okogbaa O. G., Das T. K. Global supply chain management: A reinforcement learning approach. Internat. J. Production Res. (2002) 40:1299–1317Crossref, Google Scholar
• Poznyak A. S., Najim K.Learning Automata and Stochastic Optimization (1997) 225(Springer-Verlag, London) Lecture Notes in Control and Information SciencesGoogle Scholar
• Puterman M. L.Markov Decision Processes (1994) (Wiley Interscience, New York) Crossref, Google Scholar
• Pyeatt L., Howe A. Decision tree function approximation in reinforcement learning. (1998) . Technical Report CS-98-112, Colorado State University, Fort Collins, COGoogle Scholar
• Quinlan J. Induction of decision trees. Machine Learn. (1986) 1:81–106Crossref, Google Scholar
• Ravulapati K. K., Rao J., Das T. K. A reinforcement learning approach to stochastic business games. IIE Trans. (2004) 36:373–385Crossref, Google Scholar
• Robbins H., Monro S. A stochastic approximation method. Ann. Math. Statist. (1951) 22:400–407Crossref, Google Scholar
• Rummery G. A., Niranjan M. On-line Q-learning using connectionist systems. (1994) . Technical Report CUED/F-INFENG/TR 166, Cambridge University, Cambridge, UKGoogle Scholar
• Satia J. K., Lave R. E. Markovian decision processes with uncertain transition probabilities. Oper. Res. (1973) 21:728–740Link, Google Scholar
• Sato M., Abe K., Takeda H., Touretsky D. S., Elman J. L., Sejnowski T. J. Learning control of finite Markov chains with explicit trade-off between estimation and control. Connectionist Models: Proc. 1990 Summer School (1990) (Morgan Kaufmann, San Francisco) 287–300Google Scholar
• Schuurmans D., Patrascu R. Direct value-approximation for factored MDPs. Neural Information Processing Systems (2001) 14(MIT Press, Cambridge, MA) 1579–1586Google Scholar
• Schwartz A. A reinforcement learning method for maximizing undiscounted rewards. Proc. 10th Ann. Conf. Machine Learn. (1993) (Morgan Kaufmann, San Francisco) 298–305Crossref, Google Scholar
• Singh S. P. Reinforcement learning algorithms for average-payoff Markovian decision processes. Proc. 12th AAAI (1994) (MIT Press, Cambridge, MA) 700–705Google Scholar
• Singh S. P., Bertsekas D. Reinforcement learning for dynamic channel allocation in cellular telephone systems. Adv. Neural Inform. Processing Systems (1997) 9:974–980Google Scholar
• Singh S. P., Sutton R. S. Reinforcement learning with replacing eligibility traces. Machine Learn. (1996) 22:123–158Crossref, Google Scholar
• Singh S. P., Yee R. An upper bound on the loss from approximate optimal value functions. Machine Learn. (1994) 16:227–233Crossref, Google Scholar
• Singh S. S., Tadic V., Doucet A. A policy-gradient method for semi-Markov decision processes with application to call admission control. Eur. J. Oper. Res. (2007) 178:808–818Crossref, Google Scholar
• Smallwood R. D., Sondik E. J. The optimal control of partially observable Markov processes over a finite horizon. Oper. Res. (1973) 21:1071–1088Link, Google Scholar
• Smart W., Kaelbling L. Practical reinforcement learning in continuous spaces. Proc. 17th Internat. Conf. Machine Learn. (2000) Stanford, CA(Morgan Kaufmann, San Francisco) 903–910Google Scholar
• Sondik E. The optimal control of partially observable Markov processes over the infinite horizon: Discounted costs. Oper. Res. (1978) 26:282–304Link, Google Scholar
• Sutton R. S. Temporal credit assignment in reinforcement learning. (1984) . Unpublished Ph.D. dissertation, University of Massachusetts, AmherstGoogle Scholar
• Sutton R. S. Integrated architectures for learning, planning, and reacting based on approximating dynamic programming. Proc. 7th Internat. Conf. Machine Learn. (1990) Austin, TX(Morgan Kaufmann, San Francisco) 216–224Crossref, Google Scholar
• Sutton R. S. Reinforcement learning. Machine Learn. (1992) 8:225–227Crossref, Google Scholar
• Sutton R. S. Generalization in reinforcement learning: Successful examples using sparse coarse coding. Neural Information Processing Systems (1996) 8(MIT Press, Cambridge, MA) 1038–1044Google Scholar
• Sutton R., Barto A. G.Reinforcement Learning: An Introduction (1998) (MIT Press, Cambridge, MA) Google Scholar
• Sutton R., Precup D., Singh S. P. Between MDPs and semi-MDPs: A framework for temporal abstraction in reinforcement learning. Artificial Intelligence (1998) 112:181–211Crossref, Google Scholar
• Sutton R., McAllester D., Singh S. P., Mansour Y. Policy gradient methods for reinforcement learning with function approximation. Proc. Adv. Neural Information Processing Systems (2000) (MIT Press, Cambridge, MA) 1057–1063Google Scholar
• Szita I., Takacs B., Lorincz A. ϵ-MDPs: Learning in varying environments. J. Machine Learn. Res. (2002) 3:145–174Google Scholar
• Tadepalli P., Ok D. Model-based average reward reinforcement learning algorithms. Artificial Intelligence (1998) 100:177–224Crossref, Google Scholar
• Tesauro G. Practical issues in temporal difference learning. Machine Learn. (1992) 8:257–277Crossref, Google Scholar
• Tezcan T., Gosavi A. Optimal buffer allocation in production lines using an automata search. Proc. Inst. Indust. Engrg. Conf. (2001) Dallas(Institute of Industrial Engineers, Norwell, GA) Google Scholar
• Thathachar M. A. L., Sastry P. S. Learning optimal discriminant functions through a cooperative game of automata. IEEE Trans. Systems, Man, Cybernetics (1987) 17:73–85Crossref, Google Scholar
• Thrun S., Moller K. Active exploration in dynamic environments. Advances in Neural Information Processing Systems (1992) (Morgan Kaufmann, San Francisco) 531–538Google Scholar
• Tsitsiklis J. N. Asynchronous stochastic approximation and Q-learning. Machine Learn. (1994) 16:185–202Crossref, Google Scholar
• Tsitsiklis J. N., van Roy B. Feature-based methods for large-scale dynamic programming. Machine Learn. (1996) 22:59–94Crossref, Google Scholar
• Tsitsiklis J. N., van Roy B. An analysis of temporal-difference learning with function approximation. IEEE Trans. Automatic Control (1997) 42:674–690Crossref, Google Scholar
• van Nunen J. A. E. E. A set of successive approximation methods for discounted Markovian decision problems. Z. Oper. Res. (1976) 20:203–208Google Scholar
• van Roy B., Bertsekas D. P., Lee Y., Tsitsiklis J. N. A neuro-dynamic programming approach to retailer inventory management. Proc. IEEE Conf. Decision and Control (1997) San Diego(IEEE, Washington, D.C.) 4052–4057Crossref, Google Scholar
• Watkins C. J. Learning from delayed rewards. (1989) . Ph.D. thesis, Kings College, Cambridge, UKGoogle Scholar
• Werbös P. J. Building and understanding adaptive systems: A statistical/numerical approach to factory automation and brain research. IEEE Trans. Systems, Man, Cybernetics (1987) 17:7–20Crossref, Google Scholar
• Werbös P. J., White D. A., Sofge D. A. Approximate dynamic programming for real-time control and neural modeling. Handbook of Intelligent Control: Neural, Fuzzy, and Adaptive Approaches (1992) (Van Nostrand, NY) 493–525Google Scholar
• Wheeler R. M., Narendra K. S. Decentralized learning in finite Markov chains. IEEE Trans. Automatic Control (1986) 31:373–376Crossref, Google Scholar
• White D. J. Real applications of Markov decision processes. Interfaces (1985) 15:73–83Link, Google Scholar
• White C. C., Eldeib H. K. Markov decision processes with imprecise transition probabilities. Oper. Res. (1994) 42:739–749Link, Google Scholar
• White C. C., Scherer W. T. Solution procedures for partially observed Markov decision processes. Oper. Res. (1989) 37:791–797Link, Google Scholar
• Whitehead S. A study of cooperative mechanisms for faster reinforcement learning. (1991) . Technical Report 365, Computer Science Department, University of Rochester, Rochester, NYGoogle Scholar
• Whiteson S., Stone P. Evolutionary function approximation for reinforcement learning. J. Machine Learn. Res. (2006) 7:877–917Google Scholar
• Williams R. Simple statistical gradient following algorithms for connectionist reinforcement learning. Machine Learn. (1992) 8:229–256Crossref, Google Scholar
• Williams R., Baird L. Analysis of some incremental variants of policy iteration: First steps toward understanding actor-critic learning systems. (1993) . Technical Report NU-CCS-93-11, College of Computer Science, Northeastern University, BostonGoogle Scholar
• Witten I. H. An adaptive optimal controller for discrete time Markov environments. Inform. Control (1977) 34:286–295Crossref, Google Scholar
• Zhang W., Dietterich T. A reinforcement learning approach to job-shop scheduling. Proc. 14th Internat. Joint Conf. Artificial Intelligence (1995) (Morgan Kaufmann, San Francisco) 1114–1120Google Scholar