On-line Policy Improvement using Monte-Carlo Search

Abstract

We present a Monte-Carlo simulation algorithm for real-time policy improvement of an adaptive controller. In the Monte-Carlo simulation, the long-term expected reward of each possible action is statistically measured, using the initial policy to make decisions in each step of the simulation. The action maximizing the measured expected reward is then taken, resulting in an improved policy. Our algorithm is easily parallelizable and has been implemented on the IBM SP1 and SP2 parallel-RISC supercomputers. We have obtained promising initial results in applying this algorithm to the domain of backgammon. Results are reported for a wide variety of initial policies, ranging from a random policy to TD-Gammon, an extremely strong multi-layer neural network. In each case, the Monte-Carlo algorithm gives a substantial reduction, by as much as a factor of 5 or more, in the error rate of the base players. The algorithm is also potentially useful in many other adaptive control applications in which it is possible to simulate the environment.

Accompanied by oral presentation by Gregory Galperin at NeurIPS 1996 (then known as NIPS*96)

Cited by in corpus (26)

• A Survey on Compiler Autotuning using Machine Learning
• Approximate Policy Iteration with a Policy Language Bias: Solving Relational Markov Decision Processes
• Lifelong Incremental Reinforcement Learning with Online Bayesian Inference
• Near-optimal planning using approximate dynamic programming to enhance post-hazard community resilience management
• Deep Controlled Learning for Inventory Control
• Learning to Win by Reading Manuals in a Monte-Carlo Framework
• Learning 6-DoF Grasping and Pick-Place Using Attention Focus
• Beyond the One Step Greedy Approach in Reinforcement Learning
• Policy Gradient Search: Online Planning and Expert Iteration without Search Trees
• Analysis of Watson's Strategies for Playing Jeopardy!
• On the role of planning in model-based deep reinforcement learning
• Model-Based Opponent Modeling
• Multiple-Step Greedy Policies in Online and Approximate Reinforcement Learning
• A Dynamic Programming Algorithm for Finding an Optimal Sequence of Informative Measurements
• Lessons from AlphaZero for Optimal, Model Predictive, and Adaptive Control
• Simulation Based Algorithms for Markov Decision Processes and Multi-Action Restless Bandits
• Proximal Algorithms and Temporal Differences for Large Linear Systems: Extrapolation, Approximation, and Simulation
• Fast Reinforcement Learning with Large Action Sets using Error-Correcting Output Codes for MDP Factorization
• Review, Analysis and Design of a Comprehensive Deep Reinforcement Learning Framework
• Constrained Multiagent Rollout and Multidimensional Assignment with the Auction Algorithm
• Continuous Control for Searching and Planning with a Learned Model
• Approximate Policy Iteration for Budgeted Semantic Video Segmentation
• Data-driven Rollout for Deterministic Optimal Control
• Leveraging Tripartite Interaction Information from Live Stream E-Commerce for Improving Product Recommendation
• Average-Case Performance of Rollout Algorithms for Knapsack Problems
• Learn a Prior for RHEA for Better Online Planning