TY - GEN
T1 - Improving UCT planning via approximate homomorphisms
AU - Jiang, Nan
AU - Singh, Satinder
AU - Lewis, Richard
N1 - Publisher Copyright:
Copyright © 2014, International Foundation for Autonomous Agents and Multiagent Systems (www.ifaamas.org). All rights reserved.
PY - 2014
Y1 - 2014
N2 - 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.
AB - 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.
KW - Abstraction
KW - Planning
KW - Reinforcement learning
KW - UCT
UR - http://www.scopus.com/inward/record.url?scp=84911401632&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84911401632&partnerID=8YFLogxK
M3 - Conference contribution
AN - SCOPUS:84911401632
T3 - 13th International Conference on Autonomous Agents and Multiagent Systems, AAMAS 2014
SP - 1289
EP - 1296
BT - 13th International Conference on Autonomous Agents and Multiagent Systems, AAMAS 2014
PB - International Foundation for Autonomous Agents and Multiagent Systems (IFAAMAS)
T2 - 13th International Conference on Autonomous Agents and Multiagent Systems, AAMAS 2014
Y2 - 5 May 2014 through 9 May 2014
ER -