Efficient Reward Identification In Max Entropy Reinforcement Learning with Sparsity and Rank Priors
Mohamad Louai Shehab Alperen Tercan Necmiye Ozay · 2025
Read Efficient Reward Identification In Max Entropy Reinforcement Learning with Sparsity and Rank Priors by Mohamad Louai Shehab Alperen Tercan Necmiye Ozay (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2508-07400.txt.
Introduction
Mohamad Louai Shehab, Alperen Tercan, and Necmiye Ozay recover reward functions from behavior in max entropy reinforcement learning in a 2025 paper. Learning the hidden reward behind a policy or a set of demonstrations is ill posed without extra assumptions. Two common priors make it tractable, rewards that stay mostly constant and change rarely, or rewards built from a few feature functions.
With the first prior, the task becomes a sparsification problem under linear constraints, and the authors give an exact method that runs in polynomial time. With the second, it becomes a rank minimization problem where convex relaxations apply. Examples show the recovered rewards are accurate and generalize well.
Catalog record
| CREATOR | Mohamad Louai Shehab Alperen Tercan Necmiye Ozay |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 43 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2508-07400
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Efficient Reward Identification In Max Entropy Reinforcement Learning with Sparsity and Rank Priors Mohamad Louai Shehab Alperen Tercan Necmiye Ozay Abstract In this paper, we consider the problem of recovering time-varying reward functions from either optimal policies or demonstrations coming from a max entropy reinforcement learning problem. This problem is highly ill-posed without additional assumptions on the underlying rewards. However, in many applications, the rewards are indeed parsimonious, and some prior information is available. We consider two such priors on the rewards: 1) rewards are mostly constant and they change infrequently, 2) rewards can be represented by a linear combination of a small number of feature functions. We first show that the reward identification problem with the former prior can be recast as a sparsification problem subject to linear constraints. Moreover, we give a polynomial-time algorithm that solves this sparsification problem exactly. Then, we show that identifying rewards representable with the minimum number of features can be recast as a rank minimization problem subject to linear constraints, for which convex relaxations of rank can be invoked. In both cases, these observations lead to efficient optimization-based reward identification algorithms. Several examples are given to demonstrate the accuracy of the recovered rewards as well as their generalizability. I INTRODUCTION Reward identification, or Inverse Reinforcement Learning (IRL), is the problem of learning rewards from data. The premise behind IRL is that the reward function serves as the most succinct representation of an agent’s behavior [ 1 ] . Learning a reward function from demonstrations allows agents to generalize beyond observed behaviors [ 1 ] , infer underlying human intentions [ 2 ] , and capture pairwise preferences [ 3 , 4 ] . However, like many inverse problems, IRL is inherently ill-posed as there may be infinitely many reward functions consistent with the same observed behavior [ 5 , 6 , 7 ] . For instance, suppose an agent moves from location A to location B . One possible hypothesis is that the agent likes B , but another equally valid hypothesis is that the agent dislikes A . Both reward hypotheses are consistent with the observed behavior, highlighting the fundamental ambiguity in IRL [ 8 ] . To address this ambiguity, recent research has shifted toward learning the entire set of reward functions that can explain observed behaviors [ 9 , 10 , 11 , 12 ] . However, there is generally no consensus on how to select a specific reward function from within this set. The choice is often guided by the requirements of the downstream task or heuristic considerations. For example, Linear Programming IRL [ 1 ] and Max Margin IRL [ 13 ] select the reward function that makes the demonstrated policy as optimal as possible relative to the next-best alternative, effectively maximizing the opportunity cost—a principle widely studied in economics, where rational agents seek to maximize the value of their chosen actions relative to foregone alternatives [ 14 ] . Adversarial IRL [ 15 ] aims to find a reward function that generalizes well across environments, often selecting a state-only reward that maximizes transferability. Maximum Entropy IRL [ 16 ] selects the reward function that maximizes the likelihood of the observed demonstrations, assuming an entropy-regularized policy model. More recently, [ 17 ] introduced a framework for quantitatively selecting the best reward—potentially outside the solution set—based on a given target application. In this work, we study reward identification in finite-horizon settings with time-varying reward functions. This is an important generalization for real-world applications where rewards evolve over time due to changing preferences, environmental conditions, or task requirements. While most prior IRL methods assume static rewards, the dynamic setting makes IRL even more ill-posed, as reward ambiguity can now arise at every time step [ 6 , 18 ] . Existing approaches for dynamic rewards either (1) impose restrictive parametric assumptions (e.g., Gaussian random walks [ 19 ] or generalized linear models [ 20 ] ), limiting their expressiveness to predefined reward dynamics, or (2) assume privileged knowledge on the number of underlying reward regimes [ 21 ] . Relatedly, learning time-varying objective functions is also considered in the area of inverse optimal control [ 22 , 23 ] . Building on prior work, we propose a principled framework that systematically incorporates structure-aware priors—such as minimal reward switches and shared feature bases—to resolve ambiguity in time-varying reward identification, enabling flexible yet interpretable reward identification without strong parametric assumptions. Our contributions include (1) a polynomial-time algorithm for recovering minimally switching rewards, (2) a convex relaxation for feature-based reward decomposition, and (3) robustness guarantees under finite-sample policy estimates. Empirical results validate our approach in several gridworld environments, showing improved interpretability and transferability over existing methods. II PRELIMINARIES II-A Notation \mathbb{R} and \mathbb{N} are the sets of real and natural numbers respectively. The identity matrix in \mathbb{R}^{n\times n} is denoted by \mathbf{I}_{n} . The zero matrix in \mathbb{R}^{m\times n} is denoted by \mathbf{0}_{m\times n} ( m are n are dropped sometimes when they are clear from context). \mathbf{1}_{m} is the constant vector of ones in \mathbb{R}^{m} . \mathbb{I}(x\in X) is the indicator function. Given a matrix A , \mathrm{rank}(A)\text{ and }\mathrm{colspan}(A) denote its rank and column span, respectively. When B is another matrix of compatible dimension, \begin{bmatrix}A&B\end{bmatrix} denotes the horizontal concatenation of A and B , and A\otimes B denotes their Kronecker product. Given a vector space V with a basis B=\{v_{1},\cdots,v_{m}\} , [w]_{B} is the vector representation of w in V . For a set S , \Delta(S) denotes the set of probability distributions over it, and |S| denotes its cardinality. II-B Markov Decision Processes A Markov Decision Process (MDP) is a tuple \mathcal{M}=(\mathcal{S},\mathcal{A},\mathcal{\mathcal{T}},\mu_{0},r,\gamma,T) , where \mathcal{S}=\{s^{(1)},\dots,s^{(n)}\} is a finite set of states with cardinality |\mathcal{S}|=n ; \mathcal{A}=\{a^{(1)},\dots,a^{(m)}\} is a finite set of actions with cardinality |\mathcal{A}|=m ; \mathcal{T}:\mathcal{S}\times\mathcal{A}\to\Delta(\mathcal{S}) is a Markov transition kernel; \mu_{0}\in\Delta(S) is an initial distribution over the set of states; r=(r_{t})_{t=0}^{T-1}\text{ is a time-varying reward function where each }r_{t}:\mathcal{S}\times\mathcal{A}\to\mathbb{R} is the reward function at time step t ; \gamma\in[0,1] is a discount factor; and T\in\mathbb{N} is the non-negative time horizon. An MDP without a reward function, denoted \mathcal{M}\setminus r , is called an MDP model . A policy \pi_{t}:\mathcal{S}\to\Delta(\mathcal{A}) is a function that describes an agent’s behavior at time step t by specifying an action distribution at each state. We denote by \pi=(\pi_{t})_{t=0}^{T-1} the time-varying stochastic policy throughout the entire horizon. A trajectory \tau (of length T ) is an alternating sequence of states and actions (ending with a state), i.e., \tau=(s_{0},a_{0},s_{1},a_{1},\dots,s_{T-1},a_{T-1},s_{T}) with s_{t}\in\mathcal{S} and a_{t}\in\mathcal{A} . Under a policy \pi , a trajectory \tau occurs with probability \mathbb{P}_{\mu_{0}}^{\pi}(\tau)=\mu_{0}(s_{0})\prod\limits_{t=0}^{T-1}\pi_{t}(a_{t}|s_{t})\prod\limits_{t=0}^{T-1}\mathcal{T}(s_{t+1}|s_{t},a_{t}), (1) which depends on the distribution of initial states, the policy, and the Markov transition kernel. We consider the Maximum Entropy Reinforcement Learning (MaxEntRL) objective given by: J_{\text{MaxEnt}}(\pi;r)=\mathbb{E}^{\pi}_{\mu_{0}}[\sum\limits_{t=0}^{T-1}\gamma^{t}\biggl(r(s_{t},a_{t})+\mathcal{H}(\pi_{t}(.|s_{t}))\biggr)], (2) where \mathcal{H}(\pi_{t}(.|s_{t}))=-\sum\limits_{a\in\mathcal{A}}\pi_{t}(a|s_{t})\log(\pi_{t}(a|s_{t})) is the entropy of the policy \pi_{t} . The expectation is with respect to the probability measure \mathbb{P}^{\pi}_{\mu_{0}} . We define the optimal policy \pi_{r}^{*} , corresponding to a reward function r , as the maximizer of ( 2 ), i.e.: \pi_{r}^{*}=\arg\max\limits_{\pi}J_{\text{MaxEnt}}(\pi;r), (3) which is known to be unique [ 24 ] up-to accessible states. The maximum entropy policy is [ 25 , 26 , 27 ] :