In reinforcement learning, the performance of an algorithm is typically evaluated along two dimensions: computational and statistical complexity. While theoretical researchers often prioritize statistical efficiency—minimizing the number of samples needed to reach the desired accuracy—practitioners focus mainly on reducing computational costs, such as training time and resource consumption. Bridging these two perspectives requires algorithms able to deliver strong statistical guarantees while remaining computationally efficient in practice. In this paper, we introduce MetaStep, a meta-algorithm designed to enhance state-of-the-art RL algorithms by improving their computational efficiency while maintaining competitive sample efficiency. MetaStep is based on the novel notion of W-step Markov decision process (MDP), where, instead of performing a single action and transitioning to the next state, the agent executes a sequence of W actions before observing the resulting state and collecting the discounted W-step cumulative reward. First, we provide a theoretical analysis of the suboptimality introduced in the optimal policy performance when planning in a W-MDP, highlighting the impact of the environment stochasticity. Second, we apply MetaStep to GPOMDP, a well-known policy gradient method, and theoretically investigate the advantages of learning in the W-MDP in terms of variance reduction and improved sample complexity. Finally, empirical evaluations confirm that MetaStep reduces computational costs while preserving sample efficiency.
