An improved algorithm for solving communicating average reward Markov decision processes

This paper provides a policy iteration algorithm for solving communicating Markov decision processes (MDPs) with average reward criterion. The algorithm is based on the result that for communicating MDPs there is an optimal policy which is unichain. The improvement step is modified to select only unichain policies; consequently the nested optimality equations of Howard's multichain policy iteration algorithm are avoided. Properties and advantages of the algorithm are discussed and it is incorporated into a decomposition algorithm for solving multichain MDPs. Since it is easier to show that a problem is communicating than unichain we recommend use of this algorithm instead of unichain policy iteration.This research has been partially supported by NSERC Grant A-5527.     

非时齐部分可观察Markov决策规划的最优策略问题

本文讨论了一类非时齐部分可观察Markov决策模型．在不改变状态空间可列性的条件下，把该模型转化为[5]中的一般化折扣模型，从而解决了其最优策略问题，并且得到了该模型的有限阶段逼近算法，其中该算法涉及的状态是可列的．     

Models and algorithms for skip-free Markov decision processes on trees

We introduce a class of models for multidimensional control problems that we call skip-free Markov decision processes on trees. We describe and analyse an algorithm applicable to Markov decision processes of this type that are skip-free in the negative direction. Starting with the finite average cost case, we show that the algorithm combines the advantages of both value iteration and policy iteration—it is guaranteed to converge to an optimal policy and optimal value function after a finite number of iterations but the computational effort required for each iteration step is comparable with that for value iteration. We show that the algorithm can also be used to solve discounted cost models and continuous-time models, and that a suitably modified algorithm can be used to solve communicating models.     

Continuous time control of Markov processes on an arbitrary state space: Average return criterion

The paper deals with continuous time Markov decision processes on a fairly general state space. The economic criterion is the long-run average return. A set of conditions is shown to be sufficient for a constant g to be optimal average return and a stationary policy π¹ to be optimal. This condition is shown to be satisfied under appropriate assumptions on the optimal discounted return function. A policy improvement algorithm is proposed and its convergence to an optimal policy is proved.     

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.     

Finding optimal memoryless policies of POMDPs under the expected average reward criterion

In this paper, partially observable Markov decision processes (POMDPs) with discrete state and action space under the average reward criterion are considered from a recent-developed sensitivity point of view. By analyzing the average-reward performance difference formula, we propose a policy iteration algorithm with step sizes to obtain an optimal or local optimal memoryless policy. This algorithm improves the policy along the same direction as the policy iteration does and suitable step sizes guarantee the convergence of the algorithm. Moreover, the algorithm can be used in Markov decision processes (MDPs) with correlated actions. Two numerical examples are provided to illustrate the applicability of the algorithm.     

Equivalence of Lyapunov stability criteria in a class of Markov decision processes

We are concerned with Markov decision processes with countable state space and discrete-time parameter. The main structural restriction on the model is the following: under the action of any stationary policy the state space is acommunicating class. In this context, we prove the equivalence of ten stability/ergodicity conditions on the transition law of the model, which imply the existence of average optimal stationary policies for an arbitrary continuous and bounded reward function; these conditions include the Lyapunov function condition (LFC) introduced by A. Hordijk. As a consequence of our results, the LFC is proved to be equivalent to the following: under the action of any stationary policy the corresponding Markov chain has a unique invariant distribution which depends continuously on the stationary policy being used. A weak form of the latter condition was used by one of the authors to establish the existence of optimal stationary policies using an approach based on renewal theory.This research was supported in part by the Third World Academy of Sciences (TWAS) under Grant TWAS RG MP 898-152.     

Short-term booking of air cargo space

This paper proposes a stochastic dynamic programming model for a short-term capacity planning model for air cargo space. Long-term cargo space is usually acquired by freight forwarders or shippers many months ahead on a contract basis, and usually the forecasted demand is unreliable. A re-planning of cargo space is needed when the date draws nearer to the flight departure time. Hence, for a given amount of long-term contract space, the decision for each stage is the quantity of additional space required for the next stage and the decision planning model evaluates the optimal cost policy based on the economic trade-off between the cost of backlogged shipment and the cost of acquiring additional cargo space. Under certain conditions, we show that the return function is convex with respect to the additional space acquired for a given state and the optimal expected cost for the remaining stages is an increasing convex function with respect to the state variables. These two properties can be carried backward recursively and therefore the optimal cost policy can be determined efficiently.     

The stochastic shortest-path problem for Markov chains with infinite state space with applications to nearest-neighbor lattice chains

The aim of this paper is to solve the basic stochastic shortest-path problem (SSPP) for Markov chains (MCs) with countable state space and then apply the results to a class of nearest-neighbor MCs on the lattice state space $\mathbb Z \times \mathbb Z $ whose only moves are one step up, down, to the right or to the left. The objective is to control the MC, by suppressing certain moves, so as to minimize the expected time to reach a certain given target state. We characterize the optimal policies for SSPPs for general MCs with countably infinite state space, the main tool being a verification theorem for the value function, and give an algorithmic construction. Then we apply the results to a large class of examples: nearest-neighbor MCs for which the state space $\mathbb Z \times \mathbb Z $ is split by a vertical line into two regions inside which the transition probabilities are the same for every state. We give a necessary and sufficient condition for the so-called distance-diminishing policy to be optimal. For the general case in which this condition does not hold we develop an explicit finite construction of an optimal policy.     

