Skip to main content

Dynamic Programs with Shared Resources and Signals: Dynamic Fluid Policies and Asymptotic Optimality

Publication ,  Journal Article
Brown, DB; Zhang, J
Published in: Operations Research
September 1, 2022

We consider a sequential decision problem involving shared resources and signals in which a decision maker repeatedly observes some exogenous information (the signal), modeled as a finite-state Markov process, then allocates a limited amount of a shared resource across a set of projects. The framework includes a number of applications and generalizes Markovian multiarmed bandit problems by (a) incorporating exogenous information through the signal and (b) allowing for more general resource allocation decisions. Such problems are naturally formulated as stochastic dynamic programs (DPs), but solving the DP is impractical unless the number of projects is small. In this paper, we develop a Lagrangian relaxation and a DP formulation of the corresponding fluid relaxation—a dynamic fluid relaxation—that provide upper bounds on the optimal value function as well as a feasible policy. We develop an iterative primal-dual algorithm for solving the dynamic fluid relaxation and analyze the performance of the feasible dynamic fluid policy. Our performance analysis implies, under mild conditions, that the dynamic fluid relaxation bound and feasible policy are asymptotically optimal as the number of projects grows large. Our Lagrangian relaxation uses Lagrange multipliers that depend on the history of past signals in each period: we show that the bounds and analogous policies using restricted forms of Lagrange multipliers (e.g., only depending on the current signal state in each period) in general lead to a performance gap that is linear in the number of projects and thus are not asymptotically optimal in the regime of many projects. We demonstrate the model and results in two applications: (i) a dynamic capital budgeting problem and (ii) a multilocation inventory management problem with limited production capacity and demands that are correlated across locations by a changing market state.

Duke Scholars

Published In

Operations Research

DOI

EISSN

1526-5463

ISSN

0030-364X

Publication Date

September 1, 2022

Volume

70

Issue

5

Start / End Page

3015 / 3033

Related Subject Headings

  • Operations Research
  • 3507 Strategy, management and organisational behaviour
  • 1503 Business and Management
  • 0802 Computation Theory and Mathematics
  • 0102 Applied Mathematics
 

Citation

APA
Chicago
ICMJE
MLA
NLM
Brown, D. B., & Zhang, J. (2022). Dynamic Programs with Shared Resources and Signals: Dynamic Fluid Policies and Asymptotic Optimality. Operations Research, 70(5), 3015–3033. https://doi.org/10.1287/opre.2021.2181
Brown, D. B., and J. Zhang. “Dynamic Programs with Shared Resources and Signals: Dynamic Fluid Policies and Asymptotic Optimality.” Operations Research 70, no. 5 (September 1, 2022): 3015–33. https://doi.org/10.1287/opre.2021.2181.
Brown DB, Zhang J. Dynamic Programs with Shared Resources and Signals: Dynamic Fluid Policies and Asymptotic Optimality. Operations Research. 2022 Sep 1;70(5):3015–33.
Brown, D. B., and J. Zhang. “Dynamic Programs with Shared Resources and Signals: Dynamic Fluid Policies and Asymptotic Optimality.” Operations Research, vol. 70, no. 5, Sept. 2022, pp. 3015–33. Scopus, doi:10.1287/opre.2021.2181.
Brown DB, Zhang J. Dynamic Programs with Shared Resources and Signals: Dynamic Fluid Policies and Asymptotic Optimality. Operations Research. 2022 Sep 1;70(5):3015–3033.

Published In

Operations Research

DOI

EISSN

1526-5463

ISSN

0030-364X

Publication Date

September 1, 2022

Volume

70

Issue

5

Start / End Page

3015 / 3033

Related Subject Headings

  • Operations Research
  • 3507 Strategy, management and organisational behaviour
  • 1503 Business and Management
  • 0802 Computation Theory and Mathematics
  • 0102 Applied Mathematics