Index Policies and Performance Bounds for Dynamic Selection Problems

We consider dynamic selection problems, where a decision maker repeatedly selects a set of items from a larger collection of available items. A classic example is the dynamic assortment problem with demand learning, where a retailer chooses items to offer for sale subject to a display space constraint. The retailer may adjust the assortment over … Read more

Information Relaxations, Duality, and Convex Dynamic Programs

We consider the information relaxation approach for calculating performance bounds for stochastic dynamic programs (DPs), following Brown, Smith, and Sun (2010). This approach generates performance bounds by solving problems with relaxed nonanticipativity constraints and a penalty that punishes violations of these nonanticipativity constraints. In this paper, we study DPs that have a convex structure and … Read more

Dynamic Portfolio Optimization with Transaction Costs: Heuristics and Dual Bounds

We consider the problem of dynamic portfolio optimization in a discrete-time, finite-horizon setting. Our general model considers risk aversion, portfolio constraints (e.g., no short positions), return predictability, and transaction costs. This problem is naturally formulated as a stochastic dynamic program. Unfortunately, with non-zero transaction costs, the dimension of the state space is at least as … Read more

Information Relaxations and Duality in Stochastic Dynamic Programs

We describe a dual approach to stochastic dynamic programming: we relax the constraint that the chosen policy must be temporally feasible and impose a penalty that punishes violations of temporal feasibility. We describe the theory underlying this dual approach and demonstrate its use in dynamic programming models related to inventory control, option pricing, and oil … Read more