| Report ID: | 05-06-02 |
| Initial Submission Date: | 2005-06-24 |
| Title: | A Linear Program for Bellman Error Minimization with Performance Guarantees |
| Summary: | We introduce a new algorithm based on linear programming for optimization of average-cost Markov decision processes (MDPs). The algorithm approximates the differential cost function of a perturbed MDP via a linear combination of basis functions. The approximation minimizes a version of Bellman error. We establish an error bound that scales gracefully with the number of states without imposing the (strong) Lyapunov condition required by its counterpart in [8]. We investigate implications of this result in the context of a queueing problem. |
| Authors: | de Farias, Daniela; Van Roy, Benjamin |
| Contact email: | bvr@stanford.edu |
| | Number of views : 1151 Number of downloads : 682 |
