Regret-based Reward Elicitation for Markov Decision Processes

Kevin Regan, Craig Boutilier

Introduction

A significant hurdle in deploying autonomous agents is the "reward specification problem." While Markov Decision Processes (MDPs) provide a robust framework for decision-making, they rely on a precisely defined reward function. In practice, human experts find it difficult to provide exact numerical values for every state-action pair. This paper, authored by Kevin Regan and Craig Boutilier, proposes a minimax regret framework to find optimal policies using only partially specified rewards, elicited through targeted queries.

The Challenge of Reward Specification

Traditional Reinforcement Learning assumes the reward function is known. However, translating human preferences into precise decimals is cognitively taxing and error-prone. While "maximin" approaches offer robustness by assuming the worst-case reward, they often result in overly conservative and mediocre policies. The authors argue for a "middle ground" that seeks high-quality policies while minimizing the burden on the user.

Methodology

Minimax Regret (MMR)

The core of the approach is the Minimax Regret criterion. Instead of maximizing the worst-case value, MMR identifies a policy that minimizes the maximum possible "loss" (regret) relative to the optimal policy under any feasible reward realization. This approach is more intuitive as it evaluates a policy by how much better it could have been if the true rewards were known.

Benders' Decomposition

Computing MMR is computationally intensive. The authors formulate the problem as a mathematical program and solve it using Benders' decomposition. This iterative process involves a "Master Problem" that proposes a policy and a "Subproblem" (an adversary) that identifies the reward function maximizing the regret for that policy.

Regret-Based Elicitation

To refine the reward bounds, the system uses the Current Solution (CS) heuristic. It asks "bound queries" (e.g., "Is the reward for state $s$ and action $a$ at least $x$?") focusing on state-action pairs that are both highly uncertain and frequently visited by either the current policy or the adversarial policy.

Key Results

Anytime Performance and Convergence

One of the most significant findings is the "anytime" nature of the algorithm. The regret gap—the difference between the current policy's performance and the theoretical optimum—decreases rapidly in the initial stages of the process.

Figure 1: The reward gap narrows significantly in the early stages of the elicitation process, allowing for high-quality policies even with early termination.

Query Efficiency

The MMR-CS strategy proves remarkably efficient. In an autonomic computing resource allocation scenario with 900 reward parameters, the system reached near-zero regret by querying only about 12% of the reward space.

Figure 2: A histogram showing that the vast majority of reward points require zero queries, demonstrating that the system ignores irrelevant regions of the state space.

On average, the system required fewer than 0.25 queries per state-action pair. This confirms that precise reward values are unnecessary for states that are rarely visited or clearly dominated by other options.

Approximation and Scalability

While exact MMR computation involves complex Mixed Integer Programming, the authors demonstrated that a linear relaxation provides a very close approximation (typically under 10% relative error). This makes the approach practical for larger domains where exact solutions might be computationally prohibitive.

Conclusion

Regan and Boutilier demonstrate that we do not need perfect information to make perfect decisions. By focusing on regret rather than absolute reward, and by intelligently targeting queries to high-impact states, their framework significantly reduces the human effort required to train autonomous agents in complex MDP environments. Future work aims to extend this to factored MDPs and more sophisticated query types, such as trajectory comparisons.

Summary updated

Abstract

The specification of aMarkov decision process (MDP) can be difficult. Reward function specification is especially problematic; in practice, it is often cognitively complex and time-consuming for users to precisely specify rewards. This work casts the problem of specifying rewards as one of preference elicitation and aims to minimize the degree of precision with which a reward function must be specified while still allowing optimal or near-optimal policies to be produced. We first discuss how robust policies can be computed for MDPs given only partial reward information using the minimax regret criterion. We then demonstrate how regret can be reduced by efficiently eliciting reward information using bound queries, using regret-reduction as a means for choosing suitable queries. Empirical results demonstrate that regret-based reward elicitation offers an effective way to produce near-optimal policies without resorting to the precise specification of the entire reward function.
BibTeX
@inproceedings{regan2009regret,
  author = {Kevin Regan and Craig Boutilier},
  title = {{Regret-based Reward Elicitation for Markov Decision Processes}},
  booktitle = {Conference on Uncertainty in Artificial Intelligence},
  year = {2009},
  url = {https://openreview.net/forum?id=nAB8rWNdO1},
}
Figure