Improving UCT Planning via Approximate Homomorphisms. Jian, Singh, Lewis. AAMAS 2014

  1. Improves performance of UCT by:
    1. finding local abstractions in the DAG built by UCT
    2. using approximate homomorphisms (as opposed to true homomorphisms which preserve optimal policies, but are rare and computationally difficult to develop)
  2. Derive a lower bound on the performance of the abstraction method when used with UCT
    1. <If the bounds are specific for UCT it might be moot anyway because of the horrible worst-case performance of the algorithm>
  3. Also global homomorphisms are global, but the paper is concerned with UCT which is generally applied when global methods are too expensive
  4. “One interesting overall insight obtained herein is that the more computationally limited UCT is, the coarser are the
    best-performing abstractions.”
  5. “A homomorphism is a perfect abstraction in the sense that the induced MDP is equivalent to the original MDP for planning purposes.”
  6. Here, they just glob states together into clusters and use that set as an abstracted state (counts average returns apply to set as a whole)
  7. <OK, think I get the idea, not so relevant for now but may come back to it>

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

%d bloggers like this: