Conservation Laws, Extended Polymatroids and Multi-Armed Bandit Problems; A unified Approach to Indexabel Systems
We show that if performance measures in stochastic and dynamic scheduling problems satisfy generalized conservation laws, then the feasible space of achievable performance is a polyhedron called an extended polymatroid that generalizes the usual polymatroids introduced by Edmonds. Optimization of a...
| Main Authors: | , |
|---|---|
| Format: | Working Paper |
| Language: | en_US |
| Published: |
Massachusetts Institute of Technology, Operations Research Center
2004
|
| Online Access: | http://hdl.handle.net/1721.1/5203 |
| _version_ | 1826188564940980224 |
|---|---|
| author | Bertsimas, Dimitris J. Nino-Mora, Jose |
| author_facet | Bertsimas, Dimitris J. Nino-Mora, Jose |
| author_sort | Bertsimas, Dimitris J. |
| collection | MIT |
| description | We show that if performance measures in stochastic and dynamic scheduling problems satisfy generalized conservation laws, then the feasible space of achievable performance is a polyhedron called an extended polymatroid that generalizes the usual polymatroids introduced by Edmonds. Optimization of a linear objective over an extended polymatroid is solved by an adaptive greedy algorithm, which leads to an optimal solution having an indexability property (indexable systems). Under a certain condition, then the indices have a stronger decomposition property (decomposable systems). The following classical problems can be analyzed using our theory: multi-armed bandit problems, branching bandits. multiclass queues, multiclass queues with feedback, deterministic scheduling problemls. Interesting consequences of our results include: (1) a characterization of indexable systems as systems that satisfy generalized conservation laws, (2) a. sufficient condition for idexable systems to be decomposable, (3) a new linear programming proof of the decomposability property of Gittins indices in multi-armed bandit problems, (4) a unified and practical approach to sensitivity analysis of indexable systems, (5) a new characterization of the indices of indexable systems as sums of dual variables and a new interpretation of the indices in terms of retirement options in the context of branching bandits, (6) the first rigorous analysis of the indexability of undiscounted branching bandits, (7) a new algorithm to compute the indices of indexable systems (in particular Gittins indices), which is as fast as the fastest known algorithm, (8) a unification of the algorithm of Klimov for multiclass queues and the algorithm of Gittins for multi-armed bandits as special cases of the same algorithm. (9) closed form formulae for the performance of the optimal policy, and (10) an understanding of the nondependence of the indices on some of the parameters of the stochastic schediiuling problem. Most importantly, our approach provides a unified treatment of several classical problems in stochastic and dynamic scheduling and is able to address in a unified way their variations such as: discounted versus undiscounted cost criterion, rewards versus taxes. preemption versus nonpreemption, discrete versus continuous time, work conserving versus idling policies, linear versus nonlinear objective functions. |
| first_indexed | 2024-09-23T08:01:20Z |
| format | Working Paper |
| id | mit-1721.1/5203 |
| institution | Massachusetts Institute of Technology |
| language | en_US |
| last_indexed | 2024-09-23T08:01:20Z |
| publishDate | 2004 |
| publisher | Massachusetts Institute of Technology, Operations Research Center |
| record_format | dspace |
| spelling | mit-1721.1/52032019-04-09T16:09:14Z Conservation Laws, Extended Polymatroids and Multi-Armed Bandit Problems; A unified Approach to Indexabel Systems Bertsimas, Dimitris J. Nino-Mora, Jose We show that if performance measures in stochastic and dynamic scheduling problems satisfy generalized conservation laws, then the feasible space of achievable performance is a polyhedron called an extended polymatroid that generalizes the usual polymatroids introduced by Edmonds. Optimization of a linear objective over an extended polymatroid is solved by an adaptive greedy algorithm, which leads to an optimal solution having an indexability property (indexable systems). Under a certain condition, then the indices have a stronger decomposition property (decomposable systems). The following classical problems can be analyzed using our theory: multi-armed bandit problems, branching bandits. multiclass queues, multiclass queues with feedback, deterministic scheduling problemls. Interesting consequences of our results include: (1) a characterization of indexable systems as systems that satisfy generalized conservation laws, (2) a. sufficient condition for idexable systems to be decomposable, (3) a new linear programming proof of the decomposability property of Gittins indices in multi-armed bandit problems, (4) a unified and practical approach to sensitivity analysis of indexable systems, (5) a new characterization of the indices of indexable systems as sums of dual variables and a new interpretation of the indices in terms of retirement options in the context of branching bandits, (6) the first rigorous analysis of the indexability of undiscounted branching bandits, (7) a new algorithm to compute the indices of indexable systems (in particular Gittins indices), which is as fast as the fastest known algorithm, (8) a unification of the algorithm of Klimov for multiclass queues and the algorithm of Gittins for multi-armed bandits as special cases of the same algorithm. (9) closed form formulae for the performance of the optimal policy, and (10) an understanding of the nondependence of the indices on some of the parameters of the stochastic schediiuling problem. Most importantly, our approach provides a unified treatment of several classical problems in stochastic and dynamic scheduling and is able to address in a unified way their variations such as: discounted versus undiscounted cost criterion, rewards versus taxes. preemption versus nonpreemption, discrete versus continuous time, work conserving versus idling policies, linear versus nonlinear objective functions. 2004-05-28T19:27:53Z 2004-05-28T19:27:53Z 1993-03 Working Paper http://hdl.handle.net/1721.1/5203 en_US Operations Research Center Working Paper;OR 277-93 2801726 bytes application/pdf application/pdf Massachusetts Institute of Technology, Operations Research Center |
| spellingShingle | Bertsimas, Dimitris J. Nino-Mora, Jose Conservation Laws, Extended Polymatroids and Multi-Armed Bandit Problems; A unified Approach to Indexabel Systems |
| title | Conservation Laws, Extended Polymatroids and Multi-Armed Bandit Problems; A unified Approach to Indexabel Systems |
| title_full | Conservation Laws, Extended Polymatroids and Multi-Armed Bandit Problems; A unified Approach to Indexabel Systems |
| title_fullStr | Conservation Laws, Extended Polymatroids and Multi-Armed Bandit Problems; A unified Approach to Indexabel Systems |
| title_full_unstemmed | Conservation Laws, Extended Polymatroids and Multi-Armed Bandit Problems; A unified Approach to Indexabel Systems |
| title_short | Conservation Laws, Extended Polymatroids and Multi-Armed Bandit Problems; A unified Approach to Indexabel Systems |
| title_sort | conservation laws extended polymatroids and multi armed bandit problems a unified approach to indexabel systems |
| url | http://hdl.handle.net/1721.1/5203 |
| work_keys_str_mv | AT bertsimasdimitrisj conservationlawsextendedpolymatroidsandmultiarmedbanditproblemsaunifiedapproachtoindexabelsystems AT ninomorajose conservationlawsextendedpolymatroidsandmultiarmedbanditproblemsaunifiedapproachtoindexabelsystems |