Determinantal Reinforcement Learning

Takayuki Osogami, Rudy RaymondAAAI 2019 · OpenReview

Abstract

We study reinforcement learning for controlling multiple agents in a collaborative manner. In some of those tasks, it is insufficient for the individual agents to take relevant actions, but those actions should also have diversity. We propose the approach of using the determinant of a positive semidefinite matrix to approximate the action-value function in reinforcement learning, where we learn the matrix in a way that it represents the relevance and diversity of the actions. Experimental results show that the proposed approach allows the agents to learn a nearly optimal policy approximately ten times faster than baseline approaches in benchmark tasks of multi-agent reinforcement learning. The proposed approach is also shown to achieve the performance that cannot be achieved with conventional approaches in partially observable environments with exponentially large action spaces.

Introduction

In multi-agent reinforcement learning (MARL), agents must learn to coordinate their actions to achieve a common goal. However, as the number of agents increases, the joint action space grows exponentially—a phenomenon known as the "curse of dimensionality." Traditional approaches often struggle with this scale. Global approaches that treat the entire team as a single agent do not scale well, while independent approaches, where agents act greedily on their own, often fail to achieve the necessary coordination for complex tasks.

A critical missing component in many MARL frameworks is diversity. For a team to be effective, agents should not only select actions that are individually "good" (relevant) but also ensure their collective actions are diverse to avoid redundancy. This paper introduces a novel method that explicitly models both relevance and diversity using determinantal point processes.

Methodology: Determinantal SARSA

The core innovation of this work is the approximation of the action-value function ($Q$-function) using the log-determinant of a positive semidefinite kernel matrix. This approach is grounded in geometric intuition.

Geometric Intuition

If we represent each possible action as a vector, the length of the vector can represent the action's "relevance" to the current state, while the angle between vectors represents their "similarity." The volume of the parallelotope formed by these vectors represents the value of that specific combination of actions.

Geometric intuition of the determinantal approach, where the squared volume of the parallelotope represents the value of combined actions.

Mathematically, the squared volume is equal to the determinant of the kernel matrix $L$. The authors propose that the value of a combination of actions is proportional to $\log \det(L)$. This naturally encourages diversity: if two agents choose identical or highly similar actions, the vectors will overlap, the volume will collapse toward zero, and the resulting $Q$-value will be low.

Implementation

The method is integrated into the SARSA framework. The kernel matrix $L_t$ is decomposed into $V D_t V^\top$, where $D_t$ is a diagonal matrix representing state-dependent relevance (often learned via a neural network) and $V$ is a matrix representing the inherent similarity between actions. By learning these components, the agents discover which actions are individually useful and which combinations provide the best coverage of the problem space.

Experimental Evaluation

The proposed approach was tested on two primary benchmarks:

  1. The Blocker Task: A grid world where three agents must coordinate to bypass two blockers and reach an end zone.
  2. Stochastic Policy Tasks: A partially observable environment requiring agents to match a hidden cycling state through specific bit combinations, testing the model's ability to handle exponential action spaces.

Results and Discussion

The experimental results demonstrate a significant performance leap over traditional methods.

10x Learning Speedup

In the Blocker Task, the determinantal approach reached near-optimal performance (average reward > -0.7) in approximately 20,000 steps. In contrast, baseline methods like Free Energy SARSA and Energy-based Natural Actor-Critic (ENATDAC) required nearly 200,000 steps to reach the same level of performance.

Comparison of average reward per action over time, showing the proposed determinantal approach (black line) achieving near-optimal performance much faster than baselines.

Handling Exponential Action Spaces

The method also excelled in environments with large action spaces and partial observability. In Stochastic Policy Tasks with up to $2^8 = 256$ possible action combinations, the determinantal approach found nearly optimal policies where standard neural network-based SARSA models failed.

Interpretability

Visualizations of the learned similarity matrix revealed that the model correctly identified spatial relationships. For example, it learned that adjacent positions in a grid are "similar" and should not be occupied by multiple agents simultaneously, even without being explicitly provided with the grid's geometry.

Conclusion

By treating diversity as a fundamental property of the value function rather than an auxiliary reward, Determinantal Reinforcement Learning offers a powerful solution to the coordination challenges in MARL. The approach provides a 10x speedup in learning and scales effectively to complex, partially observable environments. Future work includes applying this determinantal layer to more advanced RL architectures and exploring its utility in large-scale real-world simulations.

Summary updated

Abstract

We study reinforcement learning for controlling multiple agents in a collaborative manner. In some of those tasks, it is insufficient for the individual agents to take relevant actions, but those actions should also have diversity. We propose the approach of using the determinant of a positive semidefinite matrix to approximate the action-value function in reinforcement learning, where we learn the matrix in a way that it represents the relevance and diversity of the actions. Experimental results show that the proposed approach allows the agents to learn a nearly optimal policy approximately ten times faster than baseline approaches in benchmark tasks of multi-agent reinforcement learning. The proposed approach is also shown to achieve the performance that cannot be achieved with conventional approaches in partially observable environment with exponentially large action space.
BibTeX
@inproceedings{osogami2019determinantal,
  author = {Takayuki Osogami and Rudy Raymond},
  title = {{Determinantal Reinforcement Learning}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2019},
  url = {https://openreview.net/forum?id=pZV_S3ewXj1},
}

Loading related content...

Figure