Efficient reinforcement learning

ABSTRACT

In this paper we propose a new formal model for studying reinforcement learning, based on Valiant's PAC framework. In our model the learner does not have direct access to every state of the environment. Instead, every sequence of experiments starts in a fixed initial state and the learner is provided with a “reset” operation that interrupts the current sequence of experiments and starts a new one (from the initial state). We do not require the agent to learn the optimal policy but only a good approximation of it with high probability. More precisely, we require the learner to produce a policy whose expected value from the initial state is &egr;-close to that of the optimal policy, with probability no less than 1−&dgr;. For this model, we describe an algorithm that produces such an (&egr;,&dgr;)-optimal policy for any environment, in time polynomial in N,K,1/&egr;,1/&dgr;,1/(1−&bgr;) and rmax, where N is the number of states of the environment, K is the maximum number of actions in a state, &bgr; is the discount factor and rmax is the maximum reward on any transition.

REFERENCES

• 1: A.G. Barto, R.S. Sutton, and C.W. Anderson. Neuronlike adaptive elements that can solve difficult learning control problems. IEEE Transactions on Systems, Man and Cybernetics, 13:834-846, 1983.
• 2: A.G. Barto, R.S. Sutton, and C. Watkins. Learning and sequential decision making. In M. Gabriel and J.W. Moore, editors, Learning and Computational Ncuroacie~cc. MIT Press, Cambridge, MA, 1990.
• 3: Peter Dayan, The Convergence of TD(λ) for General λ, Machine Learning, v.8 n.3-4, p.341-362, May 1992 [doi>10.1007/BF00992701]
• 4: J.J. Grefenstette. Credit assignment in rule discovery systems based on genetic algorithms. Machine Learning, 5:355-382, 1989.
• 5: John J. Grefenstette , Connie Loggia Ramsey, An approach to anytime learning, Proceedings of the ninth international workshop on Machine learning, p.189-195, July 1992, Aberdeen, Scotland, United Kingdom
• 6: Kenneth De Jong, Introduction, Machine Learning, v.5 n.4, p.351-353, Oct. 1990 [doi>10.1023/A:1022625623050]
• 7: D. Haussler, Quantifying inductive bias: AI learning algorithms and Valiant's learning framework, Artificial Intelligence, v.36 n.2, p.177-221, September 1988 [doi>10.1016/0004-3702(88)90002-1]
• 8: Wassily Hoeffding. Probability inequalities for sum of bounded random variables. Journal of the Amer. ican Statistical Association, 58(301), 1963.
• 9: J.H. Holland. Escaping brittleness: The possibilities of general-purpose learning algorithms applied to parallel rule-based systems. In R.S. Michalski, }.G. Carbonell, and T.M. Mitchell, editors, Machine Learning: An Artfcial Intelligence Approach (Volume II). Morgan Kaufmann, San Mateo, CA, 1986.
• 10: S. Koenig and R.G. Simmons. Complexity analysis of real-time reinforcement learning. In Proceedings of the Tenth International Conference on Machine Learning, pages 99-105. Morgan Kaufmann, 1993.
• 11: H. Mine and S. Osaki. Markovian Decision Processes. Modern Analytic and Computational Methods in Science and Mathematics. Elsevier, New York, NY, 1970.
• 12: Christos Papadimitriou , John N. Tsitsiklis, The complexity of Markov decision processes, Mathematics of Operations Research, v.12 n.3, p.441-450, August 1, 1987 [doi>10.1287/moor.12.3.441]
• 13: Leonard Pitt, Inductive Inference, DFAs, and Computational Complexity, Proceedings of the International Workshop on Analogical and Inductive Inference, p.18-44, October 01-06, 1989
• 14: Richard S. Sutton, Learning to Predict by the Methods of Temporal Differences, Machine Learning, v.3 n.1, p.9-44, August 1988 [doi>10.1023/A:1022633531479]
• 15: Gerald Tesauro, Temporal difference learning of backgammon strategy, Proceedings of the ninth international workshop on Machine learning, p.451-457, July 1992, Aberdeen, Scotland, United Kingdom
• 16: L. G. Valiant, A theory of the learnable, Communications of the ACM, v.27 n.11, p.1134-1142, Nov. 1984 [doi>10.1145/1968.1972]
• 17: C. Watkins. Learning From Delayed Rewards. PhD thesis, Cambridge University, Cambridge, MA, 1989.
• 18: Steven D. Whitehead , Dana H. Ballard, Learning to Perceive and Act by Trial and Error, Machine Learning, v.7 n.1, p.45-83, July 1991 [doi>10.1023/A:1022619109594]

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE

General Terms:
Algorithms, Theory, Verification