Online Learning in Markov Decision Processes with Adversarially Chosen Transition Probability Distributions
Online Learning in Markov Decision Processes with Adversarially Chosen Transition Probability Distributions
复制标题
DOI：
--
复制
发表时间：
2013-03
期刊：
影响因子：
--
通讯作者：
Yasin Abbasi-Yadkori;P. Bartlett;Csaba Szepesvari
中科院分区：
文献类型：
--
作者：
Yasin Abbasi-Yadkori;P. Bartlett;Csaba Szepesvari
研究了当对手同时选择转移分布和损失函数时，马尔可夫决策过程的在线学习问题。我们给出了一个算法，在混合假设下，对于一组比较策略II，该算法可以获得O(√T LOG|II|+LOG|II|)个遗憾，并且该遗憾与状态和动作空间的大小无关。当样本路径上的期望可以有效地计算并且比较集II具有多项式大小时，该算法是有效的。我们还考虑了插段式对抗性在线最短路径问题。这里，在每一集中，对手可以选择具有所标识的开始和结束节点的加权有向无环图。学习算法的目标是选择一条从开始到结束节点遍历时损失最小的路径。在每一集的结尾，向学习算法揭示损失函数(由边上的权重给出)。目标是最大限度地减少对选择路径的固定策略的遗憾。此问题是在线MDP问题的特例。结果表明，对于随机选择的图和对抗性损失，该问题可以得到有效的解决。我们证明，对于对抗性图和随机选择的损失，该问题也可以有效地求解。当图和损失都被对抗性地选择时，我们证明了为对抗性在线最短路径问题(因此对于对抗性MDP问题)设计有效的算法与学习带噪声的奇偶校验一样困难，这是一个众所周知的用于设计高效密码方案的困难问题。最后，我们给出了一个有效的算法，该算法的遗憾程度与不同图的数目成线性关系。
We study the problem of online learning Markov Decision Processes (MDPs) when both the transition distributions and loss functions are chosen by an adversary. We present an algorithm that, under a mixing assumption, achieves O(√T log |II| + log |II|) regret with respect to a comparison set of policies II. The regret is independent of the size of the state and action spaces. When expectations over sample paths can be computed efficiently and the comparison set II has polynomial size, this algorithm is efficient. We also consider the episodic adversarial online shortest path problem. Here, in each episode an adversary may choose a weighted directed acyclic graph with an identified start and finish node. The goal of the learning algorithm is to choose a path that minimizes the loss while traversing from the start to finish node. At the end of each episode the loss function (given by weights on the edges) is revealed to the learning algorithm. The goal is to minimize regret with respect to a fixed policy for selecting paths. This problem is a special case of the online MDP problem. It was shown that for randomly chosen graphs and adversarial losses, the problem can be efficiently solved. We show that it also can be efficiently solved for adversarial graphs and randomly chosen losses. When both graphs and losses are adversarially chosen, we show that designing efficient algorithms for the adversarial online shortest path problem (and hence for the adversarial MDP problem) is as hard as learning parity with noise, a notoriously difficult problem that has been used to design efficient cryptographic schemes. Finally, we present an efficient algorithm whose regret scales linearly with the number of distinct graphs.