Dueling Posterior Sampling for Preference-Based Reinforcement Learning

Ellen R. Novoseller 1 Yanan Sui 2 Yisong Yue 1 Joel W. Burdick 1

Abstract
In preference-based reinforcement learning(PBRL), an agent interacts with the environment
while receiving preferences instead of absolutefeedback. While there is increasing research
activity in PBRL, the design of formal frameworks that admit tractable theoretical analysis remains an open challenge. We present D UELINGP OSTERIOR S AMPLING (DPS), which employs
preference-based posterior sampling to learn boththe system dynamics and the underlying utility
function that governs the user’s preferences. To
solve the credit assignment problem, we develop
a Bayesian approach to translate user preferences
to a posterior distribution over state/action reward
models. We prove an asymptotic no-regret ratefor DPS with Bayesian logistic regression credit
assignment; to our knowledge, this is the firstregret guarantee for PBRL. We also discuss possible avenues for extending this proof methodology
to analyze other credit assignment models, andfinally, evaluate the approach empirically.

1. Introduction
In many domains, ranging from clinical trials (Sui et al.,2018a) to autonomous driving (Sadigh et al., 2017) andhuman-robot interaction (Kupcsik et al., 2018), it can be unclear how to define a reward signal for reinforcement learning (RL). In such situations, the RL agent seeks to interact
optimally with a human user; thus, rewards should reflect
the extent to which the algorithm achieves the user’s goals.
Yet, for many systems, for instance in autonomous driving(Basu et al., 2017) and robotics (Argall et al., 2009; Akrour
et al., 2012), users have difficulty with both specifying numerical reward functions and providing demonstrations ofdesired behavior. In such cases, the user’s preferences form
1

Department of Computing and Mathematical Sciences, California Institute of Technology, Pasadena, California, USA
2
Department of Computer Science, Stanford University, Stanford,
California, USA. Correspondence to: Ellen R. Novoseller <enovoseller@caltech.edu>.
Real-world Sequential Decision Making workshop at ICML 2019.
Copyright 2019 by the author(s)a more reliable measure of desired system behavior.
We thus study the problem of preference-based reinforcement learning (PBRL), where the RL agent executes a pairof trajectories, and the user provides (noisy) preference feedback regarding which trajectory has higher utility. While
the study of PBRL has seen increased interest in recent
years (Christiano et al., 2017; Wirth et al., 2017), it remains
an open challenge to design formal frameworks that admit
tractable theoretical analysis. Compared to the preferencebased bandit setting, which has seen significant theoreticalprogress (Yue et al., 2012; Dudík et al., 2015; Wu & Liu,
2016; Sui et al., 2017; 2018b), one major challenge is how
to address credit assignment when only receiving feedback
at the trajectory level compared to the state/action level.
In this paper, we present D UELING P OSTERIOR S AM PLING (DPS), which uses preference-based posterior sampling to tackle the PBRL problem in the Bayesian regime.
Posterior sampling (also known as Thompson sampling)(Thompson, 1933; Osband et al., 2013; Gopalan & Mannor,
2015; Agrawal & Jia, 2017; Osband & Van Roy, 2017) is
a Bayesian model-based approach to balancing explorationand exploitation, enabling the algorithm to efficiently learn
models of both the environment’s state transition dynamics and the reward function. Previous work on posterior
sampling in RL (Osband et al., 2013; Gopalan & Mannor,
2015; Agrawal & Jia, 2017; Osband & Van Roy, 2017) all
focused on learning from absolute rewards, while we show
how to extend posterior sampling to both elicit and learn
from trajectory-level preference feedback.
To elicit preference feedback, at every episode of learning,
DPS draws two independent samples from the posterior
to generate two trajectories. This approach is inspired by
the Self-Sparring algorithm proposed for the bandit setting(Sui et al., 2017); however, our theoretical analysis is quite
different, due to the need to incorporate trajectory-level
preference learning and state transition dynamics.
To learn from preference feedback, DPS internally maintains a Bayesian state/action reward model that explains thepreferences. This reward model is a solution to the temporal
credit assignment problem (Akrour et al., 2012; Zoghi et al.,2014; Szörényi et al., 2015; Christiano et al., 2017; Wirthet al., 2016; 2017) and determines which of the encounteredstates and actions are responsible for the trajectory-level

