000
001
002
003
004
005
006
007
008
009
010
011
012
013
014
015
016
017
018
019
020
021
022
023
024
025
026
027
028
029
030
031
032
033
034
035
036
037
038
039
040
041
042
043
044
045
046
047
048
049
050
051
052
053
054

Reinforcement learning with Human Feedback: Learning Dynamic Choices via
Pessimism
Anonymous Authors1

Abstract
In this paper we study offline Reinforcement
Learning with Human Feedback (RLHF) where
we aim to learn the human’s underlying reward and the MDP’s optimal policy from a
set of trajectories induced by human choices.
We focus on the Dynamic Discrete Choice(DDC) model for modeling and understanding human choices, which is widely used tomodel a human decision-making process withforward-looking and bounded rationality. We
propose a Dynamic-Choice-Pessimistic-PolicyOptimization (DCPPO) method and prove that the
suboptimality of DCPPO almost matches the classical pessimistic offline RL algorithm in terms ofsuboptimality’s dependency on distribution shift
and dimension. To the best of our knowledge, thispaper presents the first theoretical guarantees foroff-policy offline RLHF with dynamic discrete
choice model.

knowledge becomes pivotal.
Dynamic Discrete Choice (DDC) model is a framework forstudying learning for human choices from data, which has
been extensively studied in econometrics literature. (Rust,
1987; Hotz & Miller, 1993; Hotz et al., 1994; Aguirregabiria & Mira, 2002; Kalouptsidi et al., 2021; Bajari et al.,2015; Chernozhukov et al., 2022). In a DDC model, theagent make decisions under unobservable perturbation, i.e.
πh (ah | sh ) = argmaxa {Qh (sh , a) + ϵh (a)}, where ϵh isan unobservable random noise and Qh is the agent’s action
value function.
In this work, we focus on RLHF within the context of a
dynamic discrete choice model. Our challenges are threefolded: (i) The agent must first learn the human behavior
policies from the feedback data. (ii) As the agent’s objective
is to maximize cumulative reward, the reward itself is notdirectly observable. We need to estimate the reward from thebehavior policies. (iii) We face the challenge of insufficient
dataset coverage and large state space.
With these coupled challenges, we ask the following question:

1. Introduction
Reinforcement Learning with Human Feedback (RLHF) isan area in machine learning research that incorporates human guidance or feedback to learn an optimal policy. In
recent years, RLHF has achieved significant success in large
language models, clinical trials, auto-driving, robotics, etc.
(Ouyang et al., 2022; Gao et al., 2022; Glaese et al., 2022;
Hussein et al., 2017; Jain et al., 2013; Kupcsik et al., 2018;
Menick et al., 2022; Nakano et al., 2021; Novoseller et al.,2020). Unlike conventional offline reinforcement learning, where the learner aims to determine the optimal policy
using observable reward data, in RLHF, the learner does
not have direct access to the reward signal but instead can
only observe a historical record of visited states and humanpreferred actions. In such cases, the acquisition of reward
1
Anonymous Institution, Anonymous City, Anonymous Region,
Anonymous Country. Correspondence to: Anonymous Author<anon.email@domain.com>.

Preliminary work. Under review by the International Conference
on Machine Learning (ICML). Do not distribute.

Without access to the reward function, can one learn the
optimal pessimistic policy from merely human choices
under the dynamic choice model?
Our Results. In this work, we propose the DynamicChoice-Pessimistic-Policy-Optimization (DCPPO) algorithm. By addressing challenges (i)-(iii), our contributions
are three folds: (i) For learning behavior policies in large
state spaces, we employ maximum likelihood estimation toestimate state/action value functions with function approximation. We establish estimation error bounds for generalmodel class with low covering number. (ii) Leveraging thelearned value functions, we minimize the Bellman meansquared error (BMSE) through linear regression. This allows us to recover the unobservable reward from the learned
policy. Additionally, we demonstrate that the error of ourestimated reward can be efficiently controlled by an uncertainty quantifier. (iii) To tackle the challenge of insufficient
coverage, we follow the principle of pessimism, by incorporating a penalty into the value function during value iteration.

055
056
057
058
059
060
061
062
063
064
065
066
067
068
069
070
071
072
073
074
075
076
077
078
079
080
081
082
083
084
085
086
087
088
089
090
091
092
093
094
095
096
097
098
099
100
101
102
103
104
105
106
107
108
109

We establish the suboptimality of our algorithm with highprobability with only single-policy coverage.
Our result matches existing pessimistic offline RL algorithms in terms of suboptimality’s dependence on distribution shift and dimension, even in the absence of an observable reward. To the best of our knowledge, our results offer
the first theoretical guarantee for pessimistic RL under thehuman dynamic choice model.
1.1. Related Work
Reinforcement Learning with Human Feedback. In
recent years RLHF and inverse reinforcement learning(IRL) has been widely applied to robotics, recommendation
system, and large language model (Ouyang et al., 2022;
Lindner et al., 2022; Menick et al., 2022; Jaques et al., 2020;
Lee et al., 2021; Nakano et al., 2021). However, there arevarious ways to incorporate human preferences or expertise
into the decision-making process of an agent. (Shahet al., 2015; Ouyang et al., 2022; Saha & Krishnamurthy,2022) learn reward from pairwise comparison and ranking.
(Pacchiano et al., 2021) study pairwise comparison withfunction approximation in pairwise comparison. (Zhu
et al., 2023) study various cases of preference-basedcomparison in contextual bandit problem with linear
function approximation, however convergence of theiralgorithm relies on the implicit assumption of sufficient
coverage. The majority of prior researches in RLHF only
consider bandit cases and have not studied MDP case withtransition dynamics. (Wang et al., 2018) study how to learna uniformly better policy of an MDP from an offline dataset
by learning the advantage function. However, they cannot
guarantee the learned policy converges to the optimal policy.

