Apprenticeship learning with prior beliefs using inverse optimization

This paper unifies inverse reinforcement learning, inverse optimization, and apprenticeship learning by incorporating prior beliefs into a regularized min-max framework that resolves the ill-posedness of cost function learning and is solved via stochastic mirror descent with established convergence guarantees.

The Gist

The Big Picture: Teaching a Robot by Watching a Flawed Human

Imagine you are trying to teach a robot how to drive a car. You don't know the rules of the road (the "cost function"), but you have a video of a human driver.

• The Problem: The human driver isn't perfect. Maybe they are tired, maybe they are driving a different car, or maybe they just made a few mistakes. If you try to copy them exactly, the robot might learn bad habits.
• The Old Way: Previous methods tried to figure out exactly what the human was thinking. But because the human made mistakes, there were infinite possibilities for what they were thinking. It was like trying to guess a password with no clues.
• The New Way (This Paper): The authors say, "Let's bring in a hunch." Before we even look at the video, we have a general idea of what driving should look like (e.g., "Don't hit walls," "Get to the destination"). We combine this hunch with the video of the driver. If the driver does something weird, our hunch helps us decide if it was a mistake or a clever trick.

---

The Core Concepts (Translated)

1. The "Ghost" of the Cost Function

In robotics, every action has a "cost." Turning left might cost 1 point; crashing costs 1,000 points. The robot's goal is to minimize these points.

• The Mystery: We don't know the point system. We only see the driver's moves.
• The Inverse Problem: Usually, you give a robot the points, and it learns the moves. Here, we see the moves and have to guess the points. This is called Inverse Reinforcement Learning (IRL).

2. The "Suboptimal" Expert

The paper focuses on a realistic scenario: the expert (the human driver) is suboptimal. They aren't perfect.

• The Analogy: Imagine a cooking show where the chef is trying to make a perfect soufflé but drops an egg.
  • If you only watch the chef, you might think "dropping eggs" is part of the recipe.
  • If you have a prior belief (a hunch) that "eggs should go in the bowl, not the floor," you can ignore the drop and learn the real recipe.
• The Paper's Solution: They introduce a Proxy Cost Vector ($\hat{c}$). This is your "hunch" or "prior belief." It's a rough guess of the rules (e.g., "I think crashing is bad").

3. The Balancing Act (The Regularization Parameter $\alpha$)

This is the secret sauce of the paper. They create a mathematical tug-of-war between two things:

1. The Hunch ($\hat{c}$): "I think the rules are X."
2. The Evidence ($\pi_E$): "But the expert did Y."

They use a dial called $\alpha$ (alpha) to control the balance:

• Turn $\alpha$ up (High): You trust your hunch more. If the expert does something weird, you assume they made a mistake and stick to your hunch.
• Turn $\alpha$ down (Low): You trust the expert more. You assume your hunch is wrong and the expert knows something you don't.

The Metaphor: Think of it like a GPS.

• If the GPS (your hunch) says "Turn Left," but the driver (the expert) swerves Right because there's a pothole, the GPS needs to decide: Is the driver crazy, or is the map wrong?
• The paper's algorithm figures out the perfect balance so the robot learns the real rules, not just the driver's mistakes.

4. The "Convex Hull" vs. The "Box"

Previous methods forced the robot to guess the rules from a tiny, pre-defined list of options (like choosing a color only from a box of 5 crayons). This is called the Convex Hull.

• The Limitation: What if the real rule isn't one of those 5 crayons? The robot gets stuck.
• The New Approach: The authors let the robot pick from a giant box of all possible crayons (the Box). They use the "hunch" to guide the robot toward the right color without forcing it into a tiny box. This makes the robot much more flexible and able to handle complex, high-dimensional worlds (like a huge maze).

---

How They Solved It (The Algorithm)

To find the perfect balance between the hunch and the expert, they used a method called Stochastic Mirror Descent (SMD).

• The Analogy: Imagine you are blindfolded in a mountain valley, trying to find the lowest point (the best cost function).
  • You can't see the whole valley.
  • You take a step, feel the ground, and take another step.
  • Because you have a "hunch" about where the valley is, you don't wander aimlessly. You use that hunch to guide your steps.
  • The algorithm does this mathematically, taking thousands of tiny steps to find the perfect cost function and the perfect robot policy.