Dueling Posterior Sampling for Preference-Based Reinforcement Learning

preference feedback. Learning from trajectory preferences
is in general a very challenging problem, as information
about rewards is sparse, is only relative to the pair of trajectories being compared, and does not explicitly include
information about actions within trajectories.
We developed DPS concurrently with an analysis framework for characterizing regret convergence in the episodic
learning setting. We evaluate several possible Bayesiancredit assignment models, and prove an asymptotic no-regret
rate for DPS using Bayesian logistic regression (Albert &Chib, 1993; Murphy, 2012) as the credit assignment model.
To our knowledge, this is the first PBRL approach with theoretical guarantees. In addition, we also demonstrate thatDPS delivers competitive performance in simulation.

2. Problem Statement
Preliminaries. We consider fixed-horizon Markov Decision Processes (MDPs), in which rewards are replaced by
preferences over trajectories. This class of MDPs can be
represented as a tuple, M = (S, A, , φ, p, p0 , h), where
the state space S and action space A are finite sets. The
agent, using policy π, episodically interacts with the environment with length-h roll-out trajectories of the form
τ = {s0 , a0 , s1 , a1 , . . . , sh−1 , ah , sh }. Since we are eliciting preference feedback, in each episode i, the agent executes two roll-outs τi1 and τi2 , and observes a preference
between the two. The initial state is sampled from p0 , while
p defines the transition dynamics: st+1 ∼ p(·|st , at ).
We use  to denote the stochastic preference relationshipbetween trajectories, and φ(τ, τ 0 ) = P(τ > τ 0 ) − 0.5 ∈[−0.5, 0.5] to capture the feedback generation mechanism.
We assume that  is a total ordering over trajectories, andτ  τ 0 ⇔ φ(τ, τ 0 ) > 0. We use τ > τ 0 to denote the eventthat trajectory τ was preferred over τ 0 in a preference elicitation, i.e., τ > τ 0 is observed with probability φ(τ, τ 0 ) + 0.5.
We further assume an underlying utility function r(τ ) for
each trajectory, such that τ  τ 0 ⇔ r(τ ) > r(τ 0 ), anddefine φ using r. For instance, if the preferences are noiseless, then: φ(τi , τj ) = I[r(τi ) > r(τj )] − 0.5. We primarily assume a logistic or Bradley-Terry link function:
φlin (τi , τj ) := [1 + exp(−c(r(τi ) − r(τj )))]−1 with “temperature” c ∈ (0, ∞). Our problem setting resembles thePSDP defined in (Wirth & Fürnkranz, 2013b), except that
we also incorporate the noise model through which the underlying utilities are stochastically translated to preferences.
Finally, we assume that the utilities decompose additively:Phr(τ ) ≡ i=1 r(si , ai ) for state/action pairs in τ .
Given a policy π, we can define the standard RL valuefunction as the expected total utility of being in state s at

