Policy regret is a well established notion of measuring the performance of an
online learning algorithm against an adaptive adversary. We study restrictions
on the adversary that enable efficient minimization of the \emph{complete
policy regret}, which is the strongest possible version of policy regret. We
identify a gap in the current theoretical understanding of what sorts of
restrictions permit tractability in this challenging setting. To resolve this
gap, we consider a generalization of the stochastic multi armed bandit, which
we call the \emph{tallying bandit}. This is an online learning setting with an
$m$-memory bounded adversary, where the average loss for playing an action is
an unknown function of the number (or tally) of times that the action was
played in the last $m$ timesteps. For tallying bandit problems with $K$ actions
and time horizon $T$, we provide an algorithm that w.h.p achieves a complete
policy regret guarantee of $\tilde{\mathcal{O}}(mK\sqrt{T})$, where the
$\tilde{\mathcal{O}}$ notation hides only logarithmic factors. We additionally
prove an $\tilde\Omega(\sqrt{m K T})$ lower bound on the expected complete
policy regret of any tallying bandit algorithm, demonstrating the near
optimality of our method.

研究了限制对手策略的措施，旨在实现最强版本的策略后悔，即完全策略后悔。提出概念式为 “计票老虎机” 的在线学习算法，并针对该算法提供了一种具有可接受保证的算法，证明了算法的近似最优性。