Blackwell optimality in the class of stationary policies in Markov decision chains with a Borel state space and unbounded rewards

This paper is the first part of a study of Blackwell optimal policies in Markov decision chains with a Borel state space and unbounded rewards. We prove here the existence of deterministic stationary policies which are Blackwell optimal in the class of all, in general randomized, stationary policies. We establish also a lexicographical policy improvement algorithm leading to Blackwell optimal policies and the relation between such policies and the Blackwell optimality equation. Our technique is a combination of the weighted norms approach developed in Dekker and Hordijk (1988) for countable models with unbounded rewards and of the weak-strong topology approach used in Yushkevich (1997a) for Borel models with bounded rewards.     

Isotone optimal policies for structured Markov decision processes

This paper deals with a particular type of Markov decision process in which the state takes the form I = S × Z, where S is countable, and Z = {1, 2}, and the action space K = Z, independently of s?S. The state space I is ordered by a partial order ?, which is specified in terms of an integer valued function on S. The action space K has the natural order ≤. Under certain monotonicity and submodularity conditions it is shown that isotone optimal policies exist with respect to ? and ? on I and K respectively. The paper examines how the particular isotone structure may be used to simplify the usual policy space algorithm. A brief discussion of the usual successive approximation (value iteration) method, and also the extension of the ideas to semi-Markov decision processes, is given.     

A new strong optimality criterion for nonstationary Markov decision processes

This paper deals with a new optimality criterion consisting of the usual three average criteria and the canonical triplet (totally so-called strong average-canonical optimality criterion) and introduces the concept of a strong average-canonical policy for nonstationary Markov decision processes, which is an extension of the canonical policies of Herna′ndez-Lerma and Lasserre [16] (pages: 77) for the stationary Markov controlled processes. For the case of possibly non-uniformly bounded rewards and denumerable state space, we first construct, under some conditions, a solution to the optimality equations (OEs), and then prove that the Markov policies obtained from the OEs are not only optimal for the three average criteria but also optimal for all finite horizon criteria with a sequence of additional functions as their terminal rewards (i.e. strong average-canonical optimal). Also, some properties of optimal policies and optimal average value convergence are discussed. Moreover, the error bound in average reward between a rolling horizon policy and a strong average-canonical optimal policy is provided, and then a rolling horizon algorithm for computing strong average ε(>0)-optimal Markov policies is given.     

Adaptive aggregation for reinforcement learning in average reward Markov decision processes

We present an algorithm which aggregates online when learning to behave optimally in an average reward Markov decision process. The algorithm is based on the reinforcement learning algorithm UCRL and uses confidence intervals for aggregating the state space. We derive bounds on the regret our algorithm suffers with respect to an optimal policy. These bounds are only slightly worse than the original bounds for UCRL.     

马氏决策规划的加速逼近算法与最小方差问题

我们涉及的折扣马氏决策规划(有些著者称为马氏决策过程),具有状态空问与每个状态可用的决策集均为可数无穷集、次随机转移律族、有界报酬函数.给出了一个求(ε_)最优平稳策略的加速收敛逐次逼近算法,比White的逐次逼近算法更快地收敛于(ε_)最优解,并配合有非最优策略的检验准则,使算法更加得益. 设β为折扣因子,一般说β(或(ε,β))_最优平稳策略,往往是非唯一的,甚至与平稳策略类包含的策略数一样多.我们自然希望在诸β(或(ε,β))_最优平稳策略中寻求方差齐次地(关于初始状态)达(ε_)最小的策略.我们证明了这种策略确实存在,并给出了获得这种策略的算法.     

Borel状态空间非平稳MDP的平均方差准则

本文考虑具有 Ｂｏｒｅｌ状态空间和行动空间非平稳 ＭＤＰ的平均方差准则．首先,在遍历条件下,利用最优方程,证明了关于平均期望目标最优马氏策略的存在性．然后,通过构造新的模型,利用马氏过程的理论,进一步证明了在关于平均期望目标是最优的一类马氏策略中,存在一个马氏策略使得平均方差达到最小．作为本文的特例还得到了 Ｄｙｎｋｉｎ Ｅ． Ｂ．和 Ｙｕｓｈｋｅｖｉｃｈ Ａ． Ａ．及 Ｋｕｒａｎｏ Ｍ．等中的主要结果．     

Long time missions and the fuel-optimal attitude maneuvering in a swinging mode

The problem of fuel-optimal attitude maneuvering of a space vehicle (SV) with non-fixed time is considered. The state constraint related to the maintenance of artificial gravitation is imposed. This problem is especially important for long-time space missions. The attitude of the space vehicle is controlled by means of a pair of reactive engines which produce a single control torque with fixed direction in the body-fixed frame. An optimal solution is obtained in the class of trajectories belonging to “swinging mode” two-periodic sliding cycling regimes. The solution is found in analytical form and optimal synthesis is obtained. The short conference version of this paper was published in Proceedings of the IFAC Workshop GSCP-04, Pereyslavl-Zalessky, Russia, September 21–29, 2004. This paper was presented as an invited lecture at the International Conference on Control and Optimization in honor of Professor Boris Polyak, Institute of Control Science RAN, Russia, Moscow, May 19–20, 2005.