Year: 2021

Abstract:
Understanding a decision-maker’s priorities by observing their behavior is critical for transparency and accountability in decision processes—such as in healthcare. Though conventional approaches to policy learning almost invariably assume stationarity in behavior, this is hardly true in practice: Medical practice is constantly evolving as clinical professionals fine-tune their knowledge over time. For instance, as the medical community’s understanding of organ transplantations has progressed over the years, a pertinent question is: How have actual organ allocation policies been evolving? To give an answer, we desire a policy learning method that provides interpretable representations of decision-making, in particular capturing an agent’s non-stationary knowledge of the world, as well as operating in an offline manner. First, we model the evolving behavior of decision-makers in terms of contextual bandits, and formalize the problem of Inverse Contextual Bandits (ICB). Second, we propose two concrete algorithms as solutions, learning parametric and nonparametric representations of an agent’s behavior. Finally, using both real and simulated data for liver transplantations, we illustrate the applicability and explainability of our method, as well as benchmarking and validating the accuracy of our algorithms.

heading: 1 INTRODUCTION
text: Modeling decision-making policies is a central concern in computational and behavioral science, with key applications in healthcare [1], economics [2], and cognition [3]. The business of policy learning is to determine an agent’s decision-making policy given observations of their behavior. Typically, the objective is either to replicate the behavior of some demonstrator (cf. “imitation learning”) [4, 5], or to match their performance on the basis of some reward function (cf. “apprenticeship learning”) [6, 7]. However, equally important is the pursuit of “descriptive modeling” [8, 9]—that is, of learning interpretable parameterizations of behavior for auditing, quantifying, and understanding decision-making policies. For instance, recent work has studied representing behaviors in terms of rules [10], goals [11], intentions [12], preferences [13], subjective dynamics [14], as well as counterfactual outcomes [15].
Evolving Behaviors In this work, we ask a novel descriptive question: How has the observed behavior changed over time? While conventional approaches to policy learning almost invariably assume that decision-making agents are stationary, this is rarely the case in practice: In many settings, behaviors evolve constantly as decision-makers learn more about their environment and adjust their policies accordingly. In fact, disseminating new knowledge from medical research into actual clinical practice is itself a major endeavor in healthcare [16–18]. This research question is new: While capturing “variation in practice” in observed data has been studied in the context of demonstrations containing mixed policies [19, 20], multiple tasks [21, 22], and subgroup-/patient-specific preferences [8], little work has attempted to capture variation in practice over time as an agent’s knowledge of the world evolves.
Example (Organ Allocations) As our core application, consider organ allocation practices for liver transplantations: In the medical community, our understanding of organ transplantations has changed numerous times over past decades [23–25]. Thus an immediate question lies in how actual organ allocation practices have changed over the years. Having a data-driven, quantitative, and— importantly—interpretable description of how practices have evolved is crucial: It would enable policy-makers to evaluate if the policies they introduced have had the intended impact on practice; this would in turn play a substantial role in designing better policies going forward [8] (see Figure 1).
To tackle questions of this form, we desire a policy learning method that satisfies three key desiderata:
• It should provide an (i.) interpretable description of observed behavior (see Appendix C).
Suppose that policy-makers introduce a new policy to promote Features A and B as main factors of consideration in decision-making (whereas clinicians rely on Feature C at the time), and the policy succeeds at establishing Feature A as such but fails to do so for Feature B. Using ICB, we can infer the time-varying importances of these features and observe quantitatively that importance of Feature B stayed the same despite the intentions of the new policy. Having made this observation, the policymakers can now update their policy accordingly.
• It should be able to capture an agent’s (ii.) nonstationary knowledge of the world.
• It should operate in an (iii.) offline manner— since online experimentation is impossible in highstakes environments such as healthcare.
Inverse Contextual Bandits To accomplish this, we first identify the organ allocation problem as a contextual bandits problem [26–28]: Given each arriving instance of patient and organ features (i.e. the context), an agent makes an allocation decision (i.e. the action), whence some measure of feedback is perceived (i.e. internal reward). Crucially, the environment (i.e. precisely, its reward dynamics) is unknown to the agent and must be actively learned, so the agent maintains beliefs about their environment (i.e. internal knowledge). Not only must an agent select actions that “exploit” the knowledge they have, but they must also select actions that “explore” the environment to update their knowledge. Thus the behavior of a
learning agent is naturally modeled as a generalized bandit strategy—that is, how to take actions based on their knowledge, and how to update their knowledge based on the outcomes of their actions.
Now, the forward contextual bandits problem asks the (normative) question: Given an unknown environment, what is an effective bandit strategy that minimizes some notion of regret? By contrast, our focus here is instead on the opposite direction—that is, in formalizing and solving the problem of Inverse Contextual Bandits (“ICB”): We ask the (descriptive) question: Given demonstrated behavior from a decision-making agent, how has the agent’s knowledge been evolving over time? Precisely, we wish to learn interpretable representations of generalized bandit strategies from the observable context-action pairs generated by those strategies—regardless of whether those strategies are effective.
Contributions Our contributions are three-fold. In the sequel, we first formalize the ICB problem, identifying it with the data-driven objective of inferring an agent’s internal reward function along with their internal trajectory of beliefs about the environment (Section 2). Second, we propose two concrete learning algorithms, imposing different specifications regarding the agent’s behavioral strategy: The first parameterizes the agent’s knowledge in terms of Bayesian updates, whereas the second makes the milder specification that the agent’s behavior evolves smoothly over time (Section 3). Third, through both simulated and real-world data for liver transplantations, we illustrate how ICB can be applied as an investigative device for recovering and explaining the evolution of organ allocation practices over the years, as well as benchmarking and validating the accuracy of our algorithms (Section 5).

heading: 2 INVERSE CONTEXTUAL BANDITS
text: Preliminaries Consider a Markov decision process of the form D := (X,A,R, T ), where S indicates the state space, A the action space,R ∈ ∆(R)X×A the reward dynamics, and T ∈ ∆(X)X×A the transition dynamics. At each time t ∈ Z+, the decision-making agent is presented with some state xt ∈ X and decides to take an action at ∈ A, whence an immediate reward rt ∼ R(xt, at) is received, and a subsequent state st+1 ∼ T (xt, at) is presented. Let the decision-making policy employed by the agent be denoted π ∈ ∆(A)X , such that actions at any time are sampled according to at ∼ π(xt). In the forward direction, given dynamicsR, T , the reinforcement learning problem (“RL”) deals with determining the optimal policy that maximizes some notion of expected cumulative rewards [29]: π∗R,T := argmaxπ∈∆(A)X Eπ,R,T ∑ t rt. In the opposite direction, given some observed behavior policy πb and transition dynamics T , the inverse reinforcement learning problem (“IRL”) deals with determining the reward dynamics R with respect to which πb appears optimal. For instance, the classic max-margin approach seeks [30]: R∗ := argminR(maxπ Eπ,R,T ∑ t rt − Eπb,R,T ∑ t rt).
Having Dynamics Access to Having No Dynamics Access In conventional RL (and IRL), the decision-maker has unrestricted access to environment dynamics—either explicitly (i.e. R, T are simply known and used in computing the optimal policy), or implicitly (i.e. the agent may interact freely with the environment during training). In contrast, in our setting the agent has no such
luxuries—not only are the dynamics not known to the agent, but neither do they enjoy a distinct sandboxed training phase prior to live deployment. Without such access, the agent must consider both the information they may gain when taking actions (cf. “exploration”) and also the expected rewards due to those actions (cf. “exploitation”). Note that this property results in much more difficult learning problems—in both the forward and inverse directions (see Appendix B for a more detailed discussion).
Consider environments parameterized by environment parameters ρ ∈ P , such that the reward dynamics of an environment are given byRρ, and the transition dynamics by Tρ. Let ρenv denote the true environment parameter, such that the actual rewards received by an agent are distributed as rt ∼ Rρenv(xt, at), and the actual states encountered by the agent are distributed as xt+1 ∼ Tρenv(xt, at). Since ρenv is unknown, an agent takes actions on the basis of their beliefs about it; these beliefs are described by probability distributions Pβ ∈ ∆(P ) parameterized by belief parameters β ∈ B. For each time t, let βt capture the agent’s belief at the beginning of that step.
Each time step, the agent first samples an environment parameter ρt ∼ Pβt according to their belief βt, then takes an action according to π∗Rρt ,Tρt . Note that this ensures that each action is takenwith probability proportional to the probability with which the agent believes it to be optimal at time step t. Essentially, the agent’s policy at time step t is induced by their belief βt: πβt(x)[a] := Eρ∼Pβt [π ∗ Rρ,Tρ(x)[a]]. After receiving a reward rt, the agent updates their current belief parameter according to a (possibly-stochastic) belief-update function f ∈ ∆(B)B×X×A×R, such that βt+1 ∼ f(βt, xt, at, rt). Together with the initial belief parameter β1, the agent’s t-th step belief is a (possibly-stochastic) function of the history ht = {x1:t−1,a1:t−1, r1:t−1} defined recursively via f .

