Confident Approximate Policy Iteration for Efficient Local Planning in q \pi -realizable MDPs

We consider approximate dynamic programming in \gamma -discounted Markov decision processes and apply it to approximate planning with linear value-function approximation. Our first contribution is a new variant of Approximate Policy Iteration (API), called Confident Approximate Policy Iteration (CAPI), which computes a deterministic stationary policy with an optimal error bound scaling linearly with the product of the effective horizon H and the worst-case approximation error \epsilon of the action-value functions of stationary policies. This improvement over API (whose error scales with H 2) comes at the price of an H -fold increase in memory cost. Unlike Scherrer and Lesner [2012], who recommended computing a non-stationary policy to achieve a similar improvement (with the same memory overhead), we are able to stick to stationary policies. This allows for our second contribution, the application of CAPI to planning with local access to a simulator and d -dimensional linear function approximation.