Designing computationally efficient exploration strategies for on-policy first-order methods that attain optimal $\mathcal{O}(1/\epsilon^2)$ sample complexity remains open for solving Markov decision processes (MDP). This manuscript provides an answer to this question from a perspective of simplicity, by showing that whenever exploration over the state space is implied by the MDP structure, there seems to be little need for sophisticated exploration strategies. We revisit a stochastic policy gradient method, named stochastic policy mirror descent, applied to the infinite horizon, discounted MDP with finite state and action spaces. Accompanying SPMD we present two on-policy evaluation operators, both simply following the policy for trajectory collection with no explicit exploration, or any form of intervention. SPMD with the first evaluation operator, named value-based estimation, tailors to the Kullback-Leibler (KL) divergence. Provided the Markov chains on the state space of generated policies are uniformly mixing with non-diminishing minimal visitation measure, an $\tilde{\mathcal{O}}( 1 / \epsilon^2)$ sample complexity is obtained with a linear dependence on the size of the action space. SPMD with the second evaluation operator, named truncated on-policy Monte Carlo, attains an $\tilde{\mathcal{O}}(\mathcal{H}_{\mathcal{D}} / \epsilon^2)$ sample complexity, with the same assumption on the state chains of generated policies. We characterize $\mathcal{H}_{\mathcal{D}}$ as a divergence-dependent function of the effective horizon and the size of the action space, which leads to an exponential dependence of the latter two quantities for the KL divergence, and a polynomial dependence for the divergence induced by negative Tsallis entropy. These obtained sample complexities seem to be new among on-policy stochastic policy gradient methods without explicit explorations.

本文所提出的新算法不依赖于探索策略，通过引入两个新的基于策略的评估算符和对SPMD算法的新颖分析，实现了在线策略梯度方法的样本复杂度的近似上界，无需显式探索，可以避免在寻找最优策略时反复执行潜在的高风险动作，具有更强的收敛性能。

政策镜像下降算法固有地探索动作空间