heading: 2.1 CONTEXTUAL BANDITS SETTING
text: In this work, we consider state transitions that occur independently of past states and actions. Due to this property, decisions can be made greedily without consideration of what future states may be, and yields a contextual bandits problem [26–28]. Note that this captures the organ allocation problem well: Distributions of newly arriving organs are largely independent of prior allocation decisions; in fact, transplantation and allocation policies are often modeled in bandit-like settings [31, 32]. Formally:
Definition 1 (Contextual Bandits) Consider a decision-making problem D := (X,A,R, T ), where R, T are unknown to the agent. Let T (x, a) = T ′ for some T ′ ∈ ∆(X), for all x ∈ X, a ∈ A, such that policies are greedy: supp(π∗t (xt)) = argmaxat∈A R̄ρt(xt, at) , (1) where R̄ρ(x, a) := Er∼Rρ(x,a)[r] indicates the mean reward function, and ties are broken arbitrarily. Given a space of environment parameterizations P , the contextual bandits problem is to design a space of belief parameterizations B, and to determine the optimal belief-update function
f∗ := argmaxf∈∆(B)B×X×A×R ∑ tEf,πβt ,R,T [rt] . (2)
Now, suppose that an agent follows a bandit-type policy for T time steps; this would generate an observational dataset of contexts and actions D := {x1:T ,a1:T } (adhering to the contextual bandits literature, we refer to states as “contexts” hereafter).1 But since rewards rt and beliefs βt are quantities internal to the decision-maker, we assume that they are not part of the observational dataset: The former represents the agent’s preferences over outcomes after observing contexts and taking actions, which is not explicitly observable; likewise, the latter represents the agent’s beliefs about what kinds of outcomes their actions result in, which is also not explicitly observable. Thus we ask the novel question:
From D, can we infer the true environment parameter ρenv, as well as the belief trajectory β1:T ?
β1
ρ1 x1 a1 r1
β2
ρ2 x2 a2 r2
β3
ρ∗
f f ···
···
Figure 2. Graphical Model for ICB. We aim to infer the (dotted) red quantities given the (solid) blue ones.
Definition 2 (Inverse Contextual Bandits) Consider again a contextual bandit problem D := (X,A,R, T ), and recall that dynamics R, T are unknown to the agent. Given an observational dataset D, and a family of environment parameterizations P and belief parameterizations B, the inverse contextual bandits problem (“ICB”) is to determine the true environment parameter ρenv and the belief parameters β1:T (see Figure 2).
1We also use “x∈X” to denote contexts (standard in contextual bandits) instead of “s∈S” (common in RL).
It is important to observe that the novelty here is general—that is, in posing the “inverse” question of how knowledge evolves over time. Focusing our attention on contextual bandits simply represents a specific choice of problem setting: In this first work on tackling the inverse problem in modeling nonstationary agents, it presents a more tractable problem for analysis, and is moreover especially suited for our motivating application in organ allocations. Note that in the bandit setting, the fact that transition dynamics are unknown to the agent is ultimately inconsequential due to greedy policies; we refer to ρ simply as “reward parameter” hereafter. We leave generalization to arbitrary transition dynamics T ∈ ∆(X)X×A to future work. Also note that ICB itself is not a bandit problem (see Appendix C). Remark 1 (Environment vs. State Beliefs) When speaking of inferring “beliefs” here in our setting, we are referring to environment beliefs—that is, an agent’s knowledge of the environment’s rewards. It is important to distinguish this from state beliefs in partially-observed environments [33, 34]—that is, an agent’s estimate of which latent state they are in. State beliefs are computed by an agent using their (known) environment parameters, whereas environment beliefs concern the environment’s (unknown) parameters themselves. State beliefs can be easily inferred [35]: all factors that contribute to state-belief updates (i.e. observations and actions) are observable; on the other hand, environment beliefs are more technically challenging due to latent factors (i.e. internal rewards r1:T ) that are never observable. Because of the same reason, tackling ICB with conventional IO-HMM inference methods is not possible either, even though the agent can be viewed as an IO-HMM (see Appendix C).
Remark 2 (Subjective vs. Objective Reward) When speaking of learning what “rewards” an agent is optimizing, the novelty here that our objective refers to the full belief trajectory β1:T of the agent. It is important to distinguish this from simply learning the ground-truth parameter ρenv as in typical IRL. The ground-truth parameter is an objective quantity capturing the “prescriptive” notion of what the agent ought to be optimizing, whereas the belief trajectory is a subjective quantity capturing the “descriptive” notion of what the agent appears to be optimizing. Existing work in learning from nonstationary agents has focused solely on ρenv, which is all that is required for apprenticeship [36, 37]. In contrast, for the goal of understanding behavior (and how it evolves), Definition 2 brings β1:T to focus.

