A Short Note on Soft-max and Policy Gradients in Bandits Problems
This work addresses theoretical understanding of policy gradients in bandits, but it is incremental as it builds on existing differential equation approaches.
The paper tackles the analysis of policy gradient algorithms in bandit problems by providing a Lyapunov function argument to derive a regret bound for the soft-max ordinary differential equation and a similar result for another algorithm, with potential extensions to stochastic cases.
This is a short communication on a Lyapunov function argument for softmax in bandit problems. There are a number of excellent papers coming out using differential equations for policy gradient algorithms in reinforcement learning \cite{agarwal2019optimality,bhandari2019global,mei2020global}. We give a short argument that gives a regret bound for the soft-max ordinary differential equation for bandit problems. We derive a similar result for a different policy gradient algorithm, again for bandit problems. For this second algorithm, it is possible to prove regret bounds in the stochastic case \cite{DW20}. At the end, we summarize some ideas and issues on deriving stochastic regret bounds for policy gradients.