markov decision processes

From Infinite to Finite Programs: Explicit Error Bounds with Applications to Approximate Dynamic Programming

  • Daniel Kuhn
  • Tobias Sutter
  • John Lygeros
  • Peyman Mohajerin Esfahani
    • Categories Dynamic Programming, Infinite Dimensional Optimization, Stochastic Programming Tags , , , ,

    We consider linear programming (LP) problems in infinite dimensional spaces that are in general computationally intractable. Under suitable assumptions, we develop an approximation bridge from the infinite-dimensional LP to tractable finite convex programs in which the performance of the approximation is quantified explicitly. To this end, we adopt the recent developments in two areas of … Read more

    Controlled Markov Decision Processes with AVaR Criteria for Unbounded Costs

  • Kerem Ugurlu
    • Categories Applications - OR and Management Sciences Tags , ,

    In this paper, we consider the control problem with the Average-Value-at-Risk (AVaR) criteria of the possibly unbounded L 1 -costs in infinite horizon on a Markov Decision Process (MDP). With a suitable state aggregation and by choosing a priori a global variable s heuristically, we show that there exist optimal policies for the infinite horizon … Read more

    Distributionally robust inventory control when demand is a martingale

  • David A. Goldberg
  • Linwei Xin
    • Categories Applications - OR and Management Sciences, Robust Optimization, Stochastic Programming Tags , , , , ,

    Demand forecasting plays an important role in many inventory control problems. To mitigate the potential harms of model misspecification in this context, various forms of distributionally robust optimization have been applied. Although many of these methodologies suffer from the problem of time-inconsistency, the work of Klabjan, Simchi-Levi and Song [85] established a general time-consistent framework … Read more

    Controlled Markov Chains with AVaR Criteria for Unbounded Costs

  • Kerem Ugurlu
    • Categories Applications - OR and Management Sciences Tags , ,

    In this paper, we consider the control problem with the Average-Value-at-Risk (AVaR) criteria of the possibly unbounded $L^{1}$-costs in infinite horizon on a Markov Decision Process (MDP). With a suitable state aggregation and by choosing a priori a global variable $s$ heuristically, we show that there exist optimal policies for the infinite horizon problem. To … Read more

    Rectangular sets of probability measures

  • Alexander Shapiro
    • Categories Stochastic Programming Tags , , , , , ,

    In this paper we consider the notion of rectangularity of a set of probability measures, introduced in Epstein and Schneider (2003), from a somewhat different point of view. We define rectangularity as a property of dynamic decomposition of a distributionally robust stochastic optimization problem and show how it relates to the modern theory of coherent … Read more

    Information Relaxation Bounds for Infinite Horizon Markov Decision Processes

  • David B. Brown
  • Martin Haugh
    • Categories Dynamic Programming, Scheduling, Stochastic Programming Tags , ,

    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 constraints. In this paper, we study infinite horizon DPs with discounted costs and consider … Read more

    Singularly Perturbed Markov Decision Processes: A Multiresolution Algorithm

  • Chin Pang Ho
  • Panos Parpas
    • Categories Dynamic Programming Tags , , ,

    Singular perturbation techniques allow the derivation of an aggregate model whose solution is asymptotically optimal for Markov Decision Processes with strong and weak interactions. We develop an algorithm that takes advantage of the asymptotic optimality of the aggregate model in order to compute the solution of the original model with theoretically better complexity than conventional … Read more

    Interdiction Games on Markovian PERT Networks

  • Eli Gutin
  • Daniel Kuhn
  • Wolfram Wiesemann
    • Categories Stochastic Programming Tags , , ,

    In a stochastic interdiction game a proliferator aims to minimize the expected duration of a nuclear weapons development project, while an interdictor endeavors to maximize the project duration by delaying some of the project tasks. We formulate static and dynamic versions of the interdictor’s decision problem where the interdiction plan is either pre-committed or adapts … Read more

    Optimizing Trading Decisions for Hydro Storage Systems using Approximate Dual Dynamic Programming

  • Nils Löhndorf
  • David Wozabal
  • Stefan Minner
    • Categories Applications - OR and Management Sciences, Dynamic Programming, Stochastic Programming Tags , , ,

    We propose a new approach to optimize operations of hydro storage systems with multiple connected reservoirs which participate in wholesale electricity markets. Our formulation integrates short-term intraday with long-term interday decisions. The intraday problem considers bidding decisions as well as storage operation during the day and is formulated as a stochastic program. The interday problem … Read more

    A New Complexity Result on Solving the Markov Decision Problem

  • Yinyu Ye
    • Categories Linear Programming Tags , ,

    We present a new complexity result on solving the Markov decision problem (MDP) with $n$ states and a number of actions for each state, a special class of real-number linear programs with the Leontief matrix structure. We prove that, when the discount factor $\theta$ is strictly less than $1$, the problem can be solved in … Read more