heading: 3 BAYESIAN INVERSE CONTEXTUAL BANDITS
text: We operate in the standard contextual bandits setting [26]: Consider a d-dimensional action space A, and suppose at each time t the agent observes a k-dimensional context xt[a] ∈ Rk for each possible action, thus the context space is given by X := Rd×k. Let the space of reward parameters be P := Rk. Rewards are assumed linear with respect to contexts xt, and normally-distributed with mean R̄ρ(x, a) = 〈ρ, x[a]〉 and known variance σ2; that is,Rρ(x, a) := N (〈ρ, x[a]〉, σ2) with 〈·, ·〉 denoting the inner product. (Note that these assumptions can be relaxed later in Section 3.1 below).
Belief Updates Before tackling a much more general case, we begin by modeling the agent’s beliefs as Gaussian posteriors over ρenv, and their belief-update function f as Bayesian updates. Formally, beliefs are described by the family of distributions Pβ := N (µ,Σ), where β := {µ,Σ} ∈ Rk×Rk×k, andN (µ,Σ) is the multivariate Gaussian distribution with mean vector µ and covariance matrix Σ. At each time t, given the posterior βt = {µt,Σt}—such that ρenv|ht ∼ N (µt,Σt)—and the observation (xt, at, rt), the belief-update f(βt, xt, at, rt) is the Dirac delta centered at βt+1={µt+1,Σt+1}, with:
µt+1 := Σt+1 ( Σ−1t µt + 1
σ2 rtxt[at]
) , Σt+1 := ( Σ−1t + 1
σ2 xt[at]xt[at]
T )−1
, (3)
Note that the initial belief β1 = {µ1,Σ1} represents the agent’s (unknown) prior over ρenv. Finally, to facilitate Bayesian analysis, we consider soft-optimal policies as usual (see e.g. [38]). Formally, instead of picking actions uniformly from argmaxas∈A R̄ρt(xt, at), they are chosen as follows, with α ∈ R+ adjusting the stochasticity of action selection (α → ∞ recovers the hard-optimal case):
π∗Rρt (xt)[at] := eαR̄ρt (xt,at)/ ∑ a∈Ae αR̄ρt (xt,a) . (4)
Bayesian Learning Under this setup, we propose an expectation-maximization (EM)-like algorithm that estimates the true reward parameter ρenv and the initial belief parameter β1, and samples the belief trajectory β2:T in alternating steps. First, the joint distribution of all quantities of interest is:
P(ρenv, β1, r1:T ,ρ1:T ,D) = P(ρenv, β1) Prior
∏T t=1 P(xt)
T [xt] P(ρt|βt) Pβt [ρt] P(at|xt, ρt) π∗Rρt (xt)[at] P(rt|ρenv, xt, at) Rρenv (xt,at)[rt] . (5)
Note that since each belief parameter βt is a deterministic function of the initial belief parameter β1 and the history ht (cf. Equation 3), rewards r1:T−1 and belief parameters β2:T are essentially interchangeable given the initial belief and context-action pairs D (i.e. one is completely identified by the other). Then, starting with some initial estimates ρ̂env and β̂1 for the true reward parameter and the initial belief parameter, we iteratively obtain better estimates by performing the following two steps:
• Expectation step: Compute the expected log-likelihood of ρenv, β1 given current estimates ρ̂env, β̂1:
Q(ρenv, β1; ρ̂env, β̂1) := Er1:T ,ρ1:T |ρ̂env,β̂1,D[logP(r1:T ,ρ1:T ,D|ρenv, β1)] , (6)
which we shall approximate by sampling reward values and reward parameters {r(i)1:T ,ρ (i) 1:T }Ni=1
from the distribution P(r1:T ,ρ1:T |ρ̂env,β̂1,D) using Markov chain Monte Carlo (MCMC) methods. • Maximization step: Compute new estimates ρ̂′env, β̂ ′ 1 that yield an improved expected log-posterior:
Q(ρ̂′env, β̂′1; ρ̂env, β̂1) + logP(ρ̂′env, β̂′1) > Q(ρ̂env, β̂1; ρ̂env, β̂1) + logP(ρ̂env, β̂1) , (7) which can be achieved using gradient-based methods.
Sampling Reward Values and Reward Parameters Observe that reward values r1:T are Gaussiandistributed when conditioned on reward parameters ρ1:T (which means they can be sampled exactly):
Lemma 1 Let r1:T = [r1 · · · rT ] ∈ RT and let Xt = (1/σ2)[x1[a1] · · ·xt[at] 0k,(T−t)] ∈ Rk×T , where 0i,j is the i-by-j zero matrix. Then we have that r1:T |ρ1:T , ρ̂env, β̂1,D ∼ N (µ̃, Σ̃), where
µ̃ := Σ̃ ( XTT ρ̂env + ∑T t=2X T t−1(ρt − Σ̂tΣ̂−11 µ̂1) ) , Σ̃ := ( 1
σ2 I +
∑T t=2X T t−1Σ̂tXt−1 )−1 . (8)
Algorithm 1 Bayesian ICB
1: Parameters: variance of rewards σ2, stochasticity of action selections α, learning rate η ∈ R+ 2: Input: dataset D, prior P(ρenv, β1) 3: Initialize ρ̂env, β̂1 ∼ P(ρenv, β1) 4: loop 5: Initialize r(0)1:T , ρ (0) 1:T 6: for i ∈ {1, 2, . . . , N} do 7: Sample r(i)1:T ∼ P(r1:T |ρ (i−1) 1:T , ρ̂env, β̂1,D) using Lemma 18: for t ∈ {1, 2, . . . , T} do 9: Sample ρ′, ρ′′ ∼ Pβt[β̂1,x1:t−1,a1:t−1,r(i)1:t−1]
10: p← min{1, P(at|xt,ρt=ρ ′)
P(at|xt,ρt=ρ′′)} 11: ρ(i)t ← ρ′ w.p. p, and ρ′′ otherwise 12: end for 13: end for 14: Q̄(ρenv,β1)= 1N ∑N i=1logP(r (i) 1:T ,ρ (i) 1:T ,D|ρenv,β1) 15: {ρ̂env, β̂1} ← {ρ̂env, β̂1} +η[∇{ρenv,β1}Q̄(ρenv, β1)]{ρenv,β1}={ρ̂env,β̂1} +η[∇{ρenv,β1} logP(ρenv, β1)]{ρenv,β1}={ρ̂env,β̂1} 16: end loop 17: Output: ρ̂env, {β(i)1:T [β̂1,x1:T ,a1:T , r (i) 1:T ]} N i=1
Proof. All proofs are found in Appendix D.
This motivates a Gibbs-like sampling procedure whereby samples from P(r1:T ,ρ1:T |ρ̂env, β̂1,D) are approximated by sampling r1:T and ρ1:T in an alternating fashion from their respective conditional distributions P(r1:T |ρ1:T , ρ̂env, β̂1,D) and P(ρ1:T |r1:T , ρ̂env, β̂1,D) instead. However, note that sampling reward parameters ρ1:T from its conditional is not as easy to perform exactly as sampling reward values r1:T . We achieve it by first observing that ρt’s are independent from each other conditioned on r1:T :
P(ρ1:T |r1:T , ρ̂env, β̂1,D) ∝ ∏T t=1P(ρt|β̂t)P(at|xt, ρt) .
(9)
Then, we sample each ρt in turn by performing a single iteration of the Metropolis-Hastings algorithm using Pβ̂t as the proposal distribution. Algorithm 1 (Bayesian ICB) summarizes the overall procedure.

heading: 3.1 NONPARAMETRIC BAYESIAN INVERSE CONTEXTUAL BANDITS
text: So far, we have modeled the learning procedure of the agent with Bayesian updates, and estimated the parameters that characterize their learning procedure (i.e. the true reward parameter ρenv and the initial belief parameter β1). Clearly, this approach can be similarly applied to different parameterizations of the agent’s behavior (e.g. using a UCB-based model, or a general function approximator for f ). In this section, instead of imposing a particular type of belief-update, we take a nonparametric approach and regard the agent’s beliefs β1:T more generally as a random process. First, we establish a prior P(β1:T ) over that belief process, then describe a procedure to sample from the posterior P(β1:T |D). Gaussian Process Prior Different from above, now let the agent’s beliefs be described by the family of distributions Pβ := N (β,ΣP ) for β ∈ Rk, where ΣP ∈ Rk×k controls the variability of reward parameters sampled from beliefs. Let β1:T = [β1 · · ·βT ] ∈ Rk×T ; here we consider a multivariate Gaussian process as prior over belief parameters β1:T :
vec(β1:T ) ∼ N (0,ΣT ⊗ ΣB) , (10)
where⊗ denotes the Kronecker product, ΣT ∈ RT×T controls the covariances between different time steps, and ΣB ∈ Rk×k controls the covariances between different components of a given belief βt. Although our methodology is applicable for any arbitrary ΣT , we shall fix (ΣT )ij = min{i, j} so our prior becomes a multivariate Wiener process, and differences δt := βt − βt−1 between consecutive beliefs are independent and identically distributed according to N (0,ΣB)—that is P(δt) ∝ exp(− 12δ T TΣ −1 B δt). Intuitively, this means our prior favors belief trajectories that vary smoothly over time, where differences between consecutive beliefs are probabilistically bounded by ΣB (since larger changes in consecutive βt’s are exponentially less likely in relation to ΣB).
Sampling Beliefs from the Posterior Having established a Gaussian process prior P(β1:T ), observe that the posterior for β1:T is still a Gaussian process when conditioned on the reward parameters ρ1:T :
Lemma 2 Let ρ1:T = [ρ1 · · · ρT ] ∈ Rk×T . Then we have that vec(β1:T )|ρ1:T ,D ∼ N (µ̃, Σ̃), with µ̃ := Σ̃(I ⊗ ΣP )−1 vec(ρ1:T ), Σ̃ := ( (ΣT ⊗ ΣB)−1 + (I ⊗ ΣP )−1 )−1 . (11)
Algorithm 2 Nonparametric Bayesian ICB 1: Parameters: covariance matrices ΣP and ΣB 2: Input: dataset D 3: Initialize ρ(0)1:T , β (0) 1:T
4: for i ∈ {1, 2, . . . , N} do 5: Sample β(i)1:T ∼ P(β1:T |ρ (i−1) 1:T ,D) using Lemma 26: for t ∈ {1, 2, . . . , T} do 7: Sample ρ′, ρ′′ ∼ P
β (i) t
8: p← min{1, P(at|xt,ρt=ρ ′)
P(at|xt,ρt=ρ′′)} 9: ρ(i)t ← ρ′ w.p. p, and ρ′′ otherwise
10: end for 11: end for 12: Output: {β(i)1:T } N i=1
Therefore, similar to the parametric version of our algorithm, we can approximate samples from the posterior P(β1:T |D) by sampling β1:T and ρ1:T in an alternating fashion from their respective conditional distributions P(β1:T |ρ1:T ,D) and P(ρ1:T |β1:T ,D), and discarding the samples for ρ1:T . Likewise, we sample each ρt in turn by performing a single iteration of the Metropolis-Hastings algorithm. Algorithm 2 (Nonparametric Bayesian ICB) summarizes the overall sampling procedure. See Appendix C for a discussion of differences between Algorithm 1 and 2.

