非负费用折扣半马氏决策过程

本文考虑可数状态非负费用的折扣半马氏决策过程.首先在给定半马氏决策核和策略下构造一个连续时间半马氏决策过程,然后用最小非负解方法证明值函数满足最优方程和存在ε-最优平稳策略,并进一步给出最优策略的存在性条件及其一些性质.最后,给出了值迭代算法和一个数值算例.     

约束折扣半马氏决策规划

本文研究约束折扣半马氏决策规划问题，即在一折扣期望费用约束下，使折扣期望报酬达最大的约束最优问题，假设状态集可数，行动集为紧的非空Ｂｏｒｅｌ集，本文给出了ｐ－约束最优策略的充要条件，证明了在适当的假设条件下必存在ｐ－约束最优策略。     

On the optimality of a full-service policy for a queueing system with discounted costs

We provide weak sufficient conditions for a full-service policy to be optimal in a queueing control problem in which the service rate is a dynamic decision variable. In our model there are service costs and holding costs and the objective is to minimize the expected total discounted cost over an infinite horizon. We begin with a semi-Markov decision model for a single-server queue with exponentially distributed inter-arrival and service times. Then we present a general model with weak probabilistic assumptions and demonstrate that the full-service policy minimizes both finite-horizon and infinite-horizon total discounted cost on each sample path.     

Optimal Control of Markov Processes with Age-Dependent Transition Rates

We study optimal control of Markov processes with age-dependent transition rates. The control policy is chosen continuously over time based on the state of the process and its age. We study infinite horizon discounted cost and infinite horizon average cost problems. Our approach is via the construction of an equivalent semi-Markov decision process. We characterise the value function and optimal controls for both discounted and average cost cases.     

A minimization problem of the risk probability in first passage semi-Markov decision processes with loss rates

This paper is the first attempt to investigate the risk probability criterion in semi-Markov decision processes with loss rates. The goal is to find an optimal policy with the minimum risk probability that the total loss incurred during a first passage time to some target set exceeds a loss level. First, we establish the optimality equation via a successive approximation technique, and show that the value function is the unique solution to the optimality equation. Second, we give suitable conditions, under which we prove the existence of optimal policies and develop an algorithm for computing ?-optimal policies. Finally, we apply our main results to a business system.     

Optimal risk probability for first passage models in semi-Markov decision processes

This paper studies the risk minimization problem in semi-Markov decision processes with denumerable states. The criterion to be optimized is the risk probability (or risk function) that a first passage time to some target set doesn't exceed a threshold value. We first characterize such risk functions and the corresponding optimal value function, and prove that the optimal value function satisfies the optimality equation by using a successive approximation technique. Then, we present some properties of optimal policies, and further give conditions for the existence of optimal policies. In addition, a value iteration algorithm and a policy improvement method for obtaining respectively the optimal value function and optimal policies are developed. Finally, two examples are given to illustrate the value iteration procedure and essential characterization of the risk function.     

离散型冲击折扣半马氏决策过程

本文讨论离散型冲击折扣半马氏决策过程，在建立模型后，我们将它化成了一个等价的离散时间马氏决策过程．     

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

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

Approximation solution and suboptimality for discounted semi-markov decision problems with countable state space

In this article we consider the approximate solution for semi-Markov decision problems with infinite horizon, countable state space, discounted cost function and finite action space. We present converging sequences of lower and upper bounds for the value function and, moreover, we derive a method for exclusion of suboptimal actions.     

Markov-type fuzzy decision processes with a discounted reward on a closed interval

We formulate a new multi-stage decision process with Markov-type fuzzy transition, which is termed Markov-type fuzzy decision process. In the general framework of the decision process, both of state and action are assumed to be fuzzy itself. The transition of states is defined using the fuzzy relation with Markov property and the discounted total reward is described as a fuzzy number on a closed bounded interval. To discuss the optimization problem, a partial order of convex fuzzy numbers is introduced. In this paper the discounted total reward associated with an admissible stationary policy is characterized by a unique fixed point of the contractive mapping. Moreover, the optimality equation for the fuzzy decision model is derived under some continuity conditions. Also, an illustrated example is given to explain the theoretical results and the computation in the paper.     

非时齐向量值马氏决策模型

章云等了一类报酬函数绝对平均相对有界的非时齐向量值马氏决策模型,得出了一最优策略存在的充分条件,并讨论了强最优和最优的关系,张升等导出了该模型的几个性质。     

Optimal stopping time on discounted semi-Markov processes

This paper attempts to study the optimal stopping time for semi- Markov processes (SMPs) under the discount optimization criteria with unbounded cost rates. In our work, we introduce an explicit construction of the equivalent semi-Markov decision processes (SMDPs). The equivalence is embodied in the expected discounted cost functions of SMPs and SMDPs, that is, every stopping time of SMPs can induce a policy of SMDPs such that the value functions are equal, and vice versa. The existence of the optimal stopping time of SMPs is proved by this equivalence relation. Next, we give the optimality equation of the value function and develop an effective iterative algorithm for computing it. Moreover, we show that the optimal and ε-optimal stopping time can be characterized by the hitting time of the special sets. Finally, to illustrate the validity of our results, an example of a maintenance system is presented in the end.     

