Back to search

University of British Columbia

A role-assignment approach to state abstraction of Markov decision processes

Abstract

dc:description

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.

Degree

thesis:*
Name thesis:degree_name
Master of Science - MSc
Level thesis:degree_level
master's
Discipline thesis:degree_discipline
Computer Science
Grantor dc:publisher
University of British Columbia
Year dc:date
2022

Author and committee

dc:creator, dc:contributor.*
Author dc:creator
  • Guo, Chaoping
Contributors dc:contributor
  • Gao, Yong

Rights

dc:rights
Statement dc:rights
  • Attribution-NonCommercial-NoDerivatives 4.0 International
Language dc:language
eng

Identifiers

dc:identifier.*
Handle dc:identifier
http://hdl.handle.net/2429/81863

Chain of custody

source
Harvested from
University of British Columbia
Base URL
circle.library.ubc.ca/oai/request
Last updated
2026-11-19
Source record
OAI-PMH GetRecord
related terms
citation

Guo, Chaoping. A role-assignment approach to state abstraction of Markov decision processes. master's thesis, University of British Columbia, 2022. http://hdl.handle.net/2429/81863