Constraint relaxation in approximate linear programs

ABSTRACT

Approximate Linear Programming (ALP) is a reinforcement learning technique with nice theoretical properties, but it often performs poorly in practice. We identify some reasons for the poor quality of ALP solutions in problems where the approximation induces virtual loops. We then introduce two methods for improving solution quality. One method rolls out selected constraints of the ALP, guided by the dual information. The second method is a relaxation of the ALP, based on external penalty methods. The latter method is applicable in domains in which rolling out constraints is impractical. Both approaches show promising empirical results for simple benchmark problems as well as for a realistic blood inventory management problem.

REFERENCES

• 1: Dimitri P. Bertsekas , John N. Tsitsiklis, Neuro-Dynamic Programming, Athena Scientific, 1996
• 2: D. P. de Farias , B. Van Roy, The Linear Programming Approach to Approximate Dynamic Programming, Operations Research, v.51 n.6, p.850-865, November 2003 [doi>10.1287/opre.51.6.850.24925]
• 3: Guestrin, C., Koller, D., Parr, R., & Venkataraman, S. (2003). Efficient solution algorithms for factored MDPs. Journal of Artificial Intelligence Research, 19, 399--468.
• 4: Michail G. Lagoudakis , Ronald Parr, Least-squares policy iteration, The Journal of Machine Learning Research, 4, p.1107-1149, 12/1/2003
• 5: Petrik, M., & Zilberstein, S. (2008). Learning heuristic functions through approximate linear programming. International Conference on Automated Planning and Scheduling (ICAPS) (pp. 248--255).
• 6: Warren B. Powell, Approximate Dynamic Programming: Solving the Curses of Dimensionality (Wiley Series in Probability and Statistics), Wiley-Interscience, 2007
• 7: Martin Stolle , Doina Precup, Learning Options in Reinforcement Learning, Proceedings of the 5th International Symposium on Abstraction, Reformulation and Approximation, p.212-223, August 02-04, 2002
• 8: Richard S. Sutton , Andrew G. Barto, Introduction to Reinforcement Learning, MIT Press, Cambridge, MA, 1998

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.6 Optimization
          Subjects: Linear programming

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

  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.6 Learning
  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