heading: 4 RELATED WORK
text: Policy Learning In modeling an agent’s decision-making from their observed behavior, the overarching goal is often in imitation learning (i.e. to replicate their actions) or in apprenticeship learning (i.e. to match their performance). The former directly parameterizes imitation policies as blackbox functions, typically based on behavioral cloning [39–41] or state-action distribution matching [42–44]. The latter takes the indirect approach of first inferring some reward function for which the agent’s demonstrations are assumed to be optimal—and on the basis of which an apprentice policy is trained; this is often done via Bayesian [38, 45, 46] or max-ent [47–49] IRL. In contrast, our overarching goal is in descriptive modeling (i.e. to learn interpretable parameterizations for explaining observed behavior, see Appendix C for a detailed discussion on our interpretability criteria) [8, 9]. For instance, recent work has represented policies in terms of human-understandable rules [10], goals [11], intentions [12], preferences [13], subjective dynamics [14], and counterfactuals [15].
Learning from Variation Precisely, we wish to understand how behavior has changed over time, especially relevant in healthcare as knowledge [23–25] and practices [16–18] continuously evolve. While variation in practice has been captured in policy learning from multi-modal [19, 20], multi-task [21, 22], and compound-task [50, 51] demonstrations, little has sought to describe variation over time. Some research has explored IRL from non-stationary agents, using labeled data generated by agents performing specific policy updates over time [36, 37] or ranked post-hoc by an expert [52, 53]. However, all of these simply attempt to infer the optimal reward (viz. ground-truth ρenv) for the (prescriptive) goal of apprenticeship, revealing nothing about how the actual behavior has evolved (viz. trajectories β1:T ) for the (descriptive) goal of understanding. The only close attempt has simply used a change-point detection intermediate step to allow inferring a sequence of optimal rewards as usual [54].
Bandits Setting To the best of our knowledge, this is the first formal attempt at learning interpretable representations of non-stationary behavior. In formulating and solving this challenge of learning β1:T , we have focused on the bandit setting [26–28]. Now, the general notion of an “inverse” bandit problem had been independently proposed by [55] and [56] as the bandit-based counterpart to apprenticeship from a learning agent [36, 37, 52, 53]. However, they both ignore the presence of contexts (viz. “non-contextual” bandits), and—more importantly—identical to the apprenticeship works above, they only attempt to infer the ground-truth reward ρenv, without regard to the trajectory of evolution itself. Table 1 contextualizes ICB with respect to related works in learning from decision-making behavior.

heading: 5 ILLUSTRATIVE EXAMPLES
text: Three aspects of our approach deserve empirical demonstration, and we shall highlight them in turn:
• Explainability: ICB should help us understand how medical practice has changed over the years. This is our primary motivation—in providing interpretable representations of variation over time.
• Belief Accuracy: ICB should recover accurate beliefs in a robust manner across a variety of learning agents—that is, it should not be sensitive to the learning procedure of the underlying agent.
• Reward Accuracy: ICB should recover accurate ground-truth reward parameters in a similarly robust manner—that is, it should be capable of “extrapolating beyond” suboptimal demonstrations.
Decision Environments We consider data from the Organ Procurement & Transplantation Network (“OPTN”) as of December 4, 2020, which consists of patients registered for liver transplantation from 1995 to 2020 [58]. We are interested in the decision-making problem of matching organs that become available with patients who are waiting for a transplantation. For each decision, the action space At consists of patients who were in the waitlist at the time of an organ’s arrival t, while the context xt[a] for each patient a ∈ At includes the features of both the organ and the patient. We consider k = 8 features: {ABO mismatch, age, creatinine, dialysis, INR, life support, bilirubin, weight difference}. In addition to the OPTN dataset, to better validate the performance of our method in a more controlled manner, we also devise a semi-synthetic decision environment, where the features {xt[a]}a∈At of potential organ-patient pairs are taken from the OPTN dataset, but the organs are matched with a final patient at ∈ At for transplantation according to the policies of a variety of simulated learning agents. We determine the ground-truth reward parameter ρenv of this semi-synthetic environment by performing simple linear regression over the survival time of patients who actually underwent a transplantation.
Learning Agents For the semi-synthetic experiments, we generate observational datasets by employing the following simulated agents, which includes a stationary agent as well as six learning agents:
• Stationary: The agent knows the ground-truth ρenv and takes actions accordingly (i.e. ρt = ρenv for all t). • Sampling: The agent employs the posterior sampling-based bandit strategy proposed in [26] (cf. Equation 3). • Optimistic: The agent selects actions based on optimistic estimates of their rewards; this is LinUCB in [27]. • Greedy: The agent only exploits their knowledge greedily and does not explore their environment effectively. • Stepping: The agent first explores the environment using uniform preferences until some time step t∗,
whence they learn the ground-truth reward parameter ρenv and immediately begin taking actions accordingly. In healthcare settings, stepping behavior like this may occur when new guidelines are introduced.
• Linear: The agent learns the true reward parameter ρenv in a linear fashion, starting with uniform preferences. • Regressing: The agent first acquires the ground-truth reward parameter ρenv gradually until some time
step t∗, at which point they begin to regress while retaining some amount of knowledge. Note that this is a particularly challenging setting because the regressing agent’s behavior does not improve monotonically.
Benchmark Algorithms In addition to our two proposed algorithms Bayesian ICB (B-ICB) and Nonparametric Bayesian ICB (NB-ICB), we consider all the applicable algorithms in the literature:
• B-IRL [38]: This is the classic Bayesian inverse reinforcement learning algorithm that has been widely applied to a variety of problem settings [45, 59, 60]. As usual, it assumes ρt = ρenv for all t ∈ {1, . . . , T}.
• M -fold-IRL: This runs a copy of Bayesian IRL for each ofM equal-sized intervals in the dataset. Note that settingM = T is equivalent to assuming that beliefs over time are completely independent from each other.
• CP-IRL [54]: This recently-proposed method runs M copies of Bayesian IRL as well but it employs a change-point detection algorithm to learn best places to divide the dataset (hence referred to as “CP”-IRL).
• I-SPI [36]: This recently-proposed method assumes the agent updates their behavioral policy via “soft policy improvements”, which can be “inverted” to recover ρenv (hence referred to as inverse “SPI”). In our setting, this is equivalent to assuming the agent is less stochastic over time (i.e. larger values of α). However, I-SPI only recovers the ground-truth ρenv, and does not provide any estimate for belief trajectories. • T-REX [52]: This recently-proposed method learns ρenv using rankings between context-action pairs; absent explicit rankings, it assumes the agent learns monotonically, such that pairs encountered later in time are preferred over earlier ones (i.e. (xt, at) ≺ (xt′ , at′) if t < t′). Like I-SPI, T-REX only infers ρenv, not beliefs.
ABO Mismatch
Age
Creatinine
Dialysis
INR
Life Support
Bilirubin
Weight Difference
1
0.1
0.01
0.001
(a) Feature Importances in 2000
ABO Mismatch
Age
Creatinine
Dialysis
INR
Life Support
Bilirubin
Weight Difference
1
0.1
0.01
0.001
(b) Feature Importances in 2010
1996 2000 2004 2008 2012 2016 2020
Time
0.00
0.02
0.04
0.06
0.08
0.10
0.12
R el
at iv
e Im
p or
ta n ce (s u m s to on e fo r al l fe at
u re
s)
O P
T N
F in
al R
u le
M E
L D
/P E
L D
S co
re
R eg
io n
al S
h ar
in g
fo r
M E
L D >
15
R eg
io n
al S
h ar
in g
fo r
S ta
tu s
1
R ev
is ed
P ol
ic y
fo r
H ig
h ly
U rg
en t
C as
es
R ev
is ed
P ol
ic y
fo r
H C
C
E n
h an
ce d
L iv
er D
is tr
ib u
ti on
P ol
ic y
Creatinine INR Bilirubin
Figure 4. Relative Feature Importances over Time for Creatinine, INR, and Bilirubin. Significant changes in behavior have generally coincided with the important events surrounding guidance on liver allocation policies [61].
In addition to these benchmark algorithms, as a baseline we also report the performance of simply estimating all preferences to be uniform— that is, ρ̂env = ρ̂t = −1/k (Baseline). Details regarding both the learning agents and the benchmark algorithms can be found in Appendix E.
Explainability First, we direct attention to the potential utility of ICB as an investigative device for auditing and quantifying behaviors as they evolve. We use NB-ICB to estimate belief parameters {βt = E[ρt]}Tt=1 for liver transplantations in the OPTN dataset. Since the agent’s rewards are linear combinations of features weighted per their belief parameters, we may naturally interpret the normalized belief parameters |βt(i)|/ ∑k j=1 |βt(j)| as the relative importance of each feature i ∈ {1, . . . , k}. Figure 3 shows the relative importances of all eight features in 2000 and 2010, and Figure 4 shows the importance of creatinine, INR, and bilirubin—components considered in the MELD score (“Model for End-Stage Liver Disease”), a scoring system for assessing
the severity of chronic liver disease, [62]. Empirically, three observations immediately stand out: First, INR and creatinine appear to have gained significant importance over the 2000s, despite being the least important features in 2000. Second, their importances appear to have subsequently decreased towards the end of the decade. Third, since 2015 their importances appear to have steadily increased once again.
Interestingly, we can actually verify that these findings are perfectly consistent with the medical environments of their respective time periods. First, the MELD scoring system itself was introduced in 2002, which—using INR and creatinine as their most heavily weighted components—explains the rise in importance of those features in the 2000s. Second, over time there was an increase in the usage of MELD exception points (i.e. patients getting prioritized for special conditions like hepatocellular carcinoma, which are not directly reflected in their laboratory MELD scores), which explains the decrease in relative importance for such MELD components. Third, 2015 saw the introduction of an official cap on the use of MELD exception points (e.g. limited at 34 for hepatocellular carcinoma), which is consistent with the subsequent increase in relative importance of those features once again. Figure 4 also plots important historical events that happened regarding liver allocation policies [61]. Of course, ICB has no knowledge of these events during training, so any apparent changes in behavior in the figure are discovered solely on the basis of organ-patient matching data in the OPTN dataset. Intriguingly, the importance of bilirubin appears to have not increased until 2008, instead of earlier when the MELD score was first introduced. Now, there are possible clinical explanations for this: For instance, bilirubin is not weighted as heavily as other features when computing MELD scores, so their importance may not have been apparent until the later years, when patients generally became much sicker (with higher MELD scores overall). In any case, however, the point here is precisely that ICB is an investigative device that allows introspectively describing how policies have changed in
Table 2. Mean Error of Belief Estimates. B-ICB and NB-ICB are best across all types of agents. Note that I-SPI and T-REX are not applicable as they do not estimate belief trajectories. Results show mean± std. error (5 runs).
Learning Agent Algorithm Stationary Sampling Optimistic Greedy Stepping Linear Regressing Baseline 0.477± 0.000 0.395± 0.030 0.391± 0.030 0.385± 0.020 0.238± 0.000 0.238± 0.000 0.238± 0.000 B-IRL 0.252± 0.248 0.206± 0.099 0.241± 0.195 0.248± 0.204 0.262± 0.027 0.165± 0.019 0.154± 0.018 5-fold IRL 0.294± 0.041 0.369± 0.075 0.313± 0.043 0.310± 0.033 0.333± 0.040 0.289± 0.031 0.292± 0.070 10-fold IRL 0.424± 0.017 0.407± 0.062 0.401± 0.061 0.399± 0.57 0.398± 0.027 0.386± 0.017 0.388± 0.043 T -fold IRL 1.168± 0.012 1.134± 0.021 1.140± 0.011 1.135± 0.011 1.117± 0.010 1.103± 0.011 1.105± 0.010 5-fold CP-IRL 0.272± 0.040 0.334± 0.039 0.280± 0.029 0.277± 0.029 0.294± 0.046 0.282± 0.029 0.278± 0.010 10-fold CP-IRL 0.409± 0.036 0.462± 0.075 0.388± 0.057 0.384± 0.055 0.374± 0.047 0.376± 0.049 0.401± 0.035 B-ICB 0.120± 0.032 0.140± 0.014 0.121± 0.016 0.120± 0.018 0.234± 0.016 0.153± 0.010 0.147± 0.026 NB-ICB 0.201± 0.027 0.178± 0.017 0.152± 0.042 0.149± 0.036 0.150± 0.012 0.134± 0.015 0.140± 0.017
this manner—such that notable phenomena may be duly investigated with a data-driven starting point (see Appendix C for a discussion on how to interpret behavior with ICB).
Belief Accuracy Since it is not possible to compare the belief parameters of different algorithms directly, we define ‖Eρ∼Pβt [ρ] − Eρ∼Pβ̂t [ρ]‖1 as the error of belief estimate β̂t at time t. Then,Table 2 shows the mean error of belief estimates learned by various algorithms in our semi-synthetic environment. As we would expect, B-ICB performs the best for the Sampling, Optimistic, and Greedy agents—which learn via Bayesian updates—while NB-ICB—which is more flexible in terms how it models belief trajectories—performs the best for the Stepping, Linear, and Regressing agents. Interestingly, we also observe that both M -fold IRL and CP-IRL perform worse than vanilla IRL. This could be due to the fact that—in both algorithms—the estimates for each interval are trained with fewer data points and independently from the other intervals; that is, there is no information sharing and potential similarities between adjacent intervals are disregarded. In contrast, both B-ICB and NB-ICB formalize some relationship between beliefs at different time steps (viz. Equations 3 and 10); under either formulation, beliefs at different time steps are never independent from each other. Finally, it is worth noting that NB-ICB is capable of capturing the sudden change in the Stepping agent’s behavior (despite assuming “smoothly” evolving beliefs, see Appendix A for additional experiments).
Reward Accuracy Defining ‖ρenv − ρ̂env‖1 as the error in estimating the ground-truth parameter ρenv, Table 3 shows the mean error for various algorithms. B-ICB performs the best; this shows that not only can it recover (subjective) descriptors of how the agent appears to be behaving over time, but can also infer the (objective) prescriptor of how the agent ought to be behaving ideally. That is, B-ICB can also “extrapolate beyond” suboptimal demonstrations to infer the ground-truth reward. Interestingly, T-REX completely fails: This is because in the contextual bandits setting, it effectively assumes later context-action pairs (i.e. generated by a better policy) on average earn larger rewards than earlier ones (i.e. generated by a worse policy)—but this ignores the stochastic arrival of contexts themselves, which (in contextual bandits) is independent of the policy! For instance, sicker patients at a later time may always yield worse outcomes, no matter how much better the allocation policy has become. Appendix A discusses in much more detail why existing methods fail in the ICB setting.

