DeepTOP: Deep Threshold-Optimal Policy for MDPs and RMABs
This work addresses control and bandit problems by exploiting monotone properties for more efficient policy learning, representing an incremental improvement with specific algorithmic gains.
The paper tackles the problem of learning optimal threshold policies for control problems, proving that their policy gradients have a simple expression and using this to develop an off-policy actor-critic algorithm that significantly outperforms other reinforcement learning algorithms in simulations. It also shows that the Whittle index for restless multi-armed bandits is equivalent to an optimal threshold policy, leading to a faster algorithm for learning the Whittle index compared to recent indirect methods.
We consider the problem of learning the optimal threshold policy for control problems. Threshold policies make control decisions by evaluating whether an element of the system state exceeds a certain threshold, whose value is determined by other elements of the system state. By leveraging the monotone property of threshold policies, we prove that their policy gradients have a surprisingly simple expression. We use this simple expression to build an off-policy actor-critic algorithm for learning the optimal threshold policy. Simulation results show that our policy significantly outperforms other reinforcement learning algorithms due to its ability to exploit the monotone property. In addition, we show that the Whittle index, a powerful tool for restless multi-armed bandit problems, is equivalent to the optimal threshold policy for an alternative problem. This observation leads to a simple algorithm that finds the Whittle index by learning the optimal threshold policy in the alternative problem. Simulation results show that our algorithm learns the Whittle index much faster than several recent studies that learn the Whittle index through indirect means.