A Theoretical Framework for Partially-Observed Reward States in RLHF
Authors: Chinmaya Kausik
Mirco Mutti
Aldo Pacchiano
Ambuj Tewari
Venue: ICLR 2025 Poster (2025)
Keywords: reinforcement learning
learning theory
reinforcement learning theory
reinforcement learning from human feedback
eluder dimension
partial observability
Primary area: reinforcement learning
TL;DR: We provide a novel general theoretical framework for RLHF that also subsumes other RL problems, provide algorithms with cardinal regret/sample complexity guarantees and a novel reduction from dueling to cardinal regret methods

Abstract: The growing deployment of reinforcement learning from human feedback (RLHF) calls for a deeper theoretical investigation of its underlying models. The prevalent models of RLHF do not account for neuroscience-backed, partially-observed "internal states'' that can affect human feedback, nor do they accommodate intermediate feedback during an interaction. Both of these can be instrumental in speeding up learning and improving alignment. To address these limitations, we model RLHF as reinforcement learning with partially observed reward-states (PORRL). We accommodate two kinds of feedback &mdash; cardinal and dueling feedback. We first demonstrate that PORRL subsumes a wide class of RL problems, including traditional RL, RLHF, and reward machines. For cardinal feedback, we present two model-based methods (POR-UCRL, POR-UCBVI). We give both cardinal regret and sample complexity guarantees for the methods, showing that they improve over naive history-summarization. We then discuss the benefits of a model-free method like GOLF with naive history-summarization in settings with recursive internal states and dense intermediate feedback. For this purpose, we define a new history aware version of the Bellman-eluder dimension and give a new guarantee for GOLF in our setting, which can be exponentially sharper in illustrative examples. For dueling feedback, we show that a naive reduction to cardinal feedback fails to achieve sublinear dueling regret. We then present the first explicit reduction that converts guarantees for cardinal regret to dueling regret. In both feedback settings, we show that our models and guarantees generalize and extend existing ones.

Published as a conference paper at ICLR 2025
A THEORETICAL FRAMEWORK FOR PARTIALLY- OBSERVED REWARD STATES IN RLHF
Chinmaya Kausik
Mirco Mutti
University of Michigan
Techmion
ckausi kêumí ch. edu
mi r wwt.:/mttecciiin...mmmm ac. i1
Aldo Pacchiand
Ambuj Tewari University of Michigan
Boston University
Broad Insitute of MIT & Harvard pacchi an@bu. edu
tewaria@uss umi edu
ABSTRACT
The growing deployment of reinforcement learning from human feedback (RLHF) calls for a deeper theoretical investigation of its underlying models. The prevalent models of RLHF do not account for neuroscience-backed. partially-observed "inter- nal states" that can affect human feedback, nor do they accommodate intermediate feedback during an interaction. Both of these can be instrumental in speeding up learning and improving aligmment. To address these limitations, we model RLHF as reinforcement learning with partially observed reward-states (PORRL). We accommodate two kinds of feedback cardinal and dueling feedback. We first demonstrate that PORRL subsumes a wide class of RL problems, including traditional RL, RLHF, and reward machines. For cardinal feedback, model-based methods -CCL, POR-UCBVIL VI). We give both cardinal regret and sample complexity guarantees for the methods, showing that they improve over naive distory-summarization We then discuss the benefits of a model-free method like GOLF with naive history-summarizztioon in settings with recursive internal states and dense intermediate feedback. For this purpose, we define a new history aware version the Bellman-elude dimension and give a new guarantee for GOLF in our setting, which can be exponentially sharper in illustrative examples. For dueling feedback, we show that a naive reduction to cardinal feedback fails to achieve sublinear dueling regret. We then present the first explicit reduction that converts guarantees for cardinal regret to dueling regret. In both feedback settings, we show that our models and guarantees generalize and extend existing ones.
present two
INTRODUCTION
As automated systems become more ubiquitous, the need understand how align their objectives with the needs of humans that interact with them has become increasingly important (Ji et al., (023). The development and study of reinforcement learning from human feedback (RLHF) has been an important way of formalizing these problems and design methods for aligmment (Wirth et al., (017)) RLHF is concerned with the study of how to find a policy that maximizes an objective defined in terms of human labeled data in an RI domain (Christiano et al. 2017).
Many RLHF methods entail learning a reward function from human data, and then using the learned reward function
input to traditional reinforcement learning algorithm such as PPO (Schulman ct al., 2017). These reward-based RLHF methods have been pivotal in the development of several technologies such as robotics (Brown et al. 2019 Shin al. 2023), recommender systems (Xue
eet al. 2022), and the training of large language models (LLMs) (Ouyang et al. 2022).
It is important to emphasize that reward- based RLHF is not limited to preferential feedback. In fact, there exist two dominant kinds of feedback, namely cardinal and dueling feedback. Cardinal feedback requires the human labeler to provide single label over entire trajectory of interaction between the agent and the environment. Dueling feedback requires the human to specify preference between two trajectories. In practice, cardinal feedback has been used for LLM alignment algorithms
$ Joint senior authorship.

---

Published as a conference paper at ICLR 2025
like KTO (Ethayarajh et al. 2024), while ducling feedback has been used in algorithms like DPO (Rafailov et al. 2023) and PPO-RLH RF (Ouyang et al. 2022). Past theoretical work (Chatterji et al.)
2021hWang et a 2023b] Saha et al. 2023) has designed algorithms for both cardinal and dueling feedback under various metrics standard/cardinal regret, sample complexity or dueling regret.
We observe that current models of reward- -ased RLHF assume very specific model of non- Markovian rewards. Modeling rewards as non-Markovian is natural, since human responses to stimuli known be affected by partially-observed and evolving "internal states" (Flavell al.) (022). For example, when a human reads piece of text (possibly generated by an LLM), their assessment may oscillate between opposing sentiments in different parts of the text. Unfortunately, current models do not explicitly incorporate such "internal states" that affect rewards, and are limited to specific linear model of rewards. While one can incorporate internal states using naive
i.e. by treating the entire trajectory 7 [A]] so far as the state, we show below that better general algorithms can be designed with improved guarantees.
Additionally, current models assume that feedback is received only once at the end of an episode or pair of episodes. In many applications such as robot motion (Lee et al., 2021) and mathematical reasoning (Uesato et al., 2022), correctly incorporating intermediate or "snippet-level" feedback can speed up learning as well as improve alignment. With this in mind, we ask the following questions:
How do we generalize the RLHF setting to incorporate internal states and intermediate feedback? here?
What algorithum and guarantees can improve over naive
Contributions:
Introducing PORRL:
In Section 2 we introduce PORRL, which generalizes current RLHF models to incorporate "internal states" and intermediate feedback.
(model-based algorithms): In Section 3.1 we design model-based optimistic algorithms that, POR-UCRL and POR-UCBVI, achieving re- gret (ppoly H, S, A) + pydrde) /T) and a sample complexity of ((poly(( H, S, A)/=² + p² dddgc/=²)) under minimal assumptions/ The poly( H, S, term would be (SA))(1)) under naive suntar--summaizzaiiinn We show that guarantees subsume and improve over past results. Leveraging recursive structure on internal states (model-free algorithms): In Section 3.2 we study the model-free algorithm GOLF, applied using history distory-summarizationn We define a new "history-aware" notion of dimension, dHABE and show that GOLF has regret ÖpH /dHABEdd We show using an example that when internal states have a recursive structure, our guarantee can be exponentially smaller than existing guarantees and guarantees for our model-based methods.
Improving over naive history-summarizuue
Reduction from Dueling to Cardinal PORRL: In section we show that naive blackbox reduction from dueling to cardinal PORRI always fails. We design a whitebox reduction from dueling PORRL a large class of optimistic algorithms for cardinal PORRL. To the best of our knowledge, this is the first explicit reduction from cardinal to dueling regret guarantees for MDPs. Practical Implications: While the aim of our work is largely theoretical, we extract practical insights from our results throughout the text. These are summarized in section
1.1 RELATED WORK
RLHE. RL with human preferences has long history (Akrour et al., 2012. Busa-Fekete & Hüllermeier 2014, Sadigh et al., (017). It has been successfully used in disparate domains such as robotics, games, and LLMs. The problem of learning from cardinal feedback has been theoretically studied in (Efroni et al. 2021; Chatterji et al. 202T). Theoretical guarantees for utility-based preferential (dueling) feedback can be found in (Novoseller et al. 2020 Saha et al., 20023] Chen et al.,
2022b Zhan et al. 2023). The non-Markovian nature of the optimal policy under these RLHF models contributes greatly to why the problem is harder than traditional RI..
Internal states and intermediate feedback. There is evidence in neuroscience research indicating that human responses to stimuli are affected by "internal states" partially hidden variables that profoundly shape perception, cognition, and action" (see (see Flavell et al. 2022). Despite not explicitly
'Eg is a relevant eluder dimension and de is a relevant covering dimension. We are working under general cimctioonapproximmatin for the reward model. It is straightforward to also add general function-approximation for the transition model, abstracting out the S, A dependence. See remark and Appendix
2

---

Published as a conference paper at ICLR 2025
agent
41
d1
dx
Cardinal Feedbuuck
trajectory
human
feedback
agent
(1)
dg X4
trajectory Ti
human
Dueling
Feedback
agent
$1
41
trajectory F>
human
fredback
Figure I: Illustrating how human's 's internal states (represented by emojis) affect their feedback to an agent or LLM. Top: Cardinal or good/bad feedback. Bottom: Dueling or preferential feedback. In line with Definition Up E il are represented by the emojis, p = 2 and Hp {2, 4 in both cases.
recognizing the phenomenon of human internal states, several works in RLHF incorporate richer forms of feedback. For example, WW et al. (2023) consider human labeling over sub-sections of the text. In work on process supervision (Uesato et al., [2222] Lightman et al. 2023). humans give feedback on intermediate steps. Our work aims lay out the groundwork for theoretical treatment of internal human states and intermediate feedback in RLHF, using partially observed reward-states.
Partial observability in RL. Although learning in POMDPS
(Aström 1965 is statistically
intractable in general (Krishnamurthy al. 2016 Jin al. 2020),
flurry of recent works have
studied POMDPS under various assumptions (Du et al. 2019 Liu et al. 2022a b Golowich et al.
2022
Zhan et al., 2022 Cai al. 2022, Chen et al., 2022a| 2023 Wang et al. 2023a| Zhong et al.)
2023
Our model is distinct from POMDPs since it does not require the latent state evolution to be
Markovian, but assumes Markovian transitions for observed states. See Section 2.3 for discussion.
2 DEFINING RL WITH PARTIALLY-
REWARD STATES (PORRL)
In this paper, we consider an episodic reinforcement learning setting in which a learner interacts with an MDP having state space S, action space A, transitions dynamics P. and episode length H. At each time-step E [H] of an episode, the learner observes the state 8,, and takes an action Os. P In a typical RLHF setting, the learner observes a human feedback oн E O at the end of the episode, which associated but potentially different from a reward now describe how internal states and intermediate feedback shall be incorporated in the latter RLHF framework through guiding example, and we use this to formally introduce the PORMDP model.
generating trajectory т (S1, ($1, a1. SH 0.) E I, where I denotes the space of trajectories
r IR encoding the task. We
2.1 PORMDPS
Let us consider the example of human interacting with language model, in Figure I Here, an action is a token, the state is the text so far, and the reward is some score representing the human's satisfaction, which induces stochastic feedback. The internal states could be the human's 's emotional reaction to the text (e.g., happy, frustrated, or amused), or numbers in [0, 1] encoding a confidence level that the text progressing towards a coherent response. While an agent goes through sequence of states and actions, the system (i.c., the human) progresses through internal states, which inevitably affect, together with agent's 's actions and the state of the process, the human's satisfaction.
Formally, this can be modeled by introducing internal states u E 2 and defining the set of underlying histories _ that incorporate internal states by r% == {-"[h 1] = {((s) 4, a))/== st E S, ar E A, u4 E 24) We model the dynamics of internal states by saying that there exists an internal state generator w/ 11 S A A(U) so that the human's 's internal state un sampled from the distribution defined by wa(T" [T 17, Sh, an). The human's 's satisfaction at time h should then be a function of the current state and action, but also the current internal state, given by rh, (Sh, Wh, ox).
The agent does observe the reward rı directly, but feedback on depending rh- Typically, On will be (0. 1} feedback reflecting whether the human says that they are satisfied or not. In general, this
We will further denote r[h] (#1, .......8... an) the sub-trajectory of of length h and T3 the corre- sponding space of sub-trajectories of length h.
3

---

Published as a conference paper at ICLR 2025
could be stochastic. For instance, this could be (rr() for some function dh So. on en (Ti.) for some distribution e, (Mn). This leads to the general definition below, where we have introduced new objects U, Hp. w, not seen in traditional RL:
Definition 1. A PORMDP M with cardinal feedback is tuple (S, Hp. T, w. e), where:
S.A are fully observable states and actions, U are unobserved internal reward-states, O is a space of feedback, P([ s, s,a) is Markovian transition matrix, 81 E S is initial state
Hp [M] is set of timesteps where reward and feedback is obtained with size (Hpl = p.
: fTA so that Th : S x 1 x A - IR are reward functions at time h.
w := kEW, so that wh: 11 x S x A - A are internal state generators that map underlying histories of (s, a, u) tuples to distributions over U.
e := heH are feedback finctions so that the feedback on (A(r)) is sampled from an ?h m-suugaausian distribution en with mean (Tk) for some activation function σn IR - R
In some relevant RLHF applications, the human is presented with two trajectories and they pro- vide feedback based on the pair. In most cases, this involves indicating a 0-1 preference between trajectories. To accommodate this setting, we extend the framework to dueling feedback.
PORMDP M with dueling feedback is tuple (S A,U, O, P, Hp. r; w,e),, where everything is identical to [ except that every episode now involves running two trajectories T2 that produce rewards 1, Th,2 wh E Hp. and feedback is distributed as o₁2 ~ en (Th,1 2h22).
Definition 2.
We note that PORMDPs subsume and model a wide class of RL settings, including RLHF A brief list of settings that PORMDPs subsume is follows: (i) traditional MDPs, by setting '4 {+); (ii)
existing linear models of RLHF, setting 21 (Ø(T) w) for a known feature map 6 and unknown w (Chatterji al. 2021 Efroni et al.) 2021 Saha et al. 2023 Wang et al. 2023b); (iii) learning reward models with stochastic feedback by setting U/ to be the set of reward states (Icarte et al. 2019 2018
2022 Icarte 2022). By using 14 to model implicit intentions, PORMDPS can also model learning from the following feedback: (iv) process supervision (Lightman el al. 2023; Uesato et all 2022), (v)
fine-grained feedback (Wu al.] 2023) and (vi) snippet-level feedback (Lee et al. 202 Further, one can show that in all these settings, we can define the U generators wv to be deterministic.
One illustrative hard example of PORRL is that of combination lock JockFwhich we will also use later in the paper. Consider an H -igit numerical lock with set A of options at each digit. Let the true combination be ai ...... azz - An agent tries to unlock it by listening for "clicks" while rotating the dial at each digit h. Naturally, we only hear clicks at digit h if the entire combination so far is correct. We thus model this as PORMDP with non-Markovian rewards, S = (+), 2 = (U, A and the appropriate dynamics. Arguing that the click might sometimes be too faint, we consider stochastic rewards. Specifically, we model this as TA (5h, uh, an) = Ber(glle;.... (ux)) for some uncertainty parameter q. Notice that the internal states have recursive structure here, and they evolve in Markovian way. This is a toy model for the problem of learning to take desirable sequences of actions using intermediate feedback. It can be viewed simplified version of many such tasks navigating mazes, writing structured essays with guidance, writing proof with feedback on correctness.
2.2 REINFORCEMENT LEARNING IN PORMDPS WITH CARDINAL AND DUELING FEEDBACK
Due to the complex nature of observability in our problem, we will use this subsection to carefully set up a meaningful set of RL problems, in which an agent interacts with PORMDP to optimize a policy. At each step h, the agent observes a history T 1] E - and takes an action an ~ T(T - 1], sn). The agent does not observe the reward rh, but receives an observation o₁ ex(r)).
Defining the learning objective. Since rewards are partially observed and dependent on the entire history, there is subtlety in defining value functions. We first choose and fix some subclass II of history-dependent policies and we define the total expected reward of a policy E II as
(M, == E,a.pw.r ΣnEN, (ih uh, an)
'Recall that choosing formal state to
a placeholder initial state is not restrictive.
"This subsumes and generalizes the example of Bernoulli foedhack RLHF. SThis is variant of a common example used to generate lower hounds in POMDPs (Krishnamurthy al.
2016 Umn et al. 2020). In contrast, we will it illustrate the power of upper bounds.
4

---

Published as a conference paper at ICLR 2025
Vu (M, T) is taking an expectation over the dynamics of underlying trajectories 7" [(s,, un an)) h=1 ~ pm... Since the states u are never revealed. these dynamics can never be learnt, making Vi hard to directly deal with. In this light, we introduce stochastic functions 9h П₁ A(U) that marginalize the internal state generator wh over the sequence u1, 14-1- That is, given an (s, a) history r[h], can define (%. MM / |TMb] Now define
(M, अ) Pp EnEN, Lan-gg (Tih)//TT Un, an)l
Vg (M, Tt) is much more tractable object, where the outer expectation is taken over the dynamics of the observed trajectories т. The following result establishes that as one would hope, V = Vg.
Lemma 1 (Replacing w with g). For any history- policy π that selects an action an TTT[h- 86,) (M,,M, .) Vg (M, x) holds for any M.
For the purposes of value functions, M is fully specified by (S,, O.P, 7. e). Henceforth replace w with and denote V (M, π) by V(M, T). The optimal policy is π. := arg max V(M, T).
Cardinal PORRL. Consider algorithm producing sequence of policies *....., Tr 11, where Te is chosen only using trajectories (ri)/=] generated by {m:)== We measure the performance of such algorithm by its cardinal regret under model M.:
T
Regret Σ V(M., m.) V(M.,
t=1
One can also ask for the sample complexity of learning good policy. Given a randomized algorithm that completes N episodes of interaction and outputs TN. the sample complexity N(,,, 5) of the algorithm is the minimum N so that V(M., n.) - V(M,, nx) & e with probability at least 1 - 8 over the randomness of the feedback and the algorithm. makes sense to study cardinal regret and sample complexity in two RLHF settings:
Using learnt reward model: In most deployments of offline RLHF, an offline dataset of dueling feedback from humans is typically used to create cardinal feedback oracle (a reward model), which is then used to train the policy using RL. In fact, (Anoyymous) (2024) do exactly this under model. The sample complexity of the algorithm is important in this setting.
Improving a deployed model with batched feedback: One can learn from batches of interaction with humans and hope to improve the model/policy adaptively over multiple batches. This compatible with deploying LLMs or recommender systems to users, collecting a batch of good/bad feedback, and then tine-tuning the model offline using this batch. This approach is also discussed in (Swamy) et al. 2024 Dong et al. 2024). Regret is better metric than sample complexity here, since we want users to be satisfied (exploiting) while improving the model (exploring). Instead good/bad feedback, we can also ask for dueling feedback against fixed mo and treat it as cardinal feedback
Dueling PORRL. In ducling PORRL, we play a duel by running two policies (T1, R2) x II in parallel to obtain trajectories (TI, 72) and receive feedback {o,] Again, note that the rewards of the policies are not observed. While the definitions of V(M, .τ) and v. are the same as before, we define a new measure of regret accordingly. If we play T duels (TT,1 T2,1)...., (T.,..,,,,,,,,,, T2,r) according to an algorithm, we aim to minimize the dueling regret given by
(T1,2,
Regret (T) = Σ V(M., m.) V(M,, (1.) + V(M,, T2,1)
T
2
makes sense consider this metric when improving a deployed model with batched ducling feedback. We can do the same batching as the batched feedback example above, but instead compare our model/policy स, to fixed base policy Wo and ask for dueling feedback. The induced feedback can be treated as cardinal feedback. This is similar to the ideas in Wang et al. (2023b). who consider this setting and give cardinal regret/sample complexity guarantees. However, when deploying a model, we typically want humans to be satisfied with both the options they are given. Cardinal regret only accounts for one of the options being good. Dueling regret demands that both policies used are good.
*More technically, define ()(TT[]) to be the regular conditional distribution of the random variable wa [[T[A- - 1]. u1,... uh-1), Sh, aa.) conditioned on r[A].
(h,.).uh-1).
'If the activation function is ippschitz and monotone, then we can get cardinal regret guarantees for this problem by using the difference function class.
5

---

Published as a conference paper at ICLR 2025
Remark 1. PORRL subsumes the settings of (Saha et al. 2023 Chatterji et al. 2021 which in turn
subsume the feedback models of RLHF (Wang et al. 2023b). Crucially, Wang et al. [202bb] |023b]/hatterii Chatterii et al. 2021) measure performance using only sample complexity cardinal regret, while (Saha et al.
2023
only study dueling regret. We have discussed above why both metrics are important.
2.3
GENERAL YET TRACTABLE CASE
The nature of the feedback in PORMDPs, which depends reward that is function of the entire history, signals that PORRI. may be intractable in general. We now instantiate the model into a statistically tractable sub-class that still subsumes most existing work on RLHF and all the examples provided at the end of Section 2. Specifically, we assume that the internal reward-state functions Oh are deterministic and the feedback is emitted according reward. We will work under this assumption in the remainder of the paper.
Bernoulli distribution depending on the
Assumption 1. We work in realizable setting. That is, the unknown transition kernel P lies in known class P. and the unknown reward function rh S x U x A - R lies in known class Rs with |ral & B for all h. Assume that yh. is deterministid (but unknown) and belongs to known class of "decoder functions" Gh. Let O {0, 13 and let EΛ only depend on the rewards. For dueling feedback, let en 1 Th.2) be 77 -ssbaauussiin with unknown mean T (Ti, - -22,)). Also assume that oh and 0% are Lipschitz with unknown Lipschitz constants Ki,h and K2gh respectively. Call the resulting class of PORMDPs M.
We also define function class induced by Rr and Gn.
Definition 3. Let us then consider the decoder-induced function classes Fn given by
fx(T[(]) = (s (T(h - -]), an), Vr FA = fn I'm - RR 3gh E Gh,, TA E Rs s.t.
Also define F == Thee, Fs so that f (fn)NEH, E F. A model M is then fully determined by
(P, we denote fi) = V(M, π). Note that ((P,, Erep [nen, [T(]I]]]
Remark 2. We note that all examples from Section 2.1 satisfy Assumption |
Giving statistically efficient algorithms for this framework comes with numerous challenges:
Traditional RL incurs linear regret: We show in Lemma 3 that any method returning possibly time-dependent but memoryless policy can incur linear regret.
POMDP results do not apply: PORMDPs cannot be viewed as subease of POMDPs with latent states S x 24 since s, u1 a - s', u' is not Markovian Even if we considered the subclass of PORMDPS where 8, u, a 8', u' is Markovian, which would be subelass of reward machines, this is a specific kind of overcomplete POMDP.. Literature on overcomplete POMDPS is much more scarce than their undercomplete counterpart. The only paper that gives guarantees for overcomplete POMDPS to our knowledge is (Liu et al. 2022a). where they assume that the reward function fully observable and only depends on observed states. This cannot apply to our setting, since our rewards have to be partially observable, and fundamentally depend on latent states too.
Also, this is not a minor difference, since the number of latent states can be (SA))(()) Naive somoory-uummaiitiiio is inefficient: It overkill to use naive history- sumtaai-uumaaiization where one treats the history r[h] as the state s, and executes traditional RL. This is because while policies are non-Markovinn, state transitions are Markovian. It is unclear if we can leverage this structure without running into explicit exponential dependence on H. Moreover, most work on MDPs works with known rewards, but not knowing the rewards is a truly non-trivial problem here, since exploring the reward at each latent state could take (S)))(1)))) steps.
Ensuring satisfactory utilization of additional structure: Examples like the combination lock signal that there are intuitive ways to leverage a recursive structure on the internal states. In the combination lock, one should wait for the "click" at each digit before moving onto the next digit, giving us a polynomial dependence on A, H in sample complexity. is unclear if general algorithms for PORRL can implicitly leverage such structure to achieve polynomial guarantees.
We make this assumption for simplicity of exposition, it not necessary. As long as fn is T) subgaussian conditioned on r[A]. all our theory follows verbatim irrespective of whether is deterministic or stochastic. Since observed state transitions Markovian, PORMDPS also not more general than POMDPs.

