nips nips2002 nips2002-33 nips2002-33-reference knowledge-graph by maker-knowledge-mining
Source: pdf
Author: Benjamin V. Roy, Daniela D. Farias
Abstract: This paper extends our earlier analysis on approximate linear programming as an approach to approximating the cost-to-go function in a discounted-cost dynamic program [6]. In this paper, we consider the average-cost criterion and a version of approximate linear programming that generates approximations to the optimal average cost and differential cost function. We demonstrate that a naive version of approximate linear programming prioritizes approximation of the optimal average cost and that this may not be well-aligned with the objective of deriving a policy with low average cost. For that, the algorithm should aim at producing a good approximation of the differential cost function. We propose a twophase variant of approximate linear programming that allows for external control of the relative accuracy of the approximation of the differential cost function over different portions of the state space via state-relevance weights. Performance bounds suggest that the new algorithm is compatible with the objective of optimizing performance and provide guidance on appropriate choices for state-relevance weights.
[1] D. Adelman. A price-directed approach to stochastic inventory/routing. Preprint, 2002.
[2] D. Adelman. Price-directed replenishment of subsets: Methodology and its application to inventory routing. Preprint, 2002.
[3] D. Bertsekas. Dynamic Programming and Optimal Control. Athena Scientific, 1995.
[4] D. Bertsekas and J.N. Tsitsiklis. Neuro-Dynamic Programming. Athena Scientific, 1996.
[5] D. Bertsimas, D. Gamarnik, and J.N. Tsitsiklis. Performance of multiclass Markovian queueing networks via piecewise linear Lyapunov functions. Annals of Applied Probability, 11.
[6] D.P. de Farias and B. Van Roy. The linear programming approach to approximate dynamic programming. To appear in Operations Research, 2001.
[7] D.P. de Farias and B. Van Roy. On constraint sampling in the linear programming approach to approximate dynamic programming. Conditionally accepted to Mathematics of Operations Research, 2001.
[8] C. Guestrin, D. Koller, and R. Parr. Efficient solution algorithms for factored MDPs. Submitted to Journal of Artificial Intelligence Research, 2001.
[9] A.S. Manne. Linear programming and sequential decisions. Management Science, 6(3):259– 267, 1960.
[10] J.R. Morrison and P.R. Kumar. New linear program performance bounds for queueing networks. Journal of Optimization Theory and Applications, 100(3):575–597, 1999.
[11] P. Schweitzer and A. Seidmann. Generalized polynomial approximations in Markovian decision processes. Journal of Mathematical Analysis and Applications, 110:568–582, 1985.