Artificial intelligence (AI) research is constantly pushing the boundaries of what machines can do. The ultimate aspiration is to create machines that not only replicate human capabilities but surpass them, executing tasks with greater efficiency and precision. In the early years of the 21st century, this ambition was channeled into solving tangible problems like automated helicopter flight and sophisticated locomotion in robots.
While machines have achieved superhuman performance in well-defined tasks such as playing Go and image classification, a significant gap remains in areas requiring subjective judgment and nuanced understanding of human values. Consider tasks like evaluating an artistic performance, navigating a cluttered environment safely, or, most fundamentally, understanding human preferences and intentions. These are domains where humans still hold a distinct advantage. To bridge this gap, machines need not only vast amounts of data about the world but also effective methods to learn from and about the humans within it.
This is where the concepts of Inverse Reinforcement Learning (IRL) and apprenticeship learning become crucial. These frameworks, developed nearly two decades ago, offer a pathway to address these discrepancies, paving the way for AI systems that can truly learn from human expertise and behavior. Understanding inverse reinforcement learning is a significant step towards creating more human-aligned and capable AI systems.
Inverse RL: Deciphering the Reward Function
In the realm of traditional Reinforcement Learning (RL), the primary objective is to train an agent to make decisions that maximize a predefined reward function. This reward function acts as a guide, explicitly defining the goals and desired outcomes for the agent. Inverse reinforcement learning, introduced by Andrew Ng and Stuart Russell in their seminal 2000 paper, inverts this paradigm. Instead of designing a reward function, IRL aims to infer the reward function from observing the behavior of an agent, typically a human expert.
Consider the complex task of autonomous driving. A conventional RL approach might involve meticulously crafting a reward function that incorporates every aspect of desirable driving behavior: stopping at traffic lights, staying within lane markings, yielding to pedestrians, and so on. However, this approach is inherently limited and cumbersome. It requires anticipating every conceivable scenario and assigning precise weights to each behavior – a nearly impossible task, especially when considering the relative importance of different safety regulations and social norms.
Alt text: Simulation of autonomous driving scenario, highlighting the decision-making process of a self-driving car.
In contrast, inverse reinforcement learning offers an elegant solution. By feeding the system with data from human driving experiences, IRL algorithms can learn to approximate the reward function that underlies human driving behavior. This learned reward function, even if simplified, encapsulates much of the essential information needed to solve the driving problem. As Ng and Russell astutely noted, “the reward function, rather than the policy, is the most succinct, robust, and transferable definition of the task.” The reward function provides a fundamental understanding of what constitutes good or bad actions in a given context. Once we have a well-defined reward function, the problem of autonomous driving is transformed into a standard reinforcement learning problem: finding a policy that maximizes this learned reward function.
In essence, for our self-driving car example, IRL leverages human driving data to automatically determine the appropriate weights for various features in the reward function. Crucially, IRL focuses on learning the task itself, defined by the reward function, rather than mimicking the specific policy employed by the human driver. This means we don’t need to perfectly understand how humans drive, but rather what goals they are trying to achieve. In broader terms, inverse reinforcement learning algorithms act as a powerful tool for extracting expert knowledge, converting complex task descriptions into concise and actionable reward functions.
However, a critical challenge in IRL is the inherent ambiguity in mapping behavior to reward functions. A single observed policy can be optimal for multiple, even vastly different, reward functions. This means that simply observing expert actions is not enough to uniquely determine the underlying reward. For instance, a trivial reward function that assigns zero reward to all states would technically be consistent with any observed policy, as all policies become equally optimal (or rather, equally non-optimal). Our goal in IRL is to find a reward function that is not only consistent with the expert’s behavior but also meaningfully captures the essence of the task, effectively distinguishing between desirable and undesirable actions.
To address this challenge, Ng and Russell framed inverse reinforcement learning as an optimization problem. The primary goal is to identify a reward function for which the observed expert policy is indeed optimal. However, within this constraint, we further seek a reward function that maximizes certain desirable properties, ensuring it is not just any optimal reward function, but one that is informative and useful.
Inverse RL in Finite State Spaces
To delve deeper into the mechanics of IRL, let’s consider a simplified scenario: a Markov Decision Process (MDP) with a finite set of states ($S$), a finite set of actions ($A$), and transition probability matrices ($P_a$) defining the outcomes of each action in each state.
In their foundational paper, Ng and Russell presented a key theorem demonstrating how to determine if a given policy is optimal within this finite MDP framework. Specifically, they proved that a policy $pi$, where $pi(s) equiv a_1$ (meaning action $a_1$ is always chosen in any state $s$), is optimal if and only if for all other possible actions $a$, the reward vector $R$ (which enumerates the reward for each state) satisfies the following condition:
$$ (P_{a_1} – Pa)(I – gamma P{a_1})^{-1} R succeq 0 $$
This theorem is significant because it provides a computationally tractable way to select the “best” reward function for which a given policy is optimal, using the tools of linear programming. This allows us to formulate IRL as a concrete optimization problem, where we aim to optimize heuristics that capture what makes a reward function a good fit for the observed expert data. Ng and Russell proposed two key heuristics:
-
Maximize the optimality margin: Maximize the difference in value between the optimal action (as demonstrated by the expert) and the next best alternative action. This maximization is typically subject to a constraint on the magnitude of the reward to prevent arbitrarily large differences. The intuition here is to find a reward function that clearly distinguishes the expert’s chosen policy as superior to other plausible policies. A larger margin implies a clearer preference for the expert’s actions.
-
Minimize reward complexity: Minimize the magnitude or complexity of the rewards in the reward vector or function. This heuristic is based on the principle of Occam’s Razor – simpler explanations are generally preferred. In the context of IRL, using smaller rewards encourages the algorithm to find a simpler, more parsimonious reward function. This is analogous to regularization techniques in supervised learning, which prevent overfitting by penalizing overly complex models. Ng and Russell specifically utilized the L1 norm with a tunable penalty coefficient ($lambda$), which promotes sparsity in the reward vector, effectively encouraging the reward to be non-zero in only a few key states.
Alt text: Illustration showing how increasing the penalty coefficient lambda in inverse reinforcement learning leads to a simpler estimated reward function, based on the work of Ng and Russell.
While these heuristics are intuitively appealing, it’s important to note that they are not exhaustive. Subsequent research has explored alternative heuristics and approaches to IRL. Notable examples include Maximum Entropy Inverse Reinforcement Learning (MaxEnt IRL) by Ziebart et al., and Bayesian Inverse Reinforcement Learning (BIRL) by Ramachandran et al., which offer different perspectives and refinements to the basic IRL framework, addressing some of its limitations and expanding its applicability.
Inverse Reinforcement Learning from Trajectories
Expanding upon the finite state space scenario, Ng and Russell also developed IRL algorithms to handle situations where we don’t have access to a complete expert policy but can only observe sampled trajectories generated by an optimal policy. This is a more realistic scenario in many real-world applications, particularly when dealing with human expert data, where we typically observe examples of behavior rather than a fully defined policy.
In this formulation, instead of working directly with a reward vector for each state, we approximate the reward function using a linear combination of feature functions. We define a set of feature functions $phi_i(s)$ that extract relevant information from the state space, transforming high-dimensional states into lower-dimensional feature vectors. For each feature $phi_i(s)$ and a corresponding weight $alpha_i$, the reward function is represented as:
$$ R(s) = alpha_1 phi_1(s) + alpha_2 phi_2(s) + dots + alpha_d phi_d(s) $$
The core objective then becomes to determine the optimal values for each feature weight $alpha_i$. These weights effectively define the relative importance of each feature in shaping the reward.
The general strategy for IRL from sampled trajectories is iterative refinement. The algorithm starts with an initial guess for the reward function and iteratively improves it by comparing the performance of the expert policy (as observed in the trajectories) with a set of policies generated by the algorithm itself. The process typically involves these key steps:
-
Value Estimation: Estimate the value of the expert policy, $hat{V}^{pi}(s_0)$, and the values of a set of $k$ generated policies, $hat{V}^{pi_i}(s_0)$, from a starting state $s_0$. This value estimation is typically done by averaging the cumulative reward obtained over multiple randomly sampled trials for each policy.
-
Reward Function Update: Update the estimated reward function $R$ by solving a linear programming problem. The goal is to adjust the feature weights $alpha_i$ to maximize the difference in value between the expert policy and each of the generated policies. This step refines the reward function to better reflect the preferences implied by the expert’s behavior.
-
Iteration Control: Determine whether to terminate the algorithm or continue iterating. If a sufficient number of iterations have been performed, the algorithm may terminate, returning the current estimated reward function.
-
Policy Generation: If continuing, use a standard reinforcement learning algorithm to find a new optimal policy $pi_{new}$ based on the updated reward function $R$. This new policy may differ from the expert policy, as the estimated reward function is still an approximation of the true underlying reward.
-
Policy Set Expansion: Add the newly generated policy $pi_{new}$ to the set of $k$ candidate policies, and repeat the procedure from step 1. This expands the set of policies being compared to the expert, leading to further refinement of the reward function.
This iterative process allows the algorithm to progressively refine its understanding of the reward function by comparing the expert’s performance against its own attempts to optimize behavior based on the current reward estimate.
Apprenticeship Learning: Learning from a Teacher’s Example
Beyond inferring reward functions, we can also directly learn a policy that performs comparably to an expert. This approach, known as apprenticeship learning, is particularly valuable when the expert policy is only approximately optimal, or when the primary goal is to replicate expert-level performance without explicitly needing to understand the underlying reward function. Apprenticeship learning, formalized by Pieter Abbeel and Andrew Ng in 2004, provides a solution for learning from a “teacher” policy with minimal exploration.
The “minimal exploration” aspect is particularly crucial in scenarios where excessive exploration can be costly or dangerous, such as in autonomous helicopter flight. A traditional RL algorithm, starting with random exploration, would likely lead to catastrophic failures early in the learning process (e.g., helicopter crashes). Ideally, we want to leverage expert demonstrations to establish a good initial policy that can be safely refined over time. This expert-guided initialization provides a significant advantage over random initialization, accelerating the learning process and mitigating risks associated with unguided exploration.
The Apprenticeship Learning Algorithm
Abbeel and Ng’s apprenticeship learning algorithm hinges on iteratively refining an estimated MDP model and learning policies based on that model, guided by expert demonstrations. The algorithm uses expert trajectories to gather information about the underlying MDP, then iteratively executes what it believes to be the best policy for the actual MDP. Each policy execution provides further data about environment transitions, allowing for continuous improvement of the MDP model. Here’s a breakdown of the algorithm in a discrete environment:
Phase 1: MDP Learning from Expert Policy
-
Expert Trajectory Collection: Run a fixed number of trials using the expert policy, recording every state-action trajectory observed. These trajectories serve as the primary source of information about the environment and expert behavior.
-
Transition Probability Estimation: Estimate the transition probabilities for every state-action pair based on the collected expert trajectories. Maximum likelihood estimation is a common method for this step. This creates a model of how the environment responds to different actions.
-
Expert Policy Value Estimation: Estimate the value of the expert policy by averaging the total reward obtained in each expert trial. This provides a benchmark for evaluating the performance of learned policies.
Phase 2: Iterative Policy Learning and Refinement
-
Policy Learning for Estimated MDP: Learn an optimal policy for the estimated MDP model obtained in Phase 1. Any standard reinforcement learning algorithm can be used for this step, such as value iteration or policy iteration.
-
Policy Testing in Actual Environment: Test the learned policy in the actual environment. This step is crucial for evaluating the policy’s real-world performance, as the estimated MDP model is only an approximation.
-
Performance Evaluation and Iteration: Compare the performance of the learned policy to the estimated value of the expert policy. If the performance is deemed “close enough” to the expert’s performance, the algorithm may terminate. Otherwise, add the state-action trajectories from the current trial (using the learned policy) to the training dataset (collected in Step 1) and repeat the procedure from Step 2. Including trajectories from the learned policy helps refine the MDP model and adapt to discrepancies between the estimated and actual environment.
The key advantage of this apprenticeship learning method is that at each iteration, the policy being tested is the algorithm’s best estimate of the optimal policy for the system. This minimizes the need for extensive exploration, as the algorithm leverages expert knowledge to guide its learning process. The core assumption underlying apprenticeship learning is that the expert policy is already near-optimal, providing a strong starting point for learning and refinement.
Future Directions in Inverse Reinforcement Learning
While foundational methods like inverse reinforcement learning, apprenticeship learning, and imitation learning have made significant strides by leveraging expert demonstrations, the long-term vision for AI is even more ambitious. The ultimate goal is for machine learning systems to learn from diverse human data sources and ultimately surpass human capabilities in complex tasks.
Andrew Ng and Stuart Russell, in their discussion of future research directions for inverse reinforcement learning, emphasize the critical issue of suboptimality in expert actions. In real-world scenarios, especially when learning from human experts, it’s unrealistic to assume that the observed expert policy is perfectly optimal. Experts may exhibit biases, make mistakes, or operate under constraints not fully captured in the environment model. A key challenge for future IRL research is to develop methods that can effectively extract reward functions even when the demonstrated expert behavior is suboptimal. This requires algorithms that are robust to noise and imperfections in expert data.
Another exciting direction is learning from human identification rather than demonstration. This paradigm shifts the focus from requiring an expert policy to simply needing a human to identify desired behaviors. This is particularly relevant in domains where humans can easily recognize correct or incorrect behavior but struggle to explicitly demonstrate the correct control sequence. For example, humans can readily judge if an agent in a physics simulator is running realistically, even if they cannot manually program the complex control sequence needed to achieve realistic running. This approach, which might involve using classifiers trained by humans to evaluate agent behavior, could enable reinforcement learning systems to achieve human-approved performance in tasks where expert policies are unavailable or difficult to obtain.
The transition from the early 2000s to the present day has seen significant progress in scaling up inverse reinforcement learning methods to work with deep learning architectures. Recent research has explored using deep neural networks to approximate reward functions, enabling IRL to handle high-dimensional state and action spaces. For example, Wulfmeier et al. have employed fully convolutional neural networks for reward function approximation, while Finn et al. have applied neural networks to solve inverse optimal control problems in robotics. As these deep IRL methods continue to advance, inverse reinforcement learning is poised to play an increasingly vital role in developing AI systems that can learn complex skills and policies that transcend human limitations.
Citation:
For academic or book citations, please use:
Jordan Alexander, “Learning from humans: what is inverse reinforcement learning?”, The Gradient, 2018.
BibTeX Citation:
@article{alexander2018humanreinforcement, author = {Alexander, Jordan} title = {Learning from humans: what is inverse reinforcement learning?}, journal = {The Gradient}, year = {2018}, howpublished = {url{https://thegradient.pub/learning-from-humans-what-is-inverse-reinforcement-learning/} } }, }