---

Published as a conference paper at ICLR 2025
3
OPTIMISTIC ALGORITHMS FOR CARDINAL PORRL
3.1
IMPROVING OVER NAIVE
WITH MODEL-BASED METHODS
We present optimistic methods that leverage Markovian transitions in PORMDPS POR-UCRL and POR-UCBVI The methods explicitly learn both the unknown reward model and the unknown transition model, while still accounting for the Markovian nature of transitions. We describe them below and provide formal versions in Appendix D
POR-UCRL: At each timestep t. we maintain least squares estimate ft+t1 of f and an MLE estimate P; and define confidence sets Cj that consider all fr. with a small mean squared error against ft+1 such that (5) = _ C2 (6). The probability transition confidence sets C%(5) (6) are the same as UCRL (Jaksch et 2010). At timestep t. following confidence- set optimism. we play an optimistic policy Te that maximizes its highest value (MM, πT) over all models M E C* x Cp. POR-UCBVI: It is trickier to adapt ideas from UCBVI (Azar et al.) 2017). Yet again, we maintain a least squares estimate fcr and MLE estimate P., Instead of confidence sets, we define jejjectorr-deenneeet bonuses for F as (T == L max ff,, [r(]] f% (T[h)) We use these to define policy-level bonuses for F as (F, I,, 6) := E (T, 5)]. Then, the standard UCBVI bonuses provide policy-level bonuses for P. At timestep t, following bonus- based optimism, we play an optimistic policy #. that maximizes its bonus-boosted value under fr, Pr. POR-UCBVI bonuses are in fact computable for many and F, such as those in remark
We show that POR-UCRL enjoys the guarantee below.
Theorem 1 (POR-UCRL Regret). Under Assumption bounded by the following with probability at least
7 the regret Regret(T) of POR-UCRL is
δ ((pSV HA EnER, /dg,dC.A) VT)
where d dimg (Fr, 4) and dc,, (o,, (1x)))
Here, the first term comes from uncertainty in P. Under naive history- sunrairsuumaaizztinnnn the first term would be exponential in H since the modified state space of trajectories would have size (S (SA)") "). Similar regret guarantees are given for POR-UCBVI in Theorem X Both guarantees are proved by viewing each algorithm as specific instance of a generic optimistic algorithm for PORRI (see Appendix
D
E) By a simple regret-to-PAC conversion, we also show that POR-UCRL has sample p² H
complexity of O
p² p'dgde) where dE maxKEH, dr and de maxkeH, dc,.-
POR-UCBVI has sample complexity δ H max(H + pFdg max(de, H) log( 1/6)
There are three main technical challenges in proving these guarantees. First, we have to handle non-Markovian reward functions with Markovian transitions. Second, in POR-UCBVI, we have the added challenge of ensuring that the bonus is uniformly optimistic over all history-dependent policies. This is typically a doubly exponential set (A(SA))) ), so union bound does not help us. Third, we are working with general function approximation for reward functions using F.
Challenges:
Remark 3 (Comparison to past results). Notice that with 24 = ((r) w with w e Rd and Hp = { ;H). are in the setting of (Chatterji al. 2021). Here, dæ dc,H d, so POR-UCRL and POR- UCBVI both improve over their regret guarantees. With respect to sample complexity guarantees, we compare (Wang al. (0226)). While they use dueling feedback, our methods use cardinal feedback. In their setting, 21 is the set of all histories and Hp = {H). Their best guarantee is from P-OMLE, which makes δ 5²2 + Hdd dueling oracle queries for tabular P. Both POR-UCRL and -UBVIC have smaller complexity for cardinal feedback queries.
z²
Remark 4 (General function approximation for P). For clearer exposition. have assumed that P a tabular class with finite S, A in the results stated above. This is because handling general function approximation for F is the non-trivial part of this work. We provide straightforward extensions to general function approximation for P with continuous S,A in Appendix using existing work.
3.2 LEVERAGING RECURSIVE SEEEIIIEESRRTCCI
STRUCTURES USING MODEL.-FREE METHODS
We have established that the model-based methods POR-UCRL and POR-UCBVI improve over naive history-summarization and have poly(S, A, H) guarantee in terms of transition function estimation.
7

---

Published as a conference paper at ICLR 2025
However, recall the last challenge mentioned in Section 2.3 can they adapt to examples like the combination lock, where there a recursive structure on the internal states? Disappointingly, we will see in Proposition that the answer is no they are exponentially worse than the ideal solution. Intuitively, learning the reward and transition models separately is needlessly expensive here. At the more technical level, since POR-UCRL and POR-UCBV decouple the learning of reward functions across timesteps, they are unable to incorporate a recursive structure on the reward functions.
In this light, we consider model-free methods. Unlike model-based methods that have to account for Markovian transitions, we can simply use naive tistory-summarization here and treat 7 r[/o] as the state for Q-functions Qn. However, under sumuoaryuuumaiziaiiinn there is subtlety involved in choosing the class Q of Q-functions given a known class M of models. Using product classes Q1 x ..... x QH wasteful, since often exponentially many tuples in product class cannot be realized by any model M [0 Instead, one should consider the class of only the tuples (Q1,..., Q+I) ) that can be realized by model M. practice, this translates to the problem of good representation learning - one should use shared network for all Q-functions instead of using different network for each timestep. This is reflected in the experimental choices of Anonymous 2024))
Model-free methods rely on the Bellman error, which relates consecutive Q-functions and couples their learning. It is thus natural to expect model-free methods like GOLF (Jin et al. (022]) to adapt to recursive structure existing guarantees do not reflect this. It turns out from Proposition T hellow that the Bellman-eluder (BE) dimension of the combination lock problem is A even with the minimal Q-function class.
internal states and perform better than model-basee methods. However,
The issue is that the proof of GOLF bounds the h-step Bellman errors in a decoupled manner, which why still fails to incorporate a recursive structure on internal states. Intuitively, one wants to wait for Bellman errors at timesteps 1....,ie - to become small before bounding the Bellman error at h. In this light, given parameter a, we define the function class
@(a, { Q [Emiro))Q TiQ+ill & a, v1 < ( h}
that considers all tuples (Q.,-.., Qu) where the Bellman errors until step h are already low. We can use this class to define the a- a-history aware Bellman -eluder dimension (HABE) of Q as follows. Recall that mo is the policy that acts greedily according to Q = -Q11.... QH).
Definition 4. Consider the Bellman errors 4 1Q², ThQu+1/Q Q(a, h h-1)3. Denote nn (Q()) the distribution induced on r[h- 1/1 an by HQ and let Da.e := (2)(Q) Q Q). Let dimpE the dis- tributional eluder dimension and define dimHABE 2 a) max, dim ( ((.)))).-))
Intuitively, o-HABE, dimension measures how hard to reduce the Bellman error at timestep h the errors at previous timesteps I,..., h 1 are already small. This captures the hardness of adapting to the recursive structure on internal states one/a few timesteps at a time. We discuss in Appendix G.1 how the a-HABB dimension compares to the Bellman-eluder dimension in general. We now give new guarantee for GOLF using the a-HABE dimension.
Theorem 2 (Modified GOLF Regret). Let Assumption 7 hold, let Q be Bellman complete, let dHABE= = dimHABE( Q, at min(a, ,, /1/T)) and let de. == log(N((Q u G. Iko))) Choose hyperparameter 3 clog((H)) + dc.2) for some universal constant e and the auxiliary function class G used in GOLF, and define. Then, GOLF satisfies Regret(T) = O (pH ddAREdo..T)
Using regret-to- PAC conversion, we also show in Corollary 7 that the sample complexity of GOLF As foreshadowed above, we now show in Proposition that these guarantees
O
p² HH'ddn duanndde
can be polynomial even when the the usual guarantees for GOLF as well guarantees for model-based algorithms are exponential. Note that this improvement is achieved only given dense intermediate feedback. Under sparse intermediate feedback, one cannot adapt internal states "a few timesteps at time." " and we in fact have Ω v TA regret under any algorithm. However, dense feedback case is quite realistic for many applications, such as automated mathematical reasoning.
Proposition (Dimensions for the Combination Lock), Consider the combination lock problem with model class M = P x F and induced Q-function class Q.
The reader use the example of the combination lock to convince themselves of this.
8

---

