研究多步过渡前瞻的强化学习接近最优规划
Near-Optimal Reinforcement Learning with Multi-Step Transition Lookahead
这个研究挺有意思，作者解决了强化学习中多步过渡前瞻的接近最优规划问题，证明了精确规划是NP难的，但提出了一个高效的近似算法，并且扩展到了更复杂的情况。
这篇论文研究了强化学习中的多步过渡前瞻方法，其中代理在决定行动前可以观察在执行任意序列动作后可能访问的状态。作者证明了对于任何固定的折扣因子，精确规划仍然是NP难问题，但提出了一个随机多项式时间近似方案来解决固定前瞻深度的规划问题。他们还扩展了该方法以处理未知过渡和随机奖励，最终算法的累积遗憾与经典表格折扣RL相比，其主导项仅相差对数因子。
Near-Optimal Reinforcement Learning with Multi-Step Transition Lookahead
We study reinforcement learning (RL) with transition look-ahead, where the agent may observe which states would be visited upon playing any sequence of $\ell$ actions before deciding its course of action. Although look-ahead can substantially improve achievable performance, it is known that optimal planning with multi-step transition look-ahead is NP-hard, but this hardness was established using discount factors arbitrarily close to one. It was therefore unknown whether the problem remains hard for any discount factor, and whether near-optimal planning can nevertheless be performed efficiently. We resolve both questions. First, we show that for every fixed rational discount factor ($γ\in(0,1)$), exact planning remains NP-hard. Second, we introduce a randomized polynomial-time approximation scheme for every fixed look-ahead depth. We then extend our approach to unknown transitions and stochastic rewards using optimism and variance-adaptive confidence bounds. The resulting algorithm achieves cumulative regret whose leading term matches classical tabular discounted RL up to logarithmic factors. Thus, although exact planning with transition look-ahead is NP-hard, efficient near-optimal planning and learning remain possible.
