I detta arbete beaktas den urvals- och beräkningsmässiga komplexiteten i att erhålla en ε-optimal policy i en diskonterad Markovbeslutsprocess (MDP), som endast ger tillgång till en generativ modell. I denna modell får eleven tillgång till den underliggande övergångsmodellen via ett provtagnings- orakel som ger ett prov av nästa tillstånd, när det ges ett stat-action-par som indata. Denna allmänt studerade miljö ger en naturlig abstraktion som gör det möjligt att studera provbaserad planering över en lång horisont, frikopplad från komplexiteten i prospektering. I detta arbete studerar vi effektiviteten hos den mest naturliga plug-in metoden för modellbaserad planering: vi bygger den maximala sannolikheten uppskattning av övergångsmodellen i MDP från observationer och sedan hitta en optimal politik i denna empiriska MDP. Vi ställer utan tvekan den mest grundläggande och olösta frågan i modellbaserad planering: är den naiva "plug-in"-metoden, icke-asymmetriskt, minimax optimal i kvaliteten på den politik som den finner, med tanke på en fast urvalsstorlek? Här avser det icke-asymptotiska systemet när provstorleken är sublinjär i modellstorleken. Med tillgång till en generativ modell löser vi denna fråga i starkaste möjliga bemärkelse: vårt huvudresultat visar att alla lösningar med hög noggrannhet i den plug-in-modell som konstruerats med N prover, ger en ε-optimal policy i den verkliga underliggande MDP (där ε är minimax noggrannhet med N prover i varje tillstånd, åtgärd par). I jämförelse använder alla tidigare (icke-asymptotiskt) minimax optimala resultat modellfria metoder, såsom Variance Reducerad Q-värde iteration algoritm (Sidford et al., 2018a), medan de mest kända modellbaserade resultaten (t.ex. Azar m.fl. (2013) kräver större urvalsstorlekar i beroendet av planeringshorisonten eller tillståndsutrymmet. Särskilt visar vi att det modellbaserade tillvägagångssättet gör det möjligt att använda någon effektiv planeringsalgoritm i den empiriska MDP, vilket förenklar algoritmdesignen eftersom detta tillvägagångssätt inte binder algoritmen till provtagningsförfarandet. Kärnan i vår analys är en ny "absorberande MDP" konstruktion för att ta itu med de statistiska beroendefrågor som uppstår i analysen av modellbaserade planeringsmetoder, en konstruktion som kan vara till nytta mer allmänt.
I REF fastställs liknande resultat genom att man gör en uppskattning av parametrarna i MDP-modellen med hjälp av uppskattning av maximallikelihood.
On the Optimality of Sparse Model-Based Planning for Markov Decision Processes.
{'venue': 'ArXiv', 'journal': 'ArXiv', 'mag_field_of_study': ['Mathematics', 'Computer Science']}