REVIEW 4 cited by
Towards Principled, Practical Policy Gradient for Bandits and Tabular MDPs
Not yet reviewed by Pith; the record is open.
This paper has not been read by Pith yet. Machine review is queued; the pith claim, tier, and objections will appear here once it completes.
SPECIMEN: schema-true, not a live event
T0 review · schema-true
One-sentence machine reading of the paper's core claim.
pith:XXXXXXXX · record.json · timestamp
Signed reviews
read the original abstract
We consider (stochastic) softmax policy gradient (PG) methods for bandits and tabular Markov decision processes (MDPs). While the PG objective is non-concave, recent research has used the objective's smoothness and gradient domination properties to achieve convergence to an optimal policy. However, these theoretical results require setting the algorithm parameters according to unknown problem-dependent quantities (e.g. the optimal action or the true reward vector in a bandit problem). To address this issue, we borrow ideas from the optimization literature to design practical, principled PG methods in both the exact and stochastic settings. In the exact setting, we employ an Armijo line-search to set the step-size for softmax PG and demonstrate a linear convergence rate. In the stochastic setting, we utilize exponentially decreasing step-sizes, and characterize the convergence rate of the resulting algorithm. We show that the proposed algorithm offers similar theoretical guarantees as the state-of-the art results, but does not require the knowledge of oracle-like quantities. For the multi-armed bandit setting, our techniques result in a theoretically-principled PG algorithm that does not require explicit exploration, the knowledge of the reward gap, the reward distributions, or the noise. Finally, we empirically compare the proposed methods to PG approaches that require oracle knowledge, and demonstrate competitive performance.
Forward citations
Cited by 4 Pith papers
-
On the Policy Convergence of Policy Mirror Descent Methods
Unregularized PMD with any constant step size converges to a limiting optimal policy for general decomposable Legendre mirror maps, with behavior governed by differentiability of ψ at 0 and 1.
-
Rethinking the Global Convergence of Softmax Policy Gradient with Linear Function Approximation
Under explicit feature-ordering conditions, softmax policy gradient with linear function approximation converges to the optimal policy in stochastic bandits even with non-zero approximation error.
-
Small steps no more: Global convergence of stochastic gradient bandits for arbitrary learning rates
The softmax gradient bandit converges almost surely to the optimal action for any constant learning rate, removing the small-learning-rate restriction of prior work.
-
Fast Convergence of Softmax Policy Mirror Ascent
Softmax policy mirror ascent is a normalization-free mirror ascent on logits that converges linearly in tabular MDPs and linearly to a neighborhood with function approximation.
Discussion (0). Continue with ORCID to comment.