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 Tools annual

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 Tools monthly

Global: Zendy Plus monthly

Presents the access of premium content as premium feature

Premium Content

Global: Zendy Plus annual

Global: Zendy Free Plan

This work considers the sample and computational complexity of obtaining an$\epsilon$-optimal policy in a discounted Markov Decision Process (MDP), givenonly access to a generative model. In this work, we study the effectiveness ofthe most natural plug-in approach to model-based planning: we build the maximumlikelihood estimate of the transition model in the MDP from observations andthen find an optimal policy in this empirical MDP. We ask arguably the mostbasic and unresolved question in model based planning: is the naive "plug-in"approach, non-asymptotically, minimax optimal in the quality of the policy itfinds, given a fixed sample size? Here, the non-asymptotic regime refers towhen the sample size is sublinear in the model size.  With access to a generative model, we resolve this question in the strongestpossible sense: our main result shows that \emph{any} high accuracy solution inthe plug-in model constructed with $N$ samples, provides an $\epsilon$-optimalpolicy in the true underlying MDP (where $\epsilon$ is the minimax accuracywith $N$ samples at every state, action pair). In comparison, all prior(non-asymptotically) minimax optimal results use model free approaches, such asthe Variance Reduced Q-value iteration algorithm (Sidford et al 2018), whilethe best known model-based results (e.g. Azar et al 2013) require larger samplesizes in their dependence on the planning horizon or the state space. Notably,we show that the model-based approach allows the use of \emph{any} efficientplanning algorithm in the empirical MDP, which simplifies algorithm design asthis approach does not tie the algorithm to the sampling procedure. The core ofour analysis is avnovel "absorbing MDP" construction to address the statisticaldependency issues that arise in the analysis of model-based planningapproaches, a construction which may be helpful more generally.

Model-Based Reinforcement Learning with a Generative Model is Minimax Optimal