Dynamic Discrete Choice Model. Dynamic Discrete
Choice (DDC) model is a widely studied choice model ineconometrics and is closely related to reward learning in
IRL and RLHF. In the DDC model, the human agent isassumed to make decisions under the presence of Gumbel
noise (Type I Extreme Error)(Aguirregabiria & Mira, 2002;
Chernozhukov et al., 2022; Bajari et al., 2015; Kalouptsidi
et al., 2021; Adusumilli & Eckardt, 2019), i.e. underbounded rationality, and the task is to infer the underlying
utility.
Most work in econometrics cares for asymptotic√
n-convergence of estimated utility, and does not study
finite sample estimation error. Moreover, their methods
suffer from significant computation burdens from large
or high dimensional state space (Zeng et al., 2022). In
recent years, there has been work combining the dynamic
discrete choice model and IRL. (Zeng et al., 2022) provethe equivalence between DDC estimation problem andmaximum likelihood IRL problem and propose an online
gradient method for reward estimation under ergodic

dynamics assumption. (Zeng et al., 2023) reformulate
the reward estimation in the DDC model into a bilevel
optimization and propose a model-based approach byassuming an environment simulator.

Offline Reinforcement Learning and Pessimism. The
idea of introducing pessimism for offline RL to deal with
distribution shift has been studied in recent years (Jin et al.,2021; Uehara et al., 2021). (Jin et al., 2021) show that pessimism is sufficient to eliminate spurious correlation andintrinsic uncertainty when doing value iteration. (Uehara
et al., 2021) show that with single-policy coverage, i.e. coverage over the optimal policy, pessimism is sufficient toguarantee a O(n−1/2 ) suboptimality. In this paper, we connect RLHF with offline RL and show our algorithm achieves
pessimism by designing an uncertainty quantifier that cantackle error from estimating reward functions, which is crucial in pessimistic value iteration.
1.2. Notations and Preliminaries
d×d
For a positive-semidefinitematrix A
and vector√∈ Rd⊤x ∈ R , we use ∥x∥A to denote x Ax. For an arbitrary space X , we use ∆(X ) to denote the set of all probability distribution on X . For two vectors x, y ∈ Rd ,Pd
we denote x · y =i xi yi as the inner product of x, y.
We denote the set of all probability measures on X as∆(X ). We use [n] to represent the set of integers from0 to n − 1. For two matrices A and B, we write A ⪰ B
if A − B ⪰ 0. We define a finite horizon MDP modelM = (S, A, H, {Ph }h∈[H] , {rh }h∈[H] ), H is the horizon
length, in each step h ∈ [H] , the agent starts from state shin the state space S, chooses an action ah ∈ A with probability πh (ah | sh ) , receives a reward of rh (sh , ah ) and transits
to the next state s′ with probability Ph (s′ | sh , ah ). HereA is a finite action set with |A| actions and Ph (·|sh , ah ) ∈∆(sh , ah ) is the transition kernel condition on state action
pair (s, a). For convenience we assume that rh (s, a) ∈[0, 1] for all (s, a, h) ∈ S × A × [H]. Without loss of generality, we assume that the initial state of each episode s0
is fixed. Note that this will not add difficulty to our analysis. For any policy π = {πh }h∈[H] the state value function
 PH
is Vhπ (s) = Eπ
sh = s , and the act=h rt (st , at )P
Htion value function is Qπh (s, a) = Eπt=h rt (st , at )sh = s, a , here the expectation Eπ is taken with respect
to the randomness of the trajectory induced by π, i.e. is
obtained by taking action at ∼ πt (· | st ) and observing
st+1 ∼ Ph (· | st , at ). For any function f : S → R, wedefine the transition operator Ph f (s, a) = E[f (sh+1 ) |sh = s, ah = a]. We also define the Bellman equation forany policy π, Vhπ (s) = ⟨πh (a | s), Qπhb (s, a)⟩, Qπh (s, a) =πrh (s, a) + Ph Vh+1
(s, a). For an MDP we denote its opti∗
mal policy as π , and define the performance metric for any

110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164

∗

policy π as SubOpt(π) = V1π − V1π .

