Optimization Online


Approximations to Stochastic Dynamic Programs via Information Relaxation Duality

Santiago Balseiro(srb2155***at***columbia.edu)
David Brown(dbbrown***at***duke.edu)

Abstract: In the analysis of complex stochastic dynamic programs, we often seek strong theoretical guarantees on the suboptimality of heuristic policies. One technique for obtaining performance bounds is perfect information analysis: this approach provides bounds on the performance of an optimal policy by considering a decision maker who has access to the outcomes of all future uncertainties before making decisions, i.e., fully relaxed nonanticipativity constraints. A limitation of this approach is that in many problems perfect information about uncertainties is quite valuable and thus the resulting bound is weak. In this paper we study the information relaxation duality approach developed in Brown, Smith, and Sun (2010) to show that by including a penalty that punishes violations of these nonanticipativity constraints, we can derive stronger analytical bounds on the suboptimality of heuristic policies in stochastic dynamic programs that are too difficult to solve. The general framework we develop ties the heuristic policy and the performance bound together explicitly through the use of an approximate value function: heuristic policies are greedy with respect to this approximation, and penalties are also generated in a specific way using this approximation. We apply this approach to three challenging problems: stochastic knapsack problems, stochastic scheduling on parallel machines, and sequential search problems. In each of these problems, we consider a greedy heuristic policy generated by an approximate value function and a corresponding penalized perfect information bound. We then characterize the gap between the performance of the policy and the information relaxation bound in each problem; the results imply asymptotic optimality of the heuristic policy for specific "large" regimes of interest

Keywords: Dynamic programming, greedy heuristic policies, information relaxation duality, asymptotic optimality, stochastic knapsack problems, stochastic scheduling, sequential search problems

Category 1: Applications -- OR and Management Sciences

Category 2: Other Topics (Dynamic Programming )

Category 3: Stochastic Programming


Download: [PDF]

Entry Submitted: 11/22/2017
Entry Accepted: 11/22/2017
Entry Last Modified: 11/22/2017

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society