Algorithm 1 D UELING P OSTERIOR S AMPLING (DPS)H = ∅ {Initialize history}
T = ∅ {Initialize list of preference data}
Initialize prior for f {Initialize state transition model}
Initialize prior for g {Initialize utility model}
while True do
π1 ← A DVANCE(H, T , f , g)
π2 ← A DVANCE(H, T , f , g)
Sample trajectories τ1 and τ2 from π1 and π2
Observe feedback b = I(τ2 > τ1 )2
2
, aτh−1, sτh2 )H = H ∪ (sτ11 , aτ11 , sτ21 ) ∪ . . . ∪ (sτh−1
T = T ∪ (τ1 , τ2 , b)
FEEDBACK (H, T , f , g)end while

step i, and following policy π:hXVπ,i (s) = E r(sj , π(sj ))|si = s ,

(1)

j=i

and now we can define the optimal policy π ∗ as theone with maximal value for all input states. Note thatEs0 ∼p0 [Vπ,0 (s0 )] ≡ Eτ ∼π,M [r(τ )]. Given fully specified
dynamics and reward models, p and r, it is straightforward
to apply standard dynamic programming approaches suchas value iteration to arrive at the optimal policy under p andr (Sutton & Barto, 2018). The goal of learning, then, is infer
p and r to the extent necessary for good decision-making.
Learning Problem. In each iteration (or episode) i, theagent selects two policies, πi1 and πi2 . The two policies
are rolled out to obtain trajectories τi1 and τi2 , and a binary
preference bi ∈ {0, 1} between them is sampled according
to the underlying utilities of τi1 and τi2 . We quantify the performance of the learning agent using expected cumulative
regret relative to the optimal policy:( dT /(2h)eh
X X
E[R EGT ] = E
p(s) 2Vπ∗ ,0 (s)
(2)
i=1

s∈S

)
i
− Vπi1 ,0 (s) − Vπi2 ,0 (s) .

(3)

To minimize regret, the agent must balance exploration (collecting new data) with exploitation (behaving optimally w.r.t.
existing models). In contrast to the standard formulation
in RL (Osband et al., 2013), at each iteration/episode wecompare the utilities of both selected policies.

3. Algorithm
As outlined in Algorithm 1, D UELING P OSTERIOR S AM PLING (DPS) iterates over three main steps: (a) sample
two policies π1 , π2 from the Bayesian posteriors of the dynamics and utility models (A DVANCE – Algorithm 2); (b)Dueling Posterior Sampling for Preference-Based Reinforcement Learning

Algorithm 2 A DVANCE: Sample policy from dynamics andutility models
Input: H, T, f, g
Sample M ∼ f (·|H) {Sample MDP transition dynamics fromposterior}
Sample R ∼ g(·|T ) {Sample utilities from posterior}Compute π = argmaxπ V (M, R) {Value iteration yields sampled MDP’s optimal policy}
Return π

Algorithm 3 FEEDBACK: Update dynamics and utility models based on new user feedback
Input: H, T, f, g
Apply Bayesian update to f , given H {Update dynamics model
given history}
Apply Bayesian update to g, given T {Update utility model
given preferences}
Return f , groll out π1 and π2 to obtain trajectories τ1 and τ2 , andreceive preference feedback between them; (c) store the
new state transitions and feedback and update the posterior(FEEDBACK – Algorithm 3). Compared to conventional
posterior sampling with absolute feedback (Osband et al.,2013), the two key differences are that: two policies are sampled rather than one each iteration, and a credit assignment
problem is solved when learning from feedback.
A DVANCE (Algorithm 2) samples from the Bayesian posteriors of the dynamics and utility models. The sampled
dynamics and utilities form an MDP, and value iteration isused to derive the optimal policy π under the sample. Intuitively, peaked (i.e., certain) posteriors lead to less variability
when sampling π, which implies less exploration, while diffuse (i.e., uncertain) posteriors lead to greater variability
when sampling π, which implies more exploration.
FEEDBACK (Algorithm 3) updates the Bayesian posteriorsof the dynamics and utility models based on new data. Updating the dynamics posterior is relatively straightforward,
as we assume the dynamics are fully-observed; for instance,
the dynamics prior can be modeled via Dirichlet distributions with multinomial conjugate observation likelihoods(Osband et al., 2013). In contrast, performing Bayesian inference over state/action utilities from trajectory-level feedback is much more challenging. Considering a range ofapproaches (see Appendix A1), we found Bayesian logistic regression (Section 3.1) to both be well-performing andadmit tractable analysis within our theoretical framework.
3.1. Bayesian Logistic Regression for Utility Inference
and Credit Assignment
Credit assignment (Wirth, 2017) is the problem of inferring which state/action pairs are responsible for observed
trajectory-level preferences. We detail a Bayesian logis-

tic regression approach to address this task in our setting.
Logistic regression is a binary classification method thatlearns a weight vector w for the model p(y = 1|x, w) =1
. Bayesian logistic regression (Albert & Chib,
1+exp(−wT x)
1993; Murphy, 2012) maintains a posterior over possible
weight vectors. Because there is no convenient prior yielding a closed-form conjugate posterior, we use the Laplaceapproximation to the posterior as specified below.
Preliminaries. Let N be the number of trajectories pairs
observed so far, and D = SA be the total number ofstate/action pairs. Let xij ∈ RD , j ∈ {1, 2} be the visitation vector corresponding to trajectory τij , with the k th(k)element xij being the number of times that state/action
pair k was visited in τij . Define xi := xi1 − xi2 . The
observation matrix X and label vector y are defined as: (x11 − x12 )T
y1



.
. 
..
X=
(4)
 , y =  ..  ,(xN 1 − xN 2 )TyN

where yi = 2I[τi1 >τi2 ] − 1, so that yi ∈ {−1, 1}.
The observation matrix X ∈ RN ×D has rank at most D − 1,since each row xi = xi1 − xi2 must sum to zero. To obtaina full-row-rank observation matrix for Bayesian logistic
regression, we transform
X ∈ RN ×D∈ RN ×(D−1)
 to W
D×(D−1)
via the matrix V = v1 . . . vD−1 ∈ R, wherevi ∈ RD form an orthonormal basis spanning the (D − 1)dimensional, full possible row space of X. To obtain thevector wi ∈ RD−1 that expresses xi in this basis, apply:
wi = [xTi v1 . . . xTi vD−1 ]T = V T xi ,(5)

while wi ∈ RD−1 is converted to the original space via:
xi =

D−1
X

wij vj = V wi ,

(6)

j=1

where wij is the j th element of wi .
Utility Model & Posterior Inference. We fit a Bayesianlogistic regression model to the transformed data (W, y).
This model predicts the probability that τ is preferred to τ 0
as a logistic regression function of their visitation vector
differences xτ − xτ 0 . The model parameters correspondexactly to the state/action utilities r. The model internallycomputes an element-wise product between xτ − xτ 0 andestimated reward vector r, within the (D − 1)-dimensional
space given by (5). Because (5) preserves inner products(see Appendix A2), this is exactly the trajectory utility, andtaking the expectation over trajectories generated by a policy
is exactly the value function (1).
We are chiefly interested in sampling from the posterior ofparameter/utility vector r, which can be combined with theDueling Posterior Sampling for Preference-Based Reinforcement Learning

sampled dynamics to perform value iteration and obtain apolicy. As shown below, using the Laplace approximation,
the posterior is Gaussian distributed, from which samples
can easily be drawn. The internal utility representation liesin r̃ 0 ∈ RD−1 , and we convert to r̃ ∈ RD via (6).
We now describe the Bayesian logistic regression step. A
Gaussian prior is defined over utilities r 0 ∈ RD−1 : p(r 0 ) ∼N (r 0 |r0 , V0 ). The logistic regression likelihood is:p(W, y|r 0 ) =

N
Y

1
.
T 0
1
+
exp(y
i wi r )i=1(7)

We model the posterior via the Laplace approximation:p(r 0 |W, y) ≈ N (r 0 |r̂ 0 , H −1 ), where:(8)r̂ 0 = argmin f (r 0 ),

(9)

r0
0

f (r ) := −log p(r 0 ) − log p(W, y|r 0 ),H = ∇2r0 f (r 0 )

r̂

.
0

(10)
(11)

To show a regret convergence using this approximate posterior, we leverage asymptotic normality of the maximum
likelihood estimator of logistic regression in our proofs.

4. Theoretical Results
We now sketch our asymptotic no-regret analysis for D UEL ING P OSTERIOR S AMPLING (DPS) with Bayesian logistic
regression; the full proof is in Appendix A2. Additionally,
Appendix A2.1 discusses possible avenues for extending
this proof methodology toward analyzing other credit assignment models. The proof has two main parts: first provingthat DPS with logistic credit assignment is asymptoticallyconsistent (Theorem 1), and then proving that DPS has
a sublinear regret rate (Theorem 2). Both parts leverage
results on the asymptotic behavior of logistic regression(Gourieroux & Monfort, 1981). As before, we consider
Bayesian logistic regression with data W ∈ RN ×(D−1) andlabels y ∈ RN , with [W ]ij = wij . To show that DPS is
asymptotically consistent in learning the reward function,
we first provide some definitions and necessary conditions.
Definition 1 (Derivative of sigmoid). f : R −→ R, wheree−xf = (1+e−x )2 . Note that f (x) = f (−x).
Definition 2. Let r ∈ RD−1 be the vector of true
state/action utilities; we assume r exists. Define r̃k ∈ RD−1
as the state/action rewards sampled from the posterior in
episode k, r̂k ∈ RD−1 as the maximum a posteriori (MAP)
estimate of the Bayesian logistic regression model at episodek, and finally, r̂M L,k ∈ RD−1 as the maximum likelihood
estimate of the logistic regression model at k.
Condition 1. ∃ M0 such that |wij | ≤ M0 for all i ∈{1, . . . , N }, j ∈ {1, . . . , D − 1}.

(k)

(k)

Condition 2. Let λ1 and λD−1 be the largest and smallest
Pkeigenvalues, respectively, of i=1 f (wiT r)wi wiT . Then,(k)∃ M1 such that

λ1

(k)
λD−1

< M1 , for all k.

Proposition 1 (Asymptotic consistency of logistic regression (Gourieroux & Monfort, 1981)). If Conditions 1 and 2
are satisfied, then the maximum likelihood estimator r̂M L,kof r exists almost surely as k −→ ∞, and r̂M L,k converges almost surely to the true values r if and only if(k)lim λD−1 = ∞.
k−→∞

We first show that Proposition 1’s final condition is satisfied
with known transition dynamics, and afterwards consider
the convergence of the dynamics model posterior.
Lemma 1. UnderPknown transition dynamics, all eigenvalk
ues of the matrix i=1 f (wiT r)wi wiT approach infinity ask −→ ∞.
Lemma 2 (Convergence of dynamics model). Given
Lemma 1, DPS’s dynamics model converges to thetrue
and as it converges, all eigenvalues of
Pk dynamics,
T
T
f
(w
r)w
i wi approach infinity.
i
i=1
Combining these results, we obtain:
Theorem 1 (Asymptotic consistency of DPS). If there
exists a reward function such that a logistic regression model
explains the preference feedback, then DPS with a Bayesianlogistic regression credit assignment model will learn an
asymptotically consistent reward model.
We turn next to characterizing the regret rate of DPS. We
apply two prior results, one from Gourieroux and Monfort(1981) regarding the asymptotic distribution of the logistic
regression maximum likelihood estimate (Prop. 2), and theother from Osband et al. (2013) regarding a regret boundfor posterior sampling RL (Prop. 3).
Proposition 2 (Asymptotic normality of logistic regression
maximum likelihood estimator (Gourieroux & Monfort,
1981)). If Conditions 1 and 2 are satisfied, and if r̂M L,kconverges almost surely to the true value r, then:
" k
X

# 12
f (wiT r̂M L,k )wi wiT(r̂M L,k − r)(12)−→ N (0, I) as k −→ ∞,

(13)

i=1
D

D

1

where −→ implies convergence in distribution and Q 2 isthe positive definite matrix associated with positive definite
1
matrix Q such that [Q 2 ]2 = Q.
Proposition 3 (Expected regret of posterior sampling RL(Osband et al., 2013)).
p Posterior sampling RL has expected
T -step regret O(hS AT log(SAT )), with horizon h andnumbers of states and actions S and A.

Dueling Posterior Sampling for Preference-Based Reinforcement Learning

Leveraging these results, we show that under preference
feedback, the regret can be decomposed into two terms:
one that reflects the converging dynamics model, and onethat reflects the converging reward model (inferred fromtrajectory-level preference feedback).
Lemma 3 (Regret decomposition). The expected regretof DPS can be decomposed into two terms. One term
can be bounded by the regret bound of Osband et al.
(2013), stated in Proposition (3). The other is bounded
PdT /hePdT /heby: h k=1 E[||r − r̃k ||∞ ] ≤ h k=1 E[||r̂k − r||∞ ] +PdT /heh k=1 E[||r̂k − r̃k ||∞ ].
The most burdensome part of our proof is analyzing convergence of r̃k to r̂k and r̂k to r, which requires analyzing
convergence of credit assignment. Afterwards, we reach thefinal result:
Theorem 2 (Asymptotic regret rate of DPS). If
there exists a reward function such that a logistic regression model explains the preference feedback,DPS has an q
asymptotic no-regret
rate of thenp
SA
O hS AT log(SAT ) + h c0 T log(T ) , where c0 isalinear rate at which all eigenvalues of
PkminimumTT
i=1 f (wi r)wi wi must increase with k.

5. Experiments
We validate the empirical performance of D UELING P OS TERIOR S AMPLING (DPS) on two simulated domains withvarying preference functions, and also evaluate DPS using
alternative credit assignment models. We find that DPS generally performs well, and outperforms standard PBRL baselines (Wirth & Fürnkranz, 2013a).
Experimental Setup. We evaluate on two simulated environments: RiverSwim and random MDPs. The RiverSwim
environment (Osband et al., 2013) has six states and two
actions (actions 0 and 1); the optimal policy is to always
choose action 1, which maximizes the probability of reaching a particular goal state/action pair. Meanwhile, a suboptimal policy—yielding a much smaller reward comparedto the goal—is quickly and easily discovered and incentivizes the agent to always select action 0. The algorithm
must demonstrate sufficient exploration to have hope of
discovering the optimal policy quickly.
In the second simulated environment, we generate random
MDPs according to the procedure of Osband et al. (2013).
Each random MDP is generated with 50 states and 5 actions,and the transition dynamics and rewards are generated from
Dirichlet and Normal-Gamma distributions, respectively.
All parameters of these two distributions were set to 1 toobtain a diffuse distribution over possible MDPs. The sampled reward vectors were shifted and normalized so that all
rewards fell between 0 and 1.

In both of these environments, preferences between pairs of
trajectories were generated by (noisily) comparing the total
rewards that they accumulated; this reward information was
hidden from the learning algorithm, which observed only the
trajectory preferences and state transitions. Preference noise
is generated according to a logistic model: for trajectories
τi and τj , P (τi > τj ) = {1 + exp[−c(r(τi ) − r(τj ))]}−1 ,where r(τi ) and r(τj ) are the total rewards accrued by thetwo trajectories, respectively, while the hyperparameter ccontrols the degree of noisiness.
Methods Compared. We evaluate DPS under three noiselevels (c ∈ {0.1, 1, 1000}) and three credit assignment models: 1) Bayesian logistic regression, 2) Bayesian linear regression, and 3) Gaussian process regression, where thelatter two are described in Appendix A1. In addition, we
evaluate Every-Visit Preference Monte Carlo (EPMC) withprobabilistic credit assignment (Wirth & Fürnkranz, 2013b;
Wirth, 2017) as a baseline. Lastly, we compare against
the posterior sampling RL algorithm (Osband et al., 2013),
which learns using the true numerical rewards at each step,and thus yields an upper-bound on the performance that apreference-based algorithm could achieve.
Results. Figure 1 shows the performance comparison forc = 1 in both environments, as well as c = 1, 000 in RiverSwim (additional results are in Appendix A3, including
hyperparameter details). DPS performs well in all simulations, and sometimes significantly outperforms the EPMC
baseline. This may be because EPMC uses a uniform exploration strategy, while DPS prioritizes exploration by
sampling high rewards for more uncertain state/action pairs.
Notice that c = 1, 000 results in nearly-noiseless preferences; this can decrease performance in RiverSwim in somecases, since preference noise can help the agent to escape
the local minimum. We also see that DPS is competitive
with PSRL, which has access to the full cardinal rewards
at each state/action. Finally, we see that the performanceof DPS is robust to the choice of credit assignment model,
and in fact using Gaussian process regression (for which
we do not have an end-to-end regret analysis) often leads tothe best empirical performance. These results suggest that
DPS is a practically promising approach that can robustly
incorporate many modeling approaches as subroutines.

