在具有庞大或无限状态和动作空间的环境中，设计样本效率高且计算可行的强化学习 (RL) 算法尤其具有挑战性。本文通过提出一种针对马尔可夫决策过程 (MDP) 的高效算法，推动了这一努力，其中任何策略的状态-动作值函数在给定特征映射中是线性的。这种具有挑战性的设置可以模拟具有无限状态和动作的环境，严格概括了经典的线性 MDP，并且目前在在线访问 MDP 的情况下缺乏计算效率高的算法。具体来说，我们介绍了一种新的 RL 算法，该算法能够在该设置中有效地找到近似最优策略，使用数量级为问题参数的多项式的集数和对成本敏感分类 (CSC) 预言机的调用次数。值得注意的是，当特征维数恒定时，我们的 CSC 预言机可以有效地实现，这比最先进的方法有了明显改进，后者需要解决具有水平数量变量的非凸问题，并且会产生水平指数级的计算成本。