Markov决策过程：理论与应用探索

需积分: 10 84 浏览量更新于2024-07-19 收藏 3.67MB PDF 举报

Markov决策过程（MDPs）是一种强大的数学工具，最初在20世纪60年代发展起来，用于解决在随机环境下多期动态决策问题。MDPs的核心包括离散时间MDP、连续时间MDP和半马尔可夫决策过程，这些分支为模型化各种实际问题提供了基础框架。它们能够处理不确定性，例如部分可观测的MDPs（POMDPs），适应性MDPs，以及在随机环境中的MDPs，还考虑了多目标、约束或参数不精确的情况。 MDPs的应用范围广泛，涉及通信、信号处理、人工智能领域，如强化学习算法中的决策制定；在运营管理中，如在调度和制造系统中优化资源分配；在系统工程中，如离散事件系统的控制策略设计；在经济学中，用于研究随机经济环境下的决策优化。《马尔可夫决策过程及其应用》这本书，由胡启英教授和日本京都大学的叶吾一教授合著，收录于Advances in Mechanics and Mathematics系列中，展示了MDPs理论的深入探讨以及在实际问题中的具体应用实例。书中详细介绍了MDP的基本概念，包括状态转移概率、奖励函数、价值函数和策略等核心元素，以及如何通过动态规划方法求解最优策略。它还涵盖了数值解法，如值迭代、政策迭代，以及如何处理复杂环境下的计算挑战。此外，书中还讨论了MDPs与其他数学工具（如概率论、线性代数和优化理论）的融合，以增强模型的实用性。 MDPs的重要性在于它们提供了一种结构化的框架，使得决策者能够在面对复杂和不确定的未来时做出最优选择。随着计算能力的提升和技术的发展，MDPs在实时决策系统、自动驾驶、医疗健康管理和智能投资等领域展现出更大的潜力。马尔可夫决策过程是现代信息技术和决策科学中的基石，其理论和应用将继续推动各个行业的创新与进步。

2 MARKOV DECISION PROCESSES WITH THEIR APPLICATIONS

on A(i

). Taking a policy π means that if a history h

occurs at period n

then the action is chosen according to the probability distribution π

(·|h

).If

(·|h

)=π

(·|i

) depends only on n and the last state i

for each h

, then

we call π a Markov policy, the set of which is denoted by Π

. Under Markov

policies, the action is chosen irrespectively of the system’s past. A special case

of the type of Markov policies is that of stochastic stationary policies, which are

deﬁned as π

(·|i

)=π

(·|i

) for each n. The set of all stochastic stationary

policies is denoted by Π

. On the other hand, if for each n =0, 1,..., there

is f

∈ F such that π

(i)|i)=1for all i ∈ S (in this case, we write

π =(f

,...)), then such a policy π is called a deterministic Markov policy,

the set of which is denoted by Π

. A stationary deterministic Markov policy

π =(f,f,...) for some f ∈ F is simply called a stationary policy. We write

it as f

∞

or f . Surely, a stationary policy corresponds to a decision function.

So, we view F as the set of all stationary policies.

For n ≥ 0, let X

and ∆

be the state and the action chosen at period n,

respectively. Then it can be shown that the stochastic process {X

, ∆

,n≥ 0}

is well deﬁned under any policy π ∈ Π. Especially, under a Markov policy

π ∈ Π

, {X

, ∆

,n ≥ 0} is a discrete time Markov chain [52]. For each

π ∈ Π and i ∈ S, let P

π,i

and E

π,i

be, respectively, the probability and the

expectation corresponding to the stochastic process {X

, ∆

,n ≥ 0} under

policy π with the initial state i.

The system will receive a reward r(X

, ∆

) at period n. This reward is

random under any policy. Then, how to compare different policies? This can

be answered by the decision criteria. The basic criteria are the discounted

expected total reward and the average criterion. The former applies to either

ﬁnite horizons or inﬁnite horizons whereas the latter only applies to inﬁnite

horizons.

Criterion 1. Discounted expected total reward in ﬁnite horizons.

This criterion is deﬁned by

β,N

(π, i)=

N−1



n=0

