State-Separated SARSA: A Practical Sequential Decision-Making Algorithm
  with Recovering Rewards
Yuto Tanimoto Kenji Fukumizu
While many multi-armed bandit algorithms assume that rewards for all arms are
constant across rounds, this assumption does not hold in many real-world
scenarios. This paper considers the setting of recovering bandits (Pike-Burke &
Grunewalder, 2019), where the reward depends on the number of rounds elapsed
since the last time an arm was pulled. We propose a new reinforcement learning
(RL) algorithm tailored to this setting, named the State-Separate SARSA
(SS-SARSA) algorithm, which treats rounds as states. The SS-SARSA algorithm
achieves efficient learning by reducing the number of state combinations
required for Q-learning/SARSA, which often suffers from combinatorial issues
for large-scale RL problems. Additionally, it makes minimal assumptions about
the reward structure and offers lower computational complexity. Furthermore, we
prove asymptotic convergence to an optimal policy under mild assumptions.
Simulation studies demonstrate the superior performance of our algorithm across
various settings.