A solvable case of the variance minimization problem

An algorithm is derived, which solves the completion time variance (CTV) problem with equal processing times in O(n log n) time. This result indicates that the special case formulated by Merten and Muller [1] is well solvable.     

连续时间Markov决策过程的均值-方差优化问题

本文考虑连续时间Markov决策过程折扣模型的均值-方差优化问题.假设状态空间和行动空间均为Polish空间,转移率和报酬率函数均无界.本文的优化目标是在折扣最优平稳策略类里,选取相应方差最小的策略.本文致力于寻找Polish空间下Markov决策过程均值-方差最优策略存在的条件.利用首次进入分解方法,本文证明均值-方差优化问题可以转化为"等价"的期望折扣优化问题,进而得到关于均值-方差优化问题的"最优方程"和均值-方差最优策略的存在性以及它相应的特征.最后,本文给出若干例子说明折扣最优策略的不唯一性和均值-方差最优策略的存在性.     

Variance minimization for continuous-time Markov decision processes: two approaches

This paper studies the limit average variance criterion for continuous-time Markov decision processes in Polish spaces. Based on two approaches, this paper proves not only the existence of solutions to the variance minimization optimality equation and the existence of a variance minimal policy that is canonical, but also the existence of solutions to the two variance minimization optimality inequalities and the existence of a variance minimal policy which may not be canonical. An example is given to illustrate all of our conditions.     

To the discord problem for a jump-like Markov process

We obtain the structure of the optimal halting moment (setting off an alarm) and an integrodifferential equation for the risk function in the discord problem for an observed jump-like Markov process in the case that the moment of discord coincides with one of the jumps of the process.     

A Markov decision process model for equitable distribution of supplies under uncertainty

Many individuals suffering from food insecurity obtain assistance from governmental programs and nonprofit agencies such as food banks. Much of the food distributed by food banks come from donations which are received from various sources in uncertain quantities at random points in time. This paper presents a model that can assist food banks in distributing these uncertain supplies equitably and measure the performance of their distribution efforts. We formulate this decision problem as a discrete-time, discrete state Markov decision process that considers stochastic supply, deterministic demand and an equity-based objective. We investigate three different allocation rules and describe the optimal policy as a function of available inventory. We also provide county level estimates of unmet need and determine the probability distribution associated with the number of underserved counties. A numerical study is performed to show how the allocation policy and unmet need are impacted by uncertain supply and deterministic, time-varying demand. We also compare different allocation rules in terms of equity and effectiveness.     

A survey of solution techniques for the partially observed Markov decision process

We survey several computational procedures for the partially observed Markov decision process (POMDP) that have been developed since the Monahan survey was published in 1982. The POMDP generalizes the standard, completely observed Markov decision process by permitting the possibility that state observations may be noise-corrupted and/or costly. Several computational procedures presented are convergence accelerating variants of, or approximations to, the Smallwood-Sondik algorithm. Finite-memory suboptimal design results are reported, and new research directions involving heuristic search are discussed.This research was supported by NSF Grant ECS-8708183 and ARO Contract DAAG-29-85-K0089.     

The Dirichlet problem of a discontinuous Markov process

Given a Markov process satisfying certain general type conditions, whose paths are not assumed to be continuous. LetD be an open subset of the state spaceE. Any bounded function defined on the complement ofD extends to be a function onE such that it is harmonic inD and satisfies the Dirichlet boundary condition at any regular boundary point ofD. The relation between harmonic functions and the characteristic operator of the given process is discussed.     

A dynamical neural network approach for distributionally robust chance-constrained Markov decision process

In this paper, we study the distributionally robust joint chance-constrained Markov decision process.Utilizing the logarithmic transformation technique, we derive its deterministic reformulation with bi-convex terms under the moment-based uncertainty set. To cope with the non-convexity and improve the robustness of the solution, we propose a dynamical neural network approach to solve the reformulated optimization problem.Numerical results on a machine replacement problem demonstrate the efficien...     

