Deciding What to Model: Value-Equivalent Sampling for Reinforcement Learning
Authors: Dilip Arumugam
Benjamin Van Roy
Venue: NeurIPS 2022 Accept (2022)
Keywords: Reinforcement learning
Efficient exploration
Information theory
Bayesian reinforcement learning
Value equivalence

Abstract: The quintessential model-based reinforcement-learning agent iteratively refines its estimates or prior beliefs about the true underlying model of the environment. Recent empirical successes in model-based reinforcement learning with function approximation, however, eschew the true model in favor of a surrogate that, while ignoring various facets of the environment, still facilitates effective planning over behaviors. Recently formalized as the value equivalence principle, this algorithmic technique is perhaps unavoidable as real-world reinforcement learning demands consideration of a simple, computationally-bounded agent interacting with an overwhelmingly complex environment, whose underlying dynamics likely exceed the agent's capacity for representation. In this work, we consider the scenario where agent limitations may entirely preclude identifying an exactly value-equivalent model, immediately giving rise to a trade-off between identifying a model that is simple enough to learn while only incurring bounded sub-optimality. To address this problem, we introduce an algorithm that, using rate-distortion theory, iteratively computes an approximately-value-equivalent, lossy compression of the environment which an agent may feasibly target in lieu of the true model. We prove an information-theoretic, Bayesian regret bound for our algorithm that holds for any finite-horizon, episodic sequential decision-making problem. Crucially, our regret bound can be expressed in one of two possible forms, providing a performance guarantee for finding either the simplest model that achieves a desired sub-optimality gap or, alternatively, the best model given a limit on agent capacity.

Deciding What to Model: Value-Equivalent Sampling for Reinforcement Learning
Dilip Arumugam Department of Computer Science Stanford University dilip@cs. stanford.cm edu
Benjamin Van Roy
Department of Electrical Engineering
Department of Management Science & Engineering Stanford University bvr@stanford. edu
Abstract
The quintessential model-based www.forrement-leammnn agent iteratively refines its estimates or prior beliefs about the true underlying model of the environment. Recent empirical successes in model-based reinforcement learning with function approximation, however, eschew the true model in favor of a surrogate that, while ignoring various facets of the environment, still facilitates effective planning over behaviors. Recently formalized as the value equivalence principle, this algorithmic technique is perhaps unavoidable as real-world reinforcement learning demands consideration of a simple, computationally-bonndde whelmingly complex environment, whose underlying dynamics likely exceed the agent's capacity for representation. In this work, we consider the scenario where agent limitations may entirely preclude identifying an exactly value-equivalent model, immediately giving rise to a trade-off between identifying a model that is simple enough to learn while only incurring bounded sub-optimality. To ad- dress this problem, we introduce algorithm that, using rate- rate- distortion theory, iteratively computes an approximately-vain wewtinnttelllllleeeuuueee equiialeuui lossy compression of the environment which an agent may feasibly target in lieu of the true model. We prove an information-theorrticc. Bayesian regret bound for our algorithm that holds for any finite-horizon, episodic sequential decision-make maainn problem. Crucially, our regret bound can be expressed in one of two possible forms, providing a per- formance guarantee for finding either the simplest model that achieves desired sub-optimality gap or, alternatively, the best model given a limit on agent capacity.
agent interacting with over-
Introduction
A central challenge of the reinforcement-leamingg problem [154, 87] is exploration, where a sequential decision-making agent must judiciously balance exploitation of knowledge accumulated thus far against the need to further acquire information for optimal long-term performance. Historically, provably-efficien reinforneementtleamingg algorithms [91, 35, 90, 20, 23, 151, 81, 121, 45, 120, 22, 46, 10, 85, 168, 56, 105] have often relied upon one of two possible mechanisms for addressing the exploration challenge in principled manner: optimism sampling. Briefly, methods in the former category begin with optimistically- for all state-action pairs; an agent acting greedily with respect to these estimates will incentivized to visit all state-action pairs sufficient number of times until this bias dissipates and the agent left with an accurate estimate of the value function for deriving optimal behavior. In contrast, posterior-sampling methods primarily operate based on Thompson sampling [156. 141] whereby the agent begins with a prior belief over the Markov Decision Process (MDP) with which it is interacting and acts optimally with respect to single sample drawn from these beliefs. The resulting experience sampled from the true environment allows the agent to derive a corresponding posterior distribution
the face of uncertainty or posterior
value estimates
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

