Reinforcement learning in the presence of rare events

ABSTRACT

We consider the task of reinforcement learning in an environment in which rare significant events occur independently of the actions selected by the controlling agent. If these events are sampled according to their natural probability of occurring, convergence of conventional reinforcement learning algorithms is likely to be slow, and the learning algorithms may exhibit high variance. In this work, we assume that we have access to a simulator, in which the rare event probabilities can be artificially altered. Then, importance sampling can be used to learn with this simulation data. We introduce algorithms for policy evaluation, using both tabular and function approximation representations of the value function. We prove that in both cases, the reinforcement learning algorithms converge. In the tabular case, we also analyze the bias and variance of our approach compared to TD-learning. We evaluate empirically the performance of the algorithm on random Markov Decision Processes, as well as on a large network planning task.

REFERENCES

• 1: T. P. I. Ahamed , V. S. Borkar , S. Juneja, Adaptive Importance Sampling Technique for Markov Chains Using Stochastic Approximation, Operations Research, v.54 n.3, p.489-504, May-June 2006 [doi>10.1287/opre.1060.0291]
• 2: Asmussen, S. & Glynn, P. (2007). Stochastic Simulation: Algorithms and Analysis. Springer.
• 3: Baxter, J. & Bartlett, P. (2001). Infinite-horizon policy-gradient estimation. Journal of Artificial Intelligence Research, 15, 319--350.
• 4: Dimitri P. Bertsekas , John N. Tsitsiklis, Neuro-Dynamic Programming, Athena Scientific, 1996
• 5: Shalabh Bhatnagar , Vivek S. Borkar , Madhukar Akarapu, A Simulation-Based Algorithm for Ergodic Control of Markov Chains Conditioned on Rare Events, The Journal of Machine Learning Research, 7, p.1937-1962, 12/1/2006
• 6: Bucklew, J. (2004). Introduction to Rare Event Simulation. Springer.
• 7: Shie Mannor , Duncan Simester , Peng Sun , John N. Tsitsiklis, Bias and Variance Approximation in Value Function Estimates, Management Science, v.53 n.2, p.308-322, February 2007 [doi>10.1287/mnsc.1060.0614]
• 8: Doina Precup , Richard S. Sutton , Sanjoy Dasgupta, Off-Policy Temporal Difference Learning with Function Approximation, Proceedings of the Eighteenth International Conference on Machine Learning, p.417-424, June 28-July 01, 2001
• 9: Doina Precup , Richard S. Sutton , Satinder P. Singh, Eligibility Traces for Off-Policy Policy Evaluation, Proceedings of the Seventeenth International Conference on Machine Learning, p.759-766, June 29-July 02, 2000
• 10: Reuven Y. Rubinstein , Dirk P. Kroese, The Cross Entropy Method: A Unified Approach To Combinatorial Optimization, Monte-carlo Simulation (Information Science and Statistics), Springer-Verlag New York, Inc., Secaucus, NJ, 2004
• 11: 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]
• 12: Richard S. Sutton, Reinforcement Learning, Kluwer Academic Publishers, Norwell, MA, 1992

INDEX TERMS

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

Additional Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.2 Approximation

  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.8 Problem Solving, Control Methods, and Search
          Subjects: Plan execution, formation, and generation
  I.6 SIMULATION AND MODELING
      I.6.4 Model Validation and Analysis
      I.6.5 Model Development
          Subjects: Modeling methodologies

General Terms:
Algorithms, Design, Performance, Theory