Computational bounds for elevator control policies by large scale linear programming

We computationally assess policies for the elevator control problem by a new column-generation approach for the linear programming method for discounted infinite-horizon Markov decision problems. By analyzing the optimality of given actions in given states, we were able to provably improve the well-known nearest-neighbor policy. Moreover, with the method we could identify an optimal parking policy. This approach can be used to detect and resolve weaknesses in particular policies for Markov decision problems.     

Continuous time Markovian decision processes average return criterion

Continuous time Markovian decision models with countable state space are investigated. The existence of an optimal stationary policy is established for the expected average return criterion function. It is shown that the expected average return can be expressed as an expected discounted return of a related Markovian decision process. A policy iteration method is given which converges to an optimal deterministic policy, the policy so obtained is shown optimal over all Markov policies.     

Nonstationary value-iteration and adaptive control of discounted semi-Markov processes

We consider in this paper discounted-reward, denumerable state space, semi-Markov decision processes which depend on unknown parameters. The problems we are interested in are: Given that the true parameter value is unknown, (I) give an iterative scheme to determine the total maximal discounted reward, and (II) find an asymptotically discount optimal (adaptive) policy. Our solutions are inspired by the nonstationary value iteration (NVI) scheme of Federgruen and Schweitzer (J. Optim. Theory Appl.34 (1981), 207–241) combined with the ideas of Schäl (Preprint No. 428, Inst. Angew. Math. Univ. Bonn, 1981) concerning the “principle of estimation and control” for the adaptive control of semi-Markov processes.     

A Stagewise Action Elimination Algorithm for the Discounted Semi-Markov Problem

An efficient algorithm for solving discounted semi-Markov (Markov-renewal) problems is proposed. The value iteration method of dynamic programming is used in conjunction with a test for non-optimal actions. A non-optimality test for the discounted semi-Markov processes, which is an extension of Hastings and Van Nunens (1976) test for the undiscounted or discounted returns with infinite or finite planning horizon, is used to identify actions which cannot be optimal at the current stage of a discounted semi-Markov process. The test proposed eliminates actions for one or more stages after which they may enter the set of possibly optimal actions, but such re-entries cease as convergence proceeds.     

Optimal threshold probability and expectation in semi-Markov decision processes

We consider undiscounted semi-Markov decision process with a target set and our main concern is a problem minimizing threshold probability. We formulate the problem as an infinite horizon case with a recurrent class. We show that an optimal value function is a unique solution to an optimality equation and there exists a stationary optimal policy. Also several value iteration methods and a policy improvement method are given in our model. Furthermore, we investigate a relationship between threshold probabilities and expectations for total rewards.     

Continuous-Time Markov Decision Processes with State-Dependent Discount Factors

We consider continuous-time Markov decision processes in Polish spaces. The performance of a control policy is measured by the expected discounted reward criterion associated with state-dependent discount factors. All underlying Markov processes are determined by the given transition rates which are allowed to be unbounded, and the reward rates may have neither upper nor lower bounds. By using the dynamic programming approach, we establish the discounted reward optimality equation (DROE) and the existence and uniqueness of its solutions. Under suitable conditions, we also obtain a discounted optimal stationary policy which is optimal in the class of all randomized stationary policies. Moreover, when the transition rates are uniformly bounded, we provide an algorithm to compute (or?at least to approximate) the discounted reward optimal value function as well as a discounted optimal stationary policy. Finally, we use an example to illustrate our results. Specially, we first derive an explicit and exact solution to the DROE and an explicit expression of a discounted optimal stationary policy for such an example.     

Constrained optimality for finite horizon semi-Markov decision processes in Polish spaces

This paper focuses on solving a finite horizon semi-Markov decision process with multiple constraints. We convert the problem to a constrained absorbing discrete-time Markov decision process and then to an equivalent linear program over a class of occupancy measures. The existence, characterization and computation of constrained-optimal policies are established under suitable conditions. An example is given to demonstrate our results.     

An optimality principle for Markovian decision processes

The following optimality principle is established for finite undiscounted or discounted Markov decision processes: If a policy is (gain, bias, or discounted) optimal in one state, it is also optimal for all states reachable from this state using this policy. The optimality principle is used constructively to demonstrate the existence of a policy that is optimal in every state, and then to derive the coupled functional equations satisfied by the optimal return vectors. This reverses the usual sequence, where one first establishes (via policy iteration or linear programming) the solvability of the coupled functional equations, and then shows that the solution is indeed the optimal return vector and that the maximizing policy for the functional equations is optimal for every state.