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.
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.
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