State-Separated SARSA: A Practical Sequential Decision-Making Algorithm with Recovering Rewards

本文研究的是恢复赌博机（Pike-Burke & Grunewalder, 2019）的情境，其中奖励取决于自上次拉动手臂以来经过的轮数，而许多多臂赌博算法假定所有手臂的奖励在每轮中都是恒定的，这种假设在许多实际情况下并不成立。我们提出了一种新的强化学习（RL）算法，专门针对这种情况，名为状态分离 SARSA（SS-SARSA）算法，将轮数视为状态。SS-SARSA算法通过减少Q-learning / SARSA所需的状态组合数量来实现高效学习，对于大规模RL问题，Q-learning / SARSA经常遭受组合问题。此外，它对奖励结构做出最少的假设，并提供较低的计算复杂度。此外，我们证明了在温和假设下渐近收敛到最优策略。模拟研究证明了我们的算法在各种情况下的卓越性能。

解决问题：论文试图解决回收赌博机中奖励与轮数相关的问题，提出一种新的强化学习算法。这是一个新问题。

关键思路：论文中提出的算法是State-Separate SARSA (SS-SARSA)，将轮数作为状态，通过减少状态组合来实现有效学习，同时对奖励结构做出了最少的假设。

其他亮点：论文的算法在不同的设置下表现出优异的性能，实验设计合理，使用了开源数据集，并证明了渐进收敛到最优策略。值得进一步研究。

相关研究：最近的相关研究包括多臂赌博机算法和强化学习算法，如UCB、Thompson Sampling、Q-learning、SARSA等。