OREGON STATE UNIVERSITY

You are here

PAC Optimal Planning for Invasive Species Management: Improved Exploration for Reinforcement Learning from Simulator-Defined MDPs

TitlePAC Optimal Planning for Invasive Species Management: Improved Exploration for Reinforcement Learning from Simulator-Defined MDPs
Publication TypeConference Paper
Year of Publication2013
AuthorsDietterich, T. G., M. Alkaee Taleghan, and M. Crowley
Conference NameAAAI Conference on Artificial Intelligence, AAAI-2013
Date Published07/2013
Conference LocationBellevue, Washington
KeywordsMDP Planning, reinforcement learning, Simulator-Defined MDPs
Abstract

Often the most practical way to define a Markov Decision Process (MDP) is as a simulator that, given a state and an action, produces a resulting state and immediate reward sampled from the corresponding distributions. Simulators in natural resource management can be very expensive to execute, so that the time required to solve such MDPs is dominated by the number of calls to the simulator. This paper presents an algorithm, DDV, that combines improved confidence intervals on the Q values (as in interval estimation) with a novel upper bound on the discounted state occupancy probabilities to intelligently choose state-action pairs to explore. We prove that this algorithm terminates with a policy whose value is within epsilon of the optimal policy (with probability 1-delta) after making only polynomially-many calls to the simulator. Experiments on one benchmark MDP and on an MDP for invasive species management show very large reductions in the number of simulator calls required.

URLhttp://www.aaai.org/ocs/index.php/AAAI/AAAI13/paper/view/6478