Improving UCT planning via approximate homomorphisms

Nan Jiang, Satinder Singh, Richard Lewis

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

In this paper we show how abstractions can help UCT's performance. Ideal abstractions are homomorphisms because they preserve optimal policies, but they rarely exist, and are computationally hard to find even when they do. We show how a combination of (i) finding local abstractions in the layered-DAG MDP induced by a set of UCT trajectories (rather than finding abstractions in the global MDP), and (ii) accepting approximate homomorphisms, leads to greater prevalence of good abstractions and makes them computationally easier to find. We propose an algorithm for finding abstractions in UCT planning and derive a lower bound on its performance. We show empirically that it improves performance on illustrative tasks, and on the game of Othello.

Original languageEnglish (US)
Title of host publication13th International Conference on Autonomous Agents and Multiagent Systems, AAMAS 2014
PublisherInternational Foundation for Autonomous Agents and Multiagent Systems (IFAAMAS)
Pages1289-1296
Number of pages8
ISBN (Electronic)9781634391313
StatePublished - 2014
Externally publishedYes
Event13th International Conference on Autonomous Agents and Multiagent Systems, AAMAS 2014 - Paris, France
Duration: May 5 2014May 9 2014

Publication series

Name13th International Conference on Autonomous Agents and Multiagent Systems, AAMAS 2014
Volume2

Other

Other13th International Conference on Autonomous Agents and Multiagent Systems, AAMAS 2014
CountryFrance
CityParis
Period5/5/145/9/14

Keywords

  • Abstraction
  • Planning
  • Reinforcement learning
  • UCT

ASJC Scopus subject areas

  • Artificial Intelligence

Fingerprint Dive into the research topics of 'Improving UCT planning via approximate homomorphisms'. Together they form a unique fingerprint.

Cite this