Personalized Reinforcement Learning with a Budget of Policies

Dmitry Ivanov, Omer Ben-Porat

Abstract

Personalizing Reinforcement Learning (RL) models for large user populations is often hindered by the high cost of regulatory approval for each individual model. We introduce represented Markov Decision Processes (r-MDPs), a framework that learns a small budget of $k$ representative policies to serve $n$ diverse users. By optimizing for social welfare through EM-like and end-to-end algorithms, we demonstrate that a minimal number of policies can achieve near-optimal personalization, effectively bypassing the regulatory bottleneck in high-stakes applications.

Introduction

The "holy grail" of machine learning is personalization—tailoring AI behavior to specific user needs. However, in high-stakes domains like healthcare or autonomous driving, every new model requires rigorous regulatory audits (e.g., FDA approval). This creates a "regulatory bottleneck": while we might have 10,000 users, we cannot afford to audit 10,000 unique models. Conversely, a "one-size-fits-all" model often fails to meet individual requirements. This research explores the middle ground: finding the optimal $k$ policies to satisfy $n$ users, where $k$ is a small, manageable budget.

Methodology: Represented MDPs

The authors formalize this problem as the represented Markov Decision Process (r-MDP). In this framework, $n$ agents (users) each possess unique reward functions. Instead of individual models, users are assigned to one of $k$ "representative" policies. The objective is to maximize "social welfare" (the average reward across the entire population) by simultaneously learning the $k$ policies and the optimal user-to-policy mapping.

Two primary algorithms are proposed:

  1. EM-like Algorithm (Hard Assignment): An iterative process where users are assigned to the representative policy yielding the highest reward (E-step), followed by updating the policies to better serve their assigned groups (M-step).
  2. End-to-End Algorithm (Soft Assignment): This approach treats user assignment as a differentiable parameter, using gradient descent to learn the mapping and policies concurrently.

Both methods utilize Proximal Policy Optimization (PPO) as the core RL engine.

Experimental Evaluation

The framework was evaluated on two distinct environments:

  • Resource Gathering: A 5x5 grid world where 25 agents aim to collect specific resources and return to a home base. This environment tests spatial division efficiency.
  • MuJoCo Benchmarks: Continuous control tasks (Ant, HalfCheetah, etc.) modified so that 100–1,000 agents have varying target velocities, testing the ability to handle continuous preference spaces.
Policy specialization in the Resource Gathering task for varying budgets $k$.

Key Insights

Optimization over Heuristics

Unlike traditional clustering methods that group users based on observed behavior (trajectories), r-MDPs group users based on their underlying preferences (reward functions). This preference-based optimization leads to significantly higher performance when the policy budget is constrained.

The Efficiency of Small Budgets

A critical finding is the rapid plateauing of performance as $k$ increases. In the Resource Gathering task, a budget of just $k=3$ policies for 25 agents captured over 90% of the performance of a fully personalized system ($k=25$). This suggests that most populations can be effectively served by a very small number of specialized models.

Automatic Niche Discovery

The algorithms naturally partition the preference space. In MuJoCo tasks, agents were automatically categorized into velocity "buckets" (e.g., slow, medium, fast) without manual intervention, demonstrating the framework's ability to discover latent user segments.

Results and Discussion

The proposed EM-like and End-to-End algorithms consistently outperformed standard clustering-based baselines and random assignments across all benchmarks. The framework scaled effectively to populations of 1,000 agents. Furthermore, the authors provided theoretical guarantees that the EM-like algorithm converges to a local maximum of social welfare, a crucial property for deployment in regulated environments.

Limitations and Future Directions

While maximizing average social welfare is efficient, it can lead to a "tyranny of the majority," where users with outlier preferences are underserved. Future work should incorporate "egalitarian" fairness metrics to ensure equitable service across the population. Additionally, addressing the "cold start" problem—identifying user preferences in real-time without prior simulation—and developing methods to dynamically determine the optimal budget $k$ remain open challenges.

Summary updated

Abstract

Personalization in machine learning (ML) tailors models' decisions to the individual characteristics of users. While this approach has seen success in areas like recommender systems, its expansion into high-stakes fields such as healthcare and autonomous driving is hindered by the extensive regulatory approval processes involved. To address this challenge, we propose a novel framework termed represented Markov Decision Processes (r-MDPs) that is designed to balance the need for personalization with the regulatory constraints. In an r-MDP, we cater to a diverse user population, each with unique preferences, through interaction with a small set of representative policies. Our objective is twofold: efficiently match each user to an appropriate representative policy and simultaneously optimize these policies to maximize overall social welfare. We develop two deep reinforcement learning algorithms that efficiently solve r-MDPs. These algorithms draw inspiration from the principles of classic K-means clustering and are underpinned by robust theoretical foundations. Our empirical investigations, conducted across a variety of simulated environments, showcase the algorithms' ability to facilitate meaningful personalization even under constrained policy budgets. Furthermore, they demonstrate scalability, efficiently adapting to larger policy budgets.
BibTeX
@inproceedings{ivanov2024personalized,
  author = {Dmitry Ivanov and Omer Ben-Porat},
  title = {{Personalized Reinforcement Learning with a Budget of Policies}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2024},
  doi = {10.1609/aaai.v38i11.29169},
}

Loading related content...

Figure