On the Expressivity of Markov Reward (Extended Abstract)
Abstract
Reward is the driving force for reinforcement-learning agents. We here set out to understand the expressivity of Markov reward as a way to capture tasks that we would want an agent to perform. We frame this study around three new abstract notions of "task": (1) a set of acceptable behaviors, (2) a partial ordering over behaviors, or (3) a partial ordering over trajectories. Our main results prove that while reward can express many of these tasks, there exist instances of each task type that no Markov reward function can capture. We then provide a set of polynomial-time algorithms that construct a Markov reward function that allows an agent to perform each task type, and correctly determine when no such reward function exists.
Cite
Text
Abel et al. "On the Expressivity of Markov Reward (Extended Abstract)." International Joint Conference on Artificial Intelligence, 2022. doi:10.24963/IJCAI.2022/730Markdown
[Abel et al. "On the Expressivity of Markov Reward (Extended Abstract)." International Joint Conference on Artificial Intelligence, 2022.](https://mlanthology.org/ijcai/2022/abel2022ijcai-expressivity/) doi:10.24963/IJCAI.2022/730BibTeX
@inproceedings{abel2022ijcai-expressivity,
title = {{On the Expressivity of Markov Reward (Extended Abstract)}},
author = {Abel, David and Dabney, Will and Harutyunyan, Anna and Ho, Mark K. and Littman, Michael L. and Precup, Doina and Singh, Satinder},
booktitle = {International Joint Conference on Artificial Intelligence},
year = {2022},
pages = {5254-5258},
doi = {10.24963/IJCAI.2022/730},
url = {https://mlanthology.org/ijcai/2022/abel2022ijcai-expressivity/}
}