heading: 6 CONCLUSION
text: In this paper, we motivated the importance of learning interpretable representations of non-stationary behavior, formalized the problem of ICB, and proposed algorithms with advantages both in explainability and accuracy over any existing methods. Two points deserve brief comment: First, we focused on contextual bandits; while this encapsulates a large class of applications, future work may investigate generalizing this approach to environments with arbitraray T . Second, it is crucial to keep in mind that ICB does not claim to identify the real intentions of an agent: humans are complex, and rationality is bounded. What it does do, is to provide an interpretable explanation of how an agent is effectively behaving, offering a quantitative yardstick by which to investigate hypotheses and understand behavior.

heading: A DISCUSSION ON EXPERIMENTS
text: Applicability of Existing Methods Why existing methods should fail or otherwise not apply in our setting requires further exposition. First, note that since ICB is a novel problem (which the proposed B-ICB and NB-ICB algorithms are designed to solve directly), algorithms from prior works will inherently be suboptimal, because they were simply not designed to solve the ICB problem. Concretely, the goal of capturing the evolution of non-stationary behavior requires the following (see Table 1):
• (a) Trajectory of Changes: Instead of learning a single, static ground-truth reward parameter, we specifically wish to capture the entire trajectory of changes itself.
• (b) Stepwise Evolution: If the agent’s knowledge evolves continuously over time (i.e. in a step-wise fashion), we wish to capture this (vs. a course, interval-wise appraoch).
• (c) Information Sharing: For efficiency in learning, the method should be able to share information between consecutive estimate (i.e. βt, βt+1 are not independent).
No prior work has been designed with all of these consideration in mind. With respect to Table 2 results (i.e. assessing how well evolving knowledge is learned):
• B-IRL: This only learns a single, static ground-truth reward parameter for the entire trajectory, failing all of (a), (b), and (c), hence would underfit.
• M -fold IRL and CP-IRL: These accomplish (a), but their interval-wise approach fails both (b) and (c), hence would underfit, and is data inefficient.
• T -fold IRL: This accomplishes (a) and (b), but fails (c) catastrophically by using only one datum to generate each estimate, hence is data inefficient.
With respect to Table 3 (i.e. assessing how well the ground-truth reward is learned), the method should accoutn for non-stationary behavior—that is, instead of assuming the agent is optimal for the learned ground-truth reward the entire time:
• B-IRL: This assumes the agent is optimal for the learned ground-truth reward the entire time, which is a model mismatch.
• I-SPI: This accounts for non-stationarity, but makes the specific assumption that the behavioral policy is updated via soft policy improvement steps. In the contextual bandits setting, this is equivalent to the assumption that the agent behaves less stochastically as time passes. This is clearly an unreasonably strong assumption, and leads to a model mismatch.
• T-REX: This makes the specific assumption that context-action pairs encountered later in time are preferred over earlier ones. In the contextual bandits setting, this is equivalent to the assumption that later context-action pairs (i.e. generated by a better policy) on average earn larger rewards than earlier ones (i.e. generated by a worse policy). But this ignores the stochastic arrival of contexts themselves, which (in contextual bandits) is independent of the policy. For instance, sicker patients at a later time may always yield worse outcomes, no matter how much better the allocation policy has become.
For these reasons, we do not expect existing methods to work, for the simple reason that they were not designed to handle the ICB problem. (And the results corroborate our hypotheses).
Modeling Sudden Changes NB-ICB is capable of identifying sudden changes in behavior since it does not assume a particular mechanism with which the non-stationary behavior has came to be. In this section, we aim to demonstrate this capability with additional experiments. Such sudden changes might occur in clinical settings when new guidelines are introduced or existing guidelines are amended—hence it is critical for our purposes to be able to model them.
Before the introduction of MELD score, the dominant factor of consideration in allocating organs was the waiting time of patients [63]. In fact, MELD was partly introduced to promote the use of features that are more reliable indicators of a patient’s liver function (namely creatinine, INR, and bilirubin) than waiting time. Now, consider a hypothetical scenario where a MELD-based policy is introduced at time t = dT/3e but later withdrawn at time t = b2T/3c for T = 2500. Suppose this causes two sudden changes in clinical practice: (i) Before MELD is introduced, clinicians make decisions based solely on waiting times but they start complying perfectly with the MELD-based
policy once it is introduced. (ii) Later when the MELD-based policy is withdrawn, clinicians revert back to following their original policy based on waiting times again.
In this hypothetical scenario, the context x[a] for a potential organ-patient match consists of four features: {waiting time, creatinine, INR, bilirubin}. Like in our semi-synthetic experiments, we sample these features from the real OPTN data for liver transplantations. For t ∈ [T/3, 2T/3] (i.e. when the MELD-based policy is in place), ρt is such that R̄ρt(x, a) = 9.57 log(creatinine) + 11.2 log(INR) + 3.78 log(bilirubin), which matches with the real feature weights used in MELD score [63]. Otherwise, ρt is such that R̄ρt(x, a) = (waiting time). Figure 5 qualitatively shows that NB-ICB is able to identify the sudden changes caused by the introduction and later the withdrawal of the MELD-based policy. Quantitatively, Table 4 show that NB-ICB is still the most accurate algorithm in estimating belief parameters.

