Action Selection for MDPs: Anytime AO* vs. UCT
This addresses the challenge of action selection in MDPs that cannot be solved by existing offline methods, offering a new algorithmic approach for researchers in AI planning and reinforcement learning.
The paper tackled the problem of developing an anytime optimal algorithm for AND/OR graphs, specifically applying it to finite-horizon MDPs, and tested it on large infinite-horizon MDPs, showing it eventually delivers an optimal policy using non-admissible random heuristics.
In the presence of non-admissible heuristics, A* and other best-first algorithms can be converted into anytime optimal algorithms over OR graphs, by simply continuing the search after the first solution is found. The same trick, however, does not work for best-first algorithms over AND/OR graphs, that must be able to expand leaf nodes of the explicit graph that are not necessarily part of the best partial solution. Anytime optimal variants of AO* must thus address an exploration-exploitation tradeoff: they cannot just "exploit", they must keep exploring as well. In this work, we develop one such variant of AO* and apply it to finite-horizon MDPs. This Anytime AO* algorithm eventually delivers an optimal policy while using non-admissible random heuristics that can be sampled, as when the heuristic is the cost of a base policy that can be sampled with rollouts. We then test Anytime AO* for action selection over large infinite-horizon MDPs that cannot be solved with existing off-line heuristic search and dynamic programming algorithms, and compare it with UCT.