2. Problem Formulation
In this paper, we aim to learn from a dataset of humanchoices under dynamic discrete choice model. Suppose weare provided with dataset D = {Dh = {sih , aih }i∈[n] }h∈[H] ,containing n trajectories collected by observing a single
human behavior in a dynamic discrete choice model. Our
goal is to learn the optimal policy π ∗ of the underlying MDP.
We assume that the agent is bounded-rational and makes
decisions according to the dynamic discrete choice model(Rust, 1987; Hotz & Miller, 1993; Chernozhukov et al.,2022; Zeng et al., 2023). In dynamic discrete choice model,
the agent’s policy has the following characterization (Rust,
1987; Aguirregabiria & Mira, 2002; Chernozhukov et al.,2022),
exp(Qhπb ,γ (s, a)),πb ,γ(s, a′ ))a′ ∈A exp(Qhπb,h (a | s) = P(1)

here Qhπb ,γ (·, ·) works as the solution of the discounted
Bellman equation,
Vhπb ,γ (s) = ⟨πb,h (a | s), Qhπb ,γ (s, a)⟩,

(2)

πb ,γ
Qhπb ,γ (s, a) = rh (s, a) + γ · Ph Vh+1
(s, a)(3)for all (s, a) ∈ S × A. Note that (2) differs from theoriginal Bellman equation due to the presence of γ, which
is a discount factor in [0, 1], and measures the myopia of theagent. The case of γ = 0 corresponds to a myopic humanagent. Such choice model comes from the perturbation ofnoises,Our algorithm consists of two steps: (i) The first step is toestimate the agent behavior policy from the pre-collected
dataset D by maximum likelihood estimation (MLE). We
recover the action value functions {Qπhb ,γ }h∈[H] from (1)and the state value functions {Vhπb ,γ }h∈[H] from (2) using
function approximation. In Section 3.1, we analyze the errorof our estimation and prove that for any model class witha small covering number, the error from MLE estimation
is of scale Õ(1/n) in dataset distribution. We also remarkthat our result does not need the dataset to be well-explored,
which is implicitly assumed in previous works (Zhu et al.,2023; Chen et al., 2020). (ii) We recover the underlying
reward from the model class by minimizing a penalized
Bellman MSE with plugged-in value functions learned instep (i). In Section 3.2, we study linear model MDP asa concrete example. Theorem 3.5 shows that the error of
estimated reward can be bounded by an elliptical potential
term for all (s, a) ∈ S × A in both settings. First, we makethe following assumption for function approximation.
Assumption 3.1 (Function Approximation Model Class).
We assume the existence of a model class M ={Mh }h∈[H] containing functions f : S × A → [0, H]
for every h ∈ [H], and is rich enough to capture rh and Qh ,i.e. rh ∈ Mh , Qh ∈ Mh .
In practice, Mh can be a (pre-trained) neural network or arandom forest. We now present our algorithm for reward
learning in RLHF.

Algorithm 1 DCPPO: Reward Learning for General ModelClass
Require: Dataset Dh = {sih , aih }i∈[n] h∈[H] , constant
λ > 0, penalty function ρ(·), parameter β.
πb,h (· | sh ) = 1: for step h = H, . . . , 1 doπb ,γb h by maximizing (4).
argmaxa∈A rh (sh , a) + ϵh (a) + γ · Ph Vh+1
(sh , a) , 2: Set Q
3:
Set πbh (ah |sh ) by (5).
b h (sh , ·), π
4:Set Vbh (sh ) = ⟨Qbh (· | sh )⟩A .
where {ϵh (a)}a∈A are i.i.d Gumbel noises that is observed
5:
Set
r
b
(s
,
a
)
by
(6).
h
h
h
by the agent but not the learner, {Vhγ,πb }h∈[H] is the value
6: end forfunction of the agent, and is widely used to model human de7: Output: {brh }h∈[H] .
cision. We also remark that the state value function definedin (2) corresponds to the ex-ante value function in econometric studies (Aguirregabiria & Mira, 2010; Arcidiacono
3.1. First Step: Recovering Human Policy and Human& Ellickson, 2011; Bajari et al., 2015). When consideringState-Action Values
Gumbel noise as part of the reward, the value function may
have a different form. However, such a difference does not
For every step h, we use maximum liklihood estimaton
add complexity to our analysis.
(MLE) to estimate the behaviour policy πb,h , corresponds
to Qπhb ,γ (s, a) in a general model class Mh . For each step
3. Reward Learning from Human Dynamich ∈ [H], we have the log-likelihood function

Choicesn

In this section, we present a general framework of an offline
algorithm for learning the reward of the underlying MDP.

Lh (Q) =

1X
log
n i=1



exp(Q(sih , aih ))′a′ ∈A exp(Q(s, a ))

P


(4)

165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219

for Q ∈ Mh , and we estimate Qh by maximizing (4). Then
we recover the policy πbh byXb h (sh , ah ))/b h (sh , a′ ).
πbh (ah | sh ) = exp(Q
exp(Q
a′ ∈A

(5)
Note that by Equation (1), adding a constant on Qπhb ,γ willproduce the same policy under dynamic discrete model, andthus the real behavior value function is unidentifiable in general. For identification, we have the following assumption.
Assumption 3.2 (Model Identification). We assume that
there exists one a0 ∈ A, such that Q(s, a0 ) = 0 for everys ∈ S.
Note that this assumption does not affect our further analysis. Other identifications includes parameter constraint (Zhu
et al., 2023) or utility constraints (Bajari et al., 2015). We
can ensure the estimation of the underlying policy and corresponding value function is accurate in the states the agent
has encountered. Formally, we have the following theorem,
Theorem 3.3 (Policy and Value Functions Recovery from
Choice Model). With Algorithm 1 , we have
EDh ∥bπh (· | sh ) − πb,h (· | sh )∥21
log N (Mh , ∥ · ∥∞ , 1/n)/δ
≤Onmodel class. We define the function class Mh = {f (·) =ϕ(·)⊤ θ : S × A → R, θ ∈ Θ} for h ∈ [H], where ϕ ∈ Rd
is the feature defined on S × A, Θ is a subset of Rd whichparameterizes the model class, and d > 0 is the dimensionof the feature. Corresponding to Assumption 3.2, We also
assume that ϕ(s, a0 ) = 0 for every s ∈ S. Note that thismodel class contains the reward rh and state action valuefunction Qh in tabular MDP where ϕ(s, a) is the one-hot
vector of (s, a). The linear model class also contains linear
MDP, which assumes both the transition P (sh+1 | sh , ah )and the reward rh (sh , ah ) are linear functions of featureϕ(sh , ah ) (Jin et al., 2020; Duan et al., 2020; Jin et al.,2021). In linear model case, our first step MLE in (4) turns
into a logistic regression,
X

n
1X
i
i
i
′
b
θh = argmaxθ∈Θϕ(sh , ah )·θ−log
exp(ϕ(sh , a )·θ) ,
n i=1
a′ ∈A
(7)
which can be efficiently solved by existing state-of-art opb h }h∈[H] , {btimization methods. We now have {Qπh }h∈[H]and {Vbh }h∈[H] in Algorithm 1 to be our estimations forQπhb ,γ , πb,h and Vhπb ,γ correspondingly.
Note that in linear case, Line 5 has a closed form solution,
X

n

−1
i
i
i
i
i
b
b
w
bh = (Λh + λI)
ϕ(sh , ah ) Qh (sh , ah ) − γ · Vh+1 (sh+1 ) ,
i=1

and

(8)



b h (sh , ·) − Qπb ,γ (sh , ·)∥21
EDh ∥Qh 2 H
H · e · log N (Mh , ∥ · ∥∞ , 1/n)/δ
≤Onwith probability at least 1 − δ. Here EDh [·] means the
expectation is taken on collected dataset Dh , i.e. the meanvalue taken with respect to {sih }i∈[n] .
Theorem 3.3 shows that we can efficiently learn πb,h fromthe dataset under identification assumption. As a result, we
can provably recover the value functions by definition in
Equation 1.

where Λh =nXϕ(sih , aih )ϕ(sih , aih )⊤ ,i=1

and we set rb(sh , ah ) = ϕ(sh , ah ) · w
bh . We also make thefollowing assumption on the model class Θ and the featurefunction.
Assumption 3.4 (Regular Conditions).
We assume that: (i)√For all θ ∈ Θ, we have √∥θ∥2 ≤ d; (ii) For all (sh , ah ) ∈S × A, ∥ϕ(sh , ah )∥2 ≤ d. (iii)For all n > 0, log N (Θ, ∥ ·∥∞ , 1/n) ≤ c · d log n for some absolute constant c.
We are now prepared to highlight our main result:

Bellman equation motivates the following estimate of the
reward function:

Theorem 3.5 (Reward Estimation for Linear Model
MDP). With probability at least 1 − δ, we have the following estimation of our reward function for all (s, a) ∈ S × A
and λ > 0,rbh (sh , ah ) =|rh (s, a) − rbh (s, a)|3.2. Reward Learning from Dynamic Choices

argminr∈Mh

(6)
n
X

rh (sih , aih ) + γ · Vbh+1 (sih+1 )

i=1

(9)

≤ ∥ϕ(s, a)∥(Λh +λI)−1


q
√

·O
λ · d + (1 + γ)HeH · d log nH/δ .

b h (sih , aih ) 2 + λρ(r) ,−Qi.e. we can recover the reward with previously learnedb h by minimizing Bellman MSE. As a concrete examVbh , Q
ple, we study the instantiation of Algorithm 1 for the linear

Note that the error can be bounded by the product of two
terms, the elliptical potential term ∥ϕ(s, a)∥(Λ+λ·I)−1 andthe norm of a self normalizing term of scale O(HeH ·

220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274

p
d log(n/δ)). Here the exponential dependency O(eH )comes from estimating Qπhb ,γ with logistic regression andalso occurs in logistic bandit (Zhu et al., 2023; Fei et al.,2020). It remains an open question if this additional factor
can be improved, and we leave it for future work.

4.1. Suboptimality Gap of Pessimitic Optimal Policy
In Line (3) of Algorithm 2, we update Ph V̂h+1 by solving
the following minimization:X2
eh Veh+1 (sh , ah ) = argminPf (sih , aih )−Veh+1 (sh+1 ) .
f ∈M
i∈[n]

Remark 3.6. We remark that except for the exponential termin H, Theorem 3.5 almost matches the result when doing
linear regression on an observable reward dataset, in whichcase error of estimation is of scale Õ(∥ϕ(s, a)∥(Λ+λI)−1 ·dH) (Ding et al., 2021; Jin et al., 2021). When the humanbehavior policy has sufficient coverage, i.e. the minimal
eigenvalue of Eπb [ϕϕ⊤ ], σmin (Eπb [ϕϕ⊤ ]) ≥ 0, we have∥ϕ(s, a)∥(Λh +λI)−1 = O(n−1/2 ) holds for all (s, a) ∈ S ×
A (Duan et al., 2020) and ∥rh − rbh ∥∞ = O(n−1/2 ).

(10)
For linear model class defined in Section 3.2, we assume that
we can capture the conditional expectation of value functionin the next step with the known feature ϕ. In formal words,
we make the following assumption.
Assumption 4.1 (Linear MDP). For the underlying MDP,
we assume that for every Vh+1 : S → [0, H − h], there
exists uh ∈ Rd such that

4. Policy Learning from Dynamic Choices via
Pessimistic Value Iteration

for all (s,√a) ∈ S × A. We also assume that ∥uh ∥ ≤ (H −h + 1) · d for all h ∈ [H].

In this section, we describe the pessimistic value iteration
algorithm, which minus a penalty function Γh : S × A →R from the value function when choosing the best action. Pessimism is achieved when Γh is a uncertainty
quantifier for our learned value functions {Ṽh }h∈[H] , i.e.
eh Veh+1 (s, a) − rh + Ph Veh+1 (s, a) ≤ Γh (s, a)
rbh + P
for all (s, a) ∈ S × A with high probability. Then weuse {Γh }h∈[H] as the penalty function for pessimistic planning, which leads to a conservative estimation of the valuefunction. We formally describe our planning method in Algorithm 2. However, when doing pessimistic value iteration
with {brh }h∈[H] learned from human feedback, it is moredifficult to design uncertainty quantifiers, since the estimation error from reward learning is inherited in pessimisticplanning. In Section 4.1, we propose an efficient uncertainty
quantifier and prove that with pessimistic value iteration,
Algorithm 2 can achieve a O(n−1/2 ) suboptimality gap.

Note that this assumption is directly satisfied by linear MDPclass (Jin et al., 2021; 2020; Yang & Wang, 2019). For
linear model MDP defined in Section 3.2, it suffices to havethe parameter set Θ being closed under subtraction, i.e. if
x, y ∈ Θ then x − y ∈ Θ. Meanwhile, we construct Γh in
Algorithm 2 based on dataset D as
1/2
Γh (s, a) = β · ϕ(s, a)⊤ (Λh + λI)−1 ϕ(s, a)(11)

Algorithm 2 DCPPO: Pessimistic Value iteration
Require: Surrogate reward {brh (·, ·)}h∈[H] , collected
dataset {(sih , aih )}i∈[n],h∈[H] , parameter β, penalty .
eH+1 (·) = 0.
1: Set V
2: for step h = H, . . . , 1 do
eh Veh+1 (sh , ah ) by (10).
3:
Set P
4:
Construct Γh (sh , ah ) based on D.
e h (sh , ah )
5:
Set Q
=
min rbh (sh , ah ) +Peh Veh+1 (sh , ah ) − Γh (sh , ah ), H − h + 1 + .
e h (·, ·), πh (· | ·)⟩.
6:Set πeh (· | ·) = argmax⟨Qe h (·, ·), π̃h (· | ·)⟩.
7:
Set Veh = ⟨Q
8: end for
9: Output: {eπh }h∈[H] .

Ph Vh+1 (s, a) = ϕ(s, a) · uhfor every h ∈ [H]. Here that Λh is defined in (8). To
establish suboptimality for Algorithm 2, we assume thatthe trajectory induced by π ∗ is “covered” by D sufficiently
well.
Assumption 4.2 (Single-Policy Coverage). Suppose there
exists an absolute constant c† > 0 such thathi⊤Λh ≥ c† · n · Eπ∗ ϕ (sh , ah ) ϕ (sh , ah )holds with probability at least 1 − δ/2.
We remark that Assumption 4.2 only assumes the humanbehavior policy can cover the optimal policy and is therefore
weaker than assuming well-explored dataset, or sufficient
coverage(Duan et al., 2020; Jin et al., 2021). With thisassumption, we prove the following theorem.
Theorem 4.3 (Suboptimality Gap for DCPPO). Suppose
Assumptionq
3.2, 3.4, 4.1,4.2 holds. With λ = 1 and β =HO(He · d log nH/δ ), we have (i) Γh defined in (11)being uncertainty quantifiers, and (ii)pSubOpt {π̃h }h∈[H] ≤ c · (1 + γ)d3/2 H 2 eH n−1/2 ξholds with probability at least 1 − δ , here ξ = log(dHn/δ).
In particular, if rank(Σh ) ≤ r at each step h ∈ [H], thenpSubOpt {π̃h }h∈[H] ≤ c · (1 + γ)r1/2 dH 2 eH n−1/2 ξ,here Σh = Eπb [ϕ(sh , ah )ϕ(sh , ah )⊤ ].

275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329

Remark. It is worth highlighting that Theorem 4.3 nearlymatches the standard result for pessimistic offline RL withobservable rewards in terms of the dependence on data sizeand distribution, up to a constant factor of O(HeH ) (Jinet al., 2020; Uehara & Sun, 2021), where their suboptimality
is of Õ(dH 2 n−1/2 ). Therefore, Algorithm 1 and 2 almost
matches the suboptimality gap of standard pessimism planning with an observable reward, except for a O(eH ) factor
inherited from reward estimation.

5. DCPPO for Reproducing Kernel HilbertSpace
In this section, we assume the model class M ={Mh }h∈[H] are subsets of a Reproducing Kernel Hilbert
Space (RKHS). For notations simplicity, we let z = (s, a)denote the state-action pair and denote Z = S × A for anyh ∈ [H]. We view Z as a compact subset of Rd where thedimension d is fixed. Let H be an RKHS of functions on
Z with kernel function K : Z × Z → R, inner product⟨·, ·⟩ : H × H → R and RKHS norm ∥ · ∥H : H → R.
By definition of RKHS, there exists a feature mapping
ϕ : Z → H such that f (z) = ⟨f, ϕ(z)⟩H for all f ∈ H
and all z ∈ Z. Also, the kernel function admits the feature
representation K(x, y) = ⟨ϕ(x), ϕ(y)⟩H for any x, y ∈ H.
We assume that the kernel function is uniformly bounded assupz∈Z K(z, z) < ∞.
Let L2 (Z) be the space of square-integrable functions on Z
and let ⟨·, ·⟩L2 be the inner product for L2 (Z). We define
the Mercer operater TK : L2 (Z) → L2 (Z),Z
TK f (z) =K (z, z ′ ) · f (z ′ ) dz ′ , ∀f ∈ L2 (Z). (12)Z

By Mercer’s Theorem (Steinwart & Christmann, 2008),
there exists a countable and non-increasing sequence of
non-negative eigenvalues {σi }i≥1 for the operator TK , andthe associated eigenfunctions {ψi }i>1 form an orthogonalbasis of L2 (Z). In what follows, we assume the eigenvalueof the integral operator defined in 12 has a certain decay
condition.
Assumption 5.1 (Eigenvalue Decay of H). Let {σj }j≥1
be the eigenvalues induced by the integral opretaor TK
defined in Equation (12) and {ψj }j≥1 be the associatedeigenfunctions. We assume that {σj }j≥1 satisfies one of
the following conditions for some constant γ > 0.
(i) µ-finite spectrum: σj = 0 for all j > µ, where µ is apositive integer.
(ii) µ-exponential decay: there exists some constants
C1 , C2 > 0, τ ∈ [0, 1/2) and Cψ > 0 such that σj ≤C1 · exp (−C2 · j µ ) and supz∈Z σjτ · |ψj (z)| ≤ Cψ forall j ≥ 1.

(iii) µ-polynomial decay: there exists some constants C1 >0, τ ∈ [0, 1/2) and Cψ > 0 such that σj ≤ C1 · j −µand supz∈Z σjτ · |ψj (z)| ≤ Cψ for all j ≥ 1, whereµ > 1.
For a detailed discussion of eigenvalue decay in RKHS, werefer the readers to Section 4.1 of (Yang et al., 2020).
5.1. Gurantee for RKHSIn RKHS case, our first step MLE in (4) turns into a kernel
logistic regression,
X

n
1X
i
i
′
Q̄h = argminQ∈H
Q(sh , ah )−logexp(Q(s, a )) .
n i=1
a′ ∈A
(13)
Line 5 in Algorithm 1 now turns into a kernel ridge regression for the Bellman MSE, with ρ(f ) being ∥f ∥2H . Following Representer’s Theorem (Steinwart & Christmann, 2008),
we have the following closed form solutionrbh (z) = kh (z)⊤ (Kh + λ · I)−1 yh ,where we define the Gram matrix Kh ∈ Rn×n and thefunction kh : Z → Rn as


⊤
′ 
Kh = K zhi , zhi i,i′ ∈[n] ∈ Rn×n , kh (z) = K zhi , z i∈[n] ∈ Rn ,(14)
and the entry of the response vector yh ∈ Rn corresponding
to i ∈ [n] isb h (sih , aih ) − γ · Vbh+1 sih+1 .
[yh ]i = Q
Meanwhile, we also construct the uncertainty quantifier Γhin Algorithm 2,
1/2−1
Γh (z) = β·λ−1/2 · K(z, z)−kh (z)⊤ (Kh + λI) kh (z)for all z ∈ Z. Parallel to Assumption 4.1, we impose thefollowing structural assumption for the kernel setting.
Assumption 5.2. Let Rr > 0 be some fixed constant and
we define function class Q = {f ∈ H : ∥f ∥H ≤ HRr }.
We assume that Ph Vh+1 ∈ Q for any Vh+1 : S → [0, H].
We also assume that ∥r∥H ≤ Rr for some constant Rr > 0.
We set the model class Mh = Q for all h ∈ [H].
The above assumption states that the Bellman operator maps
any bounded function into a bounded RKHS-norm ball, andholds for the special case of linear MDP (Jin et al., 2021).
Besides the closeness assumption on the Bellman operator,
we also define the maximal information gain (Srinivas et al.,2009) as a characterization of the complexity of H :G(n, λ) = sup {1/2 · log det (I + KC /λ) : C ⊂ Z, |C| ≤ n}
(15)

330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384

Here KC is the Gram matrix for the set C, defined similarlyas Equation (14). In particular, when H has µ-finite spectrum, G(n, λ) = O(µ · log n) recovers the dimensionalityof the linear space up to a logarithmic factor.
We are now ready to present our result for reward estimationin the RKHS case.

SubOpt({π̃h }h∈[H] )

p
′ ˜
H

µ · log(nRr H/δ)}C · d · He |A| p′
H˜≤ C · d · He |A| · (log(nRr H)/δ)1+1/µ
p

∗
 ′ ˜
C · d · HeH |A| · (nRr )κ · log(nRr H/δ).

Theorem 5.3 (Reward Estimation for RKHS). For Algorithm 1 and 2, with probability at least 1 − δ, we havethe following estimations of our reward function for allz ∈ Z × A and λ ≥ 1 + 1/n,

for µ-finite spectrum, µ-exponential decay and µpolynomial decay respectively. Here C, C ′ , C ′′ are absolute
constants irrelevant to n and H andsampd˜ = dpop,
ef · def|rh (z) − rbh (z)|≤ ∥ϕ(z)∥(Λh +λIH )−1 ·

1/2

2
2
2
O H · G n, 1 + 1/n + λ · Rr + ζ,ζ = O dsampefqH · log N (Q, ∥ · ∥∞ , 1/n)/δ · HeH

here dsamp
is the sampling effective dimension.
ef
Here ∥ϕ(z)∥(Λh +λIH )−1 = ⟨ϕ(z), (Λh + λIH )−1 ϕ(z)⟩H ,where we define
Λh =

n
X

d+1
1
+
.
2(µ + d) µ(1 − 2τ ) − 1

Here dpop
ef is the population effective dimension, which measures the ”coverage” of the human behavior πb for the
optimal policy π ∗ .

where


κ∗ =

ϕ(zhi )ϕ(zhi )⊤ .

Parallel to the linear setting, Theorem 5.4 demonstrates theperformance of our method in terms of effective dimension.
If the behavior policy is close to the optimal policy and the
3/2 −1/2
RKHS satisfies Assumption 5.1, dpopn)ef = O(Hsampand def
remains in constant level. In this case, suboptimality is of order O(n−1/2 ) for µ-finite spectrum andµ-exponential decay, while for µ-polynomial decay we ob∗tain a rate of O(nκ −1/2 ), which also matches the results instandard pessimistic planning under RKHS case (Jin et al.,2021), where the reward is observable.

i=1

With the guarantee of Theorem 5.3, Theorem 5.4 establishes the concrete suboptimality of DCPPO under various
eigenvalue decay conditions.
Theorem 5.4 (Suboptimality Gap for RKHS). Supposethat Assumption 5.1 holds. For µ-polynomial decay, we
further assume µ(1 − 2τ ) > 1. For Algorithm 1 and 2, weset
µ-finite spectrum,C · µ · log(n/δ)
1+1/µλ = C · log(n/δ)µ-exponential decay,2
µ(1−2τ
)−1
C ·n· log(n/δ) µ-polynomial decay,
and

p
samp
′′
H

· µ · · log(nH/δ)C · He |A|def p
β = C ′′ · HeH |A|dsamp(log(nH/δ))1+1/µ
ef
p

∗
 ′′
samp
C · HeH |A|def · nκ · log(nH/δ)for µ-finite spectrum, µ-exponential decay and µpolynomial decay respectively. Here C > 0 is an absolute
constant that does not depend on n or H. Then withprobability at least 1 − δ, it holds that

6. Conclusion
In this paper, we have developed a provably efficient online algorithm, Dynamic-Choice-Pessimistic-PolicyOptimization (DCPPO) for RLHF under dynamic discrete
choice model. By maximizing log-likelihood function of the
Q-value function and minimizing mean squared Bellman
error for the reward, our algorithm learns the unobservablereward, and the optimal policy following the principle ofpessimism. We prove that our algorithm is efficient in sample complexity for linear model MDP and RKHS model
class.

References
Adusumilli, K. and Eckardt, D. Temporal-difference estimation of dynamic discrete choice models. arXiv preprint
arXiv:1912.09509, 2019.
Aguirregabiria, V. and Mira, P. Swapping the nested fixed
point algorithm: A class of estimators for discrete markov
decision models. Econometrica, 70(4):1519–1543, 2002.
Aguirregabiria, V. and Mira, P. Dynamic discrete choice
structural models: A survey. Journal of Econometrics,
156(1):38–67, 2010.

385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439

Arcidiacono, P. and Ellickson, P. B. Practical methods for
estimation of dynamic discrete choice models. Annu. Rev.
Econ., 3(1):363–394, 2011.
Bajari, P., Chernozhukov, V., Hong, H., and Nekipelov, D.
Identification and efficient semiparametric estimation ofa dynamic discrete game. Technical report, National
Bureau of Economic Research, 2015.
Chen, X., Wang, Y., and Zhou, Y. Dynamic assortment
optimization with changing contextual information. The
Journal of Machine Learning Research, 21(1):8918–8961,
2020.
Chernozhukov, V., Escanciano, J. C., Ichimura, H., Newey,
W. K., and Robins, J. M. Locally robust semiparametricestimation. Econometrica, 90(4):1501–1535, 2022.
Ding, D., Wei, X., Yang, Z., Wang, Z., and Jovanovic, M.
Provably efficient safe exploration via primal-dual policy
optimization. In International Conference on Artificial
Intelligence and Statistics, pp. 3304–3312. PMLR, 2021.

Jaques, N., Shen, J. H., Ghandeharioun, A., Ferguson, C.,
Lapedriza, A., Jones, N., Gu, S. S., and Picard, R. Humancentric dialog training via offline reinforcement learning.
arXiv preprint arXiv:2010.05848, 2020.
Jin, C., Yang, Z., Wang, Z., and Jordan, M. I. Provably
efficient reinforcement learning with linear function approximation. In Conference on Learning Theory, pp.
2137–2143. PMLR, 2020.
Jin, Y., Yang, Z., and Wang, Z. Is pessimism provably
efficient for offline rl? In International Conference on
Machine Learning, pp. 5084–5096. PMLR, 2021.
Kalouptsidi, M., Scott, P. T., and Souza-Rodrigues, E. Linear iv regression estimators for structural dynamic discrete choice models. Journal of Econometrics, 222(1):778–804, 2021.
Kupcsik, A., Hsu, D., and Lee, W. S. Learning dynamic
robot-to-human object handover from human feedback.
Robotics Research: Volume 1, pp. 161–176, 2018.

Duan, Y., Jia, Z., and Wang, M. Minimax-optimal offpolicy evaluation with linear function approximation. In
International Conference on Machine Learning, pp. 2701–
2709. PMLR, 2020.

Lee, K., Smith, L., and Abbeel, P. Pebble: Feedbackefficient interactive reinforcement learning via relabelingexperience and unsupervised pre-training. arXiv preprint
arXiv:2106.05091, 2021.

Fei, Y., Yang, Z., Chen, Y., Wang, Z., and Xie, Q. Risksensitive reinforcement learning: Near-optimal risksample tradeoff in regret. Advances in Neural Information
Processing Systems, 33:22384–22395, 2020.

Lindner, D., Tschiatschek, S., Hofmann, K., and Krause,
A. Interactively learning preference constraints in linear
bandits, 2022.

Gao, L., Schulman, J., and Hilton, J. Scaling laws for reward
model overoptimization, 2022.
Glaese, A., McAleese, N., Trebacz, M., Aslanides, J., Firoiu,
V., Ewalds, T., Rauh, M., Weidinger, L., Chadwick, M.,
Thacker, P., et al. Improving alignment of dialogue
agents via targeted human judgements. arXiv preprint
arXiv:2209.14375, 2022.
Hotz, V. J. and Miller, R. A. Conditional choice probabilities
and the estimation of dynamic models. The Review of
Economic Studies, 60(3):497–529, 1993.
Hotz, V. J., Miller, R. A., Sanders, S., and Smith, J. A simulation estimator for dynamic models of discrete choice.
The Review of Economic Studies, 61(2):265–289, 1994.
Hussein, A., Gaber, M. M., Elyan, E., and Jayne, C. Imitation learning: A survey of learning methods. ACM
Computing Surveys (CSUR), 50(2):1–35, 2017.
Jain, A., Wojcik, B., Joachims, T., and Saxena, A. Learning
trajectory preferences for manipulators via iterative improvement. Advances in neural information processing
systems, 26, 2013.

Menick, J., Trebacz, M., Mikulik, V., Aslanides, J., Song,F., Chadwick, M., Glaese, M., Young, S., CampbellGillingham, L., Irving, G., et al. Teaching language
models to support answers with verified quotes. arXiv
preprint arXiv:2203.11147, 2022.
Nakano, R., Hilton, J., Balaji, S., Wu, J., Ouyang, L., Kim,
C., Hesse, C., Jain, S., Kosaraju, V., Saunders, W., et al.
Webgpt: Browser-assisted question-answering with human feedback. arXiv preprint arXiv:2112.09332, 2021.
Novoseller, E., Wei, Y., Sui, Y., Yue, Y., and Burdick, J.
Dueling posterior sampling for preference-based reinforcement learning. In Conference on Uncertainty in
Artificial Intelligence, pp. 1029–1038. PMLR, 2020.
Ouyang, L., Wu, J., Jiang, X., Almeida, D., Wainwright, C.,
Mishkin, P., Zhang, C., Agarwal, S., Slama, K., Ray, A.,et al. Training language models to follow instructions
with human feedback. Advances in Neural Information
Processing Systems, 35:27730–27744, 2022.
Pacchiano, A., Saha, A., and Lee, J. Dueling rl: reinforcement learning with trajectory preferences. arXiv preprint
arXiv:2111.04850, 2021.

440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494

Rust, J. Optimal replacement of gmc bus engines: An empirical model of harold zurcher. Econometrica: Journalof the Econometric Society, pp. 999–1033, 1987.
Saha, A. and Krishnamurthy, A. Efficient and optimal algorithms for contextual dueling bandits under realizability.
In International Conference on Algorithmic Learning
Theory, pp. 968–994. PMLR, 2022.
Shah, N., Balakrishnan, S., Bradley, J., Parekh, A., Ramchandran, K., and Wainwright, M. Estimation from pairwise comparisons: Sharp minimax bounds with topology
dependence. In Artificial intelligence and statistics, pp.
856–865. PMLR, 2015.
Srinivas, N., Krause, A., Kakade, S. M., and Seeger,
M. Gaussian process optimization in the bandit setting: No regret and experimental design. arXiv preprint
arXiv:0912.3995, 2009.
Steinwart, I. and Christmann, A. Support vector machines.
In Information Science and Statistics, 2008.
Uehara, M. and Sun, W. Pessimistic model-based offline
reinforcement learning under partial coverage. arXiv
preprint arXiv:2107.06226, 2021.
Uehara, M., Zhang, X., and Sun, W. Representation learningfor online and offline rl in low-rank mdps. arXiv preprint
arXiv:2110.04652, 2021.
Wang, Q., Xiong, J., Han, L., Liu, H., Zhang, T., et al.
Exponentially weighted imitation learning for batchedhistorical data. Advances in Neural Information Processing Systems, 31, 2018.
Yang, L. F. and Wang, M. Sample-optimal parametric qlearning using linearly additive features, 2019.
Yang, Z., Jin, C., Wang, Z., Wang, M., and Jordan, M.
Provably efficient reinforcement learning with kernel andneural function approximations. Advances in Neural
Information Processing Systems, 33:13903–13916, 2020.
Zeng, S., Hong, M., and Garcia, A. Structural estimationof markov decision processes in high-dimensional state
space with finite-time guarantees, 2022.
Zeng, S., Li, C., Garcia, A., and Hong, M. Understanding
expertise through demonstrations: A maximum likelihood framework for offline inverse reinforcement learning, 2023.
Zhu, B., Jiao, J., and Jordan, M. I. Principled reinforcement
learning with human feedback from pairwise or k-wisecomparisons, 2023.