Average-Case Performance of Rollout Algorithms for Knapsack Problems
Rollout algorithms have demonstrated excellent performance on a variety of dynamic and discrete optimization problems. Interpreted as an approximate dynamic programming algorithm, a rollout algorithm estimates the value-to-go at each decision stage by simulating future events while following a heuri...
| Main Authors: | , |
|---|---|
| Other Authors: | |
| Format: | Article |
| Language: | en_US |
| Published: |
Springer-Verlag
2015
|
| Online Access: | http://hdl.handle.net/1721.1/100430 https://orcid.org/0000-0002-8585-6566 |
| _version_ | 1811073170749259776 |
|---|---|
| author | Mastin, Andrew Jaillet, Patrick |
| author2 | Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science |
| author_facet | Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science Mastin, Andrew Jaillet, Patrick |
| author_sort | Mastin, Andrew |
| collection | MIT |
| description | Rollout algorithms have demonstrated excellent performance on a variety of dynamic and discrete optimization problems. Interpreted as an approximate dynamic programming algorithm, a rollout algorithm estimates the value-to-go at each decision stage by simulating future events while following a heuristic policy, referred to as the base policy. While in many cases rollout algorithms are guaranteed to perform as well as their base policies, there have been few theoretical results showing additional improvement in performance. In this paper, we perform a probabilistic analysis of the subset sum problem and 0–1 knapsack problem, giving theoretical evidence that rollout algorithms perform strictly better than their base policies. Using a stochastic model from the existing literature, we analyze two rollout methods that we refer to as the exhaustive rollout and consecutive rollout, both of which employ a simple greedy base policy. We prove that both methods yield a significant improvement in expected performance after a single iteration of the rollout algorithm, relative to the base policy. |
| first_indexed | 2024-09-23T09:29:29Z |
| format | Article |
| id | mit-1721.1/100430 |
| institution | Massachusetts Institute of Technology |
| language | en_US |
| last_indexed | 2024-09-23T09:29:29Z |
| publishDate | 2015 |
| publisher | Springer-Verlag |
| record_format | dspace |
| spelling | mit-1721.1/1004302022-09-30T14:46:44Z Average-Case Performance of Rollout Algorithms for Knapsack Problems Mastin, Andrew Jaillet, Patrick Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science Massachusetts Institute of Technology. Laboratory for Information and Decision Systems Mastin, Andrew Jaillet, Patrick Rollout algorithms have demonstrated excellent performance on a variety of dynamic and discrete optimization problems. Interpreted as an approximate dynamic programming algorithm, a rollout algorithm estimates the value-to-go at each decision stage by simulating future events while following a heuristic policy, referred to as the base policy. While in many cases rollout algorithms are guaranteed to perform as well as their base policies, there have been few theoretical results showing additional improvement in performance. In this paper, we perform a probabilistic analysis of the subset sum problem and 0–1 knapsack problem, giving theoretical evidence that rollout algorithms perform strictly better than their base policies. Using a stochastic model from the existing literature, we analyze two rollout methods that we refer to as the exhaustive rollout and consecutive rollout, both of which employ a simple greedy base policy. We prove that both methods yield a significant improvement in expected performance after a single iteration of the rollout algorithm, relative to the base policy. National Science Foundation (U.S.) (Grant 1029603) United States. Office of Naval Research (Grant N00014-12-1-0033) National Science Foundation (U.S.). Graduate Research Fellowship 2015-12-18T15:07:17Z 2015-12-18T15:07:17Z 2014-07 2013-03 Article http://purl.org/eprint/type/JournalArticle 0022-3239 1573-2878 http://hdl.handle.net/1721.1/100430 Mastin, Andrew, and Patrick Jaillet. “Average-Case Performance of Rollout Algorithms for Knapsack Problems.” Journal of Optimization Theory and Applications 165, no. 3 (July 26, 2014): 964–984. https://orcid.org/0000-0002-8585-6566 en_US http://dx.doi.org/10.1007/s10957-014-0603-x Journal of Optimization Theory and Applications Creative Commons Attribution-Noncommercial-Share Alike http://creativecommons.org/licenses/by-nc-sa/4.0/ application/pdf Springer-Verlag MIT web domain |
| spellingShingle | Mastin, Andrew Jaillet, Patrick Average-Case Performance of Rollout Algorithms for Knapsack Problems |
| title | Average-Case Performance of Rollout Algorithms for Knapsack Problems |
| title_full | Average-Case Performance of Rollout Algorithms for Knapsack Problems |
| title_fullStr | Average-Case Performance of Rollout Algorithms for Knapsack Problems |
| title_full_unstemmed | Average-Case Performance of Rollout Algorithms for Knapsack Problems |
| title_short | Average-Case Performance of Rollout Algorithms for Knapsack Problems |
| title_sort | average case performance of rollout algorithms for knapsack problems |
| url | http://hdl.handle.net/1721.1/100430 https://orcid.org/0000-0002-8585-6566 |
| work_keys_str_mv | AT mastinandrew averagecaseperformanceofrolloutalgorithmsforknapsackproblems AT jailletpatrick averagecaseperformanceofrolloutalgorithmsforknapsackproblems |