摘要 Abstract
对未来事件影响进行折现是经济学中的一个关键范式,并广泛应用于计算机科学模型中,例如博弈、马尔可夫决策过程(MDPs)、强化学习和自动机。虽然单个博弈或MDP可能允许存在多个不同的折扣因子,但非确定性折扣和自动机(NDAs)的研究仅限于单一折扣因子。已知每个具有整数折扣因子的NDAs类都具有良好的计算特性:在确定化和代数运算(min、max、加法和减法)下封闭,并且其基本决策问题(如自动机等价性和包含性)存在算法。将整数折扣因子扩展到任意有理数时,大部分这些良好特性会丢失。我们定义并分析了每条转移可以具有不同整数折扣因子的非确定性折扣和自动机(积分NMDAs)。我们证明,对于任意选择的折扣因子,积分NMDAs在确定化和代数运算下不封闭,其包含问题是不可判定的。然后,我们定义并分析了一类受限的积分NMDAs,称为整洁的NMDAs,其中折扣因子的选择取决于所读单词的前缀。它们的特殊情况包括将折扣因子与动作(字母)或经过的时间相关联的NMDAs。我们证明,对于定义折扣因子选择的任何函数$\theta$,$\theta$-NMDAs类在所有上述NDAs的良好特性方面均表现出色,并且所需决策问题的复杂性相同。整洁的NMDAs在表达能力上也等价于具有任意折扣因子选择的确定性积分NMDAs。
Discounting the influence of future events is a key paradigm in economics and it is widely used in computer-science models, such as games, Markov decision processes (MDPs), reinforcement learning, and automata. While a single game or MDP may allow for several different discount factors, nondeterministic discounted-sum automata (NDAs) were only studied with respect to a single discount factor. It is known that every class of NDAs with an integer as the discount factor has good computational properties: It is closed under determinization and under the algebraic operations min, max, addition, and subtraction, and there are algorithms for its basic decision problems, such as automata equivalence and containment. Extending the integer discount factor to an arbitrary rational number, loses most of these good properties. We define and analyze nondeterministic discounted-sum automata in which each transition can have a different integral discount factor (integral NMDAs). We show that integral NMDAs with an arbitrary choice of discount factors are not closed under determinization and under algebraic operations and that their containment problem is undecidable. We then define and analyze a restricted class of integral NMDAs, which we call tidy NMDAs, in which the choice of discount factors depends on the prefix of the word read so far. Among their special cases are NMDAs that correlate discount factors to actions (alphabet letters) or to the elapsed time. We show that for every function $\theta$ that defines the choice of discount factors, the class of $\theta$-NMDAs enjoys all of the above good properties of NDAs with a single integral discount factor, as well as the same complexity of the required decision problems. Tidy NMDAs are also as expressive as deterministic integral NMDAs with an arbitrary choice of discount factors.