Ari Weinstein

AAAI Conference 2013 Conference Paper

Open-Loop Planning in Large-Scale Stochastic Domains

• Ari Weinstein
• Michael Littman

ICML Conference 2013 Conference Paper

The Cross-Entropy Method Optimizes for Quantiles

• Sergiu Goschin
• Ari Weinstein
• Michael L. Littman

Cross-entropy optimization (CE) has proven to be a powerful tool for search in control environments. In the basic scheme, a distribution over proposed solutions is repeatedly adapted by evaluating a sample of solutions and refocusing the distribution on a percentage of those with the highest scores. We show that, in the kind of noisy evaluation environments that are common in decision-making domains, this percentage-based refocusing does not optimize the expected utility of solutions, but instead a quantile metric. We provide a variant of CE (Proportional CE) that effectively optimizes the expected value. We show using variants of established noisy environments that Proportional CE can be used in place of CE and can improve solution quality.

ICAPS Conference 2012 Conference Paper

Bandit-Based Planning and Learning in Continuous-Action Markov Decision Processes

• Ari Weinstein
• Michael L. Littman

Recent research leverages results from the continuous-armed bandit literature to create a reinforcement-learning algorithm for continuous state and action spaces. Initially proposed in a theoretical setting, we provide the first examination of the empirical properties of the algorithm. Through experimentation, we demonstrate the effectiveness of this planning method when coupled with exploration and model learning and show that, in addition to its formal guarantees, the approach is very competitive with other continuous-action reinforcement learners.

EWRL Workshop 2012 Conference Paper

Planning in Reward-Rich Domains via PAC Bandits

• Sergiu Goschin
• Ari Weinstein
• Michael L. Littman
• Erick Chastain

In some decision-making environments, successful solutions are common. If the evaluation of candidate solutions is noisy, however, the challenge is knowing when a “good enough” answer has been found. We formalize this problem as an infinite-armed bandit and provide upper and lower bounds on the number of evaluations or “pulls” needed to identify a solution whose evaluation exceeds a given threshold r0. We present several algorithms and use them to identify reliable strategies for solving screens from the video games \emphInfinite Mario and \emphPitfall! We show order of magnitude improvements in sample complexity over a natural approach that pulls each arm until a good estimate of its success probability is known.

EWRL Workshop 2012 Conference Paper

Rollout-based Game-tree Search Outprunes Traditional Alpha-beta

• Ari Weinstein
• Michael L. Littman
• Sergiu Goschin

Recently, rollout-based planning and search methods have emerged as an alternative to traditional tree-search methods. The fundamental operation in rollout-based tree search is the generation of trajectories in the search tree from root to leaf. Game-playing programs based on Monte-Carlo rollouts methods such as “UCT” have proven remarkably effective at using information from trajectories to make state-of-the-art decisions at the root. In this paper, we show that trajectories can be used to prune more aggressively than classical alpha-beta search. We modify a rollout-based method, FSSS, to allow for use in game-tree search and show it outprunes alpha-beta both empirically and formally.

ICAPS Conference 2011 Conference Paper

Sample-Based Planning for Continuous Action Markov Decision Processes

• Christopher R. Mansley
• Ari Weinstein
• Michael L. Littman

In this paper, we present a new algorithm that integrates recent advances in solving continuous bandit problems with sample-based rollout methods for planning in Markov Decision Processes (MDPs). Our algorithm, Hierarchical Optimistic Optimization applied to Trees (HOOT) addresses planning in continuous-action MDPs. Empirical results are given that show that the performance of our algorithm meets or exceeds that of a similar discrete action planner by eliminating the problem of manual discretization of the action space.