A variance algorithm for constrained minimization with linear constraints

This paper presents a quadratically convergent, rank one, variance algorithm for constrained minimization with linear constraints. The algorithm does not require a linear search for a local minimum in every iteration. Linear searches are made only when needed for stability and convergence.     

A Markov decision problem in a risk model with interest rate and Markovian environment

We consider the compound binomial model in a Markovian environment presented by Cossette et al.(2004). We modify the model via assuming that the company receives interest on the surplus and a positive real-valued premium per unit time, and introducing a control strategy of periodic dividend payments. A Markov decision problem arises and the control objective is to maximize the cumulative expected discounted dividends paid to the shareholders until ruin minus a discounted penalty for ruin. We show that under the absence of a ceiling of dividend rates the optimal strategy is a conditional band strategy given the current state of the environment process. Under the presence of a ceiling for dividend rates, the character of the optimal control strategy is given. In addition, we offer an algorithm for the optimal strategy and the optimal value function.Numerical results are provided to illustrate the algorithm and the impact of the penalty.     

A loss minimization problem

The optimal stopping problem is considered in the presence of random losses with decision making concerning non-recurrent involvement of an external financial-protection mechanism. The presence of an utility function determining the attitude of the decision-making person to a risk is taken into account. It is shown that, using the Bellman equation, optimal threshold functions can be constructed numerically and, for certain types of the utility function, such functions can even be constructed in an analytical form.     

Control of a Markov process in a problem with constraints

Translated from Ukrainskii Matematicheskii Zhurnal, Vol. 41, No. 9, pp. 1226–1230, September, 1989.     

Monotonicity in multidimensional Markov decision processes for the batch dispatch problem

Structural properties of stochastic dynamic programs are essential to understanding the nature of the solutions and in deriving appropriate approximation techniques. We concentrate on a class of multidimensional Markov decision processes and derive sufficient conditions for the monotonicity of the value functions. We illustrate our result in the case of the multiproduct batch dispatch (MBD) problem.     

Mean,variance, and probabilistic criteria in finite Markov decision processes: A review

This paper is a survey of papers which make use of nonstandard Markov decision process criteria (i.e., those which do not seek simply to optimize expected returns per unit time or expected discounted return). It covers infinite-horizon nondiscounted formulations, infinite-horizon discounted formulations, and finite-horizon formulations. For problem formulations in terms solely of the probabilities of being in each state and taking each action, policy equivalence results are given which allow policies to be restricted to the class of Markov policies or to the randomizations of deterministic Markov policies. For problems which cannot be stated in such terms, in terms of the primitive state setI, formulations involving a redefinition of the states are examined.The author would like to thank two referees for a very thorough and helpful referceing of the original article and for the extra references (Refs. 47–52) now added to the original reference list.     

Finding the K best policies in a finite-horizon Markov decision process

Directed hypergraphs represent a general modelling and algorithmic tool, which have been successfully used in many different research areas such as artificial intelligence, database systems, fuzzy systems, propositional logic and transportation networks. However, modelling Markov decision processes using directed hypergraphs has not yet been considered.In this paper we consider finite-horizon Markov decision processes (MDPs) with finite state and action space and present an algorithm for finding the K best deterministic Markov policies. That is, we are interested in ranking the first K deterministic Markov policies in non-decreasing order using an additive criterion of optimality. The algorithm uses a directed hypergraph to model the finite-horizon MDP. It is shown that the problem of finding the optimal policy can be formulated as a minimum weight hyperpath problem and be solved in linear time, with respect to the input data representing the MDP, using different additive optimality criteria.     

A maximal variance problem

In this work, we provide a direct proof concerning a special type of concave density function on a bounded closed interval with minimal variance. This proof involves elementary methods, without using any advanced theories such as Weierstrass’s Approximation Theorem, from which the technical core result of the paper [C. Carlsson, R. Fullér, P. Majlender, On possibilistic correlation, Fuzzy Sets and Systems 155 (2005) 425–445] comes.