Published as a conference paper at ICLR 2025
Under dense intermediate feedback with Hp [H] dimpABE Q, A all 9, while its BE dimension is at least A" 2. The eluder dimension for reward functions functionss dim (Fis 4) is at least A for any h E H.
For sparse intermediate feedback with Hp } and any a > 0, the a- a-HABE dimension, the BE dimension and the eluder dimension of FH are all at least A - Moreover, any algorithm in this setting will have regret Q1V AT)).
We discuss Appendix G.T that in general, we do not have an inequality either direction between the a-HABE dimension and the BE dimension. However, the a-HABE dimension is typically smaller.
DUELING TO OPTIMISM REDUCTION
The dueling and cardinal feedback models intimately related. is thus tempting to use algorithms for cardinal PORRL to solve dueling PORRL. However, we detail why the "obvious" reduction from dueling feedback to cardinal feedback fails. This both demonstrates the hardness of the problem and motivates our reduction.
4.1 THE NAIVE REDUCTION ALWAYS FAILS
Consider a modified PORMDP M with S := =
where we run the pair of policies ग. := (TI, πo) and obtain observations based on the decoder-induced function [h]] rh[hh) := [h]] - fa [T2[h]). Consider the space of all such PORMDPs induced by M. and denote by M.. Since cardinal feedback in M exactly corresponds dueling feedback in M, it is tempting to restrict to searching over 1I x 1l and run any algorithm for cardinal PORRL on this modified PORMDP M to achieve low dueling regret.
This fails because the feedback model and regret metric are fundamentally non- mon-aaeg in dueling feedback, unlike in cardinal feedback. While the agent receives dueling feedback over the duel for (TI.e; T2,)), dueling regret is instead concerned with duels for (=., (1.t) and (x., T22). Running an algorithm for cardinal PORRL on the modified MDP will maximize the dueling feedbackk itself. This is achieved by playing one good and one really bad policy, unlike the two good policies needed for low dueling regret. We formalize this in Lemma 4 showing that the naive reduction leads to linear dueling regret for any PORMDP and any cardinal PORRL algorithm with sublinear regret.
4.2 REDUCING DUELING TO OPTIMISTIC CARDINAL PORRL
The naive reduction fails because maximizing dueling feedback can lead to bad policies being played. In this subsection, we present a white-box reduction where we ensure that we only play potentially good policies for both 11, and πT, We detail here how the dueling feedback problem from any optimistic algorithm for cardinal PORRL. We will focus on the case of confidence sets here for smoother exposition, the much harder case of bonuses is treated in Appendix H.2 A generic optimistic algorithm using confidence sets maintains confidence sets CM (Dr, 5) using the collected dataset D; trajectories and feedback. We define formally in Appendix C.I. For the reduction to work, we require that the confidence sets are well-designed. as This assumption satisfied for confidence sets used by POR-UCKS
obtain algorithm for
demanded by Assumption 2
Assumption 2 (Controlling Value Error due Confidence Sets). M. E CD,(D,, for arbitrary sequences (Pt, E CDr, 8), both E 11 ((P,, f", π.) - V(P,, s" m.) = O(Cr(M, (IP,, m.)] O(C'(M, T, 8)) hold with probability 6/2 each. me)
and >T= (P.,, m.) (T)
The key insight is to use confidence sets from cardinal PORRL to search for TI.r and T2,t only among policies that both have chance of being optimal. Then one plays the most uncertain duel among all possible choices for T1, and T2. This generalizes and abstracts out ideas in (Pacchiano al., 2021). which presents a specific algorithm to achieve low dueling regret in their model. We present the reduction to optimism over confidence sets in Algorithm I the version for bonuses is in Appendix H.2 Define (M, π. x²) VMM, TT) V(M, m'). We compute the confidence sets (D, 6) as the image of (D. 8) under - P. We compute Cy(D, 8) by treating (ox) (on), as cardinal feedback in M. As an example, for -CRL we perform least squares fit for 7 and use Lemma 7 to define our confidence sets again. We then get the following regret guarantee.

---

Published as a conference paper at ICLR 2025
Algorithm 1 Reduction from Dueling to Cardinal Confidence-Ser Optimism
1: Input Known reward function {rx h-1 method to compute CM(D,6) Cp( Cp(D, CD(,
2: Initialize dataset D1 - 0. (M = =
3: for t = 1, 1,.... T do
4: Compute 11, T I1 CM 0) s.t. V(M, > O E u] [Candidates T.
5: Play (TI,3; E arg max max VD n. ,,, - (M ,') (Most uncertain duel) ,, (n
6: Observe trajectories Ti, {(st . ) 1=
along with feedback (On 7: Update D, to D1+1 using the data and compute Cp(D C7(D++1,
8: end for
Theorem 3 (Reduction from Dueling to Confidence-See Seaeee-Se-BBaasaae Based Optimism), the confidence sets Cm(Dr,8) 8) satisfy Assumption 2
then the dueling regret Regret (T") of Algorithm 7 is given by
Regret O(CP(M,C,P,M...ooo
Cs(M,I,5)
Note that complexity parameter CF depends on M. is a priori unclear how the complexity of M relates to that of M. Fortunately, Lemma below settles this, and we can then use our results for POR-UCRL get Corollary [ below. See Appendix For a straightforward extension to general function approximation for PP abstracting out the S, dependence.
Lemma (Relating F and F). For any function class F, dimggFFe)) & dimgg(F eF)
Corollary (Dueling Regret using POR-UCRL Confidence Sets). The confidence sets from POR- UCRL satisfy Assumption| 2 and using them in Algorithm / leads to the following regret bound Regretp d (T) = δ ((pSv HA+ EnEH, Vdg,dd..) VT)
CONCLUSIONS AND FUTURE WORK
In this work, we have introduced PORMDPs and their analysis as way to better model internal states of humans and intermediate feedback in RLHF. We have introduced two statistically efficient algorithms for handling partially observed reward-stare states and have shown that they improve over naive history summarization. We have noted that these methods subsume as well as improve over a lot of past work in RLHF We have studied how one can further leverage recursive structure over internal states using model-free methods. For this purpose, we have defined a new notion of dimension, the a-HA BE dimension, that captures the hardness of utilizing the recursive structure. Finally, we have also provided novel reduction from dueling regret to optimistic algorithms for cardinal regret.
Besides our theoretical contributions, we would like to note the practical implications of our work.
When the feedback is suspected to have recurrent structure, conclude in sections 3.1 and 3.2 that it can be exponentially more statistically efficient to use practical model-free methods like learning deeendy-deeendent Q-functions using actor-critic methods. In the absence of such structure, a model based approach learning f. and P. explicitly will also suffice.
We note in section 3.2 that in practice, using single network for the Q-function critic across timesteps h is important for the "exponential improvement" mentioned above, as opposed to using different network for the Q-function or critic for each timestep.
We are hoping that our work inspires new practical algorithms for PORRL. Theoretical advances in known to inspire practical (e.g. perturbative) versions of the algorithms. The dueling to optimism reduction in section 4 can inspire future practical algorithms that achieve low dueling regret, which we have established section 2.2 an important metric for online (and online iterative) RLHF applications, like in Dong et al. 2024 Xiong et al. (2023).
optimistic algorithms
We hope that our ideas lay the groundwork for further understanding of both statistical and algorithmic aspects of learning good policies when interacting with "stateful" feedback, such as that of humans. Our algorithms and proofs are presented in high generality and modularity in the appendix, and we hope that they can be used to provide novel algorithms and bounds in the future.
Ackmowledgement. CK would like to acknowledge the support of the Rackham International Student Fellowship (the Indian Alumni Fellowship) for this work.
10

---

Published as a conference paper at ICLR 2025
REFERENCES
Riad Akrour, Mare Schoenauer, and Michèle Sebag. April: Active preference learning- reinforcement learning. In European Conerence on Machine Learning and Knowledge Discovery in Databases, 2012.
Anonymous. Enhancing multi-step reasoning via process--upprrvised reinforcement learning from human feedback. https//pppmmeeiiceeeee/ffddddddp
2024. [Accessed 21-05-2024).
Karl Johan Aström. Optimal control of Markov processes with incomplete state information. Journal of Mathematical Analysis and Applications, 10(1):174-205, 1965.
Mohammad Gheshlaghi Azar, Ian Osband, and Rémi Munos. Minimax regret bounds for reinforce- ment learning. In International Conference on Machine Learning, 2017.
Daniel Brown, Wonjoon Goo, Prabhat Nagarajan, and Scott Nickum. Extrapolating beyond sub- optimal demonstrations via inverse reinforcement learning from observations. In International Conference Machine Learning, 2019.
Róbert Busa-Fekete and Eyke Hüllermeier. A survey of preference-based online learning with bandit algorithms. In Algorithmic Learning Theory, 2014.
Qi Cai, Zhuoran Yang, and Zhaoran Wang. Reinforcement learning from partial observation: Linear function approximation with provable sample efficiency. In International Conference on Machine Learning, 2022.
Jeffrey Chan, Aldo Pacchiano, Nilesh Tripurameni, Yun Song. Peter Bartlett, and Michael Jordan. Parallelizing contextual linear bandits. arXiv preprint arXiv:2105. 10590, 2021.
Niladri Chatterji, Aldo Pacchiano, Peter Bartlett, and Michael Jordan. On the theory of reinforcement learning with once-per-epee mece-per-episoee feedback. In Advances in Neural Information Processing Systems, 2021.
Fan Chen, Yu Bai, and Song Mei. Partially observable with b-stability: Unified structural condition and sharp sample-efficient algorithms. In International Conference Learning Representations, 2022a.
Fan Chen, Huan Wang, Caiming Xiong, Song Mei, and Yu Bai. Lower bounds for learning in revealing pomdps. In International Conference on Machine Learning, 2023.
Xiaoyu Chen, Han Zhong, Zhuoran Yang, Zhaoran Wang, and Liwei Wang. sorman-in-the-lowe Provably efficient preference-ban reinforcement learning with general function approximation. In International Conference on Machine Learning. 2022b.
Paul F Christiano, Jan Leike, Tom Brown, Miljan Martic, Shane Legg, and Dario Amodei. Deep reinforcement learning from human preferences. In Advances in Neural Information Processing Systems, 2017.
Hanze Dong, Wei Xiong, Bo Pang, Haoxiang Wang, Han Zhao, Yingbo Zhou, Nan Jiang, Doyen Sahoo, Caiming Xiong, and Tong Zhang. Rlhf workflow: From reward modeling to online rlhf. arXiv preprint arXiv:2405.07860 2024.
Simon Du, Akshay Krishnamurthy, Nan Jiang, Alekh Agarwal, Miroslav Dudik, and John Langford. Provably efficient rl with rich observations via latent state decoding. In International Conference on Machine Learning. 2019.
Yonathan Efroni, Nadav Merlis, and Shie Mannor. Reinforcement learning with trajectory feedback. In AAAI conference on artificial intelligence, 2021.
Kawin Ethayarajh, Winnie Xu, Niklas Muennighoff, Dan Jurafsky, and Douwe Kiela. Kto: Model alignment as prospect theoretic optimization. arXiv preprint arXiv:2402.01306, 2024.
Steven W Flavell, Nadine Gogolla, Matthew Lovett-Barron and Moriel Zelikowsky. The emergence
and influence of internal states. Neuron, 2022.
Noah Golowich, Ankur Moitra, and Dhruv Rohatgi. Learning in observable pomdps, without computationally intractable oracles. In Advances in Neural Information Processing Systems, 2022.

---

Published as a conference paper at ICLR 2025
Rodrigo Andrés Toro Iearte. Reward Machines. PhD thesis, University of Toronto, Canada, 2022.
Rodrigo Toro Icarte, Toryn Klassen, Richard Valenzano, and Sheila Mcllraith. Using reward machines for high-level task specification and decomposition in reinforcement learning. In International Conference on Machine Learning, pp. 2107-2116. PMLR, 2018.
Rodrigo Toro Icarte, Ethan Waldie, Toryn Klassen, Rick Valenzano. Margarita Castro, and Sheila Mcllraith. Learning reward machines for partially observable reinforcement learning. In Advances in Neural Information Processing Systems, 2019.
Rodrigo Toro Icarte, Toryn Q Klassen, Richard Valenzano, and Sheila A Mcllraith. Reward machines: Exploiting reward function structure in reinforcement learning. Journal of Artificial Intelligence Research, 73:173-208, 2022.
Thomas Jaksch, Ronald Ornnr. and Peter Auer. Near-optimal regret bounds for reinforcement learning. Journal of Machine Learning Research, 11:1563-1600, 2010.
Jiaming Ji, Tianyi Qiu, Boyuan Chen, Borong Zhang, Hantao Lou, Kaile Wang, Yawen Duan, Zhonghao He, Jiayi Zhou, Zhaowei Zhang, et al. Ai aligmment: A comprehensive survey, arXiv preprint arXiv:23100 10. 19852, 2023.
Nan Jiang, Akshay Krishnamurthy, Alekh Agarwal, John Langford, and Robert Schapire. Contex- tual decision processes with low bellman rank are pac-learnable, 2016.
Chi Jin, Zeyuan Allen-Zhu, Sebastien Bubeck, and Michael Jordan. Is q-learning provably efficient? In Advances in Neural Information Processing Systems, 2018.
Chi Jin, Sham Kakade, Akshay Krishnamurthy, and Qinghua Liu. Sample-efficient reinforcement learning of undercomplete pomdps. In Advances in Neural Information Processing Systems, 2020.
Chi Jin, Qinghua Liu, and Sobhan Miryoosefi. Bellman eluder dimension: New rich classes of problems, and sample-efficient algorithms. In Advances in Neural Information Processing Systems, 2021.
Akshay Krishnamurthy, Alekh Agarwal, and John Langford. Pac reinforcement learning with rich observations. In Advances in Neural Information Processing Systems, 2016.
Kimin Lee, Laura Smith, and Pieter Abbeel. Pebble: Feedback-efficient interactive reinforcement learning via relabeling experience and unsupervised pre-training. arXiv preprint arXiv:2/06.05091, 2021.
Hunter Lightman, Vineet Kosaraju, Yura Burda, Harri Edwards, Bowen Baker, Teddy Lee, Jan Leike, John Schulman, Ilya Sutskever, and Karl Cobbe. Let's verify step by step. arXiv preprint arXiv:2305.20050. 2023.
Qinghua Liu, Alan Chung, Csaba Szepesvári, and Chi Jin. When is partially observable reinforcement learning not scary? In Conference on Learning Theory, 2022a.
Qinghua Liu, Praneeth Netrapalli, Csaba Szepesvari, and Chi Jin. Optimistic mle-a generic based algorithm for partially observable sequential decision making. arXiv preprint arXiv:2209. 14997, 2022b.
Pierre Ménard, Omar Darwiche Domingues, Anders Jonsson, Emilie Kaufmann, Edouard Leurent, and Michal Valko. Fast active learning for pure exploration in reinforcement learning. In Interna- tional Conference on Machine Learning, 2021.
Ellen Novoseller, Yibing Wei, Yanan Sui, Yisong Yue, and Joel Burdick. Dueling posterior sampling for preference-based reinforcement learning. In Conference on Uncertainty Artificial Intelligence, 2020.
Long Ouyang, Jeffrey Wu, Xu Jiang, Diogo Almeida, Carroll Wainwright, Pamela Mishkin, Chong Zhang, Sandhini Agarwal, Katarina Slama, Alex Ray, et al. Training language models to follow instructions with human feedback. In Advances in Neural Information Processing Systems, 2022.
Aldo Pacchiano, Aadirupa Saha, and Jonathan Lee. Dueling rl: reinforcement learning with trajectory preferences. arXiv preprint arXiv:2/11..44 2021.
12

---

Published as a conference paper at ICLR 2025
Rafael Rafailov, Archit Sharma, Erie Mitchell, Stefano Ermon, Christopher D Manning, and Chelsea Finn. Direct preference optimization: Your language model is secretly a reward model. arXiv preprint arXiv:2305.18299 2023.
Dorsa Sadigh, Anca Dragan, Shankar Sastry, and Sanjit A Seshia. Active preference-based learning of reward functions. Technical report, EECS Berkeley, 2017.
Aadirupa Saha, Aldo Pacchiano, and Jonathan Lee. Dueling rl: Reinforcement learning with trajectory preferences. In International Conference Artificial Intelligence and Statistics, 2023.
John Schulman, Filip Wolski, Prafulla Dhariwal, Alec Radford, and Oleg Klimov. Proximal policy optimization algorithms. arXiv preprint arXiv: (TG.::777706644 2017.
Daniel Shin, Anca Dragan, and Daniel S Brown. Benchmarks and algorithms for offline preference- based reward learning. arXiv preprint arXiv:2301.01399 2023.
Gokul Swamy, Christoph Dann, Rahul Kidambi, Zhiwei Steven Wu, and Alekh Agarwal. A minimaxi- malist approach reinforcement learning from human feedback. arXiv preprint arXiv:2401 .44066, 2024.
Csaba Szepesvári. Lecture notes in theoretical foundations of reinforcement learning: Lecture 23, tabular mdps. https://iltheory.gitbbbb
2023,
Andrea Tirinzoni, Aymen Al-Marjani, and Emilie Kaufmann. Optimistic pac reinforcement learning: the instance-dependent view. In International Conference on Algorithmic Learning Theory, 2023.
Jonathan Uesato, Nate Kushman, Ramana Kumar, Francis Song, Noah Siegel, Lisa Wang, Antonia Creswell, Geoffrey Irving, and Irina Higgins. Solving math word problems with process-and outcome-based feedback. arXiv preprint arXiv:2211.142755 2022.
Andrew J Wagenmaker, Max Simchowitz, and Kevin Jamieson. Beyond no regret: Instance-dependent pac reinforcement learning. In Conference on Learning Theory, 2022.
Lingxiao Wang, Qi Cai, Zhuoran Yang, and Zhaoran Wang. Represent to control partially observed systems: Representation learning with provable sample efficiency. In International Conference on Learning Representations, 2023a.
Yuanhao Wang. Qinghua Liu, and Chi Jin, Is rlhf more difficult than standard rI? arXiv preprint arXiv:2306. 2021b,
Christian Wirth, Riad Akrour, Gerhard Neumann, Johannes Fürnkranz, al. A survey of preference- based reinforcement learning methods. Journal of Machine Learning Research, 18(136): 2017.
Zeqiu Wu, Yushi Hu, Weijia Shi, Nouha Dziri, Alane Suhr, Prithviraj Ammanabrolu, Noah A Smith, Mari Ostendorf, and Hannaneh Hajishirzi. Fine-grained human feedback gives better rewards for 01693, 2023.
language model training. arXiv preprint
Wei Xiong, Hanze Dong, Chenlu Ye, Ziqi Wang, Han Zhong, Heng Ji, Nan Jiang, and Tong Zhang. Iterative preference learning from human feedback: Bridging theory and practice for rlhf under kl-constraint. arXiv preprint arXhv:2312.11456, 2023.
Wanqi Xue, Qingpeng Cai, Zhenghai Xue, Shuo Sun, Shuchang Liu, Dong Zheng, Peng Jiang, Kun Gai, and Bo An. Prefree: Recommender systems with human preferences for reinforcing long-term user engagement. arXiv preprint auXiv:2212.022779 2022.
Wenhao Zhan, Masatoshi Uchara, Wen Sun, and Jason D Lee. Pac reinforcement learning for predictive state representations. In International Conference on Learning Representations, 2022.
Wenhao Zhan, Masatoshi Uchara, Wen Sun, and Jason D Lec. How to query human feedback efficiently in rl? arXiv preprint arXiv:2305. 18505, 2023.
Han Zhong, Wei Xiong, Sirui Zheng, Liwei Wang, Zhaoran Wang, Zhuoran Yang, and Tong Zhang. Gec: A unified framework for interactive decision making in mdp, pomdp, and beyond. arXiv preprint 2..0122211.01962, 2023.
13

---

Published as a conference paper at ICLR 2025
A LEMMAS AND DISCUSSION
A.1 RELATION BETWEEN V AND Vg
Lemma 1 (Replacing with g). For any history-dependent policy that selects action an [T[[h- 11, sh), (w, = v (M, π) holds for any M.
Proof. By slight abuse of notation, the following chain of equalities holds. Here, (i) holds since Th (8h,,, Wh, an) is function of 8h, Uh, dn- Equation (ii) holds since we have already conditioned on r[h]. which includes 5h, ah. Equation (téi) holds by the definition of (r(hT)) the conditional distribution of un given [/A].
(M, n) = Eyonp
(s 24, and hEHpp
Σ
Σ
Eyuwp (sa uha an)
hetp
Σ [y- (1n uh an]
heHp
Σ [
Ex"MM] (ra un, an [T
hEHp
[+|h|>P Eun [rn un an)] [[1]]]
he Hp
(1))
P Emn~p [ra(sn, un, an)] [|h]]
he Fdp
(161)
E [Eun (sn un, an)l]
heHp
Σ FT-Po [F [Fnngg(((A)) (on uny an)]
h
= =ET-p=
Σ Ean-g((T(h)) [rn(sn, uns an) heHp
= (M)
A.2 IGNORING INTERNAL. REWARD-STATES IS BAD FOR ALIGNMENT
We define traditional RL methods as those that output possibly time-dependent Markovian policies. In this section, we provide toy example showing that there is a PORMDP with good sublinear regret guarantees where any time-dependent Markovian policy has value bounded away from the maximum value. This means that traditional RL methods will always incur linear regret. We hope that this illustrates that RL methods that ignore internal reward-states can be bad for alignment.
Lemma 3 (Markovian policies are not enough). There is PORMDP where POR-UCRI. and POR-UCBVI achieve poly( H, S, A)yT regret, but any Markovian policy is at least l-suboptimal and so any method that outputs Markovian (possibly deme-depndden) policies will lead linear regret.
Proof. Consider a PORMDP M in the setting of Chatterii et al. (2021) (see point (ii) below Def- inition 2) and set S {s1,52), $2). A (a1, and 1 R. Let the transition matrix be P(s') s, a) 2 for all s, a, s' Let the starting state always be $1.
Consider the set T of all trajectories that have 02 until s2 appears, and then only have a₁- Choose Ø(T) = 1(T T). The best non- Man-Mvavviinn policy т, can follow this rule and achieve ø(T) = 1 for all pa. Thus, max V(M, a) 1, where IT is given by all history-dependent policies.
14

---

Published as a conference paper at ICLR 2025
On the other hand, consider a Markovian but potentially dime-dependent policy If (T(2)) 0, then its value is zero. If x(a2) > O, then conditioned on the event that $2 appears first at timestep 1, the expected total reward is at most (12) TT (a2))) Conditioned on the event that 82 appears first at timestep 2, the expected total reward is at most тi (a2) (2(2)). Conditioned on seeing 82 at or after bound
h 3, the expected total reward is certainly most 1. Using these crude inequalities,
the expected reward of a Markovian policy π by
(12) (2((22) Th (122)722(222)
H 1
(1(a)) (2( +
1
1
1
3
+
2
2h
2
4
This means that the value of any time-dependent Markovian policy is most dependent Markovian policy is at least } -suopptimll and incurs 7 regret.
3 and so any time-
4
Recall that we defined traditional RL algorithms as those that output (possibly time-dependent) Markovian policies. Clearly, any traditional RL algorithm in this sense will have at least 4 regret, which is linear regret.
A.3 THE NAIVE REDUCTION FROM DUELING TO CARDINAL PORRL FAILS
Lemma 4 (Naive Reduction Lower Bound). Using any algorithm for cardinal PORRL with sublinear cardinal regret on with policy class II' == x II to get sequence (T), 12,1)....5 (T.,T T2,r) leads linear dueling regret for M whenever all policies do not have the same value (M,
Proof. Define T. arg ma V(M, TT and let Miin arg min V(M, Then note that max (D n. x') "."'
max V(M, ा V(M, X²)
n,
max V(M, + max x'ell
(V,, x']
mell
max V(M, π. min V(M,
well
n'ell
(MM, - V(M, Tmin)
Under the naive reduction described in Section 4 cardinal PORRL algorithm is used to maxi- mize dueling feedback.. If the algorithm has sublinear cardinal regret, then it will produce duels (mi,); T2,e), - T, satisfying
max VD(M, - J
= o(T)
From above, this means that
T
-V( [V(M, m2,1) VM,, mman]] o(T)
Now note that by definition of n. and minn; both terms are positive. This is the key point. We thus have
((, V(M, mI.e) o(T)
T
Σ (MM, T2,1) VMM, Tmin) = =(T)
This means that for dueling regret Regret D (T), we have the following.
Regret (T)
[VM, V(M, [V(M, m.) V(M, x22))
VVM, +
[V(M n.) - V(M, Fminn)
15

---

Published as a conference paper at ICLR 2025
T (M, Amin) - V(M, x2,1)
(T) T (M n..) - (MM, [minn]]
(T))
Where the last line holds since all policies т do not have the same value V(M, T), and so V(M, V(M, Tmin) > 0.
16

---

Published as a conference paper at ICLR 2025
B REGRET-TO-PAC CONVERSION
When learning in MDPs, we can turn any guarantee on the regret into a corresponding PAC guarantee. the so-called "regret-to-Pee PoC conversion" (Jin al. 2018 Ménard al., 2021 Wagenmaker al.
2022, Tirinzoni et al. 2023). Similarly, we want convert guarantees on the cardinal and dueling regret (see Section 2 into corresponding PAC guarantees, which are more adherent an offline setting. We provide distinct results for the cardinal and dueling regret below.
Lemma (Cardinal regret to PAC). For T E N and ó E [0, 1]. let ALG be an algorithm for cardinal PORRL producing a sequence of policies (TT))atT) with cardinal regret bounded with probability at least - as
((M, & R(T,8)
Then, a policy ār ......, Wr sampled uniformly satisfies with probability at least 1 - 28
V(M, T.) ((M, & R(T,5)
1og(1/5)
+ 8Bp/
T
T
Proof. We consider the sequence of random variables Y, V(M, V(M, mT) AA E [7]. Through the Hoeffding's inequality on Yú and |ral & B we have
V(M, T.) V(M, RT) E[V (M, v(M, 1
(VMM, vi) 8Bp
((M,
1og(1/0)
with probability at least 1 - 6. Then, combining the latter inequality with the upper bound on the regret and a union bound, we get
R(T,5)
(1g(
V(M, (M,, ((M,
8BPp
with probability at least 26.
The latter result implies PAC guarantee of the form P(V(M, m.) V(M, 2 8 for some e > 0 and 8 [0, 1] with a number episodes of order O(1/s²). An analogous result can stated for the dueling setting.
Lemma 6 (Dueling regret to PAC). For T e N and ó [0, 1]. let ALG be an algorithm for dueling PORRL producing a sequence of policy pairs (Ti, (2,4)s5(T with dueling regret bounded with probability at least - 8 as
V(M, V(M,TI,) + V(M, & RD R.
2
Then, a policy îं Ti...., or sampled uniformly satisfies with probability at least 48
RD(T,8)
+16Bp log(1/5)
V(M. VMM, 7o)
T
Proof. The proof proceeds as in the previous lemma by applying Hoeffding separately on the sequences Y1,+ V(M, T.) - (VM, m1.) and Y2+- = V(M, m.) - V(M, T2,e). then applying union bound.
17

---

Published as a conference paper at ICLR 2025
C PROOFS FOR GENERAL OPTIMISTIC ALGORITHMS FOR CARDINAL PORRL
C.I GENERIC MODEL BASED OPTIMISM USING CONFIDENCE-SETS
We present template to get regret bounds for generic model-based optimistic algorithm using confidence sets, which we will later instantiate into POR-UCHE and also use in our reduction from the dueling PORRL to optimistic algorithms for cardinal PORRI.
A generic algorithm using confidence sets is determined by confidence sets Cm(D,6) based on dataset D. Maintaining a running dataset Dr, at each step t, we run Ni given by
Tg. Me
mag max (E
V(P.f.
We obtain a trajectory Ti p and append it to D; to get Di+1. recompute confidence sets CM((D+1, 6), and continue. This algorithm formally presented in Appendix C.1below.
Algorithm 2 Generic Confidence-Sed Optimism
1: Input Known family reward functions {Ra)==1 known model class M induced by known probability transition kernel class P and known decoder-induced function class F, confidence level 6.
2: Initialize dataset D1 0 and (m, M.
3: for t = 1.... T do
4: Compute the optimistic history dependent policy,
Te, Me
arg max V(M, π)
(D,
H 5: Observe trajectory T₁ = {(s ) 4=1 and feedback (on)NER
6: Update Di+1 D, {Tr] and compute confidence set CM (D++1,
7:
end for
We now make the following assumption about confidence sets. It essentially controls the effect of shrinking confidence sets for P and F on the value. Showing this assumption is the core of proving regret bounds for any instantiation of this generic algorithm. We will see later that it is satisfied by the confidence sets for POR-UCRL.
Assumption (Controlling Value Error due Confidence Sets, Refined Version). For transition kernel P. and function f., consider any sequence of policies тe and datasets D, that contain { ;-1
generated under (P f We require that M, E (D,,D,, 8) for all with probability 1 8/16, 16. We require that there exist problem dependent functions Cr(M, T, 8) and Cr(M, T, 8) so that for arbitrary sequences (P,, f*) E Cm((D,,) 6). the following hold with probability 5/2 each.
v(P,, f.mm) m.) - V(P.,
Ō(Cp(M,T,6))
V(P., f², m²) V(P., Ö(CF(M,TT88)
Theorem 4 (Regret for Confidence-Ser Optimism). Under Assumption any generic optimistic algorithm using confidence sets CM 8) satisfies the regret bound
Regret (T) H (Cp(M,T,5) + Cx(M,T.6))
Proof. Let M2 be given by Pr and ft. Note the following inequalities, where (i) holds with probability 1 by the optimistic definition of ne.
Regret (T) = Σ (..
18

---

Published as a conference paper at ICLR 2025
T
V(P,, P mp) - ((P
V(P.. M m.) V(P., M,, me) + V(P.,, m.) - V(P., m.) (1T)
(1)
We now apply Assumption 3 to bound (7) and (IT). We can use the assumption since Dj contains
trajectories {T generated by IPt I E Cr(D,, = F and Pt Cr(Dr, This immediately gives us that with probability 5
+ Regret (T) O
as desired.
19

---

Published as a conference paper at ICLR 2025
C.2 GENERIC MODEL-BASED OPTIMISM USING BONUSES
We present a template to get regret bounds for generic model-based optimistic algorithm using bonuses, which will later instantiate into POR-UCBVI and also use our reduction from the dueling PORRL to optimistic algorithms for cardinal PORRL.
generic optimistic algorithm using bonuses relies on bonuses (1 n, 6), n, that depend on a policy и, transition kernel and dataset D. It also relies on estimates P.D and fo that depend on D. Maintaining running dataset De, at each step we run == arg ma V(P [[PD,, fo., T), where ( D., ID., π)) is given by:
V V(PD, fD. 6f (PD,, 6) + BBp)b (P,
where 2 is defined below. We obtain a trajectory Tr 1p and append it to Dr to get Di+1. compute new bonuses and estimates, and continue. This algorithm is formally presented in Appendix C.2
Algorithm 3 Generie Bonus-Based Optimism
1: Input Known family of reward functions (Ra h= method Est(D) to estimate PD and fo from dataset D, bonus functions (P тT, 5) and (P, n, 6), confidence level 8
2: Initialize D (). initialize fPi PDD arbitrarily.
3: for = I.... do
4: Compute optimistic history dependent policy,
Ti = arg max (i. + (PP., + (( (PPPPPPPPP. (T)))
5: Observe trajectory {(1// a/)) and feedback {on) hep6,
6:
Compute new estimates fiu., pP11 Est(Dr+1) and compute new bonus functions
Pi-1 b (fPtt),,,0), Pi-1 (fD+t1,,,0)
7: end for
We now make the following assumption about our bonuses. Showing this assumption is the core of proving regret bounds for any instantiation of this generic algorithm. We will see later that is satisfied by the bonuses for POR-UCBVI.
Assumption 4 (Controlling Value Error via Bonuses). For transition kemnel P. and function f.. consider any sequence of policies and datasets D, that contain (Ti)==1 generated under (IP:: f*). We require that for sequences PDD, and fD, and any sequence
F, the following hold.
Bounding effect of error in F: With probability - 5/32, for any PP and uniformly over all policies ग. (VP,, fp., T) (P, ff < bP. 5) and there is function (F(,,T,6)
that >'" 67 (P.,, Te, 8) ((CF(M,T 8)) with probability 1 1- 8/332
Bounding effect of error P: For any function μ : T, - R bounded by D, there is function 2DD) > D so that the following holds uniformly over all policies with probability 1-8/1 8/32.
(r((F.)=/((T)) ET~P; ((T) & 2 <D)b (P.,
The statement also holds we switch P. and Pr, Additionally, the statement holds for suitable D if we replace E,-p= ((()) with bp x, 8) (=((P, 0) Finally, there is function Cp(M,T, so that L Up 1 1-88/ 8/32.
1. (P., Te, TT, 8) (CC,(M, (,,T, with probability
Theorem 5 (Regret for Bonus-Based Optimism). Under Assumption 4 with 21 = x(D) + =(DD) + =22)(D)) any generic optimistic algorithm using bonuses satisfies
Regret(T)
(CF(M,,, (BB))CC,,,,
UThis would instantly hold with D Bp if by (r- 8) for some trajectory level honus by(r, 8), and similarly for P.
20

---

Published as a conference paper at ICLR 2025
Proof. Note that can Assumption since D, contains trajectories {-i)_1 generated by Pr., fD. F is computed using D. and PD. is computed using Dr. Also note that WLOG, bp n, & 2 always holds since we can otherwise clip 2 and our assumption will still hold. Similarly, WLOG b (P, 6) & 2=(Bp), otherwise we can clip it at and our assumption will still hold. Now note the following inequalities.
T
Regret(T)
- V((P.
V(PD. f" + xB (B -
m
+ +
.. (f, (B - V(P.;
fo, + by (P mr, 0) (B)) (P,, V("
b Te. (b)) (PD,. D. Te.
V(t V
Te, 0))
Here, incquality (t) holds with probability 1 - 8/16 by the second point in Assumption 4 Inequality (ii) holds with probability - 5/16 by the first point in Assumption 4 Inequality (iit) holds with probability 1 by the optimistic definition of n. Continuing, we have
(10) $
Regret (T)
2
(b (PD,, D., n., (f
2
Dr (P,, .: T 8) + 2z (Bp) (P., ne 8)) + =(Bp)(bB (P,,,, Te, 6))
22 Bp) (P.,
T 0 (P. T (B)) Fe, 0))
Σ
Here, inequality (tu) holds with probability 1 5/8 by union bound over the first and the second
point in Assumption 4 Finally, inequality (v) holds with probability 8/4 by union bound over four applications of the second point of Assumption 4 Finally, we use a union bound over both points of Assumption 4 to conclude that with probability 8/8
T Σ b (P., 0) 21 21 (P.. =
By taking union bound over the events of all inequalities above, have that with probability 1-d 8
Regret(T) = Ō (CF((M, (MBD))COTTTT)))
desired.
21

---

Published as a conference paper at ICLR 2025
C.3 GENERIC MODEL-FREE FRRE OPTIMISM
Algorithm 4 Generic Model-Free Optimism
1: Input Known Bellman-complete class of Q-functions @, confidence level 6.
2: Initialize dataset D + U and Co(D1, Q.
3: for t = 1.... do
4: -[0] ()
5: for h = L, 1.... H do
6: Play d/ Qi arg qeC Qu(r(h), and observe feedback of,
7: end for
8: Update D4+1= D, (T, (o).........
9: Compute Co(D:+1,
end for
Note that the method for choosing actions a/, at time / induces history dependent policy whose suboptimality is what we use to define regret. Regret is still given by
Regret (T) Σ V(M,, V(M.,
We now make the following assumption about our confidence sets. Showing this assumption the core of proving regret bounds for any instantiation of this generic algorithm. We know that this satisfied by GOLF using the BE-dimension. We will show that in our case, it is also satisfied by more refined notion known as the a-HABE dimension (the a-history aware Bellman eluder dimension).
Assumption 5. For a Q-function Q* induced by model M., consider any sequence of policies ne and datasets D, that contain {Ti)i_ generated under M., We require that Q' E Co(D,, 6) for all with probability 1 8/16. We require that there exists problem dependent function Co( Q (T), so that for arbitrary sequences Q' E CD,D,, 8), the following holds for all h with probability 1 8/2.
1mn T1 CQ(Q,T,8)
Theorem 6 (Regret for Generic Model-Free Optimism). If the confidence sets CD(D, 6) used in then the regret of Algorithm Iis bounded by
Algorithm 4 satisfy Assumption 5
Regret(T) = (HCQ(Q.TT.))
Proof. Note that (MM,, n.) = max, (] a) & max, Q (s1, a) for all i, giving us the following result by the policy loss decomposition in Jiang al. (2016).
Regret(T) =
max Q1 a) V(M,,
T
H
Σ
Σ
E
-TnQ
Σ
Σ
E
-1
O(HC
O(HC
where the last line holds by Assumption 5
22

---

Published as a conference paper at ICLR 2025
D DETAILS AND PROOFS FOR CARDINAL POR-UCRL
We now instantiate Algorithm using standard confidence sets to get POR-UCRL. We show that they satisfy Assumption and get regret bounds for the algorithm. Note that our algorithm is crucially different from naively summarizing the history to define a modified state space, since we are separating the use of history summarization for getting confidence sets from using only the current state while learning the Markovian transitions P. In this case, it is priori unclear if we can use ideas from optimism to prove guarantees with a favorable (non-exponential) dependence on complexity of transitions.
Recall that given a dataset of the first trajectory samples {Tr)i=1 and an index h [H], we consider the following least squares objective to estimate f:
Σ (ox - of.)
= arg min fwEFa
Simple least squares guarantees imply the lemma below.
Lemma (Concentration for Sn)) Define
MSEn,e(Jn,Jh)
N (FF..
1B+ log( (+) Then fū simulta-
Also define (6) hTi log
+ ahat with o,,
neously satisfies U Sh
2(t+1)) < Bhn (262 for all h, t with probability - 8/32.
Proof. We apply Lemma in Chan et al. (202I) and the last statement in its proof to each /t separately with the function class in the lemma set to for fulfa. E F.J. / 1, Xt.p Xt,1 [,] and misspecification = 0 (decoupled from the Eluder dimension's 's E). We also note that of. are 77-- subgaussian samples with mean (x This gives us that each of event indexed by h, below holds with probability at least - 2
5
(on(f((T(AA)) (f. Ba.e
212
So. the events all simultaneously hold with probability at least 1 by union bound.
Recall the definition of our confidence sets below.
Confidence Sets for POR-UCRL. We instantiate the generic optimistic algorithm using confi- dence sets by defining (D, 8) (o) ())(d) as our confidence sets below. We name the resulting algorithm POR-UCRI. We use the data from trajectories (Ti) to build the confidence sets C+ (6) 1I c (8) c(+1(8) with C ( (d) defined below, where (5) = Br.e (H
+ (8) = fn Fr MSE. P((t1) < Br, ())e(8) (8)
We also use the MLE estimate for after / episodes to define Pp( 8, 8, = Nola.as))
Now for
N(saa)
((n, 8)
/
S log 1)54//)
define C+.(6) as below:
2n
P|IPe s. P.( s, & ())
Confidence Sets for POR-UCRL in case P. is known. For known-model UCRL, the confidence sets (5) are still above, but (6) == (P.)
For completeness, we repeat the algorithm POR-UCRL here, which is an instantiation Algorithm the generic optimistic algorithm using confidence sets.
23

---

Published as a conference paper at ICLR 2025
Algorithm 5 POR-UCRL
Input: Known family of reward functions {RA known probability transition kernel class P
and known decoder-induced function class F, confidence level 8.
2: Initialize dataset D U and CF(D1, 6) 1 Fr. (D) 6) - P.
3: for t 1... do
4: Compute the optimistic history dependent policy,
Tei Jes P. = arg max V(P, fT
n. (DC
5: Collect trajectory 72 f(5% af )))) and feedback (ondkEn, by sampling from P with true decoder-induced function f..
6: Update Di+1 < Dj (Tr), Sxt1 for all h
7: Compute new confidence sets Cx(De+1, - II C/ (8) and Cp(D++1, where
( - { E Fr MSR ((C-1) ( & Brg (0)}
Cp(Dr-1,8) - (p|IP(-1 s,a) Peti(- (s,01 & ((N==1(s,.)
8: end for
We will now show our regret bound.
Theorem 1 (POR-UCRL Regret). Under Assumption
7 the regret Regret(T) of POR-UCRI is bounded by the following with probability at least
δ ((PSV [AS Enet, v dr.ndo. VT)
where dg dimg (Frr B) and dc,, log(N 1/T, 11o0))
D.1 SHOWING THAT ASSUMPTION IS SATISFIED
D.1.1 BOUNDING REWARD MODEL DEVIATIONS
Lemma 8 (Bounding Reward Model Deviations). Consider satisfying [fa] & that induce value functions [. T). For any sequence of policies Ts if the confidence (8) is generated using data TÜ P i = - t and f C)-(() is an arbitrary sequence of functions, then we have the following with probability 8/4.
f {fi]hens them,
Σ V(P., (m)) (PP,,
bounded by
o (
Toygloo(T/8) + Σ BRendEN+ Σ
K2n ExaN dE,n
hEHp
heHp
Proof.
Σ V(P., v, 8. mt) F,
V(P,,
P
(T[hJ)
- -E
Σ MGNDD
A=1
E E
Σ (T(]))
- -E
Σ {((((1)
hEHb
heHp
T Σ
E ET-PT
Σ (T(1)) fA(T[A])
NEHt
24

---

Published as a conference paper at ICLR 2025
[m - MM(r.(a) X1, X2.t
Hp
(86)
-M
+ (OBBVTTOON (og(1/)
H
where
X1,1 = Exapp
Σ [((T(h)
Σ (T(T)) hEHp
НEHb
X2, =
Σ [M(l KE
-ETPP
Σ [T((()) R
Inequality (i) follows by the definition of ne and P%. - that is, by optimism. Inequality (ii) holds with probability at least - since X1, and X2, both martingales with respect the filtration
G. given by the data of trajectories [Ta]S=]- Also, [.1,cl, |22,1 < Bp. We can thus apply the Azuma-Hoeffdiin inequality twice to obtain inequality (ii).
Continuing, note the following.
V(P.,,,,m) -VP.))
H f1(TT(D)) MAGGT(i) + Tpp/Tlog(T/O
On - + Bpy Bpy/Tlog(T//)
Σ
Σ
max (M(N(TT(AD)) -N (n + (og
< K2.h
Jn (5)
1=1 he
T
f22h
E KEHP
+ Bpy Tlog(T/5)
The sum of these maximum uncertainty evaluations can be upper bounded using the Eluder dimension.
The inequality below holds by applying Lemma 3 in (Chan et al. 2021] for each separately, with the
function class in the lemma set to {øx - falfa Fi.. p= 1, Xt. = Xx,1 Ti and misspecification
0 (decoupled from the Eluder dimension's 's E). We also recall that of are 7i -ubgaausssi samples
with mean T (Ja (T()))). We obtain
T
(.((To()),)) < <o <0 + Aolen+//E,nae (dE,
Σ
Where dg dimg (Fh, B) is the Eluder dimension of F, and (8, Bn,e ( Therefore, we have our result.
Σ V(P., - V(P.,
bounded by
0
Σ hEHp
BKg + Σ Nen Bp Tlog(T/8)
heHt
25

---

Published as a conference paper at ICLR 2025
Note that this entire argument be repeated with f. and f switched, by the symmetry of the definition of [n. 6) and the fact that the negative of a martingale is also a martingale.
D.1.2 BOUNDING PROBABILITY MODEL DEVIATIONS
Lemma 9 (Bounding Probability Model Deviations). Consider an arbitrary sequence of functions f E FF satisfying [frl < B that induce value functions ((P, f. For any sequence of policies To the confidence Cp is generated using data that includes Tę , an arbitrary sequence of transition structures, then we have the following with probability 1 6/4.
i= 1 t and Pr Cp (8) is
T
Σ V(Pe,f m.) V(P.. mi) & <cccBBP SAHT Bp Bpv pT log (Tg(T/6)
where сæ S/Slog(2) log( HTSA/8).
Proof. We first show the following.
Lemma 10.
Σ
V(P.,
2pC(N((s) o)). + (Bpv pf log(T/6)
Recall that we denote the Bellman operator by T where T" = P. Momentarily define the following for (1, 7'), where T--1 an arbitrary trajectory of length - 1 < H, and s is an arbitrary state.
(T = Epipp
Σ RM
Eptapme
Σ Pa(T(A)
heHp.hil
So in the definition above, the first I observations in come from T--1 while the rest are generated by the input P starting with state 8;. Note that V(P, ((, nT) (2, Also note that by the Bellman equation, we have the following.
(TeLL s1) = Ea-x, [f((+) + Eaws, [E ViL ((T (1.1[1111,..... a),, = En-n, [f((T:[()]] + Ea-a, [P(: a) (41,l 1]. 11, a), )]
Now use to set 71-1 = Tell - 1] and define the following.
Af(s)) = Vi... (T. [1 - 1], 81) (T. - 1]. 81)
Note that
Ai(s)) V(P,, m.) -
(()
(I)
The computation above then gives us the following.
(s Eg-tr Pe(- st, a) Tvt
(41,5 ((Tifl - 1], st a), a):
- Fa-m. [P. st a) V ((Ti - s aj)
= =P.(-1 st a Tve VV (T. - P. at) (T...)) + Yi, + Zr,
where Y1, and Ze, are stochastic processes defined below.
Yr, : P.(. | sf. a) ( - Ea- [P.(- si,a) T V/L,., ((Tell - st, a).
Zr, Eawxe
P.. st a) Tvt VILFE ((Telt - 11. a). - -P,( sf a) Tv VILL,, (T((..))
26

---

Published as a conference paper at ICLR 2025
Consider the filtration GL. induced by the data of [T,)==] O. 1] U {sf]. Since aj ne and (ra[l - 1], si af) T.[4] we get that E[V,,[|9, E[21,199.1 = O. So, one can see that both
processes martingales over Gi.e. Also note that (1, 12,11 p. We thus have that
PPc. af) (. ot af) (H..P(TT....
+ s), II (Tol().)) (1.,,, Yi, + Zz
[Pc(-] sf, a{) (. s/ ai)
V 1+1..
(Tal + P.( 6%, at) Ai41(5)) Y1,1 + Zr, (Tall),)) ()- 1 + Vi,+ Zt
[Pr[-] P. (.. (6)
V
1+,,P,
P sf. af) P. | ai)
V Viti.P. (rel4)-)) + (s/+1) U1a + Yt, + Zr,
where
U1 = Eg
[A
(5(+))
Consider the filtration Gr. defined by the data of (ra) r.l4]. Clearly, Ur. is martingale over Gi,t. Also note that [Ut,l & To conclude, we have that
(s() - (++1)) [ 6f, af) P.(- si ai)
V L.P. (T:l4,)) + UI + Yi, + Zt,t
Using telescoping sum over for fixed and equation I we get that for any the following holds.
V(P,,, - V(P., f
(s1)
H
= Σ
Pol. | st. af) - P.(.1 si at) V2,,,, (Te(d.)) U1e + Vi, + Zt
V(P,, fr, mz) V(P.;
Bp P.l. 1 |6 at) -P.(. st at)] Ui, Vi, + Zz,
H
By p.l. af) p.C 1..11%,a0)) of)
BBp BBp|P... (... st)
- -Pol. ( of, + U1, + Y1, Zz
(2)
Until equation statements have held with probability and did not use any facts about P.. The last inequality also holds with probability and uses the design of the confidence sets. Now, note the following well known concentration lemma. See, for example, Szepesvári (2023).
Lemma 11. For ((n, 6) = 8/ lug(2) (lg(n(n+1)SAA/))
and
2n
(6) = (1/II(-- s, P.C- s, a)ll & C(N
the true model PP* e (5) for all t with probability at least 5/32.
Applying the lemma twice and applying a union bound imply that the following holds with probability 1 6/8.
T
Σ
H1
Σ
(sp((N.(ff..))
Un. + Y1, + Zr,
27

---

Published as a conference paper at ICLR 2025
T (B
H
T Σ MEH
Una + Yn,t Zn,t
H (8)
T
2BpC (N), + (Bp piTppTiie pT (Tg(T/6)
(BPV
Note that inequality (t) is subtle since could have used more data than that from TG = 1 to construct Cpp. The inequality still holds since (nn, 6) is decreasing in n. Also, inequality (ii) holds by the Azuma-Hoefiding inequality.
Now note that the whole argument above can repeated with P. and P. switched, since the negative of martingale is also martingale. So, we have that with probability 5/4
1
H
m()
&
2Bp (Ne(s), O BBy pT log (T/(T
Finally, we need the following easy lemma, proved in Szepesvári 2023
Lemma 12. Let co == 8V Slog + log (HTSA/))) Then the following holds almost surely.
(B) cs cB SAHT + c5 cyBPAA
This establishes our claim.
D.2 PUTTING IT ALL TOGETHER
Theorem 1 (POR-UCRL Regret). Under Assumption 7 the regret Regret(T) of POR-UCRL is bounded by the following with probability least 1
3 ((DSVHA Enen, VdENNON.)) VT)
where dg dimg (Fhs #) and de,, log(W (oloo).
Proof. We combine Lemmas and 11 conclude that M, (D,,8) for all t with probability 8/16. We can now combine this observation with Lemmas (8 and t observe that Assumption is satisfied by POR-UCRL. By Theorem 4 the following holds with probability 1 8.
Regret (7) O 05 BBBpySAHT& + BpHSAA + Σ BRg +
Σ he
K2. / (6,)
heH,
where SS/glo/() + (oT( dE dimg (Fr, B) is the Eluder dimension of Fp. á
and (r)r(8) Sr,a 21 O(B2n)dc,,) This is because all the terms dependent on get
absorbed by the first term in our expression below.
We further refine it by ignoring terms independent of T and using the fact that Bn.r(0) = ((d..) to
get that
Regret(T) = = DDS/AHT+ Σ
hef,
Analogously, we can provide sample complexity result for POR-UCRI..
28

---

Published as a conference paper at ICLR 2025
Corollary 2 (POR-UCRL Sample complexity). Let 0, [0. Ignoring potynomial terms
independent of E, we can bound the sample complexity N(,, 6) of POR- COR-UCRLLC as follows
pdd
62
8²
where dg := maXheH, dg and de = maX dc
Proof. We invoke the regret-to-Par PAC conversion in Lemma with confidence = 5/2 and we plug the regret bound Theorem to write
((BISVVA
c c
AH Σ R2 Opylog(1/0)
vT)
keHp
from which we get the result by picking N T and the definition of de, dc.
Also note the following theorem and corresponding corollary.
Theorem 7 (POR-UCRL Regret if P. is Known). If we know the transition matrix P, in POR-UCRL, then our regret is given by the following with probubility 1- ô, ignoring polynomial terms independent of
(T) = =ō ((B2t
BBp
Σ ho?
Vdg.dCh
VT
Proof. We Lemmas 8 and the fact that (6) is always singleton to observe that Assumption il satisfied by this version of POR-UCKS as well. By Theorem the following holds with probability 6.
Regret (T) = Ō BpVT+ Σ BRgndER
Σ kan dE,
hER,
h
We further refine it by ignoring terms independent of I and using the fact that BA.r = ((do,) to get that
((1p+ Σ man/desBurr00) VT heH,
Regret(T) =
Corollary 3 (POR-UCRL sample complexity P. is Known). Let E > 0, E [0,1]. Ignoring polynomial terms independent of e, we can bound the sample complexity (ee,)) of POR-UCRI. when P. is known as follows
δ ( pddgde
where dg := maXheH, dg and de == maxkeH, de
Proof. The proof proceeds in Corollary by plugging Theorem in Lemma 5
29

---

Published as a conference paper at ICLR 2025
E DETAILS AND PROOFS FOR CARDINAL POR-UCBVI
We now describe how we instantiate POR-UCBVI from a generic optimistic algorithm using bonuses. Note that again, this is erucially different from naively summarizing the history define modified state space, since we are separating the use of history summarization for getting bonuses for f from using only the current state while getting bonuses for the Markovian transitions P. Like with confidence sets, it is priori unclear if we can use ideas from optimism to prove guarantees with favorable non-exponential) dependence on the complexity of transitions. In particular, we will note that showing that the bonuses are optimistic would naively need a union bound over the doubly exponential (A set of history-dependent policies, which a non-trivial challenge overcome.
Given a dataset of the first t trajectory samples {Tili=1 and an index h E [H]. we consider the following:
Estimates for POR-UCBVI:
fh-
arg min fuETa
(f(((((((()))))))))))))))))))))) -f,))
We also use the MLE estimate for after I episodes to define Pt( 8, Ne(s.a.5). Ne(s.a)
Now for
((n,8) 2
S log(2)
(og((o define (p) as below:
2n
P||P( ( s, - Pe(.
8, 01 & ())
Recall the definition of our bonus below.
Bonuses for POR-UCBVI. Recall that simple least squares guarantees imply the lemma below.
Lemma 7 (Concentration for fū). Define
MSEA..(fh. f1 =
- (o
(.l..) + Ohe with oh,t 1B 1B+ log( 1) Then fī simulta-
Also define (5) n log
neously satisfies MSF (Sio 1((41)) & Br.t (22zH) for all h,t with probability 5/32.
We use the data from trajectories {T.) to build the confidence sets C+ (6) = -I c₁ (6) with ch ct+1(5) defined below, where (0) = Bn.t (I
(0) = fn Fr MSE.. P((t1) & Bn,e (0)
We first define trajectory dependent bonus term below, with 8 = 3 A - fT((l
max Eu. (8)
-
Note that according to the definition of B, this does not create any exponential dependence in the confidence intervals used to define C++1
5
< 64
loo) + B + m. log(1/6) + ni log(THSA/O)
16SH A
= O(dc + H)
follows by union bound over all trajectory segments and all timesteps that with probability at least 1 - 5/16 and for any trajectory 7 and f. > 1, E Hp.
(M(((b)) (((T))) (T.))
30

---

Published as a conference paper at ICLR 2025
Remark 5. In the case of many popular function classes F, like the linear class FH {T
((T) w & W we can compute "M,{(T[)..) quite easily. In this case THE is given by
((T) w/ | sup w.w'e,
sup w.w'EW,
1|w w v
for suitable quadratic form Ve
[,,(T[[h], 6) induces a trajectory-deeendeer bonus, given by
(T, = Σ
HEH
This in turn induces policy-level bonus (which depends on the transition kernel,, given by:
(, E,-PT (T,
ETNPT
Σ
h
Let us define term E'(s, a, 6) that will be used to define the probability bonus.
H log(6HSA) + Slog H2? log(322
E'(s, a, == min 2, 4
(s,
This induces a trajectory-dependent bonus, given by
H-1 Σ
Mp (T,
as,,
This induces a policy- bonus (which depends on the transition kernel), given by:
H
(p = min E, [bS(T, min
4, Er
Σ
(sn, an. 8)
Estimates and Bonuses in case P. is known. P. is instead known, keep fr and (F 8) the same above, but set P. P. and (P, 8) = 0 for all
For completeness we state POR-UCBVI here, which an instantiation Algorithm the generic optimistic algorithm using bonuses.
Algorithm POR-UCBVI
Input Known family of reward functions (R+) methods Est(D) to estimate P, and fr from dataset D, confidence level
2: Initialize D2 + {). initialize fP..Pp P.D, arbitrarily.
3: for = 1, ..., do
4: Compute optimistic history dependent policy,
me arg max ((P,. f x) + (P,,, + (P,
5: Observe trajectory = ((s), af)) h-1 and feedback (on)nE
6: Compute new estimates fi+] Pren Est(Dr+1) and compute new bonus functions
(ft+1 b,, (f
7: end for
We will show the following regret bound.
31

---

Published as a conference paper at ICLR 2025
Theorem 8 (POR-UCBVI Regret). Under Assumption
satisfies Assumption 4 and its
regret (egret(T) is bounded by the following with probability at least ignoring polynomial terms independent of
((POIEL.SAA)+
δ (OLLH,,,)+
Σ Vdraaldas + H) hE?r
+H)
VT
where S,H,S,A) == HVSA+ + SVHA
E.1 SHOWING THAT ASSUMPTION 4 IS SATISFIED
E.1.1 BOUNDING EFFECT OF ERROR F
Lemma 13 (Bounding f' Value Error). Given any P. with fc computed using data from (Ti)
PT for any sequence of policies ni using least squares, the following holds with probability 1 8/16 uniformly over all π.
[VP, ft 7) V(P, ((P.ff. m) (P,
Proof. Recall that with probability at least 5/16, the following holds for any trajectory t and any t t 1, Hp.
- - FA(TADI (m.((T(h),
(4)
Now note the following ieqqullities, where (1) holds with probability 1 8/16 uniformly over all policies due to inequality abooe.
V(P - ET-OY
Σ
[M(T(A) [M(T(M)
kEHl
Enapo
Σ m,,(T((1,,
heHp
() (T
Lemma (Bounding Sum JF Bonuses). The following holds with probability
BdE Σ Vdensenrrr BpVTlog(11
Σ N
ReH,
Proof. First note the following inequality, which hold with probability 5/116 by the Azuma- Hoeffding inequality.
T
T (P . Te. T)
Σ Eq-p7
Σ NEHt
Te. (T((T(1),6))
no. (T[h],) + (BBVTToo(T/8)
h
Now apply Lemma 3 in (Chan et al. 2021) for each h separately, with the function class in the lemma
set to (a Su Fa), P 1, X Xt,1 7a rh(h)] and misspecification 0 (decoupled from the
32

---

Published as a conference paper at ICLR 2025
Eluder dimension's E). We also note that of, n-subgaussian samples with mean (ff(())))) We obtain
max ((f((TA)) - & o (Bde (6
O( + v dg).
where d = dimg (Frs B)
7') is the Eluder dimension of Fi and Ba,r(0) = 3 2
Since the
Lipschitz constant of 5ー is we have that the following holds with probability 1.
T
mA(T(1),0) & o O + #2 dE..n.r(8)))
This implies that the following holds with probability 1 - 8/166.
T
T
Σ
by (P., te. 6)
Σ
Ye.h ne, (T[[),))) + + (Bog(//)(
he
Σ ho
BR2dE,1+
Σ
x2y ww dEN + Bpy T (og(T/8)
heHp
E.1 BOUNDING EFFECT OF ERROR P We now restate Lemma B.2 of Chatterji et al. 2021 in our notation.
Lemma 15 (Change of Measure Inequality). For any function p. of trajectories bounded by D, if Pe computed from data that includes trajectories {n. P. for any sequence of policies Tú then the following holds uniformly over all policies with probability 8/16.
E.~p:La(Ti P. Lu(T)] 2og/log(D)bs) 7,)
The same statement holds if we switch the roles of P and PP, on both sides.
Proof
For the order of and PP in the statement, the following follows from Lemma B.2 of Chatterji
al. 2021 with v D and p. We pull the additive log( D) in the square root outside to fit our
assumption'' phrasing.
1 - [n(T]] (o)bb T,) 22
& loD//og(D)bbpp) m)
The only subtlety is that more data than that from {Ti could have been used to compute P,, The proof still follows since cp(PPe e, D) is decreasing in the counts (2,s,a).
Finally, if switch IP and iP, on both sides, and Pr switched everywhere, except for the martingale argument. There, instead of switching the two transition kernels, we negate the martingale to get our desired result. This exception because we still need the expectation be over the true transition kernel P. for the stochastic process defined to be a martingale.
follow the proof of Lemma B.2 verbatim with P
Lemma 16 (Bounding P. Value Error), Consider any sequence of functions f that induce value functions ((P, ff,m). For any sequence of policies Te, if the estimates Pe, bonuses by and costs op are generated using data including that of T; px. over and over all policies with probability 8/16.
t, then the following holds uniformly
V(Pr, V(P.,
Bpy Bpylog (b)
The statement also holds if we switch P. and IP..
33

---

Published as a conference paper at ICLR 2025
Proof. Note the following two inequalities that immediately follow from Lemma 15
V(P., - V(P,, f", m) < Spy/oo((BB) (P,,, T, 6)) v(P,, (L. f x) < Bpy (b) 8))
Our result follows immediately.
Lemma 17 (Bounding Sum of P Bonuses). The following holds with probability 8/1 whenever the data used compute bp (P, n, 8) includes the data of trajectories T; t t.
T bp (P. nr, o (SACs C
where
H (og((HHS)) + + Sog 8f H + Nr
0. :- 0=:=4M \V
2
This means that for any 8, (s, a, 5) until (e (s, a)
Proof. First note that by the definition of the bonus and the Azuma- quema-Hoeffding inequality, we have the following.
T
T
Up (P
TT, 8)
P (T((,
bp 8) + (
T H-1
Now note that the first inequality holds even if more data beyond that of (TeM=1 is used to compute (s, a, 0), since g'(s, a, is decreasing in No(s,a).
T
H
T
H-1
Eoh a/. 8) SAcs +
Cs
Ne(o
(t)
Nr(s.a)
SACs + C8
Σ
Σ
VI
(s.a)ESKA
& SAAc + 278
Σ
V
VNr(s,a)
(8.0)ESxA
SAAcs + 268
SA
Σ
Nr(s,
(a.))SxAA
O (SACs + SATH
This concludes our proof, since (SS))
E.1.3 PUTTING EVERYTHING TOGETHER
Theorem 8 (POR-UCBVI Regret). Under Assumption POR-UCBVI satisfies Assumption 4 fand its
regret (T) is bounded by the following with probubility at least 8, ignoring polynomial terms independent T.
δ ((
((OCLH.S.A)+
+ Σ Vddnnddn + H) VT h
where C(H,S, A) HVSA SVHA
34

---

Published as a conference paper at ICLR 2025
Proof. Note that by Lemmas
13
14
15 16
Assumption 4 is satisfied by POR-UCBVI Using
Theorem and Lemmas 14 and
17 we have the following.
B + BpHS Ads + Regret (T) = o Σ
Σ
K2,2 dr.
b
heH,
+ Bpy B B,
We further refine grouping terms and ignoring terms independent T, and also noting that Es O(VH + vS) as well as (6) = O(dc, + H)
Regret(T)) =6
Σ HEHR
M2y dEN.ddNN + H) + S VT
SINNSA++SVAA)
E heHp
Vdeandea + H) VT
From the latter we derive sample complexity result as follows.
Corollary 4 (POR-UCBVI Sample complexity). Let 0, [0, Ignoring polynomial terms independent of E, we can bound the sample complexity N(E of POR- EER-UCBVI as follows
δ p HS max H.
+ p² dE max(de, H) log(1/5)
2²
where dg maXkeH, d and de max dc
Proof. We invoke the regret-to-PAC PPC conversion in Lemma with confidence 8' 5/2 and we plug the regret bound in Theorem g to write
Ō (IBAENSAA+ (AAHUSAASVHAA) SVHA)+
Σ Vd + Bpvlog((/8)) kEH,
1 VT
from which we get the result by noting N p7 and the definition of dg de.
We also have the following theorem and corollary, in the same vein as Theorem
Theorem 9 (Regret for POR-UCBVI if is Known). When P. is known, POR- UCBVI that sets :.:= P. and Dsp (P, πδ) for all still satisfies Assumption 4 and its regret Regret (T") is bounded by the the following with probability at least 1 - 5, ignoring terms independent of T.
((I)
VdE,(dox + 11) +11 Ne
Σ
VT
where dr,r, dime (Fhs #
Proof. Note that by Lemmas 13 and 14 Assumption is satisfied by POR-UCBVI. Using Lemma 14 we have the following.
Regret(T) O
Σ
BrodE. +
den Bpy Spy/Tlog(T//
kEcH
keRp
35

---

Published as a conference paper at ICLR 2025
We further refine it grouping terms and ignoring terms independent of T, and also noting that G8 O(VH VS)
((I
(Tg 0
Σ
nay (6) Bp VT
hEHY
o
Bp VdE,Shor(0) vT
h
Σ HEMP
V dE,AldON + H)
VT
Corollary 5 (POR-UCBVI Sample complexity P. Known). Let 0, [o. 1]. Ignoring polynomial terms independent o, we can bound the sample complexity (ee, of POR-UCBVI when P. known as follows
δ 0² (D'Hdg max(de.
where dg maXheH, dg B maNhEH, (T, and de := maX de,h-
Proof. The proof proceeds as in Corollary by plugging Theorem in Lemmal
36

---

Published as a conference paper at ICLR 2025
F EXTENSION TO GENERAL FUNCTION APPROXIMATION FOR PROBABILITY TRANSITIONS
Note that for simplicity of exposition and proofs, the confidence for P in POR-UCRL and the bonuses for P in POR-UCBVI are given for tabular observed states and actions 8, a. The function approximation using and F is relegated the effect of latent states u. Using the work of Liu et al. (2022b), it is quite straightforward to extend and modify the proofs here to general function approximation for P.
Let us assume that we have set of parameters θ and mapping from 0 θ to probability transition functions Fg P so that the image of @ under this mapping all of These functions Pg mapping from 8, to distributions over 8' act
featurization 6(8, a) of 8, This is the most general function approximation setting for probability transition functions. Linear MDPs, tabular MDPs, factored MDPs, kernel linear MDPs, and many other function approximation settings special cases this.
For convenience of notation, we will occasionally drop the subscript 0. It is beneficial to remember that throughout this section, we are working under general function approximation nevertheless.
F.1 POR-UCRI.
For POR-UCRL, we redefine the confidence sets to the ones in Algorithm 2 (reward-free OMLE) in Liu et al. (2022b). That is, we first recursively define D++1 D; o {(TT,, instead of just appending 7. We also recursively define 5p(D++1, 6) below. Note that we merely rephrased the definition in Liu et al. (2022b) to use the negative logllikeldoood instead of the log-likelihood.
Cp(P:+1,))
Cp(Dr,)) 0=0
Σ
log( -log(P5(T)) min Σ
-log(P7(7)) +
(x,T)EDe41
(x,r)EDe+1
We now simply need to replace Lemma with version involving function approximation. Recall the following.
VPP, f Epaeps
Σ (T(TT))
= -Ep'apre
Σ PA((())
hEHtp
So. by a simple change of measure inequality and the fact that [f]] < B for all h, we have the following.
(T, V(P., ("...f.mm) .m) Bpdrv (P7,
(5)
Where drv represents the TV distance taken over all trajectories of length H. This implies the following.
Σ -(P.)) & Bp Σ drv (P:
Now, have options. We can either the distributional eluder dimension directly, use the strong SAIL condition Liu et al.] (20226). The former is more flexible and allows us to address all function approximation scenarios. The latter approach has very crisp guarantees and is still satisfied by most function approximation models.
F.1.1 USE THE DISTRIBUTIONAL ELUDER DIMENSION
Note that by proposition B.2 and step 2 of the proof of Theorem 3.2 in Liu et al. (2022b), we have the following upon setting (T) in their proofs. This way, are not running any extra
37

---

Published as a conference paper at ICLR 2025
"exploratory" policies every step.
c pak P..) & 0
(6)
Here, 3
+ clog(T/O)) where Nor,p(E) is the e-bracketing number of (Pe leee as in definition 2.2 of Liu et al. (002b), and e is a universal constant.
Now, consider the functions oi defined on the space of policies by (T) dF PT). Define Hy to be the Dirac-delta measures on 7t. Let the class of Dirac-delta measures over policies be Dn. and let the class of possible o, functions be ②. Let dg.p be the corresponding distributional Eluder dimension dimpg @b Dn. /I/T), as defined in Jin et al. (2021). Then by equation and the properties of the distributional Eluder dimension (Lemma 41 Jin et al. (02I), we have the following.
Σ drv (P (P.)) de,
We can further define dc = log (r (1/T)) to be the bracketing dimension of P. By equation have the following.
V(P,, m²) V(P., TT) & Ö(VdE,P331
We can now follow the rest of the proof for the guarantee for POR-UCRL verbatim and establish the following bound on POR-UCRL regret.
Theorem 10. Consider the functions dh defined on the space of policies by (e(T) dry (PT IPT). Define he to be the Dirac-delta measures on nt. Let the class of Dirac-delta measures over policies be Du, and let the class of possible de functions be h. Let dg.p be the corresponding distributional Eluder dimension dimpE Φ Dus Pu.V/I/1 I/TT). Define dc,p = log (N
to be the bracketing dimension of P. Then, Then, we have the following bound for the regret of our modified POR-UCRL. algorithm, with probability 1- 8.
Regret(T) - ((NVERAAer
+ Σ Vde,ndo,
VT
hEHp
Future work investigate the choice of the distribution class Dn and make other technical tweaks to obtain crisper versions of the dg.p defined here.
F.1.2 USE THE STRONG SAIL CONDITION
We make a minor modification to the POR-UCRI algorithm in the spirit of Algorithm 2 (reward-free OMLE) Liu al. (2022b) use this condition. Instead merely running TT, we run all policies in an exploratory set leep of size 1eep every time we collect trajectories. Recall that the strong SAIL condition Liu al. 2022bb is satisfied by well conditioned PSRs, factored MDPs, kernel linear MDPs, sparse linear bandits, etc. These automatically subsume tabular MDPs and linear MDPs.
Assume that our model class satisfies the (v/ ds,p, K, C) strong SAIL condition. That is, we define ds,p : d² for the d the original strong SAII. condition. Now by theorem 7.2 of Liu (0022)). we can conclude that since P. E (D)
we have that
Cl t
Hexpp
drv (TT PT.) & poly( H) ds.p
+ K
log (1 Tespl
Here, = clog(Nor, (1/T) + e (5)), where (or; is the e-bracketing number of P [Po and is universal constant, Adding these up across and discarding logarithmic terms, we get the following.
Bp d PT.) = =ō (poty(()) Bpn d 2T
38

---

Published as a conference paper at ICLR 2025
This means that by equation 5 we have the following.
Σ v(Pr,, 1" me) V(P.. = δ (Doly(()) Bpk ds. loxp 2T
Let us also define dc,r (rr(NNr,((1/T) to be the bracketing dimension of P. We can now follow the rest of the proof for the guarantee for POR-UCRI. verbatim and get the following bound on POR-UCRL regret, with the caveat that we are ignoring the contribution of the non-optimal exploratory policies. We have thus established the following theorem.
Theorem 11. Assume that our model class P satisfies the (yds, K. C) strong SAIL condition.
Define dc log(Nur,p) (1/T)) ) to be the bracketing dimension of Then, we have the following bound for the regret of our modified POR-UCRL algorithm, with probubility 6.
(
RTg =
Σ hEH,
VdE.Ado VT
F.2 POR-UCBVI
Again, we start with confidence sets that we will use to define the bonuses. That is, we define the confidence sets to be the ones in Algorithm 2 (reward-free free OMLE) in Liu et al. (2022b). That is, first recursively define Di+1 == D; o { T.] instead of just appending тr We also recursively define C 8) below. Note that merely rephrased the definition in Liu et al. (2022b) to the negative log-likelihood instead of the log-likelihood.
Cp((:+1,))
Cp(Di, n AE
Σ
- -log(P
& min
Σ log((P 8
(s,1))DD111
(s,r)eDD11
Defining bonuses is trickier than defining confidence sets. Like the case of POR-UCRL above, have two options again - we can use the distributional Eluder dimension or the strong SAIL condition. While it is possible to work out the details for the former, they much not cover significantly more useful examples than those covered by the strong SAIL condition. So, will focus the latter. This is especially true when considering sample complexity, since the use of exploratory policies under the strong SAIL condition creates no complications in giving sample complexity guarantees, unlike it does for regret guarantees.
involved and do
F.2.1 USING THE STRONG SAIL CONDITION
Again, make minor modification to the COR-UCBVI algorithm in the spirit of Algorithm 2 (reward-free OMLE) in Liu et al. (2022b) to use this condition. Instead of merely running m. we all policies in exploratory recall that the strong SAIL condition of Liu et al. (2022b) is satisfied by well conditioned PSRs, factored MDPs, kernel linear MDPs, sparse linear bandits, etc. These automatically subsume tabular MDPs and linear MDPs.
IT exp (t) of size TTxp every time collect trajectories. Again,
Let Pt be the MLE model time Assume that our model class satisfies the (vds, K, C) strong SAIL. condition. That is, we define ds,p := d for the in the original strong SAIL. condition. Now by theorem 7.2 Liu et al. (2022b). we can conclude that since Pt E Cp,,,, 5), we have that the following holds with probability
ClTppl
Texpl log (t/lllexp)
max drv (P).P.) P?)) < poly H1) ds.p
+ KV
Here, 3 = c cloggooinnn clo((Ni,,,(()/T + e log(T/5), where (() is the e-bracketing number of P [Pa heee and is universal constant. By a simple change of measure, for any policy म, we have the following.
V(PP,, V(P., ( (p,rr(P,,,
39

---

Published as a conference paper at ICLR 2025
holds for any policy with probability the following holds simultaneously for all policies with probability 6.
lxxp
-(P,,, & poly(H)BBy ds.p
VV
log (t./ [t/[llexpl
Define the right hand side as the bonus 65 n. 6). Adding these up across t and discarding logarithmic terms, get the following.
Σ 0) - (oly(H) ds.p Texpp1 2T
This means that by equation
5 we have the following.
Σ mT) -)) V = =ō - B ds. Ieepp 2T
Let us also define dc.p- log(Nor, ((1/T) to be the bracketing dimension of P. We can now follow the of the proof for the guarantee for POR-UCBVI verbatim and get bound POR-UCBVI regret, with the caveat that we are ignoring the contribution of the non-optimal exploratory policies. We have thus established the following theorem.
Theorem 12. Assume that our model class P satisfies the (ydg,p, C) strong SAIL condition.
Define d log(Nor,,p) ((//T)) ) to be the bracketing dimension of Then, we have the following bound for the regret of our modified COR-UCBVI algorithm, with probability 8-
(( (poly(()) (pn pel.
RTg
Σ VdE,do, NEM,
VT
F.3 DUBLING PORRL
We have the following immediate corollary of Theorem Theorem 10 and Lemma
Corollary (Dueling Regret using modified POR-UCRL Confidence Sets). Consider the functions &e defined on the space of policies by @e(TT) == drv (P, (P;; ,P)). Define μt to be the Dirac-delta measures Te- Let the class of Dirac-delta measures over policies be DDT, and let the class of possible &e functions be t. Let dr.p be the corresponding distributional Eluder dimension dimpe( Th Du. (1/T). Define de.p
log( (1g(N) to be the bracketing dimension of P. Then, the modified confidence sets for POR- FOR-UCRL described in section F.T.I satisfy Assumption 2 and using them in Algorithm leads to the following dueling regret bound with probability 1 8.
Regret (() δ
+ Σ dde,ddhh T NEH,
Similar corollaries can be immediately produced for the strong SAIL method, whenever [eexxl = 1.
The strong SAIL method doesn't quite work for dueling regret guarantees when [lxxp] 1, must stick to the distributional eluder dimension in that case.
40

---

Published as a conference paper at ICLR 2025
G DETAILS AND PROOFS FOR PORRL WITH GOLF
For completeness and establishing notation, we recall GOLF here.
Algorithm 7 GOLF
1: Input Known class of Bellman consistent Q-functions 2, confidence level 8.
2: Initialize dataset D < 0 and Co(D1, Q.
3: for = 1, 1,... 7 do
4: r[0] -
5: for h I. do
6: Compute a Q - arg (PCP..))) ((T[4],a)
7: Play aj and observe feedback of
8: end for
9: Update Di+1 - Dj u (T,
10:
Compute
Co (Cs Qu+1) & inf Lo, Qu+1) 3
gest.
11: end for
Theorem 2 (Modified GOLF Regret), Let Assumption 7 hold, let Q be Bellman complete, let
dHABE = dimHABE Q, a, min(a, VI/T)) and let dc == log(N(Q G. 1/1 )lo)))) Choose hyperparameter 3 (llog(H)) + dc, e) for some universal constant and the auxiliary function class 9 used GOLE, and define. Then, GOLF satisfies Regret(T) O (pH duuBedd..T))
Proof. The meat of the theorem is in proving Lemma 18
We 3 = c ( 1/1/T.11 llw)
for some suitably large universal constant c, and use Theorem and Lemma 18 get that
H Σ
B²p²B a²
Regrot(T))
Tw + Bp
+ +1)
d((a) + min(d, (w), By 2Bpv (dn(w)
where (e) dimpa pn, Dry E). Now set decreasing e to get that
Be and use the fact that (s) increases with 7
Regret(T) = Ö (pH dHAREBT
= O (THABBCCCC
since dHABE dimHABr(Q, min(a, Bp/T)) max, da (min(a, Bp/T)).
Corollary (GOLF Sample complexity). Let e > 0, E [0. 1]. Ignoring polynomial terms indepen- dent of e, we can bound the sample complexity (), of GOLF as follows
p H dHABEde
δ
Proof. Again, we use Lemma and quick computation shows our result.
G.1 COMPARING dİmHABE dimpE
It is easy see that since the function class 42 is subset of the class VA of all Bellman errors, dimμАBE & max, dimpg L,, D,, over the RHS and another term that uses Dirac-8 distributions, but typically, the RHS is smaller. So, in many cases, dimbABE & dimpe- However, we don't 't have a universal inequality in either direction.
Q, E). Recall that the Bellman eluder dimension a minimum
41

---

Published as a conference paper at ICLR 2025
G.2 COMPUTING DIMENSIONS FOR THE COMBINATION LOCK
Proposition (Dimensions for the Combination Lock), Consider the combination lock problem with model class M = P x F and induced Q-function class Q.
Under dense intermediate feedback with Hp = [H]] dimhABE( Q, = Afror all a < q, while its BE dimension is at least A" 2. The eluder dimension for reward functions dimg(Fu, By is at least A for any h & H.
For sparse intermediate feedback with Hp } and any a > the a-HABB dimension, the BE dimension and the eluder dimension of Fu are all at least A -2. Moreover, any algorithm in this setting will have regret Q(V AT)).
Proof. We separately resolve the cases of sparse and dense intermediate feedback.
G.2.1 DENSE INTERMEDIATE FEEDBACK, Hp [H]
Notice that we get a reward Ber(g) at every step as long as we are on the correct sequence of actions
ai.... dig. and soon we take wrong action, we always get a reward of 0 subsequently. is then
easy to see that the induced function classes Q then are given by Q = {Q QH) Eai.... ag
A s.t. Qn (H- h + 1)gla.....e.
a --BABB dimension: It suffices to show the upper bound using Dr, ((a,h 1), since the a- a-HABE dimension takes the minimum distirbutional eluder dimensions over two distributions. For any < q. consider the function class
a(a. 1) (Q (QE Q, [= TiQ++1] & A1 & (ellhhhi &1
Now note that (Q)[Q) TiQ++1] = glai....r o1l q....... If this is smaller than a, then this is smaller than q and thus must be 0. So, (a,,... 04-1) (ai, ( -111) for any 2(a, h 1). This also means that any @n 4/, there is Q Q(a, h 1) that
Φh Qn ThQu+1 qll 1
at
Thus, the size of t is just A. More importantly, the set DA, P(1,(a)) of distributions 14,(() (Q) induced by Q E Q(a, - 1) only include indicators of the form La;....0 for actions a. Thus, the set of distributions h-( has size A. We know that the distributional eluder dimension = dimpe( ( DD(.AA1)) min(a, T)) bounded by the number of possible distributions [Do(a, So, d & A.
BE dimension: The Bellman differences, from above, q qlay.... af...... This is affine transformation of family of A indicator functions. The distributions ((()) over trajectories induced by Q include indicators La.....af of all trajectories of length t. Now for any sequence ...... Mny pn of different indicator distributions not including ai....u; a/. we consider the Bellman difference #1+1 yllaj...... - .....;, with action sequence given by Mo++1. Note that E for all i & but IF "u.111h In+1 q. This means that the longest possible sequence in the definition of the distributional eluder dimension has length A 2. So, the BE dimension is least A 2.
The reward function class F, is given by all functions the form gla al......... This is scaled version of a class of A indicator functions. Since it contains A indicator functions, its eluder dimension is at least A
Eluder dimension:
G.2.2 SPARSE INTERMEDIATE FEEDBACK, H,p [H]
Notice that we get reward Ber(g) at the last step if took correct sequence of actions aj ..... air- and reward O otherwise. It is then easy to see that now, the induced function classes Q then are given by Q {(Q1.... QH) E0i.... aи E A s.t. Q qla)....aa)
a- --ABBE dimension: This time, note that Ep., [Q: Ta 2+4+l = 0 for all h < H - 1. So.
the function class 4, (0) for all h & H - 1. Only for ft = H do we have that Enr(Q)) @=1 = qlle.....a - Laa ...,, Also note that @(a, H - 1) = Q for all a since (,), T1 = 0 for all < H 1. So, this is merely the BE dimension of the problem. Now, the Bellman differences at timestep H are identical to those for the sparse feedback problem, and the
42

---

Published as a conference paper at ICLR 2025
distributions Do
H)1 ( De since have established that ((a, H 1) Q. This means that by the argument for BE dimension in the dense feedback case, we have that the distributional eluder dimension of 2, f is at least A which is then also the a-HABE dimension of this problem.
BE dimension: From the argument for the a-HABE dimension in the sparse case, the BE dimension and the a-HABE dimension match in this case, and both at least A - 2.
Eluder dimension: Again, the reward function class FH is given by all functions of the form qla.....a. This is a scaled version of class of A indicator functions. Since it contains A
indicator functions, its cluder dimension is at least A"
Also note that this example also produces a universal lower bound of ((A")) under any algorithm.. That is, algorithm can improve our bounds under sparse feedback. This lower bound is an immediate consequence of regret lower bounds for bandit algorithms by treating each sequence of actions taken different arm.
G.3 PROOFS LEMMAS
Recall that Q(a, h) IQ Q (q) TQQ+11l a, V1 & 1), that n4 (Q) is the distribution induced on r(h 1], an by To and Dn,2 == {um (Q) Q º).
Lemma 18. Let (e( = dimpe ph D ((a.) with
t : - Th
Th Q Q
Q 2(a h -11
Then, we have that for B e ( (lx))) Σj 1i=nlEnn(es)100 Th is bounded by
B²p²3 a²
h
+ Bp
+
Σ
di(a) + min(da(w)), B) 2Bpv (dn
Proof. We modify the proof of Lemma 41 Jin al. 2021). Pick arbitrary h and and let Vr be the function class given by
t = Qn - TnQu+i Q 1(a,1))
en TnQ (Q,,... ... (Q.....QHH) 2. 2.I -|Q(=]+ & a, & h
Also note that have the function class + of timestep Bellman enrors induced by "historically a-accurate" functions functions whose expected Bellman errors in previous timesteps are smaller than a. The distribution used for computing the expected Bellman errors for previous timesteps is (Q)..
Now abbreviating w// = Ø TIQ gives sequence w/.... of of functions in V for every 1 & 1 & h. This must have subsequence of.... of consisting of all the functions in the sequence that lie in L,, for every I & h. Also let d, = dim (h,, Dr. E) for any E. Now note that
F TA
E [
Em (IEm)CQUlvHI) < w)
E Em
43

---

Published as a conference paper at ICLR 2025
Faacor (IEm)O))(()) > w. QE 2(a, h -11) 1))
Em. 1 (Q 2(a.1-1)((a.))
Fmacon (Emmte) w. Qe o(a, h-1, 1))
E ceo.l ( 2(al--))
< tw +
Em. 1 (Emnce)tvi))> w, aaa,h-n11 11)
E Enncen (Immes)((())> > a)
Σ
[us [ohd| (Iancosllol)
+
(0
tw + Bp
B2p23 +1)
Σ d((a) +
1u (1mm w)
a²
Here, (1) holds since one of three possibilities holds either [m & w. or (m > w and there least &
so that Q E Q(a, I 1) but Q $ Q(a h -1, 1), or Q E Q(a h 1). (ii) holds since (Q) Vil < a for all & < - 1, then ui = of for some i. Finally, (iii) holds by Proposition 43 of Jin et al. (2021) since Σ ( & 3 by Lemma ()) of Jin et al. stochastic and theirs are not,
(2021). While our rewards after noting that the martingale defined in the beginning of their proof continues to be a martingale even for stochastic rewards that have second moments.
repeat their arguments verbatim
Now arrange the sequence (Q)))o)) in order to get e1, CrA. We can then write
B2p28
Em. Th < tw Bp
Σ d((a) + Σ
Le, > w)
a²
For any ej >> w, consider arbitrary y such that ej > y > w. This means that by Proposition 43 of Jin al. (02T) again,
B²p23 72
j &
I(e 7) &
+1 da (w(
This means that 7 < Bpg
Bda (w) (w)
for any such 7. Since ej & Bp. we get that ej <
min
[d,(ww) Bp, Bpy (w)) Finally, this means that
1
B2p23
&ww + Bp
+1)
Σ di(a)
+
e w)
a
B2222
/-1
(d)(ww) Bp, Bpn
& fw Bp
+1)
Σ di(
+
Σ min
a²
j j- (dwww)
44

---

Published as a conference paper at ICLR 2025
B3p'3
Bda(w)
& tw + Bp
+1)
Σ di(a)
+ +min(da, 1h Bp +
Σ
Bp
a²
j
j-1
B2
E lw + Bp
+1)
Σ di(a)
min( + 2Bp (w)
a²
B²
& ll + By
+1
- de(ax)
min(d + 2By (dn(ww)
Q
as desired.
45

---

Published as a conference paper at ICLR 2025
H PROOFS FOR DUELING FEEDBACK
H.1 PROOF FOR REDUCTION TO CONFIDENCE- OPTIMISM
Theorem (Reduction from Dueling to Confidence- Set- Optimism), If the confidence seis then the dueling regret Regret ((T) of Algorithm iis given by
Cm(D:, 8) satisfy Assumption 2
Regret +
Remark 6. While the theorem states that we need Assumption 2 from the main paper, we actually its slightly more refined version Assumption 3 The less refined version added to the main paper for brevity.
Proof. For ease of notation, let us use the sets CD(DD. 6) given by the pre-image of CG (D,, 8) under We first recall that M, CM, 5) and so T, IT, for all t with probability 1 - 8/16. Recall that the value of duel (x, r²) under model M c- is denoted by
the map M - M from Section 4
VD n, T') (MM, m) V(M, x²) (PP, V(P, "UP,9.T. 9')
We overload notation and use the natural maps (P <> - M to define
VM, m²) :- VD M, ,.
For case of notation, we will then work with CM( in this proof until we can. Since ni. E II for i 1, 2. there exists some Mi, E CM(D,, 8) for 1, so that VD म. T1,1) < for all x. Note that ducling regret is given below. Inequality (i) is by definition of M2,,, since V (M T. Ti,) & for 2. Inequality (ii) holds by definition of T1, N22
T
Regret (7) = Σ
(M,,, (..
1=1
T
2
VD(M, TH, T4,) (M,,,, TTp)) +
V (T,
T
Σ
(M., T.. me)) - VT,
T.
(40)
T
max (D,,))
VD(M, VD(M T1,, +2.)]
Continuing, have
Regret c
max
[VD(M, T2,) m1, [2,e]
M, (DD,
2
max
VD(M, VI,,,, + VD(M,, 11,,, T2,)
(.
MM,M,,,,,,,,22. T224)
<
max
[VD T2,) +1,n
(.
(MD,MM, VD m., [21]
(D..CM(DD..)
2 Σ ( )2,1 (M,
VD(M., T1 FL, T2.)) VD(M% 11,0 T2,e)
46

---

Published as a conference paper at ICLR 2025
where Mj and M are the respective maximisers. It suffices to analyse only one of the terms, consequence of the symmetry of Assumption
We can now use the fact that M is described by (P, f) to analyse the first term, letting M, - (Pr. Po.
Σ
VD(M,, Ti, m2 (D M1,, T2,1]
T
Σ
<
2
Vo(PP, - ,1,,
VD(P.. Pi mT. m2,1) T1 fL T2,1)
2
Σ
MM M1, V..a (D S", F T2,1
@
V(P. -VUP., m2.1)
VD( P. m,,, VD fm, (2,1)
(it)
V n1,1 -
V(P,, M, T2,1) -2.) V(P.. (. m2.)
V(P. &P.. P...7 (m,,,, V(P. P., ( (2.,))22)))
Where (i) holds by the definition of VD and V, and (ii) holds in the product MDP FT, once we define Ft [M]] = [k]] ( [h]] and recall that P. P. P.. Now, we can immediately apply Assumption 3 the last line in two different ways. For the first two terms, we apply the first point in the assumption to each under cardinal feedback for MDP M., noting that the datasets D, contain trajectories from TI. well 22 For the last term, we apply the second point in the assumption under cardinal feedback for the MDP (F.,7".
This gives us that with probability 1 - 8,
Regret(T) Ö(Cr(M,T,O) + Cr(,,T,6)
We have the following lemma, which is an immediate consequence of Lemma (Relating J and F). For any function class F, dimm((Fee) 99 dimm(F,ee2))
Proof. Let d (Fm. Pick the e' that there a sequence d, pairs T,, length l trajectories, where each one is siindeeeendd of its predecessors. Note that F; (Ti.s T2.)). now inductively build a sequence i, so that each Ti is s /2-independent of its predecessors.
d of
Pick the first i arbitrarily. Now assume that we have built the sequence until index k. Also, by definition of this sequence, there exist F,. we have V ((,,)) & e' but [F&+((T)) - -F > e'. Since a² 62 < 2(a + b)2, we have that
Σ (f)(T)))))) fT) &
Σ -11(7,,)) (fa(T-15a)) f((Ta-1,5))2
Σ - & V26'
47

---

Published as a conference paper at ICLR 2025
Additionally, since
( 1 (TI, (T=,0(22 (7221)))1111 [J++((T)) (((=))-(+i((T))) [
So, there an ig+1 so that
|fe+1 (TrrIaA1)))) (Ten((T(11)1)) E'12
So, we have a sequence 2j == Tiy.j and sequence of pairs of functions fn> fJ so that for any
1 k dn. (f))) f),)) f(ay)) < 2(=²)² but [f<+1(I<+1) fk+ (I++1) 1)1 > e'/2. This
implies the following. Inequality (i) holds by Proposition 43 of Jin et al. 2021 upon setting
2(=")² and setting the proposition's e to e'/2. Inequality (ii) holds since E / E/2.
f}(x5)1 d/22) dx Σ 1
2(E')²
+1) dimm(Fn,e/2)
(c//2)2
9 dim (Fr,E'12)
= 9 (Fr:
This establishes our claim.
We have the following immediate corollary of Theorem Theorem and Lemma 2
Corollary (Dueling Regret using POR-UCRL Confidence Sets). The confidence sets from POR-
UCRL satisfy Assumption 2 and using them in Algorithm 7 leads to the following regret bound
Regret, = δ (pSvHA+ EnEn, v /ggnde,)) vT)
48

---

Published as a conference paper at ICLR 2025
H.2 REDUCTION TO BONUS- BASED OPTIMISM
We define the reduction using the algorithm below.
Algorithm 8 Reduction from Dueling Cardinal Bonus-Based Optimism
1: Input Known reward function {rx 1 method Est(D) to estimate P.D and fo from dataset
D, bonus functions (IP,,, ō) and bp n,, 6), confidence level 8.
2: Initialize dataset D1 0
3: for t== I,....? T do
4: Compute good set II,
Valid n, candidates)
II. = { TTE (V aI) bbb (T,
(1,
=2(Bp)bp(Pp.. T, (Bplo)) > 0, vT e e
5: Pick (TI. T2,1) given by
[Most uncertain duel)
arg max by Dr x,, 2(Bp)op(PD,.))) D. 8) + (BB))) n,
D. 11,
#
6: Collect trajectories Ti.
(st (sh,0
along with feedback fon neTt, by sampling
from P for 1,2.
7: Append the data to Dr to get D4+1. update estimates and bonuses.
8: end for
Theorem 13 (Reduction from Dueling Bonus-Based Optimism). If the bonuses and estimates used in Algorithm satisfy Assumption then with probability - 6, the dueling regret Regrel (T)) of Algorithm 8 is given by
Regret
CC(,,T,)))
Proof. Recall that the value of duel (π, 7') under model M M (IP, f) is denoted by
VD T') V(M, x) V(M, x²) V(P f. T) ((P,, ((. r')
We overload notation and use the natural bijection M <> M to define T VD (M, ,|
For ease of notation in the proof, often work with arbitrary pre-image fo of J under the map - J. A careful read will confirm that this does not affect the correctness of any of the statements. First note that n. E II, for all T with probability 1 - 8/16 since the following hold uniformly over all mi
(F,((Pp,; fo.), m)) = V(Pp,, (o, SD.
[V(Po,,o, fD, m1)
S', + +VPP. m1) V(P., n..)
[(P,, v(P f2, mi)
VDD((...Jp)))) m., (P. (p)
2( (B -., 6) + (Pp,)
+0
1 D. (T.,, x))
+ (B mT. 6) Pp (T.,, क ) + 2( Bp) (PP,, +
where the inequality holds by Assumption 4 and the optimality of in the true model. Note let M be the model given by Pr., fo, and let M, be the corresponding model in M. We make the following
49

---

Published as a conference paper at ICLR 2025
abbreviation:
(M, (T,,)',)) : bx De (T, (2b):)))))((((bb(((f(r......... (B (BB))bp(PD,,T T',
Regret (7)
Σ
Tip))
1=
VD (M., Te. mi.)) - VD VD(M,, m,,, mi,)) + d (M,, (T ma,))
VD Ta,) - (T.,
T
VD(M., Tr, TH.. VD(Me, Th. T(e) + (Ma (Te, o1)),
Inequality (1) holds since VD(Me, Ta. Ti,e) VD(( Te, x.), and Ts, E II for 2 implies that
TT,, T.) + by(P (1), + ((B))bb((p,, 5) + 2 B(Bp)b (DD,, $1. 6) > 0
Now note that the following holds uniformly over all timesteps t with probability 1- for i = 1,2 simultaneously using Assumption |
multiple times and applying a union bound.
(D.M., n., Ti,e) - VD(M, .. Ti.)) = VD((P.,,'). n.. mi.)) - VD((PD, p., T,) VD((P.,, F).... t.,)) Te:
VD(( D. (..T7) (o.,Ti,,,, T)),T.. ni,t)
+ VD(((p (o, F), T.,)) - (f D., F T.,, Ti,t)
V(P..J' ,.)) v(P Di, T x.) + v( D. J ((tt) - VPP.," ,,,))
+ VD((P,, F' T., m.,1) - VD (P: D. D.).
2(Bp) bp (P ,., 5) 2 (p) by (fP D. T(,,,
+ (PP, (T.,
bml Me, (Te, Tit))
So, with probability 1 - 366/16, we have that
Regret D (T) x b (M,, M1,1),)
(1)
b (M,, (21,,,
Σ 2(Bp)bo(( (P, ( + (y (2,);
2
Σ (a (Bp))o mI,, (By)b 0) + by (mi,,, ( (2)).
where inequality (t) holds since (T., T2,1) = arg max r'el, (M, (T,, m²), 8) and inequality (ii) holds with probability 35/8 by 6 applications of the change of measure inequality in Assumption
Now, we can use the fact that Assumption iS satisfied again to conclude that with probability 1 8/32.
(Bp)) T1,. 21 (Bp)bp T2,, 8) + ( T2,)..) = (2C+(MM.T.0)+CC((M.....
50

---

Published as a conference paper at ICLR 2025
Taking union bound over all inequalities stated so far, we have the following with probability 1 1- desired.
Regret (T)) C
Again, the following corollary is immediate from Theorem
5
Theorem
9 and Lemma
2
Corollary By using COR-UCBVI as the algorithm in the dueling reduction in Algorithm get bound on the dueling regret given by
we can
(DCITT.SAA++
Regret (T) = =ō
Σ
Ve + H)
VT
b
where dF,r, dimg (Fhs 2T
51


Reviews:
[{"review_id": "2DPVhPPXSi", "reviewer": "Reviewer_Rhuq", "summary": "The paper introduces PORRL a framework that adds internal states and intermediate feedback into Reinforcement Learning from Human Feedback, which can speedup alignment. The authors provide two model-based algorithms POR-UCRL, POR-UCBVI for learning with cardinal feedback, and provide regret bounds for GOLF (a prior model-free algorithm) based on a new history aware bellman eluder dimension “HABE”. They also provide a reduction from duelling to cardinal PORRL.", "questions": "Intermediate feedback at each step requires substantially more human queries than single preferential feedback at the end of an episode. Can you compare your framework's query complexity compared to that in [1, 2]?\n\n[1] How to Query Human Feedback Efficiently in RL?\n\n[2] Reinforcement Learning from Human Feedback with Active Queries", "limitations": "", "rating": 8, "confidence": 4, "soundness": 4, "presentation": 3, "contribution": 4, "strengths": "- The PORRL framework is novel, and their modelling is highly general with non-Markovian transitions. The paper is technically solid and a good contribution in the space of theoretical guarantees for learning from Human feedback.\n- The authors analyse both model-based and model-free algorithms with regret guarantees under cardinal and duelling feedback.", "weaknesses": "The practical takeaways in the conclusion are mainly phrased as conjectures, and the authors do not provide a concrete algorithm within the PORRL framework. Given the strong theoretical contributions, a practical algorithm would have strengthened the work further.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "FWjae6Fwdn", "reviewer": "Reviewer_4dew", "summary": "This paper provides a general formulation for RLHF by introducing humans' internal states. This new framework allows reward and policy to be non-Markovian but still tractable. The authors propose algorithms for both cardinal and dueling feedback and obtain improved regret compared with previous methods. Interestingly, to design model-free algorithms for cardinal feedback, the authors introduce a modified Bellman-eluder dimension, which can be exponentially smaller than the standard Bellman-eluder dimension for the combination lock example. In the end, the authors also propose the first explicit reduction that converts guarantees for cardinal regret to dueling regret.", "questions": "1. On Page 7, three main technical challenges for model-based algorithms are mentioned. Could the authors give brief explanations of how the new design tackles these challenges?\n\n2. The model-free algorithms follow GOLF, which requires Bellman completeness (BC). Does the adaptation here also need BC? If so, I think it is better to explicitly mention it in the main text.\n\n3. For cardinal feedback, the paper assumes it is emitted according to a Bernoulli distribution. Is this assumption also used in previous papers for cardinal feedback? It seems the KTO paper utilizes a more complex feedback model?", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. This paper provides a general RLHF framework covering many important instances.\n2. The proposed algorithms lead to improved regret compared with existing results,\n3. The authors propose the first explicit reduction that converts guarantees for cardinal regret to dueling regret.\n4. A new complexity measure called HABE is proposed, which can be exponentially smaller than the standard Bellman-eluder dimension for the combination lock example.", "weaknesses": "1. The proposed algorithms follow existing frameworks, which are generally computationally inefficient.\n\n2. This paper assumes the internal state generation function $g$ is deterministic. Although this seems reasonable for rigorous math reasoning, it may not capture the complexity of human feedback for more ambiguous casual conversations.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "2HJd4E3hBy", "reviewer": "Reviewer_ExHp", "summary": "This paper studies the problem of reinforcement learning with partially observed reward-states (PORRL). The authors accommodate two kinds of feedback – cardinal and dueling feedback. The authors first demonstrate that PORRL subsumes a wide class of RL problems, including traditional RL, RLHF, and reward machines. For cardinal feedback, the authors present two model-based methods (POR-UCRL, POR-UCBVI). The authors give both cardinal regret and sample complexity guarantees for the methods, showing that they improve over naive history-summarization. The authors then discuss the benefits of a model-free method like GOLF with naive history-summarization in settings with recursive internal states and dense intermediate feedback. For this purpose, the authors define a new history aware version of the Bellman-eluder dimension and give a new guarantee for GOLF in the setting of this paper, which can be exponentially sharper in illustrative examples. For dueling feedback, the authors show that a naive reduction to cardinal feedback fails to achieve sublinear dueling regret. The authors then present the first explicit reduction that converts guarantees for cardinal regret to dueling regret. In both feedback settings, the authors show that the proposed models and guarantees generalize and extend existing ones.", "questions": "Please see the weaknesses above.", "limitations": "", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "1.\tThe authors introduce PORRL, which generalizes current RLHF models to incorporate “internal states” and intermediate feedback.\n2.\tThe authors design model-based optimistic algorithms that, POR-UCRL and POR-UCBVI, and provide regret guarantees under naive history-summarization. The authors further show that their guarantees subsume and improve over past results. \n3.\tThe authors study the model-free algorithm GOLF, applied using history-summarization. The authors establish a regret guarantee for GOLF. The authors also show that when internal states have a recursive structure, their guarantee can be exponentially smaller than existing guarantees and guarantees for their model-based methods.\n4.\tThe authors show that a naive blackbox reduction from dueling to cardinal PORRL always fails. They design a whitebox reduction from dueling PORRL to a large class of optimistic algorithms for cardinal PORRL.", "weaknesses": "1.\tThe writing of this paper needs improvement. This paper is too dense, and hard to follow.\n2.\tThere is no experiment provided. It is hard to validate the effectiveness and implementability of the proposed algorithm, and the provided theoretical results.\n3.\tThe authors should elaborative more on the motivation of combining POMDPs and RLHF, e.g., give 1-2 concrete application scenarios.\n4.\tThe authors should discuss more on the technical novelty in combining POMDPs and RLHF. It looks like a combination of existing POMDP works and preference feedback.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Poster)