Open Collections

Guo, Chaoping

University of British Columbia

This thesis extends the notion of role assignment on graphs to Markov decision processes (MDPs). A role is a categorical property of a state that describes the state's reward and structural position in the MDP. An MDP with a large state space can often be approximately summarized with a small number of roles, which can be used to build an abstract model, enabling much more efficient planning, with the performance loss bounded by the approximation error. The previously known performance bound is based on the approximation errors indiscriminatively across all actions. We show that such a bound is too loose, and minimizing it does not necessarily lead to the best possible solution; instead, a tighter bound can be used by taking into consideration the policy defined on the roles. Calculating the exact role similarities between states is very expensive in both memory and time. We develop a group of algorithms, referred to as assignment iteration and assignment update, that find role assignments using the role similarities between states and roles. Our methods are much more efficient, and we show that the state-state similarities are indirectly preserved with a notion of true similarity. Assignment update can also be applied to unknown MDPs with the experience sampled by a reinforcement learning agent. Using neural networks as assigners, it solves continuous-state-space environments such as CartPole and Catcher with sample efficiency comparable to a model-based method.

Text

2022-06-30

Attribution-NonCommercial-NoDerivatives 4.0 International

http://hdl.handle.net/2429/81863

Computer Science

University of British Columbia

UBCO

http://creativecommons.org/licenses/by-nc-nd/4.0/