Deterministic MDPs with Adversarial Rewards and Bandit Feedback
Deterministic MDPs with Adversarial Rewards and Bandit Feedback
复制标题
具有对抗性奖励和强盗反馈的确定性 MDP
DOI：
--
复制
发表时间：
2012
期刊：
影响因子：
--
通讯作者：
Ambuj Tewari
中科院分区：
文献类型：
--
作者：
R. Arora;O. Dekel;Ambuj Tewari
我们考虑具有确定性状态转换动态的马尔可夫决策过程，敌对生成的奖励在每一轮之间任意变化，以及强盗反馈模型，其中决策者仅观察其收到的奖励。在此背景下，我们提出了一种新颖且高效的在线决策算法，名为马可波罗（MarcoPolo）。在对过渡动态结构的温和假设下，我们证明马可波罗对事后最佳确定性策略的遗憾是 O(T3/4 √log T)。具体来说，我们的分析并不依赖于严格的单链假设，该假设主导了该主题之前的大部分工作。
We consider a Markov decision process with deterministic state transition dynamics, adversarially generated rewards that change arbitrarily from round to round, and a bandit feedback model in which the decision maker only observes the rewards it receives. In this setting, we present a novel and efficient online decision making algorithm named MarcoPolo. Under mild assumptions on the structure of the transition dynamics, we prove that MarcoPolo enjoys a regret of O(T3/4 √log T) against the best deterministic policy in hindsight. Specifically, our analysis does not rely on the stringent unichain assumption, which dominates much of the previous work on this topic.