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

arXiv: https://arxiv.org/abs/2403.11520 · HTML: https://mlsanity.com/paper/2403.11520/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Placed in RL theory and sample complexity, one of 15 directions in Deep reinforcement learning methods.
- Builds on 12 of its 36 references that are in the map.
- First posted on arXiv 18 Mar 2024.

## Placed in

- Deep reinforcement learning methods / [RL theory and sample complexity](https://mlsanity.com/deeprl/rl-theory-and-sample-complexity/)

## Builds on (most cited first, 12 of 12)

- [Proximal Policy Optimization Algorithms](https://mlsanity.com/paper/1707.06347/) (2017)
- [Soft Actor-Critic: Off-Policy Maximum Entropy Deep Reinforcement Learning with a Stochastic Actor](https://mlsanity.com/paper/1801.01290/) (2018)
- [Continuous control with deep reinforcement learning](https://mlsanity.com/paper/1509.02971/) (2015)
- [Weighted Linear Bandits for Non-Stationary Environments](https://mlsanity.com/paper/1909.09146/) (2019)
- [Rotting Bandits](https://mlsanity.com/paper/1702.07274/) (2017)
- [A Change-Detection based Framework for Piecewise-stationary Multi-Armed Bandit Problem](https://mlsanity.com/paper/1711.03539/) (2017)
- [Efficient Automatic CASH via Rising Bandits](https://mlsanity.com/paper/2012.04371/) (2020)
- [Recovering Bandits](https://mlsanity.com/paper/1910.14354/) (2019)
- [Rebounding Bandits for Modeling Satiation Effects](https://mlsanity.com/paper/2011.06741/) (2020)
- [Stochastic Rising Bandits](https://mlsanity.com/paper/2212.03798/) (2022)
- [A Last Switch Dependent Analysis of Satiation and Seasonality in Bandits](https://mlsanity.com/paper/2110.11819/) (2021)
- [Fatigue-Aware Ad Creative Selection](https://mlsanity.com/paper/1908.08936/) (2019)

## Abstract (arXiv)

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.