English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

We consider approximate dynamic programming in $\gamma$-discounted Markovdecision processes and apply it to approximate planning with linearvalue-function approximation. Our first contribution is a new variant ofApproximate Policy Iteration (API), called Confident Approximate PolicyIteration (CAPI), which computes a deterministic stationary policy with anoptimal error bound scaling linearly with the product of the effective horizon$H$ and the worst-case approximation error $\epsilon$ of the action-valuefunctions of stationary policies. This improvement over API (whose error scaleswith $H^2$) comes at the price of an $H$-fold increase in memory cost. UnlikeScherrer and Lesner [2012], who recommended computing a non-stationary policyto achieve a similar improvement (with the same memory overhead), we are ableto stick to stationary policies. This allows for our second contribution, theapplication of CAPI to planning with local access to a simulator and$d$-dimensional linear function approximation. As such, we design a planningalgorithm that applies CAPI to obtain a sequence of policies with successivelyrefined accuracies on a dynamically evolving set of states. The algorithmoutputs an $\tilde O(\sqrt{d}H\epsilon)$-optimal policy after issuing $\tildeO(dH^4/\epsilon^2)$ queries to the simulator, simultaneously achieving theoptimal accuracy bound and the best known query complexity bound, while earlieralgorithms in the literature achieve only one of them. This query complexity isshown to be tight in all parameters except $H$. These improvements come at theexpense of a mild (polynomial) increase in memory and computational costs ofboth the algorithm and its output policy.

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