heading: B DISCUSSION ON NOVELTY AND SETTING
text: Problem Setup Consider a Markov decision process D = (X,A,R, T ) as defined in Section 2. In the most general case, the agent has no access to environment dynamics R, T , so some degree of learning must occur. Let t index the cumulative number of interactions with the environment; if the environment is episodic, then time steps accumulate across resets.
Now, let f denote a probabilistic, online algorithm that learns some parameter ρ of the MDP; for instance, we consider this to be a parameterization of the environment dynamics (but this formalism also applies to learning value functions or black-box policies). And let βt denote the agent’s t-th step knowledge of the quantity being learned; for instance, this would be a parameterization of their probabilistic belief about the environment dynamics. Note that each β naturally induces a policy πβ : πβ(x)[a] := Eρ∼Pβ [π∗Rρ,Tρ(x)[a]] , (12) where π∗Rρ,Tρ denotes the optimal policy that corresponds to point-valued knowledge that the environment dynamics are exactlyRρ, Tρ. Finally, let T be the time step when the algorithm f terminates (e.g. due to some measure of convergence). Broadly, T partitions the agent’s behavior into two distinct phases:
• Training phase: This is where f progressively updates the agent’s knowledge by interacting with the environment. Within this phase, we may define the train-time expected return:
V Rtrain(f) := ∑ t≤T E[rt ∼ R|β1, βt ∼ f, xt ∼ T , at ∼ πβt ] . (13)
• Testing phase: Now after training, the agent ends up with final βT , and may then be deployed in the environment. Within this phase, we may define the test-time expected return:
V Rtest(π) := ∑ t>T E[rt ∼ R|xt ∼ T , at ∼ π] . (14)
Usually, if some knowledge βT were learned in a prior training phase, the agent would naturally set π = πβT in the testing phase.
Forward Problem In the forward direction, an agent seeks to determine the optimal policy that maximizes some notion of expected return. Generally, there are two distinct classes of problems that are of interest: The first assume that agent has access to environment dynamics (either explicitly, via direct knowledge ofR, T ; or implicitly, via interaction with the environment in an unassessed training phase). The second assumes the agent has no such access to environment dynamics (therefore learning must occur via interaction with the environment in an assessed training phase).
• Problem 1A (Agent has dynamics access): In this setting, either the dynamics are explicitly known, so no training phase is required (the agent can simply perform planning using dynamic programming, or simulation-based search, etc.), or the agent may freely interact with the environment in an unasses training phase. Either way, V Rtrain is irrelevant; the agent simply seeks the following:
π∗ := argmaxπ V R test(π) . (15)
• Problem 1B (Agent has no dynamics access): In this setting, the training phase is assessed as well—that is, not only does the agent seek the optimal policy for test-time deployment, but they also care about the return generated during the training phase. On the flip side, note that once f terminates, V Rtest is trivially minimized for any T by setting π = πβT . Thus the agent seeks the following:
f∗ := argmaxf V R train(f) . (16)
Crucially, in the former, the agent is optimizing π∗ based on an “exploitation-only” metric. Whereas in the latter, the agent is required to select an f∗ that balances “exploitation” and “exploration”.
Inverse Problem Now, suppose we—as investigators—are given an observational dataset D := {x1:T ,a1:T } of states and actions generated by some agent. The inverse problem deals with determining the true environment parameter ρenv and/or the agent’s belief parameters β1:T , with respect to which the agent’s behavior appears most optimal. This is often treated with a Bayesian formulation:
• Problem 2A (Agent has dynamics access): In this setting, we seek the following:
ρ̂env := argmaxρ P(D|xt ∼ Tρ, at ∼ argmaxπ V Rρ test (π))P(ρ) . (17)
• Problem 2B (Agent has no dynamics access): In this setting, we seek the following:
ρ̂env, β̂1:T := argmaxρ,β1:T P(D|β1, βt ∼ argmaxf V Rρ
train(f), xt ∼ Tρ, at ∼ πβt)P(ρ,β1:T ) . (18)
Note that Problem 2A is equivalent to a generalization of Bayesian inverse reinforcement learning [38]. More broadly, as the “opposite” to Problem 1A, different flavors of inverse reinforcement learning all share the property that they involve—explicitly or implicitly—the quantity V Rρtest . For instance, max-margin inverse reinforcement learning [30] seeks ρ̂env := argmaxρ(V Rρ test (πD)−maxπV Rρ test (π)).
On the other hand, Problem 2B is novel, and has not been studied before. Now, as an initial exploration of this problem setting, in this work we consider state transitions that occur independently of past states and actions (which is especially suited for our motivating application to organ allocations). In the forward sense, this corresponds to a special case of Problem 1B that yields the “contextual bandits”
setting; this means that decisions can be made greedily: supp(π∗Rρ,Tρ(x)) = argmaxa R̄ρ(x, a), with ties broken arbitrarily. In the inverse sense, this corresponds to a special case of Problem 2B that yields the “inverse contextual bandits” setting; this means that T being unknown is ultimately inconsequential, and we may simply treat ρ as the “reward parameter”.
Importantly, inverse contextual bandits is not—in any shape or form—subsumed by inverse reinforcement learning. Note that B-IRL is an instantiation of Problem 2A, whereas B-ICB is an instantiation of Problem 2B. Table 5 summarizes the above discussion.