π,i

r(X

, ∆

),π∈ Π,i∈ S.

Here N is a ﬁnite integer that represents the number of horizons and β is a

positive constant that represents a discount factor. In general, β ∈ (0, 1].If

we write ρ as the interest rate in the market, then the discount factor and the

interest rate have the following relationship,

β =

1+ρ

The meaning of β is that one unit reward at period n values β

at period 0.

4 MARKOV DECISION PROCESSES WITH THEIR APPLICATIONS

There are three basic types of MDPs: discrete time MDPs [5], continuous

time MDPs (CTMDPs) [82], and semi-Markov decision processes (SMDPs)

[56], and [81]. As presented in the discussion above, DTMDPs are based on

discrete time Markov chains. Similarly, CTMDPs are based on continuous time

Markov chains and SMDPs are based on semi-Markov processes. In addition,

based on the basic types of MDPs, several generalized MDPs were presented

in the literature, such as partially observable MDPs [18], adaptive MDPs [109],

and constrained MDPs [50]. Interested readers may refer to a survey paper

[148] or a handbook [39].

Optimal control of other types of Markov chains, such as diffusion proces-

ses, is mainly part of optimal control theory and is also studied extensively,

see, for example, [24], [11], and [43]. Recently, a new model called the hybrid

system has been presented. This model combines event-driven dynamics and

time-driven dynamics, for example, see [26]. In Chapter 6 of this book, we

study MDPs in stochastic environments, where the inﬂuence of environments

on systems is considered.

