Finite-Time Regret Bounds for REINFORCE in Tabular MDPs

We establish finite-time expected cumulative regret bounds for REINFORCE in finite-horizon tabular MDPs with unknown transitions and bounded deterministic rewards. The central challenge is that policies at earlier stages determine which states are visited at later stages, while inaccurate policies at later stages can make optimal actions at earlier stages appear unfavorable. We tackle this challenge through two contributions. First, we bound the value errors that can reduce the probabilities of optimal actions by the regret incurred at later stages. This bound allows a geometrically weighted potential to control cumulative regret. Second, we show that reducing an action’s probability requires cumulative use of that action, yielding quantitative bounds on state visitation along the mean flow. Together with stochastic tracking and probability control, these contributions yield $O_{\mathcal{M}}({\log }^{2}K)$ expected regret from zero initialization, using one trajectory per update and no explicit exploration or regularization. The step size is $\eta =\bar{\eta }/\log K$, with an instance-dependent scale $\bar{\eta }$, and remains constant within each run. A step size chosen using only the episode budget yields $O_{\mathcal{M}}({\log }^{3}K)$ regret. Finally, deterministic two-action chains exhibit linear expected regret over an initial window whose length grows as an exponential tower in the horizon, under a sufficiently small uniform step-size cap.