Publication Type

Conference Proceeding Article

Version

publishedVersion

Publication Date

6-2023

Abstract

Action-constrained reinforcement learning (ACRL), where any action taken in a state must satisfy given constraints, has several practical applications such as resource allocation in supply-demand matching, and path planning among others. A key challenge is to enforce constraints when the action space is discrete and combinatorial. To address this, first, we assume an action is represented using propositional variables, and action constraints are represented using Boolean functions. Second, we compactly encode the set of all valid actions that satisfy action constraints using a probabilistic sentential decision diagram (PSDD), a recently proposed knowledge compilation framework. Parameters of the PSDD compactly encode the probability distribution over all valid actions. Consequently, the learning task becomes optimizing PSDD parameters to maximize the RL objective. Third, we show how to embed the PSDD parameters using deep neural networks, and optimize them using a deep Q-learning based algorithm. By design, our approach is guaranteed to never violate any constraint, and does not involve any expensive projection step over the constraint space. Finally, we show how practical resource allocation constraints can be encoded using a PSDD. Empirically, our approach works better than previous ACRL methods, which often violate constraints, and are not scalable as they involve computationally expensive projection-over-constraints step.

Keywords

Action spaces, Action-constrained RL, Combinatorial action, Decision diagram, Knowledge compilation, Neuro-symbolic AI, Probabilistics, Reinforcement learnings, Resources allocation, Supply-demand

Discipline

Databases and Information Systems

Research Areas

Data Science and Engineering

Publication

Proceedings of the 22nd International Conference on Autonomous Agents and Multiagent Systems, London, Great Britain, 2023 May 29-June 2

First Page

860 - 86

Last Page

868

Publisher

International Foundation for Autonomous Agents and Multiagent Systems

City or Country

London

Share

COinS