heading: C FURTHER DISCUSSIONS
text: Interpretability In terms of interpretability, we are taking the standard view that an interpretable description of behavior should locate the factors that contribute to individual decision, in language readily understood by domain experts [64]. With respect to non-stationary behavior, this concretely manifests in three aspects:
• (1) Feature Importance: As is often the case for interpreting supervised learning as well, in representing decision-making a basic desideratum is that the relative importances of inputs be quantified. We argue that linear weights—which we use—are inherently interpretable.
• (2) Task-level Description: Specifically for modeling decision-making behavior, however, clearly a task-level description (viz. reward function) is a more concisely interpretable account of the behavior than standard input-output feature sensitivities for a black-box policy model.
• (3) Non-stationary Behavior: Finally, the most important factor in our setting is that we specifically wish to describe non-stationary behavior. Note that none of the usual approaches to post-hoc or ante-hoc machine learning interpretability can readily accommodate this unique characteristic.
Given these considerations, let us look at standard approaches to modeling classifiers and/or policies:
• Input-output feature importance (e.g. [65]): This satisfies criterion (1), but not (2) or (3).
• Counterfactual explanations (e.g. [66]): This satisfies criterion (1), but not (2) or (3).
• Inverse reinforcement learning (e.g. [67]): This satisfies criteria (1) and (2), but not (3).
• Compound-task imitation learning (e.g. [51]): This satisfies criteria (3), but not (1) or (2).
• Learning from a learner: In addition, while I-SPI [36] and T-REX [52] superficially handle non-stationary behavior, they actually only seek to recover the ground-truth reward from such behavior (i.e. ρenv, and do not attempt to describe the evolution of such behavior over time as we do (i.e. β1, . . . , βT )).
In contrast, this is precisely why we propose ICB, which satisfies all three criteria: ICB explicitly seeks to describe how behavior changes over time by learning β1, . . . , βT , which are beliefs over task-level reward functions that give insight into feature importances in the behavior.
It should be emphasized that the primary innovation here is not in proposing any new definition of interpretability. Rather, the novelty is in proposing a formulation and solution to ICB (more generally to Problem 2B in Appendix B) that retains all the advantages of conventional IRL, while— importantly—generalizing to the case where we learn from the non-stationary behavior of an agent with no access to environment dynamics. Of course, we can always naively adapt IRL methods to satisfy criterion (3)—that is, by conducting IRL within discrete intervals within the data: This is simply M -fold IRL, and CP-IRL [54], and does not take advantage of the fact that beliefs over time are likely correlated. As corroborated by our experiments, these methods do not appear effective, likely due to the loss of data efficiency from lack of information sharing across time.
Interpreting Behavior with ICB Suppose we were policy-makers, or auditors—in any case, suppose we had a prior hypothesis about how behaviors may/should have changed over time. For instance, consider that we introduced a new policy at some time in the past, and would like to verify that it had the intended effect on actual clinical practice. As the OPTN experiment demonstrates, ICB gives a tool for estimating an answer to this question.
In doing so external context (i.e. knoeledge of the times new policies were introduced, or otherwise knowledge of the times at which we hypothesize there to be behavior changes) is crucial. In particular, they should be known beforehand. Simply running ICB on a behavioral dataset, and then trying to fish for and explain any trends found, would not be valid use of the method.
Finally, note that ICB does not claim to identify the real intentions of an agent: Humans are complex, and rationality is bounded. What it does do, is to provide a representation of how an agent is effectively behaving, offering a quantitative emthod to investigate hypotheses.
Algorithm 1 vs. Algorithm 2 Algorithm 1 models the learning procedure of the underlying agent with Bayesian updates and learns both an estimate of the ground-truth reward, as well as the trajectory of beliefs. Whereas, Algorithm 2 models the agent’s trajectory of beliefs more generally as a random process but only learns the trajectory of beliefs, without estimating the ground-truth reward. Hence, applying and interpreting the results of each approach depends on the assumptions and specific use case.
For instance, Algorithm 1 makes stronger assumptions, but gives an estimate of ρenv. Since this estimate tells us what the behavioral policy may appear to be optimizing (but is not necessarily perfectly successful at optimizing yet), the estimate can potentially be used to set a new explicit guideline—which, if followed successfullyy—would yield new policies that outperform the existing dataset. Conversely, Algorithm 2 makes weaker assumptions, but the tradeoff is that only a description of the evolutio nof knowledge is recovered, without an estimate of the ground-turth reward for downstream use.
Forward Agent as an IO-HMM The agent in ICB can be viewed as an Input-Output HMM (IOHMM): At any point, the “hidden state” of the model is the agent’s belief βt, the “input” to the model is the tuple (xt, at, rt), the “transition function” is the belief-update function f , and the “output” of the model is the reward parameter ρt. In fact, this is depicted in Figure 2 (see the arrows on the top half of the figure).
However, there is a crucial difference: In this IO-HMM, we do not even observe its “outputs” (i.e. ρt), and even its “inputs” are only partially-observed (i.e. rt). So, learning is much more challenging—be it the IO-HMM parameter ρenv, or the hidden state sequence β1, . . . , βT . Thus even if we chose to cast this problem into a generic IO-HMM framework, it would still be the case that conventional IO-HMM learning techniques are not applicable.
Now, the reason learning is still possible, is that we have additional prior knowledge that relates the “inputs” (xt, at, rt) to the “outputs” ρ, such that we can treat them as latent variables for inference. These relationships are also depicted in Figure 2 (see the arrows on the bottom half of the figure). And the algorithms we propose precisely leverage these prior relationships for learning.
Is ICB itself a bandit algorithm that acts in the same domain? The answer is no. There is only ever a single bandit D := (X,A,R, T ) considered in our setting, which the underlying agent interacts with through a single sequence of actions. There is also only ever a single environment (identified by the tuple R, T ), which the agent starts off having no knowledge about. The agent employs a single belief-update function f to maintain their internal beliefs about the environment at each time step. Each time step, the agent is presented with a new context x ∼ T , and takes an action a ∼ πβ(x) based on their policy πβ . From the perspective of the agent, the forward problem of coming up with a good belief-update function f to maximize rewards in expectation over the entire (single) sequence of interactions is a bandit problem, precisely the “contextual bandit” problem (see Definition 1). From the perspective of the investigator, the inverse problem is simply learning ρenv,β1:T from D, which is the (single) observed sequence of contexts and actions (i.e. “inverse contextual bandits”) belongs to an entirely different class problems. Note that, unlike the agent, we as investigators do not interact the environment, observe sequential rewards, nor maintain and update beliefs of any form.

heading: D PROOFS OF LEMMAS
text: Proof of Lemma 1 First note that µt = Σt(Σ−11 µ1 +Xt−1r1:T ) by definition. Then, we have
P(r1:T |ρ1:T , ρ̂env, β̂1,D) ∝ P(r1:T ,ρ1:T , ρ̂env, β̂1,D)
∝ T∏ t=1 P(rt|ρ̂env, xt, at)× T∏ t=2 P(ρt|β̂t)
∝ T∏ t=1 Rρ̂env(xt, at)[rt]× T∏ t=2 Pβ̂t [ρt]
∝ N (σ2XTT ρ̂env, σ2I)[r1:T ]× T∏ t=2 N (µ̂t, Σ̂t)[ρt]
∝ N (σ2XTT ρ̂env, σ2I)[r1:T ]× T∏ t=2 exp ( − 1 2 · (ρt − µ̂t)TΣ̂−1t (ρt − µ̂t) ) ∝ N (σ2XTT ρ̂env, σ2I)[r1:T ]
× T∏ t=2 exp ( − 1 2 · (ρt − Σ̂tΣ̂−11 µ̂1 − Σ̂tXt−1r1:T )T · Σ̂ −1 t
· (ρt − Σ̂tΣ̂−11 µ̂1 − Σ̂tXt−1r1:T ) )
∝ N (σ2XTT ρ̂env, σ2I)[r1:T ]
× T∏ t=2 exp ( − 1 2 · ( rT1:TX T t−1Σ̂tXt−1r1:T − 2(ρt − Σ̂tΣ̂−11 µ̂1)TXt−1r1:T ) )) ∝ N (σ2XTT ρ̂env, σ2I)[r1:T ]
× T∏ t=2 exp ( − 1 2 · ( r1:T − (XTt−1Σ̂tXt−1)−1XTt−1(ρt − Σ̂tΣ̂−11 µ̂1) )T ·XTt−1Σ̂tXt−1 · ( r1:T − (XTt−1Σ̂tXt−1)−1XTt−1(ρt − Σ̂tΣ̂−11 µ̂1)
)) ∝ N (σ2XTT ρ̂env, σ2I)[r1:T ]
× T∏ t=2 N ( (XTt−1Σ̂tXt−1) −1XTt−1(ρt − Σ̂tΣ̂−11 µ̂1), (XTt−1Σ̂tXt−1)−1 ) [r1:T ]
∝ N (σ2XTT ρ̂env, σ2I)[r1:T ] ×N (( T∑
t=2
XTt−1Σ̂tXt−1 )−1( T∑ t=2 XTt−1(ρt − Σ̂tΣ̂−11 µ̂1) ) ,( T∑
t=2
XTt−1Σ̂tXt−1 )−1) [r1:T ]
∝ N (( 1
σ2 I + T∑ t=2 XTt−1Σ̂tXt−1 )−1( XTT ρ̂env + T∑ t=2 XTt−1(ρt − Σ̂tΣ̂−11 µ̂1) ) ,( 1
σ2 I + T∑ t=2 XTt−1Σ̂tXt−1 )−1) [r1:T ].
Proof of Lemma 2 We have P(β1:T |ρ1:T ,D)
∝ P(β1:T ,ρ1:T ,D) ∝ P(β1:T ) · P(ρ1:T |β1:T ,D)
∝ N (0,ΣT ⊗ ΣB)[vec(β1:T )] · N (vec(β1:T ), I ⊗ ΣP )[vec(ρ1:T )] ∝ N (0,ΣT ⊗ ΣB)[vec(β1:T )] · N (vec(ρ1:T ), I ⊗ ΣP )[vec(β1:T )]
∝ N (( (ΣT ⊗ ΣB)−1 + (I ⊗ ΣP )−1 )−1
(I ⊗ ΣP )−1vec(ρ1:T ),( (ΣT ⊗ ΣB)−1 + (I ⊗ ΣP )−1 )−1) [vec(β1:T )] .

