在谎言预言者下预测序列，实现近最优的长期表现。
Sequence prediction under a lying oracle
- 用比较查询模拟谎言预言者，设计自适应预测策略。
- 在随机与对抗环境中均达到对数级后悔上界。
- 适合需要抗欺骗预测的智能系统研究者。
我们研究了对 m 元序列的顺序预测问题：每一轮中，(i) 环境从 m 元字母表中选择一个结果，(ii) 学习者在不知晓环境结果的情况下，选择一个该字母表上的概率分布，(iii) 学习者根据其对实际结果分配的概率承担代价。所考虑的代价函数捕捉了通过向一个说谎的预言者进行比较查询来预测环境结果时的复杂性。针对随机和对抗性环境，我们分别提出了算法，并建立了对数级别的后悔上界。
原文摘要 · Abstract (English)
We consider the problem of sequential prediction of an $m$-ary sequence, where at each epoch, (i) the environment selects an outcome from an $m$-ary alphabet, (ii) the learner selects a probability distribution over the same alphabet (unaware of the outcome generated by the environment), and finally, (iii) the learner incurs a cost that depends on the probability assigned to the outcome. The cost function we consider captures the complexity of predicting the outcome generated by the environment, in a scenario where the aforementioned prediction is performed via comparative queries to a lying oracle. We consider both stochastic and adversarial environments, propose algorithms for both settings, and establish logarithmic upper bounds on their regret.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。