Publications

| Sorted by Date | Classified by Publication Type | Classified by Research Category |

Bootstrapping LPs in Value Iteration for Multi-Objective and Partially Observable MDPs

Diederik M. Roijers, Erwin Walraven, and Matthijs T. J. Spaan. Bootstrapping LPs in Value Iteration for Multi-Objective and Partially Observable MDPs. In Proc. of Int. Conf. on Automated Planning and Scheduling, pp. 218–226, 2018.

Download

pdf 

Abstract

Iteratively solving a set of linear programs (LPs) is a common strategy for solving various decision-making problems in Artificial Intelligence, such as planning in multi-objective or partially observable Markov Decision Processes (MDPs). A prevalent feature is that the solutions to these LPs become increasingly similar as the solving algorithm converges, because the solution computed by the algorithm approaches the fixed point of a Bellman backup operator. In this paper, we propose to speed up the solving process of these LPs by bootstrapping based on similar LPs solved previously. We use these LPs to initialize a subset of relevant LP constraints, before iteratively generating the remaining constraints. The resulting algorithm is the first to consider such information sharing across iterations. We evaluate our approach on planning in Multi-Objective MDPs (MOMDPs) and Partially Observable MDPs (POMDPs), showing that it solves fewer LPs than the state of the art, which leads to a significant speed-up. Moreover, for MOMDPs we show that our method scales better in both the number of states and the number of objectives, which is vital for multi-objective planning.

BibTeX Entry

@InProceedings{Roijers18,
  author =       {Diederik M. Roijers and Erwin Walraven and Matthijs
                  T. J. Spaan},
  title =        {Bootstrapping {LPs} in Value Iteration for
                  Multi-Objective and Partially Observable {MDPs}},
  booktitle =    {Proc. of Int. Conf. on Automated Planning and
                  Scheduling},
  pages =        {218--226},
  year =         2018
}

Note: This material is presented to ensure timely dissemination of scholarly and technical work. Copyright and all rights therein are retained by authors or by other copyright holders. All persons copying this information are expected to adhere to the terms and constraints invoked by each author's copyright. In most cases, these works may not be reposted without the explicit permission of the copyright holder.

Generated by bib2html.pl (written by Patrick Riley) on Thu Feb 29, 2024 16:15:45 UTC