MDPs has been applied to many areas that include communications (dy-

namic routing problems, multiple-access problems [96] and [33], ﬂow control

[13] and [112], artiﬁcial intelligence [16], stochastic scheduling and dynamic

control of manufacturing systems [32] and [84], discrete event systems [17],

management (such as optimal replacement, production/inventory [2], product

pricing [102] and [34]), and ﬁnance (dynamic asset pricing [31]). One can see

some applications in books [69] and [124] and a survey paper [147].

2. Overview of the Book

The standard results for MDP models include the following four aspects.

1. The model is well deﬁned; that is, the stochastic process under consideration

is well deﬁned (or regular in some cases). Moreover, the criterion is well

deﬁned and often is ﬁnite.

2. The optimal value function satisﬁes the optimality equation.

3. A stationary policy achieving the supremum of the optimality equation will

be optimal.

4. Algorithms to compute the optimal value function/approximating optimal

policies are presented.

The main methodology for studying a MDP model to obtain the standard

results is as follows.

• First, a set of conditions for the model is presented under which the model

is well deﬁned.

• Second, the optimal value function is shown to be a solution or the unique

solution of the optimality equation in a certain region (then we say that the

Introduction 5

optimality equation is true). For example, the optimality equation for the

total reward criterion is as follows,

(i) = sup

a∈A(i)

{r(i, a)+β



(a)V

(j)},i∈ S.

• Third, any policy that achieves the supremum in the optimality equation

is shown to be optimal, or more generally, any stationary policy achieving

the ε-supremum of the optimality equation will be ε



-optimal, where ε



is a

function of ε and tends to zero when ε tends to zero.

• Finally, algorithms may be presented to obtain the optimal value and an (ap-

proximate) optimal policy. However, the basic algorithms in MDPs are just

successive approximation, policy improvement, and linear programming.

In the literature, to ensure that the model is well deﬁned, some conditions

are often imposed. For the total reward criterion, there are three classical

cases: (a) the discount factor belongs to (0, 1) and the rewards are uniformly

bounded, (b) the discount factor is one and the rewards are nonnegative, and

models with cases (a), (b), and (c) are called discounted MDP models, positive

MDP models, and negative MDP models, respectively. But these three cases

are too strong. In order to weaken them, various conditions are presented in

the literature to suit various practical problems, especially for discrete time

MDP models and semi-Markov decision process models. For example, for

the discounted criterion, Lippman [92] presented a set of conditions on the

unbounded reward functions for a SMDP model, whereas Harrison [49] and

Wessels [145] presented conditions for DTMDP models. Hu and Hu [80]

combined the conditions presented by the above three authors and presented a

weaker one for a DTMDP model. All these conditions are sufﬁcient conditions

for studying MDP models.

Conversely to the above methodology, in this book, we try to study MDPs

under the condition that the model is well deﬁned. More precisely, we try to

show the standard results 2, 3, and 4 above by assuming the standard result 1.

This is explored in Chapters 2 and 4 for DTMDPs and CTMDPs, respectively.

Moreover, this methodology is applied to study optimal control problems in

discrete event systems in Chapters 7 and 8. This is the ﬁrst idea of this book.

The second idea of this book is to transform systematically the CTMDPs

and SMDPs into DTMDPs for the discounted criterion, the total reward cri-

terion, and the average criterion. In the literature, main studies on CTMDPs,

SMDPs, and DTMDPs are done separately, though some transformation were

presented. Schweitzer [120], Hordijk et al. [54], and Federgruen and Tijms

[36] presented transformations from SMDPs into DTMDPs for the average cri-

terion. For CTMDP models, Serfozo [126] presented a transformation for the

6 MARKOV DECISION PROCESSES WITH THEIR APPLICATIONS

discounted criterion with bounded transition rates among stationary policies,

based on probability properties of Markov chains. Hu [57] presented a transfor-

mation for the discounted criterion with unbounded transition rates. Under his

transformation, the corresponding optimality equation and the discounted crite-

rion among stationary policies in the CTMDP model and those in the DTMDP

model are equivalent. So the results for CTMDPs can be obtained directly from

those for DTMDPs. In this book, we focus on the method of transformation

for the discounted criterion, the total reward criterion, and the average crite-

rion. It seems that this is the ﬁrst time CTMDPs and SMDPs have been studied

systematically by transforming them into DTMDPs. The transformations are

based only on basic algebraic computations. This idea is contained in Section

3 of Chapter 4 for CTMDPs, Chapter 5 for SMDPs, and also appears for MDPs

in stochastic environments in Chapter 6.

The third idea is to consider the inﬂuence of environments on systems. Sys-

tems described by the traditional MDP models are all closed in the meaning

that no inﬂuence of the environments to the systems is considered. But in prac-

tice, many systems are inﬂuenced by their environments. Some other areas

had considered the inﬂuence of the environments, for example, Neuts [98] for

queueing systems and Cao [15] for reliability systems. We present MDP mod-

els in stochastic environments in this book. These models can describe such a

system that itself can be modeled by a Markov decision process, but the system

is inﬂuenced by its environment which is modeled by a semi-Markov process.

The inﬂuence includes changing the MDP model or its parameters, inducing

an instantaneous state transition of the system, and letting the system incur a

reward. This idea is explored in Chapter 6. We also apply this type of MDP

model to describe and prove optimal replacement problems in Chapter 9.

3. Organization of the Book

The rest of the book is organized as follows.

In Chapter 2, we study a discrete time MDP model with the total reward

criterion, where the state space is countable, the action set is arbitrary but

nonempty and is endowed with a measurable structure, the reward function is

extended real-valued, and the discount factor is any real number. The condition

that the model is well deﬁned here is just that the criterion, as a series, is well

deﬁned under each policy and each initial state.

We ﬁrst show that the state space can be divided into two parts. In the ﬁrst part

the optimal value is positive inﬁnite and there is an optimal stochastic stationary

policy, and in the second part the reward function is ﬁnite and bounded above

over the action set at each state. Hence, this normalizes the original model,

where the reward function is extended real-valued, into a submodel, where the

reward function is real-valued and bounded above over the action set at each

state. Thus, it sufﬁces to discuss the MDP model in the second part. In this

剩余304页未读，继续阅读

zaizhezhibin

粉丝: 0
资源: 2

Markov决策过程：理论与应用探索

Markov Decision Process.pdf

Markov Decision Process — Tutorial

MARKOV DECISION PROCESSES WITH THEIR APPLICATIONS

time difference learning

Sequential Decision Making

python MDPs

马尔可夫决策过程（Markov Decision Process，MDP）

Markov Decision Process

Python求解贝尔曼方程

Q-learning python

最新资源