and this Posterior Sampling for Reinforcement Learning (PSRL) [152] algorithm proceeds iteratively in this manner. eventually arriving at a posterior sharply concentrated around the true environment MDP. While both paradigms have laid down solid theoretical foundations for provably-efficient reinforcement learning, a line of work has demonstrated how posterior-sampling methods can be more favorable both in theory and in practice [121-123, 120, 114, 125, 63].
While existing analyses of reinforcement-leamiin algorithms have largely focused on providing guarantees for learning optimal solutions, real-world reinforcement learning demands consideration agent interacting with an overwhelmingly complex environment [105]. A simplified view of this notion can be succinctly depicted in the multi-armed bandit setting 197, 38, 100]; as the number of arms increases, Thompson sampling agent's 's relentless pursuit of the optimal arm will lead to large regret [138, 139]. On the other hand, one might simply settle for the first s-optimal arm found, for some ε > O, which may be identified in far fewer time periods. The goal of this work is to augment PSRL so as to accommodate these satisficing solutions in addition to optimal ones, paralleling existing work for satisficing in multi-armed bandit problems [140, 139, 15, 16). To help elucidate the utility of satisficing solutions in the reinforeement-learning setting, we offer the following illustrative example:
for www.uuttiiiallloounneeeooo
Example 1 (A Multi-Resolution MDP). For large but fintte N N. consider a sequence of MDPs, {Mo) J which all share a common action space A but vary in state space Sn, reward function, and transition function. Moreover, for each n E [N], the rewards of the nth MDP are bounded in the interval [0,
1.). An agent is confronted with the resulting product MDP, M, defined on the state
space Si X X SN with action space A and rewards summed across the N constituent reward functions. The transition function is defined such that each action E A is executed across all N MDPs simultaneously and the resulting individual transitions are combined into a transition of M.
Example presents simple scenario where, N t oc, complex environment retains a wealth of information and yet, due to the scale of N and the boundedness of rewards for each constituent MDP Mn. only a subset of that information is within the agent's 's reach or even necessary for producing reasonably competent behavior. Despite this fact, PSRL will persistently act to fully identify the transition and reward structure of all Jn for any value of N. Without knowing which MDPs are more important priori and even as data accumulates during learning. PSRL is unable to forego learning granular components of M. eventually accumulating optimal reward at the cost of more time, Intuitively, however, one might anticipate that there exists a value M < N such that learning the subsequence of MDPs (M, [e[[M] in fewer time periods is sufficient for achieving desired degree of sub-optimality, since the rewards of the remaining MDPs {Mr, Jn> M make suitably negligible contributions to the overall rewards of M. Alternatively, for a computationally-boundee decision maker, the agent's 's resource limitations ought to translate into a value C < N such that {M,, J is feasible and learning this subsequence is the best possible outcome under the agent capacity constraints. In this work, we introduce an algorithm that, in a purely data-driven and automated fashion, implicitly identifies such a value M or C' to facilitate tractable, near- near-optimal learning in what may otherwise be an intractable problem. Following Arumugam and Van Roy [15), a key tool for defining notion of satisficing in reinforcement learning will be rate-distortion theory [146, 25].
The paper proceeds as follows:
introduce our problem formulation in Section 3, present our generalization of PSRL in Section 4, and provide a complementary regret analysis in Section 5, Due to space constraints, technical proofs, an overview of related work, and discussion of our results in a broader context are relegated to the appendix.
2 Preliminaries
In this section, we provide brief background on information theory and details on our notation. All random variables are defined on probability space F,FF,P) For any random variable X : Ω + X taking values on the measurable space (X, X), we use (X) a (X- I A E X] C F to denote the r-aleebra generated by X. For any natural number E N, we denote the index set as [N] A 21,,,... .............................. N). For any arbitrary set X, ((X') denotes the set of all probability distributions with support X. For any two arbitrary sets X' and V, we denote the class of all (measurable)
functions mapping from X' to ) as (X - -} )} é (S1/ ʃ X + )). While our exposition throughout the paper will consistently refer to bits of information, will be useful for the purposes of analysis that all logarithms be in basc
2

---

2.1 Information Theory
Here we introduce various concepts in probability theory and information theory used throughout this paper. We encourage readers to consult [41, 71, 129, 59] for more background.
We define the mutual information between any two random variables X, Y through the Kullback- Leibler (KI.) divergence:
flg dP to0
dP aQ
P P P
=
= DKL DKL E-) P(X E ))PP E.)) DKL(P []
where P and Q are both probability measures the same measurable space and dP denotes the Radon-Nikodym derivative of P with respect Q. An analogous definition of conditional mutual information holds through the expected KL-divergence for any three random variables X, Y, Z:
T(X;Y Y 2) E [Pr.. (P((X,
2) || P(X E Z) x P(Y E [2)]]-
With these definitions in hand, we may define the entropy and conditional entropy for any two random variables X, Y
(X) I(X;XX
H(Y X) H(Y) - I(X;Y).
This yields the following identities for mutual information and conditional mutual information for any three arbitrary random variables X, Y, and Z:
I(X;Y) = H(X)-H(X Y) = H(Y)-H(Y|x),,
Y, -
Through the chain rule of the KL-divergence and the fact that (P P) for any probability measure P. we obtain another equivalent definition of mutual information,
I(x;Y)= = E [[]KL(((Y E P(Y E +)]]
well as the chain rule of mutual information: 1(X;Y1,.. YY, Σ I(XYY YI...., Y,-1). :=1
Finally, for any three random variables X, Y, and Z which form the Markov chain X + Y - Z. we have the following data-processing inequality: L(X; 2) < I(X;Y).
3 Problem Formulation
We formulate sequential decision making problem as finite-horizon, episodic Markov Decision Process (MDP) [24, 130] defined by M (S, A, R, T, H). Here S denotes a set of states, AA is a set of actions, R S x A + [0, 1] is a deterministic reward function providing evaluative feedback signals (in the unit interval) to the agent, T S x A + A(S) is a transition function prescribing distributions over next states, 3 E ASS) is an initial state distribution, and H E N is the maximum episode length or horizon.
As is standard in Bayesian reinforcement learning [70], neither the transition function nor the reward function are known the agent and, consequently, both are treated as random variables. Since all other components of the MDP are thought of as known priori, the randomness in the model (R, T) fully accounts for the randomness M the true MDP with model (R", (T) that the agent interacts with and attempts to solve over the course of K episodes. Within each episode, the agent acts for exactly H steps beginning with an initial state $1 ~ S. For each h E [H], the agent observes the current state 8/. E S, selects action ag T.(. 84) A, enjoys a reward nn R(*h, ap) [0, 1), and transitions to the next state 8h+1 ~ T(1 8h, (h) S.
M, which also a random variable. We denote by
stationary, stochastic policy for timestep h [H] TA S - (AA), encodes pattern of behavior mapping individual states to distributions over possible actions. Letting (S + A ((A)) denote the class of all stationary, stochastic policies, a non-stationary policy is a collection of exactly H stationary, stochastic policies whose overall performance in any MDP M timestep E [H] when starting at state s E S and taking action E is assessed by its H
( .,. TH) {S + A(AA) !
associated action- value function (M,n(s,
Σ R(sH, R(sw)aw)) 84 8, an a where the

---

expectation integrates over randomness in the action selections and transition dynamics. Taking the corresponding value function as ( = Ba-an(-1a))
(-1+) (M. a)), we define the optimal
policy nT (Ti .2:.....7j , as achieving supremal value VM, (8)
sup V (s) for =E(S-A((A)4"
all E S, h E [H]. For brevity, we will write any value function V E (S - R] without its argument to implicitly integrate over randomness in the initial state: V = ()) [V(si]]. We
1) be the random variable denoting the trajectory experienced by the agent in the kth episode. Meanwhile, Hy = (Ti, r2..... Th- Ha is the random variable representing the entire history of the agent's interaction within the environment at the start of the kth episode; the sequence of history random variables [ induce and, by definition, are adapted to the filtration ( ke[K] of F.) We call attention the fact that we have yet to make any further restrictions on the state-action space S x A, such as finiteness; notably, the main results of this paper are not limited to tabular MDPs. As mentioned by Lattimore and Szepesvári ári [100] (also as Proposition 7.28 of Bertsekas and Shreve [28]), the lonescu-Tulcea Theorem [80] ensures the existence of a probability space upon which 7. and H3 are well-defined random variables for all episodes & E [K].
let The = (s(1) (a) ( ....,. aH ,"H,,
(k) (k) (k) ,HH4.)
algorithm is sequence of non-stationary policies (TT(), ..... T7 (K) where for each episode & [K], x(4) Hr + {8 A(A)) is function of the current history Hg. We define the regret of reinforcement-leanne algorithm over K episodes as
Abstractly, reinforcement-leeae
K
REGRET(K, 70)) (K) Mr) =
Σ A
A A
VM
where A₂ denotes the episodic regret regret incurred during the keth episode with respect to the true MDP M An agent's 's initial uncertainty in the (unknown) true MDP MM is reflected by an arbitrary prior distribution P(M E HH), Since the regret is random variable due to uncertainty in M we integrate over this randomness to arrive at the Bayesian regret:
BAYESREGRET (1)
x (K)) = E REGRET x()) ..... (K) (K))M*)]
Broadly speaking, our goal is to design provably-efficient reinforcement-leaminng algorithm that incurs bounded Bayesian regret.
Throughout the paper, we will denote the entropy and conditional entropy conditioned upon specific
realization of an agent's history Hg. for some episode k E [K]. as Hi, (X) H(X H₃ = H&)
and HH,, (X Y) & H& Y, H& = H2), for two arbitrary random variables X and Y. This notation will also apply analogously to the mutual information T (X; Y) - T(X; H₁ H&))
(X) (X Y) = (Y) ) (V X), as well as the conditional mutual information
[X; Y Z) e I(X;Y H₃ = Hg, Z). given an arbitrary third random variable, Z. Note that their dependence the realization of random history H₃ makes both II (X; and (X;
[X;Y Y Z) random
variables themselves. The traditional notion of conditional mutual information given the random variable HŞ arises by integrating over this randomness:
E [X(;Y) I(X;Y| H₂)
E (X, Z)] = I(X;Y Hg, Z).
Additionally, will also adopt similar notation express conditional expectation given the random history Ha: Es [X] A E [x]
Satisficing Through Posterior Sampling
4.1 Rate-Distortion Theory
We begin with a brief, high-level overview of rate-distortion theory [146, 25] and encourage readers to consult [41] for more details and [26] for a survey of advances rate-distortion theory towards solving the lossy source coding problem in information theory. A lossy compression problem consumes as input fixed information source P(X E .) and measurable distortion function d: X x Z R>0 which quantifies the loss of fidelity by using Z in place of X. Then, for any

---

D E R20, the rate-distorie dite-distotton function quantifies the fundamental limit of lossy compression as
R(D)= = inf T(X; Z) ZEA(D)
A(D - (Z : Ω - 2 E [d(X,, 2) - D),
where the infimum is taken over all random variables Z that incur bounded expected distortion, E [d(X, 2)] x D. Naturally, R(D) represents the minimum number of bits of information that must be retained from X in order to achieve this bounded expected loss of fidelity'. Throughout the paper, various facts of the rate-distortion function will be referenced as needed. For now, we simply note that, in keeping with the problem formulation of the previous section which does not automatically assume discrete random variables, the rate-distortion function is well-defined for abstract information source and channel output random variables [43].
Just as in past work that studies satisficing in multi-armed bandit problems [138, 139, 15], we will use rate-distortion theory to formalize and identify the best simplified MDP .M& that the agent will attempt to learn over the course of each episode k [K]. The dependence on the particular episode comes from the fact that this lossy compression mechanism or channel will treat the agent's 's current beliefs over the true MDP P(M E
|Hx) as the information source be compressed.
4.2 The Value Equivalence Principle
As outlined in the previous section, the second input for a well-specified lossy-compression problem is a distortion function prescribing non-negative real values to realizations of the information source and channel output random variables (M** MM) that quantify the loss of fidelity incurred by using M in lieu of M To define this function, we will leverage an approximate notion of value equivalence [72, 731. For any arbitrary MDP M with model (R, T) and any stationary. stochastic policy x :S (A4,, define the Bellman operator 1
{S + R} + {S + R} as follows:
B (s)) (-wn(-ls)
[R(s, a) + -./TT(()aa) [V(')]]
The Bellman operator is a foundational tool in dynamic-programming approaches to reinforcement
learning [29] and gives rise to the classic Bellman equation: for any MDP M = A, R, T. 3, H) and any non-stationary policy π = (T1,..., ., TH). the value functions induced by π satisfy V (s) BA V 1 (s), for all h E [H] and with + = O, Vs E S. For any two MDPs M =
A, R, T, ,, H) and M = -S. A, B. H). Grimm et al. [72] define a notion of equivalence between them despite their differing models. For any policy class II S {S - ((A)} and value function class V C (S + R...M M and M are value equivalent with respect to II and V if and only if BY B B V. VT E II, V E V. In words, two different models are deemed value equivalent if they induce identical Bellman updates under any pair of policy and value function from IT V. Grimm et al. [72] prove that when II = (S + } and V = (S - R),, the set of all exactly value- equivvlevv models a singleton set containing only the true model of the environment. The key insight behind value equivalence, however, is that practical model-based reinforcement-leaming algorithms need not be concerned with modeling every granular detail of the underlying environment and may, in fact, stand to benefit by optimizing an alternative criterion besides the traditional maximum-llkkllhoon objective [ [147, 66, 116, 17, 65, 57, 1, 44, 21, 144, 110, 113, 161]. Indeed, by restricting focus to decreasing subsets of policies II {S + }(A) and value functions V c {S + R}, the space of exactly value-cquivalent models is monotonically increasing.
For brevity, let R A {S A + [0, l]} and I A (8 ( A(S)) denote the classes of all reward functions and transition functions, respectively. Recall that, with (S, A. B, H) all known, the uncertainty in a random MDP M is entirely driven by its model (R, T) such that we may think of the support of M* as (up((M') ) = m A ot x H. We define distortion function on pairs of MDPs d: 2n x DR- > R2o for any IT C {S + ((A)). V. V (S- + R) as
sup sup B B V(5)) 2
dny(MM.)) sup 1 V
B VI&
B
TEll
TEll VEV
SES
VEV
In words, du,y is the supremal squared Bellman error between MDPs M and M across all states E 8 with respect to the policy class II and value function class V.
With slight abuse of notation, overload R.
5

---

4.3 Value-Equivalent Sampling for Reinforcement Learning
By virtue of the previous two sections, we are now in position to define the lossy compression problem that characterizes a MDP M that the agent will aspire to learn in each episode E [K]
instead of the true MDP MM. For any 11 S {8 A(A)); V {S - RR;; k E [K]; and D 2 0, we define the rate-distortion function
R I1. (D)) inf (MMM;; (D) & (M Ω - 22 ExIduv(M Mi) s D}. (I) (D)
This distoistootion function characterizes the fundamental limit of MDP compression under our chosen distortion measure resulting in channel that retains the minimum amount of information from the true MDP M while yielding an approximately value-equivalent MDP in expectation. Observe that this distortion constraint is a notion of approximate value equivalence which collapses to the exact value equivalence of Grimm et al. [72] as D + O. Meanwhile, as D - oc, we accommodate a more aggressive compression of the true MDP M resulting in less faithful Bellman updates.
Algorithm Posterior Sampling for Re- Algorithm 2 Value-equivalent Sampling for Reinforce- inforcement Learning (PSRI.) [152]
ment Learning (VSRL)
Input: Prior P(M* E H1)
Input: Prior P(M* E H1). Threshold D E Rgo.
for E [K] do
Distortion function dnyy 21 x M. -> R2o
Sample Mg ~ PPM E. Ha) Get optimal policy x TiMe
for k E [K] do
Compute Mg achieving R. R... (D) limit (Equation 1)
Execute (k) and get trajectory T
Sample MDP M ~ IPM E - H2)
Update history Ha+1 H₁ U
Sample compression Mj P(M E |- M*)
Induce posterior P(M" E Hxt1)
Compute optimal policy (k) TMM
end for
Execute (R) and observe trajectory T Update history H = H₂ J Tk
Induce posterior PMM E Hx+1) end for
standard algorithm for our problem setting is widely known as Posterior Sampling for Reinforce-
ment Learning (PSRL) [152, 120], which we present Algorithm 1, while our Value-equivalent Sampling for Reinforcement Learning (VSRL) is given as Algorithm 2. The key distinction between them is that, at each episode & E [K], J, the latter takes the posterior sample M* ~ P(M" E H₂) and passes through the channel that achieves the rate-distortion limit (Equation 1) at this episode to get the M2 whose optimal policy is executed in the environment.
The core impetus for this work MDP M (as in PSRL) may be an entirely infeasible goal. Consider MDP that represents control of real-world, physical system; learning a transition function of the associated environment, at some level, demands that the agent internalize the laws of physics and motion with near-perfect accuracy. More formally, identifying M demands the agent obtain exactly H₃ (MM) bits of information from the environment which, under an uninformative prior, may either be prohibitively large by far exceeding the agent's 's capacity constraints or be simply impractical under time and resource constraints.
recognize that, for complex environments, pursuit of the exact
As remedy for this problem, we embrace the idea of being "sufficiently satisfying" or satisficing [148, 140, 138, 139, 15, 16]; as succinetly stated by Herbert A. Simon during his 1978 Nobel Memorial Lecture. "decision makers can satisfice either by finding optimum solutions for a simplified world, or by finding satisfactory solutions for more realistic world." Rather than spend an inordinate amount of time trying recover an optimum solution to the true environment, we will instead design an algorithm that pursues optimum solutions for a sequence of simplified environments. In the next section, our analysis demonstrates that finding such optimum solutions for simplified worlds ultimately acts mechanism for achieving satisfactory solution for the realistic, complex world. Naturally, the loss of fidelity between the simplified and true environments translates into a fixed amount of regret that an agent designer consciously and willingly accepts for two reasons: (1) they expect a reduction in the amount of time, data, and bits of information needed to identify the simplified environment and (2) in tasks where the environment encodes irrelevant information and

---

exact knowledge is not needed to achieve optimal behavior [66, 72, 73, 161], this worst-case error term may be negligible anyways while still maintaining greater efficiency than traditional PSRL.
Recalling Example that revolves around a particular sequence of MDPs, [Ma]NE]N), we note that the distortion threshold D increases, the significance of MDPs in the sequence indexed by
larger values of n E [N] rapidly diminishes, As D f oo, lossy compression Mr. needn't 't convey information about any of the MDPs in [Ma InENN- Conversely, at D 0, VSRL agent must necessarily obtain enough information about the entire sequence so as to facilitate planning over II and V. In between, however, the agent need only concern itself with a particular subsequence of (Mpnne(N) while the remaining MDPs can be ignored due to their negligible contribution to overall value and, therefore, expected distortion under d
5 Regret Analysis
In this section, we offer an information- thhorreticc analysis of VSRL (Algorithm before refining our regret bounds to the tabular setting. We conclude by highlighting how our performance guarantees can be expressed via a notion of agent capacity that is considerate of real-world reinforcement learning.
5.1 An Information-Thenn Thhorretie Bayesian Regret Bound
To establish a Bayesian regret bound for VSRL we first require a regret decomposition that ac- knowledges the agent's new objective of identifying approximately value-equivaleee MDP in each episode, Ma rather than the true MDP M Crucially, this regret decomposition leverages the precise form of our distortion function dM,' M.)..
Theorem Take any 2 {S + A}, any V 2 (V* 1 E T and fix any D Z For each episode k E [K]. let Mr be any MDP that achieves the rate-distortion limit of RR TI. (D) with information source P(M" E E.1 H2) and distortion function dny- Then,
BAYESREGRET
(K)) SE
Es
Ve V
(n(()) M,.1 ]
+2HVVD
Theorem I shows how the Bayesian regret incurred by VSRL can separated into an error term the agent must pay for learning a simplified MDP Mę. rather than MM", and the Bayesian regret incurred while trying to learn Mg.. This first term mirrors the satisficing regret of Russo and Van Roy [138, 139] for multi-armed bandits where the performance of the agent in the kth episode is being measured with respect to compressed MDP MR. rather than the true MDP .M". While further discussion on the choices of II and V provided later in this section, we simply note that the conditions placed upon them in Theorem 1 are an artifact of VSRL only executing optimal policies in each time period h E [H] which, under the assumptions our problem formulation, are deterministic.
The remainder of this section is devoted to an analysis for establishing an information-theorriicc bound on the satisficing regret term of Theorem A central tool of our analysis will be the information ratio [136, 137] at the kth episode:
Ey Vin. - (4
(4) 1
Me.1
Ma.1
WK E [K].
I& Tki Mb)
In words, the information ratio is the ratio between squared expected regret in the kth episode with respect to Mg and the information gained about M2 in the kth episode by sampling MDP M₁ and observing trajectory Tke given the current history Hş. Numerous prior works have leveraged similar or generalized types information ratios for analyzing multi-armed bandit problems [135- 139, 54, 99, 169, 36. 15, 98] as well reinforcement-leanee learning problems [104]; in comparison to the latter, we simply note that our analysis bears stronger resemblance to those in multi-armed bandits by not constructing confidence sets over MDPs [121, 120, 104], avoiding restricted focus tabular problems. That said, our results are contingent upon the existence of a uniform upper bound to the information ratios across all episodes, non-trivial result [78] that we leave future work.
Through our information-ratio analysis, we obtain the following information theoreeicc bound on satisficing Bayesian regret:

---

Theorem 2. IfT, 1 for all E [K], then E
K Σ Bk
V Ma.l
-x(l)) Mail
$ VTKRI (D).
An immediate consequence of the preceding theorems is the following corollary which establishes our main result, an information-thhoreee Bayesian regret bound for VSRL. We omit the proof follows directly from applying Theorems I and 2 in sequence.
Corollary 1. Take any II {S + A}. any 2 {V*
E I11 and fix any D For any prior distribution P(MM E H1), T S T for all l E [K], then VSRL (Algorithm 2) has
BAYESREGRET ( (K)) & V TTKRR..DD
2KHVD.
Once again we recall that, since the rate-distortion function is well-defined for arbitrary souree and channel output random variables defined on abstract alphabets [43], the Bayesian regret bound of Corollary 1 holds for any finite-horizon, episodic MDP, extending beyond past analyses of PSRL constrained only to tabular MDPs. We defer discussion of practical considerations for implementing VSRL the appendix.
At this point, we call attention to the parameterization of our lossy compression problem by a particular policy class IT and value function class V. whose dependence we inherit from the value equivalence principle [72]. The next result clarifies how the performance of VSRL. is affected by fluctuations in these classes via dominance relationship [150] between the induced distortion functions.
Lemma 1. For any two II, and any V, V such that II' S II {S A(A)) and V S VVC {S > R], we have R2 II. (D) 2 R IV' (D), vk E [K],D>0
D>
Property 3 of Grimm et al. [72] highlights how the set of value-equivalent MDPs grows as the policy and value function classes shrink. Lemma 1 provides an intuitive, ciormation--teoretiee counterpart to their result where, as the sets of policies and value functions over which models will be assessed diminish, an agent may naturally compress more aggressively and throw away larger quantities of bits from each source distribution over the true MDP M
Since a compressed MDP M& that achieves the rate-distortion limit has expected distortion bounded by D, one may wonder how the probability of not recovering an approximately- valle-equivallern MDP scales as D oc. To that end, we conclude this section with final result that brings clarity to this via a generalization [60] of Fano's 's inequality [64]. We leave investigation of other generalizations of Fano's inequality that might yield similarly interesting results to future work [160, 8].
Lemma 2. Take any II C (S - A(A)) and V S {S + RR.. For any D Z 0 and any h E [K]. define 8 = sup F(dn,(MM' M) - D Hs). Then, Mem
R.L.V
II. (D) + +og(22
sup (( . D H2)21 MeA((D)
log (1)
For any episode k E [K]. the left-hand side of the inequality in Lemma 2 denotes the worst-case probability of sampling compressed MDP M that is not approximately-valee valltateellallleeuuivleeleee to M The right-hand side conveys that, in order to avoid such an error with reasonable probability, one requires a setting of D < oo such that R. IT,Y (D) ze log (t)
5.2 Specializing to Tabular MDPs
While the preceding subsection constitutes the main contribution of this paper, the presence of cormmation-theoredd terms makes difficult compare our guarantees to those obtained in prior work, which typically focuses on the tabular setting. To help remedy this, we offer the following theorem which restricts focus to the case where the agent pursues an exactly value-equivalent model of the tabular environment. Notably, the results of this section still retain dependence upper bound to the information ratio whose exact form is result left to future work.
uniform
Theorem 3. Take any 11 2 {S- + A}, any V 2 {V" I E 11 }. and let D = O. For any prior distribution (PM E H1) over labular MDPs, T < for all k E [K], then VSRL (Algorithm
2) has BAYESREGRET (1), , (K)) < 0
|8| T(AIK
8

---

An immediate observation is that the Bayesian regret bound of Theorem 3 matches the dependence on the number of states, [S], obtained in the first (weaker) guarantee established for PSRL by Osband et al. [121]; we suspect that this guarantee for VSRL is unimprovable without further distributional assumptions [120, 119]. an alternative, we contemplate how change in the distortion measure used by VSRL might incur an improved regret bound when specialized to the tabular setting.
Specifically,, notice that the only piece of the VSRL analysis tethered to the particular form of the distortion function (I, is Theorem 1, while all other components remain agnostic to the precise criterion for assessing the loss of fidelity between original and compressed MDPs. Consequently, there is potential for a modified distortion function to offer an improved regret analysis relative to Theorem 3. Rather than concerning ourselves with planning over multiple behaviors, consider a distortion function based solely on the optimal action-value functions:
M. 1lse = sup sup QM.A(s, QMMA de (M, = sup IQM,a -Q he(d]
he[H] (x,0)ESxA
We use RS (D) to denote the rate-distortion function under this new measure of distortion, de- MM. order for this new distortion function to be compatible with VSRL, we require an analogue to the regret decomposition of Theorem 1.
Theorem 4. Fix any D 2 and, for each episode E [K], let ME be any MDP that achieves the rate- distortion limit of R2 (D) with information source PPM E 1 Hx) and distortion function do
Then, BAYESREGRET (()
(K)
E
Ex
V Ma.!
Vv M..
2K(H + 1)VD.
With this regret decomposition in hand, we may recover the analogue to Corollary 1, whose proof is immediate and, therefore, omitted.
Corollary 2. Fix any D > O. For any prior distribution P(M* E H1). ifT S for all l E [K], then VSRL (Algorithm 2) with distortion function dq has BAYESREGRET(K, (1) xt (K)) I
V VTKR (D) + (K + 1lvD.
As illustrated by the following lemma, the significance of this change in distortion measure from dn, to dQ- is that the optimal action-value functions may now act as an information bottleneck [158] between the original MDP M and compressed MDP Mr-
Lemma 3. For each episode k E [K] and for D = O, let MR be any MDP that achieves the rist-distortion limit of R (D) with information source PM E H2) and distortion function dq. Then, we have the Markov chain M - Qi-- - ME,, where QiM- {Q'M- jn heEM is the collection of random variables denoting the optimal action-value functions of M*
Lemma 3, through the data- pattapprccesing inequality, immediately leads to analogue of Theorem that matches the dependence on |S] in the best known Bayesian regret bound for PSRL [120].
Theorem 5. For D = 0 and any prior distribution P(M" E H1) over tabular MDPs, ifT < F for all K E [K]. then VSRL with distortion function do- has BAYESREGRET K,KK,T// 7())
(K)) <
δ [ISIAAIK
Ultimately, Theorem 5 confirms that while there is great flexibility in the original definition of value equivalence to support planning across multiple policies and value functions, focusing on optimal value functions gives rise to more efficient learning. Moreover, comparing the result with the PSRL regret bound of Osband and Van Roy [120] for tabular MDPs, this suggests an achievable uniform upper bound to the information ratio as S H2, where the S accounts for numerical constants and logarithmic factors.
5.3 Capacity-Sensitivv Performance Guarantees
We recognize that the cntormatioonthhoreete regret bounds of the previous two sections, like many other guarantees for crovably-cfficient reinforcement learning before them, implicitly and unrcalistically

---

assume that an agent is of unbounded capacity and may pursue any waw.aaatttel-auu-euuviivaaaa model under a given distortion threshold D. In the context of real-world reinforcement learning [62. 105], however, fundamental limits on computational resources and time leave agent designer with a bounded agent to be deployed within an overwhelmingly complex environment. As such, this designer may seldom be in position to dictate an ideal or desired sub-optimality threshold D, but rather must make do with a known constraint on agent capacity; guarantees on sample-efficiet reinforcement learning cognizant of such a fundamental constraint are nascent.
While there are numerous possibilities for how one might choose to formally characterize agent capacity, we here adopt a fundamental perspective that learning is the process of acquiring information and so take this capacity to imply the existence of a non negatiitee real value R R20 such that the agent may only acquire and retain exactly R bits of information. To help contextualize this notion of agent capacity, we introduce the distortion-rate function [146, 25, 41] which quantifies the fundamental limit of expected distortion under an information constraint:
Dg (R)
inf Ex (de- (M",))
Dg (R) (RR)
inf ER (MrM (2) MET((R)
MM)x((R)
where the infimum is taken over all channels with bounded rate, (R(R) A (M 8 - M (MMM; S R). In words, given the agent's current beliefs over the true MDP F(M* E Hy). the infimum of the distortion-rate function is taken over all potential lossy compressions of the environment that fall within the agent's capacity constraint of R bits and identifies the one that preserves the most useful information, measured by the distortion function. Conveniently, the rate-distortion function and distortion-rate function are inverses of one another [41] (R(D(R) = R) such that we recover the following two capacity-sensitivv regret bounds directly from Corollaries 1 and 2 by simply taking the input distortion threshold of VSRL equal to the associated distortion-rate function in the first episode (D - (Rt) and D = DI (R), respectively).
2 11 (S - A}, any V 2 {V*] a E I }, and let R >> 0 be the agent capacity. For any prior distribution P(M E HT), T S for all l E [K], then VSRI.
Corollary 3. Take any II
(Algoritim 2) with distortion function dnyy has BAYESREGRET (!), ",..,,((,,,. (K)) S vTKR- -
2KH, DILY (R).
Corollary Let > O be the agent capacity. For any prior distribution P(M* E H1). if TE S T for all lo E [K], then VSRL (Algorithm 2) with distortion function dq- has BAYESREGRET
(KK) S VTKR+ + 2K + +D/DD (R).
Turning back to Example I, note how an agent with significantly limited capacity cannot possibly hope to capture all the granularity contained in the entire MDP sequence [M.n)eeN] for large values of N. For a capacity of exactly R bits, Corollaries and 4 immediately translate this fundamental limit into corresponding performance guarantce, allowing the agent to identify subsequence {M,} Jnejc for some C < N which only requires gathering R bits of information from the environment.
Conclusion
In this paper, we began with a lnite-horizon, episodic MDP and considered the ramifications of real-world reinforcement-leariin scenario wherein the relative complexity of the environment is so immense that an agent may find itself incapable of perfectly recovering optimal behavior. An immediate consequence of this reality is the need to strike appropriate balance between what is performant and what is achievable. We introduced the VSRI. algorithm for incrementally synthesizing simple and useful approximations of the environment from which an agent might still recover near-optimal behaviors. Recognizing the Information-theoreet nature of this lossy MDP compression, we provided an analysis of VSRL whose performance guarantees, by virtue of rate rate-distortion theory, are twofold. The first set of guarantees ensure VSRL recovers the simplest compression of the environment which still incurs bounded sub-optimality. as specified by the agent designer. Alternatively, the second set of guarantees maintain that VSRL finds the best compression of the environment subject to constraints on agent capacity. Through our general problem formulation analysis, both regret bounds hold for any finite-horizon, episodic MDP, regardless of whether or not the state-action space is finite. That said, the question of how to practically instantiate VSRL for high-dimensional settings is an open problem left to future work.
and information-theoret
10

---

Acknowledgements
The authors gratefully acknowledge Christopher Grimm for initial discussions that provided an impetus for this work. The authors also thank Adithya Devraj, Shi Dong, John Duchi, Hong Jun Jeon, Saurabh Kumar, and Xiuyuan (Lucy) Lu for insightful comments on various components the paper. Financial support from Army Research Office (ARO) grant IN1200000055 is gratefully acknowledged.
References
[1] Romina Abachi, Mohammad Ghavamzadeh, and Amir-massout Farahmand. Policy-aware model learning for policy gradient methods. arXiv preprint arXiv:2003.00030 2020.
[2] Yasin Abbasi- Yadkori and Csaba Szepesvari. Bayesian optimal control of smoothly parameter- ized systems: The lazy posterior sampling algorithm. arXiv preprint arXiv:146.. 3926, 2014. 22
[3] David Abel. A Theory of Abstraction in Reinforcement Learning. PhDD thesis, Brown University, 2020. 23
[4] David Abel, David Hershkowitz, and Michael Littman. Near optimal behavior via approximate state abstraction. In International Conference on Machine Learning, pages 2915-2923. PMLR, 2016. 23, 25
[5] David Abel, Dilip Arumugam, Lucas Lehnert, and Michael Littman. State abstractions for lifelong reinforcement learning. In International Conference on Machine Learning, pages 10-19, 2018.
[6] David Abel, Dilip Arumugam, Kavosh Asadi, Yuu Jinnai, Michael L Littman, and Lawson LS Wong, State abstraction compression in apprenticeship learning. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 33, pages
2019. 22, 23, 25
[7] David Abel, Nate Umbanhowar, Khimya Khetarpal, Dilip Arumugam, Doina Precup, and Michael Littman. Value preserving state-action abstractions. In International Conference on Artificial Intelligence and Statistics, pages 1639- 1650. PMLR, 2020. 23
[8] Shuchin Aeron, Venkatesh Saligrama, and Manqi Zhao Information theoretic bounds for compressed sensing. IEEE Transactions Information Theory, 56(10):511 (11110)551115111 11-1111,,,,,, 2010.
[9] Alekh Agarwal, Sham Kakade, Akshay Krishnamurthy, and Wen Sun. FLAMBE: Structural complexity and representation learning of low rank MDPs. In H. Larochelle, M. Ranzato, R. Hadsell, M. F. Balcan, and H. Lin, editors, Advances in Neural Information Processing Systems, volume 33, pages 20095-20107. Curran Associates, Inc., 2020. 23
[10] Shipra Agrawal and Randy Jia. Optimistic posterior sampling for reinforcement learning: worst-case regret bounds. In Advances in Neural Information Processing Systems. pages 1 1194,119, 2017. 1, 22
[11] Alexander Alemi, Ben Poole, Ian Fischer, Joshua Dillon, Rif Saurous, and Kevin Murphy, Fixing a broken ELBO. In International Conference on Machine Learning, pages 159-166 168.. PMLR, 2018. 25
[12] Mauricio Araya-López, Vincent Thomas, and Olivier Buffet. Near-optimal BRL using op- timistic local transitions. In Proceedings of the 29th International Conference on Machine Learning, pages 515-522, 2012. 22
[13] Suguru Arimoto. An algorithm for computing the capacity of arbitrary discrete memoryless channels. IEEF Transactions on Information Theory, 18(1):14-20, 1972. 25
[14] Dilip Arumugam and Benjamin Van Roy. Randomized value functions via posterior state- abstraction sampling, arXiv preprint at arXiv:2010.02388 2020. 23

---

[15] Dilip Arumugam and Benjamin Van Roy. Deciding what to learn: A rate-distortion approach.
In International Conference on Machine Learning, pages 373-382. PMLR, 2021. 2, 6,
22, 25, 29
[16] Dilip Arumugam and Benjamin Van Roy. The value of information when deciding what to
learn. Advances in Neural Information Processing Systems, 34, 2021. 2, 6, 22, 25
[17] Kavosh Asadi, Dipendra Mísra, and Michael Littman. Lipschitz continuity in model-based reinforcement learning. In International Conference on Machine Learning, pages 263-273.
PMLR, 2018.
[18] John Asmuth, Lihong Li, Michael Littmann Ali Nouri, and David Wingate. A Bayesian sampling approach to exploration in reinforcement learning. In Proceedings of the Twenty-Fifth Conference on Uncertainty in Artificial Intelligence, pages 19-26, 2009. 22
[19] Karl Johan Åström. Optimal control of Markov processes with incomplete state information. Journal of Mathematical Analysis and Applications. 10(1):174-205, 1965. 23
[20] Peter Auer, Thomas Jaksch, and Ronald Ortner. Near-optimal regret bounds for reinforcement learning. In Advances in Neural Information Processing Systems, pages 89-96, 2009. 1, 22
[21] Alex Ayoub, Zeyu Jia, Csaba Szepesvari, Mengdi Wang, and Lin Yang. Model-based rein- forcement learning with value-targeted regression. In International Conference on Machine Learning, pages
PMLR, 2020. 5
[22] Mohammad Gheshlaghi Azar, Ian Osband, and Rémi Munos. Minimax regret bounds for reinforcement learning. In International Conference on Machine Learning, pages 263-272.
PMLR, 2017. 1, 22
[23] Peter L Bartlett and Ambuj Tewari. REGAL: a regularization based algorithm for reinforcement learning weakly communicating MDPs. In Proceedings of the Twenty-Fifth Conference on Uncertainty in Artificial Intelligence, pages 35-42, 2009. 1, 22
[24] Richard Bellman. A Markovian decision process. Journal of Mathematics and Mechanics, pages 679-684, 1957. 3
[25] Toby Berger. Rate Distortion Theory: A Mathematical Basis for Data Compression. Prentice- Hall, 1971. 2,4, 10
[26] Toby Berger and Jerry D Gibson. Lossy source coding. IEEE Transactions on Information Theory, 266632263,, 1998.
[27] Donald A. Berry, Robert W. Chen, Alan Zame, David C. Heath, and Larry A. Shepp. Bandit problems with infinitely many arms. Ann. Statist. 25(5):2103-2166, 10 1997. 22
[28] Dimitri Bertsekas and Steven Shreve. Stochastic optimal control: the discrete-tine case, volume 5. Athena Scientifie, 1996. 4
[29] Dimitri P. Bertsekas. Dynamic Programming and Optimal Control. Athena Scientific, 1995.
[30] Dimitri P. Bertsekas and David A. Castañon. Adaptive aggregation methods for infinite horizon dynamic programming. IEEE Transactions on Automatic Control, 34(6):589-595 1989, 23
[31] Richard Blahut, Computation of channel capacity and rate-distortion functions. IEEE Trans- actions Information Theory, 18(4):460-473, 1972. 25
[32] Thomas Bonald and Alexandre Proutiere. Two-target algorithms for infinite-armed bandits with Bernoulli rewards. In Advances in Neural Information Processing Systems, pages (184-2192. 2013. 22
[33] Vivek S Borkar, Sanjoy Mitter, and Sekhar Tatikonda. Markov control problems under communication contraints. Communications Information and Systems, 1(1::15-32, 2001. 22
12

---

[34] Pinhas Boukris. An upper bound on the speed of convergence of the Blahut algorithm for computing rate-distortion functions (conresp.). IEEE Transactions on Information Theory, 19 (5)7708-70, 1973. 25
[35] Ronen I Brafman and Moshe Tennenholtz. R-MAX-a general polynomial time algorithm for near-optimal reinforcement learning. Joumaa of Machine Learning Research, 3(Oct):213-231, 2002. 1, 22
[36] Sébastien Bubeck and Mark Sellke. First-order Bayesian regret analysis of Thompson sampling. In Algorithmic Learning Theory, pages 196-233. PMLR, 2020.
[37] Sébastien Bubeck, Rémi Munos, Gilles Stoltz, and Csaba Szepesvári. X-armed bandits. Journal of Machine Learning Research, 12(5), 2011. 22
[38] Séhastien Bubeck, Nicolò Cesa-Bianchi, al. Regret analysis of stochastic and nonstochastic multi-armes bandit problems. Foundations and Trends@ in Machine Learning, 5(1):1-122, 2012. 2, 22
[39] Pablo Samuel Castro and Doina Precup. Using linear programming for Bayesian exploration in Markov decision processes. In IJCAI, volume 24372442, 2007. 22
[40] Mung Chiang and Stephen Boyd. Geometric programming duals of channel capacity and rate distortion. IEEE Transactions on Information Theory, 50(2))245-255 2004. 25
[41] Thomas M Cover and Joy A Thomas. Elements of Information Theory. John Wiley & Sons, 2012. 3, 4, 10, 30, 33, 35
[42] Imre Csiszár. On the computation of rate-distortion functions (corresp.). IEEE Transactions Information Theory, 20 122-11222, 1974. 25
[43] Imre Csiszár. On an extremum problem of information theory. Studia Scientiarum Mathemati- carum Hungarica, 9, 1974. 5, 8, 25
[44] Brandon Cui, Yinlam Chow, and Mohammad Ghavamzadeh. Control-aware representations for model-based reinforcement learning. In International Conference on Learning Representations. 2020. 5
[45] Christoph Dann and Emma Brunskill. Sample complexity of episodic fixed-horizon reinforce- ment learning. Proceedings of the 28th International Conference on Neural Information Processing Systems- Volume 2, pages 2818-28206 2015. 1, 22
[46] Christoph Dann, Tor Lattimore, and Emma Brunskill. Unifying PAC and regret: uniform PAC bounds for episodic reinforcement learning. In Proceedings of the 31st International Conference on Neural Information Processing Systems, pages 5717-5727, 2017. 1, 22
[47] Christoph Dann, Nan Jiang, Akshay Krishnamurthy, Alekh Agarwal, John Langford, and Robert E Schapire. On oracle-efficient PAC RL with rich observations. In Proceedings of the 32nd International Conference on Neural Information Processing Systems, pages 1429 1439, 2018. 22
[48] Justin Dauwels. Numerical computation of the capacity of continuous memoryless channels. In Proceedings of the 26th Symposium on Information Theory in the BENELUX, pages 221-228.
Citeseer, 2005. 25
[49] Peter Dayan. Improving generalization for temporal difference learning: The successor representation. Neural computation, 5(4):613-624, 1993. 26
[50] Thomas Dean and Robert Givan. Model minimization in Markov decision processes. In Proceedings of the AAAI Conference on Artificial Intelligence, pages 106-111. AAAI Press, 1997. 23
[51] Richard Dearden, Nir Friedman, and Stuart Russell. Bayesian Q-learing. In Proceedings of the Fifteenth National/Tenth Conference on Artificial Inteliigence/hnoovaiiee Applications of Artificial Intelligence, pages 761-768, 1998. 22
13

---

[52] Richard Dearden, Nir Friedman, and David Andre. Model based Bayesian exploration. In Proceedings of the Fifteenth Conference on Uncertainty in Artificial Intelligence, pages 150- 159, 1999. 22
[53] Yash Deshpande and Andrea Montanari. Linear bandits in high dimension and recommen- dation systems. In 2012 50th Annual Allerton Conference on Communication, Control, and Computing (Allerton), pages 1750-1754. IEEE, 2012. 22
[54] Shi Dong and Benjamin Van Roy. An citommation-thorrete analysis for Thompson sampling with many actions. Advances Neural Information Processing Systems, pages 4157-4165, 2018. 7, 22
[55] Shi Dong, Benjamin Van Roy, and Zhengyuan Zhou, Provably efficient reinforcement learning with aggregated states. arXiv preprint M.Niv:1112.06333. 2019. 23
[56] Shi Dong, Benjamin Van Roy, and Zhengyuan Zhou Simple agent, complex environment: Efficient reinforcement learning with agent state. arXiv preprint arXiv:2102.05221, 2021. 1,
22, 23
[57] Pierluca D'Oro, Alberto Maria Metelli, Andrea Tirinzoni, Matteo Papini, and Marcello Restelli. Gradient-aware model-based policy search. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 34, pages 3801-3808, 2020.
[58] Simon Du, Akshay Krishnamurthy, Nan Jiang, Alekh Agarwal, Miroslav Dudik, and John Langford. Provably efficient RL with rich observations via latent state decoding. In Interna- tional Conference on Machine Learning, pages 1665-1674. PMLR, 2019. 22, 23
[59] John C. Duchi. Lecture Notes for Statistics 31 I/Electrical Engineering 377, Stanford University. 2021. 33,3,33 36
[60] John C. Duchi and Martin J. Wainwright. Distance-bant based and continuum Fano inequalities with applications to statistical estimation. arXiv preprint arXiv: 131.,266, 2013. 8, 33
[61] Michael O' Gordon Duff. Optimal Learning: Computational procedures for Bayes-adaptive Markov decision processes. University of Massachusetts Amherst, 2002. 22
[62] Gabriel Dulac-Amold, Nir Levine, Daniel Mankowitz, Jerry Li, Cosmin Paduraru, Sven Gowal, and Todd Hester. Challenges of real-world reinforcement learning: definitions, bench- marks and analysis. Machine Learning, pages 1-50, 2021. 10
[63] Vikranth Dwaracherla, Xiuyuan Lu, Morteza Ibrahimi, Ian Osband, Zheng Wen, and Ben- jamin Van Roy. Hypermodels for exploration. In International Conference on Learning Representations, 2020. 2, 25
[64] Robert M. Fano. Class Notes for MIT Course 6.574: Transmission of Information, MIT, Cambridge, MA. 1952. 8, 33
[65] Amir-massoud Farahmand. Iterative value model learning. In Proceedings of the 32nd International Conference on Neural Information Processing Systems, pages 9090-9101 2018.
5
[66] Amir-massoud Farahmand, Andre Barreto, and Daniel Nikovski. Value-aware loss function for model-based reinforcement learning. In Artificial Intelligence and Statistics, pages 1486-1494. PMLR, 2017. 7,7
[67] Norm Ferns, Prakash Panangaden, and Doina Precup. Metries for finite Markov Decision Processes. In Proceedings of the 20th Conference Uncertainty in Artificial Intelligence, pages 162-169, 2004. 23
[68] Norman Femn, Pablo Samuel Castro, Doina Precup, and Prakash Panangaden. Methods for computing state similarity Markov Decision Processes. arXiv preprint arXiv: / 220 6836, 2012. 23
14

---

[69] Sebastian Flennerhag, Jane X Wang, Pablo Sprechmann, Francesco Visin, Alexandre Galashov, Steven Kapturowski, Diana Borsa, Nicolas Heess, Andre Barreto, and Razvan Pascanu. Temporal difference uncertainties as a signal for exploration. arXiv preprint arXiv:2010.02255, 2020. 26
[70] Mohammad Ghavamzadeh, Shie Mannor, Joelle Pineau, and Aviv Tamar. Bayesian reinforce- ment learning: A survey. Foundations and Trends@ in Machine Learning. 8(5-6):359-44 483,
2015. 3, 22
[71] Robert M. Gray, Entropy and information theory. Springer Science & Business Media, 2011. 3
[72] Christopher Grimm, Andre Barreto, Satinder Singh, and David Silver. The value equivalence principle for model-based reinforcement learning, Advances in Neural Information Processing Systems, 33, 2020. 5, 6, 8
[73] Christopher Grimm, André Barreto, Greg Farquhar, David Silver, and Satinder Singh. Proper value equivalence. Advances in Neural Information Processing Systems, 34, 2021. 5, 23
[74] Arthur Guez, David Silver, and Peter Dayan. Efficient Bayes-adaptive reinforcement learning using sample-basee search. In Proceedings of the 25th International Conference on Neural Information Processing Systems- Dystems-Volume 1, pages 1025-1033, 2012. 22
[75] Arthur Guez, David Silver, and Peter Dayan. Scalable and efficient Bayes-adaptive reinforce- ment learning based on Monte-Carlo tree search. Journal of Artificial Intelligence Research, 48:841-858 1833, 2013.
[76] Arthur Guez, Nicolas Heess, David Silver, and Peter Dayan. Bayes-adaptive simulation-bass baasdd search with value function approximation. In Advances in Neural Information Processing Systems, pages 451 2014. 22
[77] Assaf Hallak, Dotan Di Castro, and Shie Mannor. Contextual Markov decision processes.
arXiv preprint arXiv:/502.008 1502.0225, 2015. 25
[78] Botao Hao and Tor Lattimore. Regret bounds for information-ddreectd reinforcement learning.
arXiv preprint arXiv:2206.04m6 04640, 2022. 7
[79] Matthew T Harrison and Ioannis Kontoyiannis. Estimation of the rate- dist-rrtooiion function.
IEEE Transactions on Information Theory. 54(8):3757-3762, 2008. 25
[80] Cassius T. Ionescu-Tulcea, Mesures dans les espaces produits. Atti Acad. Naz. Lincei Rend. Cl Sci. Fis. Mat. Nat, 8(7), 1949. 4
[81] Thomas Jaksch, Ronald Ortner, and Peter Auer. Near-optimal regret bounds for reinforcement learning. Journal of Machine Learning Research, 11(4), 2010. 1,22
[82] David Janz, Jiri Hron, Przemystaw Mazur, Katja Hofmann, José Miguel Hernández-Lobato. and Sebastian Tschiatschek. Successor uncertainties: exploration and uncertainty in temporal difference learning. Advances in Neural Information Processing Systems, 32, 2019. 26
[83] Nan Jiang, Alex Kulesza, and Satinder Singh. Abstraction selection in model-based rein- forcement learning. In International Conference on Machine Learning, pages 179-188, 2015. 23
[84] Nan Jiang, Akshay Krishnamurthy, Alekh Agarwal, John Langford, and Robert E Schapire. Contextual decision processes with low Bellman rank are PAC-learnable. In International Conference on Machine Learning, pages 1704-1713. PMLR, 2017. 22
[85] Chi Jin, Zeyuan Allen-Zhu, Sebastien Bubeck, and Michael Jordan. Is Q-learning provably efficient? In Proceedings of the 32nd International Conference on Neural Information Processing Systems, pages 4868-4877 2018. 1, 22
[86] Nicholas K Jong and Peter Stone. State abstraction discovery from irrelevant state variables. In Proceedings of the 19th International Joint Conference on Artificial Intelligence, pages 752-757, 2005, 23
15

---

[87] Leslie Pack Kaelbling, Michael L Littman, and Andrew W Moore. Reinforcement learning: A survey. Journal of Artificial Intelligence Research, 4:237-285, 1996.
[88] Leslie Pack Kaelbling, Michael L Littman, and Anthony R Cassandra. Planning and acting in partially observable stochastic domains. Artificial intelligence, 101(1-2)999-134, 1998. 23
[89] Sham Kakade and John Langford. Approximately optimal approximate reinforcement learning. In Proceedings of the Nineteenth International Conference Machine Learning, pages 267-274, 2002. 37
[90] Sham Machandranath Kakade. On the Sample Complexity of Reinforcement Learning. PhD thesis, Gatsby Computational Neuroscience Unit, University College London, 2003. 1, 22
[91] Michael Kearns and Satinder Singh. Near-optimal reinforcement learning in polynomial time. Muchine Learning, 49(2-3):209-232, 2002. 1, 22
[92] Robert Kleinberg, Aleksandrs Slivkins, and Eli Upfal. Multi-armed bandits in metric spaces. In Proceedings of the 40th Annual ACM Symposium on Theory of Computing, pages 681-690,
2008. 22
[93] Andrei Nikolaevich Kolmogorov and Vladimir Mikhailovich Tikhomirov. e-entropy and s-capacity of sets in function spaces. Uspekhi Matematicheskikh Nauk, 14(2):3-66, 1959, 35
[94] Zico Kolter and Andrew Y Ng. Near-Bayesian exploration in polynomial time. In Proceedings of the 26th Annual International Conference on machine Learning, pages 513-520, 2009. 22
[95] Victoria Kostina and Babak Hassibi. Rate-cost tradeoff's in control. IEEE Transactions Automatic Control, 64(11):4525-4540 2019. 22
[96] Akshay Krishnamurthy, Alekh Agarwal, and John Langford. PAC reinforcement learning with rich observations. In Proceedings of the 30th International Conference on Neural Information Processing Systems, pages 1848-18555 2016. 22
[97] Tze Leung Lai and Herbert Robbins. Asymptotically efficient adaptive allocation rules. Advances in applied mathematics, 6(1):4-22, 1985. 2
[98] Tor Lattimore and Andras Gyorgy. Mirror descent and the information ratio. In Conference on Learning Theory, pages
PMLR, 2021. 7
[99] Tor Lattimore and Csaba Szepesvári. An information -heormation-thhoretiic approach to minimax regret in partial monitoring. In Conference on Learning Theory, pages 2111-2139, PMLR, 2019.
[100] Tor Lattimore and Csaba Szepesvári. Bandit algorithms. Cambridge University Press, 2020.
2, 4, 22
[101] Lihong Li, Thomas J Walsh, and Michael L Littman. Towards unified theory of state abstraction for MDPs. ISAIM, 4:5, 2006. 23, 25
[102] Evan Z Liu, Aditi Raghunathan, Percy Liang, and Chelsea Finn. Decoupling exploration and exploitation for meta-reinforcement learning without sacrifices. In International conference on machine learning, pages 6925-6935. PMLR, 2021. 25
[103] Xiuyuan Lu and Benjamin Van Roy. Ensemble sampling. In Proceedings of the 31st In- ternational Conference on Neural Information Processing Systems, pages 3260-3268, 2017.
25
[104] Xiuyuan Lu and Benjamin Van Roy. Information-thhorrie confidence bounds for reinforce- ment learning. Advances in Neural Information Processing Systems, 32:2461-2470, 2019.
[105] Xiuyuan Lu, Benjamin Van Roy, Vikranth Dwaracherla, Morteza Ibrahimi, Ian Osband, and Zheng Wen. Reinforcement Learning, Bit by Bit, arXiv preprint 1rXiv:2103.04004 2021. 1, 2, 10, 22, 23
16

---

[106] Gerald Matz and Pierre Duhamel. Information geometric formulation and interpretation of accelerated MaauttAAimoto--t algorithms. In Information theory workshop, pages 66-70. IEFE, 2004. 25
[107] Dipendra Misra, Mikael Henaff, Akshay Krishnamurthy, and John Langford. Kinematic state abstraction and provably efficient occhobservattion reinforcement learning. In International Conference on Machine Learning, pages 6961-6971. PMLR, 2020. 23
[108] Sanjoy Mitter and Anant Sahai. Information and control: Witsenhausen revisited. In Learning, Control and Hybrid Systems, pages 281-293. Springer, 1999. 22
[109] Sanjoy K Mitter. Control with limited information. European Journal of Control, 7(2-3):
122-131, 2001. 22
[110] Suraj Nair, Silvio Savarese, and Chelsea Finn. Goal-aware prediction: Learning to model what matters. In International Conference Machine Learning, pages 7207-7219, PMLR, 2020.
[111] Ziad Naja, Florence Alberge, and Pierre Duhamel. Geometrical interpretation and improve- ments the Speech and Signal Processing, pages 2505 2508. IEEE, 2009. 25
algorithm. In 2009 IEEE International Conference on Acoustics,
[112] Urs Niesen, Devavrat Shah, and Gregory Wornell Adaptive alternating minimization algo- rithms. In 2007 IEEE International Symposium on Information Theory, pages 1641-1645. IEEE, 2007. 25
[113] Evgenii Nikishin, Romina Abachi, Rishabh Agarwal, and Pierre-Luc Bacon. Control-oriented model-based reinforcement learning with implicit differentiation. Proceedings of the AAAI Conference on Artificial Intelligence, 2022. 5
[114] Brendan O'Donoghue, lan Osband, Remi Munos, and Volodymyr Mnih. The uncertainty Bellman equation and exploration. In International Conference on Machine Learning, pages 3836-3845, 2018. 2, 26
[115] Brendan O' O'Donoghue, Ian Osband, and Catalin Ionescu. Making sense of reinforcement learning and probabilistic inference. In International Conference on Learning Representations, 2020. 25
[116] Junhyuk Oh, Satinder Singh, and Honglak Lee. Value prediction network. In Proceedings of the 31 International Conference on Neural Information Processing Systems, pages 6120-6130, 2017. 5, 23
[117] Ian Osband. Deep Exploration via Randomized Value Functions. PhD thesis, Stanford University, 2016. 26
[118] Ian Osband and Benjamin Van Roy. Model-based reinforcement learning and the Eluder dimension. Advances in Neural Information Processing Systems, 27, 2014. 22
[119] Ian Osband and Benjamin Van Roy. Gaussian-Dirichlee posterior dominance in sequential learning. arXiv preprint arXiv: / 7002 0216 2017. 9
[120] Ian Osband and Benjamin Van Roy. Why is posterior sampling better than optimism for reinforcement learning? In International Conference on Machine Learning, pages 2701-2710. PMLR, 2017. 2, 6, 7, 9, 9, 22, 38
[121] Ian Osband, Daniel Russo, and Benjamin Van Roy. (More) efficient reinforcement learning via posterior sampling. Advances in Neural Information Processing Systems, 26:3003-3011, 2013. 1, 2, 7, 9, 22, 26,33 38
[122] Ian Osband, Charles Blundell, Alexander Pritzel, and Benjamin Van Roy. Deep exploration via Bootstrapped DQN. Advances in Neural Information Processing Systems, pages 4026-4034, 2016. 25, 26
[123] lan Osband, Benjamin Van Roy, and Zheng Wen. Generalization and exploration via random- ized value functions. In International Conference on Machine Learning, pages 2377-2386,
2016. 2
17

---

[124] Ian Osband, John Aslanides, and Albin Cassirer. Randomized prior functions for deep reinforcement learning. Advances in Neural Information Processing Systems, 31, 2018. 25, 26
[125] lan Osband, Benjamin Van Roy, Daniel J Russo, and Zheng Wen. Deep exploration via randomized value functions. Journal of Machine Learning Research, 20(124):1-62, 2019.
26
[126] Ian Osband, Zheng Wen, Mohammad Asghari, Morteza Ibrahimi, Xiyuan Lu, and Benjamin Van Roy. Epistemic neural networks. arXiv preprint arXiv:2107.08924 2021. 25, 26
[127] lan Osband, Zheng Wen, Seyed Mohammad Asghari, Vikranth Dwaracherla, Botao Hao, Morteza Ibrahimi, Dieterich Lawson, Xiuyuan Lu, Brendan O' O'Donoghue, and Benjamin Van Roy. Evaluating predictive distributions: Does Bayesian deep learning work? arXiv preprint urXiv22110004622 2021. 25
[128] Hari Palaiyanur and Anant Sahai. On the uniform continuity of the rate-distortion function. In 2008 IEEE International Symposiun on Information Theory, pages 857 367-861. IEEE, 2008. 25
[129] Yury Polyanskiy and Yihong Wu. Lecture notes information theory. 2019.
[130] Martin L. Puterman. Markov Decision Processes Joocesse--Diccreee Stochastic Dynamic Programming. John Wiley & Sons, Inc., New York, NY, 1994.
[131] Kate Rakelly, Aurick Zhou, Chelsea Finn, Sergey Levine, and Deirdre Quillen. Efficient off-policy rentrrreinfrr learning via probabilistic context variables. In International conference machine learning, pages 5331 5331-5340. PMLR, 2019. 25
[132] Kenneth Rose. A mapping approach to rate-distortion computation and analysis. IEEE
Transactions on Information Theory, 40(6):1939-199 1952, 1994. 25
[133] Jonathan Rubin, Ohad Shamir, and Naftali Tishby. Trading value and information in MDPs. In Decision Making with Imperfect Decision Makers, pages 57-74. Springer, 2012. 22
[134] Paat Rusmevichientong and John N Tsitsiklis. Linearly parameterized bandits. Mathematics
Operations Research, 35(2):995-411, 2010. 22
[135] Daniel Russo and Benjamin Van Roy. Learning to optimize via informatiion-drrcted sampling. Advances in Neural Information Processing Systems, 27:1583-1591, 2014. 7, 22, 38
[136] Daniel Russo and Benjamin Van Roy. An information-theoneea analysis of Thompson sam- pling. The Journal of Machine Learning Research, 17(1):242-22771, 2016.
[137] Daniel Russo and Benjamin Van Roy. Learning to optimize via information-direeted sampling.
Operations Research, 66( ():23))222555500 252, 2018. 7, 22
[138] Daniel Russo and Benjamin Van Roy. Satisficing in time-sensitive bandit learning. arXiv
preprint arXiv: 103.008803.02855, 2018. 2, 5, 6, 7, 22
[139] Daniel Russo and Benjamin Van Roy. Satisficing time-sensitive bandit learning. Mathematics of Operations Research, 2022. 2, 5, 6, 22
[140] Daniel Russo, David Tse, and Benjamin Van Roy. Time-sensitive bandit learning and satisficing Thompson sampling. arXiv preprint arXiv: 7704.09044.90. 2017. 2, 6, 22
[141] Daniel J Russo, Benjamin Van Roy, Abbas Kazerouni, Ian Osband, and Zheng Wen. A tutorial on Thompson sampling. Foundations and Trends@ Machine Learning, 11(1):1-96, 2018. 1,
22
[142] Ilya O Ryzhov, Warren B Powell, and Peter Frazier. The knowledge gradient algorithm for general class of online learning problems. Operations Research, 60(1): 80-195, 2012. 22
[143] Jossy Sayir. Iterating the Arimoto-Blaie algorithm for faster convergence. In 2000 IEEE International Symposium on Information Theory (Cat. No. 00CH37060), page 235. IEEE,
2000. 25
18

---

[144] Julian Schrittwiese,, Ioannis Antonoglou, Thomas Hubert, Karen Simonyan, Laurent Sifre, Simon Schmitt, Arthur Guez, Edward Lockhart, Demis Hassabis, Thore Graepel, et Master- ing Atari, Go, Chess and Shogi by planning with learned model. Nature, 588(7839):604-609 2020. 5, 23, 25
[145] Ehsan Shafieepoorfard, Maxim Raginsky, and Sean Meyn. Rationally inattentive control of Markov processes. SIAM Journal on Control and Optimization, 54(2)988--0016 2016. 22, 25
[146] Claude E. Shannon. Coding theorems for discrete source with fidelity criterion. IRE Nat. Conv. Rec., March 1959, 4: 4:142-16:3 163, 1959. 2, 4, 10, 22
[147] David Silver, Hado Hasselt, Matteo Hessel, Tom Schaul, Arthur Guez, Tim Harley, Gabriel Dulac-Arnold, David Reichert, Neil Rabinowitz, Andre Barreto, et al. The Predictron: End- to-end learning and planning. International Conference on Machine Learning, pages 3191-3199. PMLR, 2017. 2,
[148] Herbert A. Simon. Models of bounded rationality. Economic Analysis and Public Policy, MIT Press, Cambridge, Mass, 1982.
[149] Jonathan Sorg, Satinder Singh, and Richard L Lewis. Variance-based rewards for approxi- mate Bayesian reinforcement learning. In Proceedings of the Twenty-Sixth Conference on Uncertuinty Artificial Intelligence, pages 564-571, 2010. 22
[150] Jan-Erik Stjemnaal.. Dominance relation between distortion measures. IEEE Transactions
Information Theory, (9(6))798-807 1983. 8, 32, 33
[151] Alexander I. Strehl, Lihong Li, and Michael I. Littman. Reinforcement learning in finite
MDPs: PAC analysis. Journal of Machine Learning Research, 10(Nov):2413-2444, 2009. 1, 22
[152] Malcolm JA Strens. A Bayesian framework for reinforcement learning. In Proceedings of the Seventeenth International Conference on Machine Learning, pages 943-950, 2000. 6, 22
[153] Wen Sun, Nan Jiang, Akshay Krishnamurthy, Alekh Agarwal, and John Langford. Model- based RL in contextual decision processes: PAC bounds and exponential improvements over model-free approaches. In Conference on Learning Theory, pages 2898-2933, PMLR, 2019.
22
[154] Richard S Sutton and Andrew G Barto. Introduction reinforcement learning. 1998.
[155] Sekhar Tatikonda and Sanjoy Mitter. Control under communication constraints. IEFE Trans- actions on Automatic Control, 1966)1056-1 2004. 22
[156] William R Thompson. On the likelihood that one unknown probability exceeds another in view of the evidence of two samples. Biometrika, 25(3/4):285 1933. 1, 22
[157] Naftali Tishby and Daniel Polani. Information theory of decisions and actions. In Perception-
action cycle, pages 601-636. Springer, 2011. 22
[158] Naftali Tishby, Fermando C Pereira, and William Bialek. The information bottleneck method.
arXiv preprint physics/0000057 2000. 9, 25
[159] Benjamin Van Roy. Performance loss bounds for approximate value iteration with state aggregation. Mathematics of Operations Research, 31(2):234-244, 2006. 23, 25
[160] Sergio Verdú et al. Generalizing the Fano inequality. IEEE Transactions on Information Theory, (:444))))2271225 1994. 8
[161] Claas A Voelcker, Victor Liao, Animesh Garg, and Amir-massoud Farahmand. Value gradient weighted model-based reinforcement learning. In International Conference on Learning Representations, 2022. 7,
[162] Pascal O Vontobel, Aleksandar Kavcic, Dieter M Amold, and Hans-Andrea Loeliger. A generalization of the Blahut-Arimoto algorithm finite-state channels. IEEE Transactions on Information Theory, 54(5):1887-111 2008. 25
19

---

[163] Tao Wang, Daniel Lizotte, Michael Bowling, and Dale Schuurmans. Bayesian sparse sampling for on-line reward optimization. In Proceedings of the 22nd International Conference on Machine Learning, pages 956-963, 2005. 22
[164] Yizao Wang, Jean- YveanYves Audibert, and Rémi Munos. Algorithms for infinitely many aamedd bandits. In Proceedings of the 21 International Conference on Neural Information Processing Systems, pages 17391773, 2008. 22
[165] Ward Whitt. Approximations of dynamic programs, I. Mathematics of Operations Research, 3 (3):231 1978. 23
[166] Hans Witsenhausen. Separation of estimation and control for discrete time systems. Pro- ceedings of the IEEE, 59(1 1971. 22
[167] Yaming Yu. Squeezing the Arimoto-Blahut algorithm for faster convergence. IEEE Transac- tions on Information Theory, 56(7):3149-3155) 2010. 25
[168) Andrea Zanette and Emma Brunskill. Tighter problem-dependen regret bounds in reinforce- ment learning without domain knowledge using value function bounds. In International
Conference on Machine Learning, pages 7304-7312. PMLR, 2019. 1, 22
[169] Julian Zimmert and Tor Lattimore. Connections between mirror descent, Thompson sampling and the information ratio. In Advances in Neural Information Processing Systems, pages 11973 11922, 2019.
[170] Luisa Zintgraf, Kyriacos Shiarlis, Maximilian Igl, Sebastian Schulze, Yarin Gal, Katja Hof- mann, and Shimon Whiteson. VariBAD: A Very Good Method for via Meta-Leamiing In International Conference Learning Representations, 2019. 25
Deep RL
Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's
contributions and scope? [Yes]
(b) Did you describe the limitations of your work? [Yes]
(c) Did you discuss any potential negative societal impacts of your work? [N/A]
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you are including theoretical results...
(a) Did you state the full of assumptions of all theoretical results? [Yes]
(b) Did you include complete proofs of all theoretical results? [Yes]
3. If you experiments...
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either in the supplemental material or as URL)? [N/A]
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [N/A]
(c) Did you report error bars (e.g., with respect the random seed after running experi- ments multiple times)? [N/A]
(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, cloud provider)? [N/A]
4. If you are using existing assets (e.g., code, data, models) or curating/releasing new assets...
(a) If your work uses existing assets, did you cite the creators? [N/A]
(b) Did you mention the license of the assets? [N/A]
(c) Did you include any new assets either in the supplemental material or as a URL? [N/A]
(d) Did you discuss whether and how consent was obtained from people whose data you're using/curating? [N/A]
20

---

(c) Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content? [N/A]
5. If you used crowdsoureing conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, if applicable? [N/A]
(b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent on participant compensation? [N/A]
21


Reviews:
[{"review_id": "q9STzllo06G", "reviewer": "Reviewer_7znE", "summary": "This paper studies exploration in reinforcement learning from the Bayesian perspective, specifically adopting a Thompson sampling approach to obtain bounded Bayesian regret. The distinguishing factor in this analysis is the addition of a model compression component in which the user can accept a (tunable) amount of additional regret in exchange for simplifying the sampled model that must be solved in each iteration, potentially improving computational and/or sample complexity.", "questions": "No questions.", "limitations": "Yes, I thought the paper did an excellent job of acknowledging limitations. For instance, it acknowledges a missing detail in the analysis (the form of a bound on information ratios). It is also quite forthcoming about the limited connection of the theory to practically applicable algorithms.", "rating": 6, "confidence": 3, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "This paper moves the theory of efficient RL in an interesting direction with a novel combination of two existing ideas (PSRL and rate-distortion theory). I found it to be well-written and compelling. It is unlikely to impact practice, but it does contribute to our understanding of sample efficiency in RL, specifically by adding a tradeoff between optimality and model complexity.\n\n--Originality--\n\nThe algorithm is clearly built upon the existing PSRL algorithm, which is fully acknowledged within the paper. The theoretical arguments are also built upon existing analyses using rate-distortion theory to quantify the simplification of the problem in a bandit context. The paper also fully acknowledges these connections.\n\nI do think that the combination of these approaches is novel, worthwhile, and non-trivial.\n\nThe paper also does an excellent job of situating this work in the context of other theoretical results regarding efficient reinforcement learning. This occurs both in the main text and in an extensive appendix.\n\n--Quality--\n\nThe findings in this paper are all theoretical in nature. The proofs seem well argued to me and I found no fault with them. That said, this is my first exposure to rate-distortion theory so it is possible that I would not detect a misapplication of those ideas.\n\n--Clarity--\n\nOverall, I found the paper to be well-written. As is typical for a theoretical paper, this paper is technically dense and requires close attention from the reader. Nevertheless, the authors have done a good job of surfacing their motivation, the core ideas of their analysis, and the potential consequences. I also appreciate the attention given to helping the reader develop intuition with rate-distortion, which is not as widely familiar to the ICML audience as other aspects of the work.\n\nI do have one minor clarity suggestion: the paper currently uses R for both reward and rate-distortion; it might be better to separate the notation for those two concepts.\n\n--Significance--\n\nI think this paper tackles an important issue. The theory of efficient RL typically implicitly assumes that the agent is capable of learning a perfect model of and then perfectly solving an arbitrary MDP. It is refreshing to see theoretical work in this area that widens attention beyond this limiting assumption. It seems plausible that the framework used here could be built upon in future work to further study efficient RL with imperfect models, for instance considering different possible limits on agent capacity.\n\nI will also say that it is not entirely clear what lesson to take from these results. The paper acknowledges that this algorithm is not practically implementable (not uncommon for a paper of this sort). But there is a high-level principle here that could inspire more practical approaches, namely that if you are careful, you can get away with simplifying the sampled model that you get from your posterior so it's easier to solve.\n\nIn all, I don't think that this paper presents a notably surprising theoretical result and certainly won't impact practice in the near term, but it does move the ball in an important direction.", "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": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "Lj0NE2y3PMB", "reviewer": "Reviewer_iP5r", "summary": "In this paper the authors describe a new theoretical framework for exploration in RL. Their work builds upon earlier results on Posterior Sampling in Reinforcement learning. The main idea is to obtain posterior models which are compressed versions of the true MDP using the value equivalence principle as a distortion metric. By doing so they can harness the benefits of using value equivalent models and of posterior sampling. They provide a Bayesian regret bound for their method, which is the result of the regret caused by the use of a compressed model and that incurred while learning the model. ", "questions": "My main concern is that it is not clear how this work can be useful in developing new algorithms even in simple tabular problems. The authors do not provide a practical instantiation of their method even in small toy domains and instead discuss the challenges of developing such an algorithm. This is different from standard PSRL. At the same time I cannot see how the results presented in this work can inform the design of better value equivalent algorithms which usually operate in high dimensional problems at scale (i.e. MuZero). Can the authors provide more insight on this ?", "limitations": "The authors have adequately addressed the limitations and potential negative societal impact of their work.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "The paper provides a solid theoretical framework for value equivalent posterior sampling in reinforcement learning. The recent success and simplicity of value-equivalent approaches provide motivation for such work. On the other hand, posterior sampling provides solid theoretical guarantees to the problem of exploration in RL. Studying the combination of the two approaches can be useful to the community.\n\nThe paper is well written / structured and provides a lot of additional analysis and discussion in the appendix. My main concern is described in the questions section to the authors. \n", "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": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "IsAVhvcD0TO", "reviewer": "Reviewer_UCCG", "summary": "This paper studies value equivalence and considers the scenario where the agent limitations may entirely preclude identifying an exact value equivalent model, which immediately gives rise to a trade-off between identifying a model that is simple enough to learn while only incurring bounded suboptimality. To address this problem, the paper proposes an algorithm that iteratively computes an approximately-value-equivalent, lossy compression of the environment which an agent may feasibly target in lieu of the true model. It also proves an information-theoretic, Bayesian regret bound for the proposed algorithm that holds for any finite-horizon, episodic sequential decision-making problem. \n", "questions": "1. On the significance of the theoretical results in terms of practicality in the deep reinforcement learning setting: Even though the theoretical results of this paper are interesting by themselves, I think that providing a brief section on how these results can at least help developing better deep RL algorithms (algorithms that work with high dimensional inputs) can significantly benefit the paper. Is it possible to provide a discussion on this?\n2. On the significance of the illustrative example multi-resolution MDP: Is it possible to provide a discussion on why the MDP structure in example 1 is an important one? When does this structure become important? As far as I know, most of the MDPs of interest in the literature do not have this kind of a structure.\n", "limitations": "Yes the authors mention the limitations of their work.\n", "rating": 5, "confidence": 1, "soundness": 2, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "**Originality:** The paper seems to be original in the sense that it introduces an algorithm that implicitly identifies, in a purely data-driven and automated fashion, the resource limitations of the agent to facilitate tractable, near-optimal learning in what may otherwise be an intractable problem. Though I would like to note that I am not particularly familiar with this area of research.\n\n**Quality:** Overall, there seems to be no serious quality issues with the paper. Though, I would like to indicate that I haven’t checked the theoretical results in a very detailed manner and just went over them at a high-level.\n\n**Clarity:** I found no problems with the clarity of the paper. The paper is very well-written. I have nothing to suggest.\n\n**Significance:** Even though the derived theoretical results seem to be interesting in their own sense, I would like to indicate that I found the paper to have problems in the significance of the results. More specifically, I am not sure if the paper provides enough discussion on how the derived results and proposed algorithm can be beneficial in the deep reinforcement learning setting. More on this can be found in the Questions section below.\n", "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": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "7sVMV8i-3O8", "reviewer": "Reviewer_gPNG", "summary": "The authors introduce Value-equivalent Sampling for Reinforcement Learning (VSRL), an extension to Posterior Sampling for Reinforcement Learning (PSRL).\n\nThe key idea behind VSRL is to sequentially solve simplified versions of the true environment with the ultimate goal of minimizing the bayesian regret of the policy.\n\nAn information-theoretic analysis of VSRL is provided with regret bounds for the general case, the tabular setting, and an agent with limited capacity.", "questions": "From what I understand, it is not trivial how to instantiate VSRL in practice. Could the authors think of a minimal example on which VSRL could be run? For instance, in the same vein as the experiments run in PSRL. Such experiments would definitely change my view on the limitations of this paper, which has already a strong theoretical foundation.", "limitations": "The main limitation of this paper is the absence of experimental results. The authors leave the application of VSRL to actual environments as future work, but in my opinion this work is incomplete without at least toy experiments demonstrating the usefulness of the approach.\n\nThe authors do not discuss potential negative impact of their work, but it is rather not applicable here since the paper is mostly about theory.  ", "rating": 5, "confidence": 2, "soundness": 3, "presentation": 4, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "# Strengths\n\n- The method proposed is well motivated and intuitive.\n- It is supported by a thorough theoretical analysis, although regret analysis is not my area of expertise.\n- The paper is mostly well written and has a nice flow of sections and ideas.\n\n# Weaknesses\n\nThe authors do not provide any empirical evidence supporting their method. VSRL is framed as an algorithm for real-world high-dimensional settings where current agents may fail due to computational issues, but it is not even applied to a toy environment. Therefore, the reader is left at the stage of theoretical guarantees, with no actual idea of how to implement the algorithm, and how it would perform in practice.", "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": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept