Blazing the trails before beating the path: Sample-efficient Monte-Carlo planning
We study the sampling-based planning problem in Markov decision processes (MDPs) that we can access only through a generative model, usually referred to as Monte-Carlo planning. Our objective is to return a good estimate of the optimal value function at any state while minimizing the number of calls to the generative model, i.e. the sample complexity. We propose a new algorithm, TrailBlazer, able to handle MDPs with a finite or an infinite number of transitions from state-action to next states. TrailBlazer is an adaptive algorithm that exploits possible structures of the MDP by exploring only a subset of states reachable by following near-optimal policies. We provide bounds on its sample complexity that depend on a measure of the quantity of near-optimal states. The algorithm behavior can be considered as an extension of Monte-Carlo sampling (for estimating an expectation) to problems that alternate maximization (over actions) and expectation (over next states). Finally, another appealing feature of TrailBlazer is that it is simple to implement and computationally efficient.
Code (0)
등록된 구현이 없습니다.
Similar Papers 제목 키워드 기반
Blazing the trails before beating the path: Sample-efficient Monte-Carlo planning
You are a robot and you live in a Markov decision process (MDP) with a finite or an infinite number of transitions from state-action to next states. You got brains and so you plan before you act. Luckily, your roboparent…
Motion trails from time-lapse video
From an image sequence captured by a stationary camera, background subtraction can detect moving foreground objects in the scene. Distinguishing foreground from background is further improved by various heuristics. Then …
Contrail-to-Flight Attribution Using Ground Visible Cameras and Flight Surveillance Data
Aviation's non-CO2 effects, particularly contrails, are a significant contributor to its climate impact. Persistent contrails can evolve into cirrus-like clouds that trap outgoing infrared radiation, with radiative forci…
Difficulty Classification of Mountainbike Downhill Trails utilizing Deep Neural Networks
The difficulty of mountainbike downhill trails is a subjective perception. However, sports-associations and mountainbike park operators attempt to group trails into different levels of difficulty with scales like the Sin…
ClassificationGeneral ClassificationPheromone-based Learning of Optimal Reasoning Paths
Large Language Models (LLMs) have demonstrated remarkable reasoning capabilities through chain-of-thought prompting, yet discovering effective reasoning methods for complex problems remains challenging due to the vast sp…
ARCGSM8KMathMixture-of-Experts