Regret-based Reward Elicitation for Markov Decision Processes

Kevin Regan, Craig Boutilier

Abstract

The specification of a Markov 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.

Introduction

Specifying exact numerical rewards for Markov Decision Processes (MDPs) is a significant challenge in reinforcement learning and decision theory. Humans often struggle to map fuzzy preferences into precise values, and the conflation of immediate rewards with long-term value further complicates the process. This paper addresses the problem of reward elicitation: minimizing the number and complexity of queries required to identify an optimal or near-optimal policy. Rather than attempting to learn the full reward function, the authors focus on learning only what is necessary to make the correct decision.

Methodology: Minimax Regret and Elicitation

The proposed approach utilizes the minimax regret (MMR) criterion to handle imprecise reward information. MMR evaluates a policy based on its worst-case loss relative to the true optimal policy across all reward functions consistent with current knowledge. This is contrasted with the more pessimistic "maximin" approach, which focuses on absolute worst-case outcomes rather than relative loss.

Computation via Benders' Decomposition

Computing MMR exactly is computationally intensive. The authors formulate the problem as a mathematical program and solve it using Benders' Decomposition. This involves iteratively solving a Master Problem (a linear program) to suggest policies and a Subproblem (a Mixed-Integer Program) to identify adversarial reward functions that maximize regret.

Elicitation Heuristics

To reduce regret efficiently, the system uses "bound queries" (e.g., "Is the reward for state $s$ and action $a$ at least 0.5?"). Two strategies for query selection are compared:

  • Halve Largest Gap (HLG): A simple strategy that focuses on reducing the largest interval of uncertainty in the reward space.
  • Current Solution (CS): A more targeted heuristic that weights uncertainty by the state-action visitation frequency of the current optimal and adversarial policies. This ensures that elicitation efforts are focused on the most decision-relevant parts of the state space.

Experimental Evaluation

The approach was evaluated on two distinct environments:

  1. Randomly Generated MDPs: Used to assess scalability and general performance across varying state and action space sizes.
  2. Autonomic Computing Scenario: A 90-state, 10-action simulation of resource allocation for application servers, featuring structured rewards based on server utilities and costs.

Key Results and Discussion

Efficiency and Targeted Elicitation

The "Current Solution" (CS) heuristic proved significantly more efficient than HLG. By focusing on high-impact state-action pairs, the system ignores large portions of the reward function that do not affect the final policy choice. In random MDP tests, the MMR-CS strategy found provably optimal policies using fewer than two queries per reward parameter on average.

Distribution of queries required per reward point, showing that most parameters require zero queries to reach optimality.

In the autonomic computing domain, MMR-CS reached near-zero regret by querying only 12% of the reward space, whereas a maximin-based strategy required 68% coverage to achieve similar results.

Anytime Performance

The algorithm exhibits strong anytime performance. The regret gap closes very rapidly in the initial stages of elicitation, meaning the system can provide a high-quality policy even if the process is terminated before reaching zero regret.

Reward gap reduction over time, demonstrating that the system rapidly converges toward a low-regret policy.

Conclusion

Minimax regret provides a robust framework for MDPs with partial reward information. By focusing on regret reduction rather than full reward learning, the MMR-CS approach effectively produces near-optimal policies with minimal user burden. While the computational complexity of the adversarial subproblem remains a challenge for very large MDPs, the efficiency of the elicitation process suggests that precision is often unnecessary for optimal decision-making. Future work will explore more intuitive query types, such as trajectory comparisons, to further simplify the elicitation process for human experts.

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