6. Conclusion
We investigate the preference-based reinforcement learning
problem, which receives comparative preferences insteadof absolute real-valued rewards as feedback. We develop
the D UELING P OSTERIOR S AMPLING (DPS) algorithm,
which optimizes policies in an highly efficient and flexible
way. To our knowledge, DPS is the first preference-based
RL algorithm with a regret guarantee. DPS also performs
well in our simulations, and seems practically promising.

Dueling Posterior Sampling for Preference-Based Reinforcement Learning(a) RiverSwim, c = 1, 000(b) RiverSwim, c = 1(c) Random MDP, c = 1

Figure 1. Empirical performance of DPS. a) and b) show RiverSwim with noise hyperparameters c = 1, 000, 1. c) displays random
MDPs with c = 1. Posterior sampling RL (PSRL) (Osband et al., 2013) is an upper-bound that receives numerical rewards; Gaussian
process regression (GPR), Bayesian linear regression, and Bayesian logistic regression are all instances of DPS. EPMC is a baseline fromWirth and Fürnkranz (2013b) as discussed. Plots display mean +/- one std over 100 runs of each algorithm tested. Additional results(more values of c) are in Appendix A3. Overall, we see that DPS performs well and is robust to the choice of credit assignment model.

There are many directions for future work. The Bayesianlogistic regression model could be improved with moreaccurate posterior estimates. Assumptions governing theuser’s preferences, such as requiring an underlying utility
model, could be relaxed. One can also incorporate kernelized methods to further improve sample efficiency. It is also
important to extend to other credit assignment models, suchas the Gaussian process regression and Bayesian linear regression methods, for which the same concept of the regret
decomposition still applies. We expect that DPS would perform well with any asymptotically consistent reward modelthat sufficiently captures users’ preference behavior.