Why Does This Matter? (The Results)

The authors tested this on two things:

1. Inventory Management: A robot managing a warehouse.
   • Result: Even when the "expert" was bad at managing stock, the robot learned the true rules of inventory management by trusting the "hunch" about how costs work.
2. Gridworld: A robot navigating a maze with obstacles.
   • Result: In complex mazes, the old methods (the "5 crayon" approach) failed because the maze was too big. The new method (the "giant box" approach) succeeded, learning a cost map that perfectly avoided obstacles, even when the expert occasionally walked into them.

The Takeaway

This paper solves a major headache in AI: What do we do when our teacher is imperfect?

By combining what we think we know (our prior beliefs) with what we observe (the expert's actions), and using a mathematical dial to balance them, we can teach robots to learn the true rules of the world, even if the human demonstrating them is making mistakes. It turns a messy, confusing problem into a clean, solvable math puzzle.

Technical Summary

1. Problem Statement

The paper addresses the fundamental challenges in Inverse Reinforcement Learning (IRL) and Apprenticeship Learning (AL) within the context of Markov Decision Processes (MDPs).

• The Core Challenge: In standard RL, the cost function is known, but in real-world scenarios, it is difficult to specify. IRL attempts to infer the cost function from an expert's behavior. However, IRL is ill-posed: multiple cost functions can explain the same expert behavior, leading to ambiguity.
• Limitations of Existing Approaches:
  • Traditional AL (e.g., Abbeel & Ng, 2004) assumes the true cost lies in a convex hull of pre-defined basis functions (features). This requires difficult feature engineering and limits flexibility.
  • Existing methods often assume the expert is optimal. In reality, experts are often suboptimal, rendering standard inverse feasibility conditions (like complementary slackness) infeasible.
  • Many methods rely on Reinforcement Learning (RL) as a subroutine, leading to high computational costs.
• The Goal: The authors aim to develop a framework that:
  1. Incorporates prior beliefs about the cost function structure to resolve the ill-posed nature of IRL.
  2. Handles suboptimal experts without requiring the expert to be perfectly optimal.
  3. Avoids the rigid assumption of a pre-defined convex hull of basis functions.
  4. Provides a computationally efficient solution using mathematical optimization tools rather than nested RL loops.

2. Methodology

The authors propose a unified framework grounded in Inverse Optimization (IO) that bridges IRL and AL.

A. Theoretical Formulation

1. Inverse Optimization Viewpoint (IRL-IO):
   The problem is framed as finding a cost vector $c$ such that the observed expert policy $\pi_E$ is optimal. Using Lagrangian duality, the set of feasible costs (inverse-feasible set) is characterized.
2. Incorporating Prior Beliefs (IRL-IO$\hat{c}$):
   To address ill-posedness, the authors introduce a proxy cost vector $\hat{c}$ representing prior beliefs (e.g., from domain knowledge). They formulate a projection problem to find the cost $c$ closest to $\hat{c}$ that satisfies the expert's optimality conditions.
3. Handling Suboptimal Experts (IO-AL$\alpha$):
   Recognizing that experts may be suboptimal, the authors relax the strict complementary slackness condition. They propose a regularized min-max problem:
   $$\min_{c, u} \alpha \|c - \hat{c}\|_2^2 + \langle \mu_{\pi_E}, c - T_\gamma^\top u \rangle$$
   $$\text{s.t. } c - T_\gamma^\top u \geq 0$$
   • $\alpha$ (Regularization Parameter): Controls the trade-off between adhering to the prior belief $\hat{c}$ and fitting the expert's demonstrated behavior.
   • Variables: $c$ is the cost vector, $u$ is the value function (dual variable), and $\mu$ is the occupancy measure.
   • Interpretation: The term $\langle \mu_{\pi_E}, c - T_\gamma^\top u \rangle$ represents the suboptimality gap of the expert. Minimizing this while penalizing deviation from $\hat{c}$ allows learning even when the expert is not optimal.

B. Algorithm: Stochastic Mirror Descent (SMD-RLfD)

The formulated problem is a convex-concave min-max problem. The authors solve it using Stochastic Mirror Descent (SMD), adapted from Jin & Sidford (2020).

• Unconstrained Reformulation: The problem is converted into an unconstrained min-max form using Lagrangian duality.
• Gradient Estimators: Since the transition dynamics and expert occupancy measures are accessed via oracles (not explicit matrices), the authors derive unbiased stochastic gradient estimators for both the cost/value variables $(c, u)$ and the occupancy measure $\mu$.
• Algorithm Steps:
  1. Sample transitions from the expert's occupancy measure and the MDP transition oracle.
  2. Compute stochastic gradients.
  3. Perform mirror descent updates with projection onto the feasible sets (Box for $c, u$; Simplex for $\mu$).
  4. Return the average of iterates as an $\epsilon$-approximate solution.

C. Theoretical Guarantees

• Convergence: The authors establish convergence bounds for the duality gap. The number of iterations $T$ required scales quadratically with the number of actions and cubically with the number of states ($O(|S|^3|A|^2/\epsilon^2)$).
• Approximation Quality: They prove that the output of the algorithm yields an expected objective value within $\epsilon$ of the optimal solution of the regularized problem (Proposition 4).
• Connection to AL: They demonstrate that the convex-analytic AL formalism (Kamoutsi et al., 2021) is a special case of their framework when the regularization term ($\alpha$) is zero and the cost is restricted to a convex hull.

3. Key Contributions

1. Unified Framework: Revisits the relationship between IRL, AL, and IO, showing that AL is a relaxation of a broader IO framework.
2. Suboptimal Expert Handling: Introduces the IO-AL$\alpha$ formulation, which explicitly handles suboptimal experts by relaxing optimality constraints and using regularization.
3. Prior Belief Integration: Incorporates a proxy cost vector $\hat{c}$ to guide the search, resolving the ill-posedness of IRL without requiring the expert to be optimal.
4. General Cost Functions: Moves beyond the restrictive assumption that costs must be linear combinations of pre-defined basis functions (convex hull), allowing for a general convex class of cost functions.
5. Algorithm & Theory: Proposes SMD-RLfD, a stochastic algorithm with proven convergence bounds for solving the regularized min-max problem.

4. Experimental Results

The authors evaluated the framework on two case studies: a Single-Product Inventory Control problem (low-dimensional) and a Gridworld environment (higher-dimensional).

• Inventory Control:

  • Prior Sensitivity: The method successfully recovered near-optimal policies even when the proxy cost $\hat{c}$ was misspecified, provided the regularization parameter $\alpha$ was tuned.
  • Suboptimality: When the expert was suboptimal, increasing $\alpha$ (relying more on the prior) significantly improved the recovery of the true cost vector and the performance of the apprentice policy compared to the suboptimal expert.
  • Convex Hull vs. Box: Compared against the convex hull approach (Kamoutsi et al., 2021). While the convex hull converged faster in low dimensions, the proposed "box" formulation (general cost space) outperformed it as the state space dimension increased, demonstrating greater flexibility.

• Gridworld:

  • Feature Engineering: Highlighted that the method does not require pre-defining basis vectors, which is a major advantage in complex environments where feature engineering is difficult.
  • Regularization Impact: Experiments showed that appropriate regularization ($\alpha > 0$) helped the algorithm learn a cost vector that aligned better with the true environment structure, even when the prior was imperfect.
  • Convergence: Stronger regularization accelerated the convergence of the cost vector $c$ but slowed the convergence of the duality gap, consistent with theoretical predictions.

5. Significance and Conclusion

This work provides a significant theoretical and practical advancement in Apprenticeship Learning:

• Robustness: It offers a robust solution for scenarios where expert data is noisy or suboptimal, a common real-world constraint often ignored in theoretical IRL.
• Flexibility: By removing the dependency on pre-defined basis functions, the method is applicable to a wider range of problems where the cost structure is unknown or complex.
• Theoretical Clarity: It clarifies the mathematical relationship between IRL and AL, showing how regularization acts as a bridge between prior knowledge and observed data.
• Practical Utility: The use of Stochastic Mirror Descent allows the method to scale to larger state spaces without the computational burden of nested RL loops.

The paper concludes that incorporating prior beliefs via regularization is critical for learning accurate cost vectors and policies, especially when dealing with imperfect experts. Future work suggested includes developing criteria for selecting $\alpha$ and exploring sparsity-inducing norms ($\ell_0$) for cost vectors.