heading: E EXPERIMENTAL DETAILS
text: Decision Environments There are 308,912 patients in the OPTN dataset who either were waiting for a liver transplantation or underwent a liver transplantation. Among these patients, we have filtered out the ones who never underwent a transplantation, the ones who were under the age of 18 or had a donor who was under the age of 18, and the ones who had a missing value for ABO Mismatch, Creatinine, Dialysis, INR, Life Support, Bilirubin, or Weight Difference. This filtering has left us with 31,059 patients, each corresponding to a different donor arrival. For the real-data experiments, we have sampled 2500 donor arrivals uniformly at random, and for each arrival, in addition to the patient who received the donor organ, sampled two more patients who were in the waitlist for a transplantation at the time of donor’s arrival in order to form an action space. For the simulated experiments, we have sampled 500 donor arrivals and two patients for each arrival uniformly at random.
Learning Agents
• Sampling: We set σ = 0.10.
• Optimistic: The agent forms the same posteriors as Sampling but selects actions such that at = argmaxa∈A µ T t xt[a] + xt[a] TΣtxt[a].
• Greedy: The agent forms the same posterior as Sampling but acts based on the mean reward parameters ρt = Eρ∼βt [ρ].
• Stepping: Formally, this agent is given by ρt = −1/k for t ∈ {1, . . . , t∗} and ρt = ρenv for t ∈ {t∗ + 1, . . . , T}. We set t∗ = T/2.
• Linear: Formally, this agent is given by ρt = t/T · ρenv + (1− t/T) · (−1/k). • Regressing: Formally, this agent is given by ρt = t/t∗ · ρenv + (1− t/t∗) · ρ0 for t ∈ {1, . . . , t∗}
and ρt = (t−t ∗)/(T−t∗) ·ργ + (1− (t−t∗)/(T−t∗)) ·ρenv for t ∈ {t∗+ 1, . . . , T}, where ρ0 = −1/k and ργ = γρenv + (1− γ)ρ0. Here, γ ∈ [0, 1] controls the amount of knowledge that is retained. We set t∗ = T/2 and γ = 0.
All learning agents select actions stochastically as described in (5) with α = 20.
Benchmark Algorithms
• B-IRL: We have run the Metropolis-Hastings algorithm for 10,000 iterations to obtain 1,000 samples from P(ρenv|D) with intervals of 10 iterations between each sample after 10,000 burn-in iterations. At each iteration, new candidate samples are generated by adding Gaussian noise with covariance matrix 0.0052I to the last sample. The final estimate ρ̂env is formed by averaging all samples.
• M -fold-IRL: Formally, this assumes ρt = ρ(j) for t ∈ {1 + b(j − 1)T/Mc, . . . , bjT/Mc} and j ∈ {1, . . . ,M}. We have used B-IRL as the IRL solver for each individual fold j ∈ {1, . . . ,M}.
• CP-IRL: Formally, similar to M -fold IRL, this assumes ρt = ρ(j) for t ∈ (t(j−1), t(j)) and j ∈ {1, ...M}, where t(0) = 0 and t(M) = T . However unlike M -fold IRL, it employs a changepoint detection algorithm to learn the t(j)’s together with the ρ(j)’s. We have partitioned the trajectory {1, . . . , T} into sub-trajectories of length 10 when detecting change points and used B-IRL as the IRL solver.
• I-SPI: We have assumed that the agent performs soft policy improvement after each time step (starting with a uniformly random policy). When computing soft policy improvements, the transition probabilities T (x, a)[x′] = T [x′] were estimated using the empirical distribution of contexts in datasetD—that is expectations of the form Ex′∼T ′ [·] were approximated by computing 1/T ∑ x′∈D[·] instead. Similar to B-IRL, we have run the Metropolis-Hastings algorithm for 10,000
iterations to obtain 1,000 samples from P(ρenv|D) with intervals of 10 iterations between each sample after 10,000 burn-in iterations. The same proposal distribution was used, and again, the final estimate ρ̂env was formed by by averaging all samples.
• T-REX: We have maximized the likelihood given in [52] using the Adam optimizer with a learning rate of 0.001, β1 = 0.9 and β2 = 0.999 until convergence, that is when the likelihood stopped improving for 100 consecutive iterations.
• B-ICB: We have set σ = 0.10, α = 20, and N = 1000 (with an additional 1000 samples as burn-in). When taking gradient steps, we have used the RMSprop optimizer with a learning rate of 0.001 and a discount factor of 0.9. We have run our algorithm for 100 iterations.
• NB-ICB: We have set ΣP = 5 ·10−4 · I and ΣB = 5 ·10−5 · I . We have taken 1,000 samples from P(β1:T |D) with an interval of 10 iterations between each sample after 10,000 burn-in iterations (i.e. N = 20,000).
For the simulated experiments, the error bars are obtained by repeating each experiment five times.
SUPPLEMENTARY REFERENCES [63] R. B. Freeman Jr, R. H. Wiesner, J. P. Roberts, S. McDiarmid, D. M. Dykstra, and R. M. Merion,
“Improving liver allcoation: MELD and PELD,” Amer. J. of Transplantation, vol. 4, pp. 114–131, 2004.
[64] A. Holzinger, C. Biemann, C. S. Pattichis, and D. B. Kell, “What do we need to build explainable ai systems for the medical domain?” arXiv preprint arXiv:1712.09923, 2017.
[65] S. Lundberg and S. Lee, “A unified approach to interpreting model predictions,” in Proc. 31st Int. Conf. Neural Inf. Process. Syst., 2017.
[66] Y. Goyal, Z. Wu, J. Ernst, D. Batra, D. Parikh, and S. Lee, “Counterfactual visual explanations,” in Proc. 36th Int. Conf. Mach. Learn., 2019.
[67] I. Bica, D. Jarrett, A. Hüyük, and M. van der Schaar, “Learning what-if explanations for sequential decision-making,” in Proc. 9th Int. Conf. Learn. Representations, 2011.

Review summaries:
This paper studies an inverse (linear) contextual bandits (ICB) problem, where, given a $T$-round realization of a bandit policy’s actions and observed rewards, the goal is to design an algorithm to estimate the underlying environment parameter, along with the “belief trajectory” of the bandit policy. A particular emphasis is placed on the belief trajectory being “interpretable” and capturing changes in the policy’s “knowledge of the world” over time.  The paper’s main contributions are (i) formalizing the inverse contextual bandits problem, (ii) designing two algorithms for this problem based on two different ways of modelling beliefs of the bandit policy, and (iii) providing empirical illustrations of how their algorithm can be used to investigate and explain changes in medical decision-making over time 

This paper addresses the problem of Inverse Contextual Bandit.  They raise an important question: given demonstrated behavior from an agent, how has the agent’s knowledge been evolving over time? Formally, Given a contextual bandit problem $(X, A, R, T )$,  where $R, T$ are unknown to the agent. Given an observational dataset $D$, and a family of reward parameterizations $P$ and belief parameterizations $B$, the inverse contextual bandits problem is to determine the true environment parameter $\rho^*$ and the belief parameters $\beta_{1:T}$.   They propose two algorithms to learn these parameters. The first uses the agent’s knowledge in terms of Bayesian update. The second uses the Gaussian process. They demonstrate their algorithm through simulated and real-world data for liver transplantations.