Markov decision problems and state-action frequencies
Markov decision problems and state-action frequencies
复制标题
马尔可夫决策问题和状态动作频率
DOI：
10.1137/0329043
复制
发表时间：
1991
影响因子：
2.2
通讯作者：
A. Shwartz
中科院分区：
文献类型：
--
作者：
E. Altman;A. Shwartz
考虑一个具有可数状态和动作空间的可控马尔可夫链。确定了决定平均成本函数值的基本量。在某些规则条件下，这些是一组数字，每个状态-操作对对应一个，描述每个状态中每个操作的相对使用次数。这些“条件频率”是按路径定义的，用于确定“状态-动作频率”，在有限情况下，已知这些频率决定了成本。这被扩展到可计数的情况，允许无界的成本。证明了频率空间是紧致的和凸的，并且用平稳确定性策略识别极值点。给出了若干优化问题的最优性搜索可能被限制于平稳策略的条件。这些问题包括标准的马尔可夫决策过程，以及约束优化（在平均成本函数方面）和变量敏感优化。给出了一个应用于排队问题的结果，这些结果暗示了约束优化问题中最优策略的存在性和显式计算。条件频率的路径定义意味着它们的值可以直接控制；此外，它们只依赖于控制的极限行为。这可以直接应用于马尔可夫链的自适应控制，包括约束下的自适应控制。
Consider a controlled Markov chain with countable state and action spaces. Basic quantities that determine the values of average cost functionals are identified. Under some regularity conditions, these turn out to be a collection of numbers, one for each state-action pair, describing for each state the relative number of uses of each action. These "conditional frequencies," which are defined pathwise, are shown to determine the "state-action frequencies" that, in the finite case, are known to determine the costs. This is extended to the countable case, allowing for unbounded costs. The space of frequencies is shown to be compact and convex, and the extreme points are identified with stationary deterministic policies. Conditions under which the search for optimality in several optimization problems may be restricted to stationary policies are given. These problems include the standard Markov decision process, as well as constrained optimization (both in terms of average cost functionals) and variability-sensitive optimization. An application to a queueing problem is given, where these results imply the existence and explicit computation of optimal policies in constrained optimization problems. The pathwise definition of the conditional frequencies implies that their values can be controlled directly; moreover, they depend only on the limiting behavior of the control. This has immediate application to adaptive control of Markov chains, including adaptive control under constraints.