On Query-efficient Planning in MDPs under Linear Realizability of the Optimal State-value Function

Understand

We consider local planning in fixed-horizon MDPs with a generative model under the assumption that the optimal value function lies close to the span of a feature map.

• The generative model provides a local access to the MDP: The planner can ask for random transitions from previously returned states and arbitrary actions, and features are only accessible for states that are encountered in this process.
• As opposed to previous work (e.g.
• Lattimore et al.