Acknowledgements
This work was funded by NIH grant EB007615 and an
Amazon graduate fellowship.

References
Agrawal, S. and Jia, R. Optimistic posterior sampling forreinforcement learning: Worst-case regret bounds. In
Advances in Neural Information Processing Systems, pp.
1184–1194, 2017.
Akrour, R., Schoenauer, M., and Sebag, M. APRIL: Active preference learning-based reinforcement learning.
In Joint European Conference on Machine Learning
and Knowledge Discovery in Databases, pp. 116–131.
Springer, 2012.
Albert, J. H. and Chib, S. Bayesian analysis of binary andpolychotomous response data. Journal of the American
statistical Association, 88(422):669–679, 1993.
Argall, B. D., Chernova, S., Veloso, M., and Browning, B.
A survey of robot learning from demonstration. Robotics
and autonomous systems, 57(5):469–483, 2009.
Basu, C., Yang, Q., Hungerman, D., Sinahal, M., and Dragan, A. D. Do you want your autonomous car to drive likeyou? In 2017 12th ACM/IEEE International Conferenceon Human-Robot Interaction (HRI, pp. 417–425. IEEE,
2017.
Christiano, P. F., Leike, J., Brown, T., Martic, M., Legg,
S., and Amodei, D. Deep reinforcement learning fromhuman preferences. In Advances in Neural Information
Processing Systems, pp. 4299–4307, 2017.
Dudík, M., Hofmann, K., Schapire, R. E., Slivkins, A., andZoghi, M. Contextual dueling bandits. In Conference on
Learning Theory (COLT), 2015.
Gopalan, A. and Mannor, S. Thompson sampling for learning parameterized Markov decision processes. In Conference on Learning Theory, pp. 861–898, 2015.

Dueling Posterior Sampling for Preference-Based Reinforcement Learning

Gourieroux, C. and Monfort, A. Asymptotic properties ofthe maximum likelihood estimator in dichotomous logit
models. Journal of Econometrics, 17(1):83–97, 1981.
Kupcsik, A., Hsu, D., and Lee, W. S. Learning dynamic
robot-to-human object handover from human feedback.
In Robotics research, pp. 161–176. Springer, 2018.
Murphy, K. P. Machine learning: A probabilistic perspective. The MIT Press, 2012.
Osband, I. and Van Roy, B. Why is posterior sampling better
than optimism for reinforcement learning? In Proceedings of the 34th International Conference on Machine
Learning-Volume 70, pp. 2701–2710. JMLR. org, 2017.
Osband, I., Russo, D., and Van Roy, B. (More) efficient
reinforcement learning via posterior sampling. In Advances in Neural Information Processing Systems, pp.
3003–3011, 2013.
Sadigh, D., Dragan, A. D., Sastry, S., and Seshia, S. A.
Active preference-based learning of reward functions. In
Robotics: Science and Systems (RSS), 2017.
Sui, Y., Zhuang, V., Burdick, J. W., and Yue, Y. Multidueling bandits with dependent arms. In Proceedings of
the Conference on Uncertainty in Artificial Intelligence,
2017.
Sui, Y., Zhuang, V., Burdick, J., and Yue, Y. Stagewisesafe Bayesian optimization with Gaussian processes. In
Proceedings of the 35th International Conference on Machine Learning, volume 80 of Proceedings of Machine
Learning Research, pp. 4781–4789. PMLR, 10–15 Jul
2018a.
Sui, Y., Zoghi, M., Hofmann, K., and Yue, Y. Advancements
in dueling bandits. In IJCAI, pp. 5502–5510, 2018b.
Sutton, R. S. and Barto, A. G. Reinforcement learning: An
introduction. MIT press, 2018.
Szörényi, B., Busa-Fekete, R., Paul, A., and Hüllermeier,E. Online rank elicitation for Plackett-Luce: A duelingbandits approach. In Advances in Neural Information
Processing Systems, pp. 604–612, 2015.
Thompson, W. R. On the likelihood that one unknown
probability exceeds another in view of the evidence of
two samples. Biometrika, 25(3/4):285–294, 1933.
Wirth, C. Efficient Preference-based Reinforcement Learning. PhD thesis, Technische Universität, 2017.
Wirth, C. and Fürnkranz, J. EPMC: Every visit preferenceMonte Carlo for reinforcement learning. In Asian Conference on Machine Learning, pp. 483–497, 2013a.

Wirth, C. and Fürnkranz, J. A policy iteration algorithm
for learning from preference-based feedback. In International Symposium on Intelligent Data Analysis, pp.
427–437. Springer, 2013b.
Wirth, C., Fürnkranz, J., and Neumann, G. Model-freepreference-based reinforcement learning. In Thirtieth
AAAI Conference on Artificial Intelligence, 2016.
Wirth, C., Akrour, R., Neumann, G., and Fürnkranz, J. A
survey of preference-based reinforcement learning methods. The Journal of Machine Learning Research, 18(1):4945–4990, 2017.
Wu, H. and Liu, X. Double Thompson sampling for duelingbandits. In Advances in Neural Information Processing
Systems, pp. 649–657, 2016.
Yue, Y., Broder, J., Kleinberg, R., and Joachims, T. The
k-armed dueling bandits problem. Journal of Computerand System Sciences, 78(5):1538–1556, 2012.
Zoghi, M., Whiteson, S., Munos, R., and De Rijke, M.
Relative upper confidence bound for the k-armed duelingbandit problem. In International Conference on Machine
Learning (ICML), 2014.