The Value of Information When Deciding What to Learn
Authors: Dilip Arumugam
Benjamin Van Roy
Venue: NeurIPS 2021 Poster (2021)
Keywords: Multi-armed bandits
sequential decision-making under uncertainty
information theory
efficient exploration
reinforcement learning

Abstract: All sequential decision-making agents explore so as to acquire knowledge about a particular target. It is often the responsibility of the agent designer to construct this target which, in rich and complex environments, constitutes a onerous burden; without full knowledge of the environment itself, a designer may forge a sub-optimal learning target that poorly balances the amount of information an agent must acquire to identify the target against the target's associated performance shortfall. While recent work has developed a connection between learning targets and rate-distortion theory to address this challenge and empower agents that decide what to learn in an automated fashion, the proposed algorithm does not optimally tackle the equally important challenge of efficient information acquisition. In this work, building upon the seminal design principle of information-directed sampling 
(Russo & Van Roy, 2014), we address this shortcoming directly to couple optimal information acquisition with the optimal design of learning targets. Along the way, we offer new insights into learning targets from the literature on rate-distortion theory before turning to empirical results that confirm the value of information when deciding what to learn.


The Value of Information When Deciding What to Learn
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
All sequential decision-making agents explore so as to acquire knowledge about a particular target. It is often the responsibility of the agent designer to construct this target which, in rich and complex environments, constitutes a onerous burden; without full knowledge of the environment itself, designer may forge sub- optimal learning target that poorly balances the amount of information an agent must acquire to identify the target against the target's associated performance shortfall. While recent work has developed a connection hetween learning targets and rate-distortion theory to address this challenge and empower agents that decide what to learn in an automated fashion, the proposed algorithm does not optimally tackle the equally important challenge of efficient information acquisition. In this work, building upon the seminal design principle of information-direed [Russo and Van Roy, 2014], we address this shortcoming directly to couple optimal information acquisition with the optimal design of learning targets. Along the way, we offer new insights into learning targets from the literature on rate-distortion theory before turning to empirical results that confirm the value of information when deciding what to learn.
sampling
Introduction
Information acquisition is fundamental consideration in the design of sequential decision-making agents. Indeed, the literature over recent years has unequivocally demonstrated its theoretical [Russo and Van Roy, 2016, 2014, 2018a] and empirical [Osband al., 2016a,b, Nikolov et al., 2018] importance in addressing the challenge of exploration in sequential decision-making problems. Despite this significance, a strategy for information acquisition, however efficient, is only as good as the information it uncovers. An agent that displays remarkable efficiency in seeking immaterial information offers little utility to its designer. Similarly, when faced with the rich complexity of real-world tasks, a sorpuutttionallyybuneeed constrained resources is equally ineffective. As a concrete example of the latter scenario, consider learning the optimal policy for the game of Go [Silver et al., 2017] solely relying on the hardware of a mobile device. While not an entirely infeasible task, the amount of time needed to complete such endeavor may force the agent designer into settling for a small fraction of the optimal policy performance in exchange for a substantial reduction in the difficulty of the learning problem.
agent aspiring to learn that which is well beyond its
Recent work has developed connection between rate dit-distootion theory [Shannon, 1959, Berger, 1971] and the problem of deciding what an agent should learn [Arumuaam and Van Roy, 2021], optimally balancing between the requisite information needed by any agent to identify a learning target and the corresponding performance shortfall associated with this target. Intuitively, the complexity of learning problem can be quantified by the bits of information an agent must acquire from the
35th Conference on Neural Information Processing Systems (NeurIPS 2021).

---

environment in order to realize a particular target. Rate-distortion theory offers a principled framework for reasoning about a learning target that comprises the minimum number of bits from the environment while retaining some degree of near-optimality. Arumugam and Van Roy [2021] operationalize the classic Blahut- Arimoto algorithm [Blahut, 1972, Arimoto, 1972] in the multi-armed bandit setting to facilitate computationally-tree -tracttale agents that are not only capable of computing such an optimal target at the start of learning but also gradually adapt this target over time as the agent's knowledge of the environment accumulates. The resulting Blahut-Arimoto Satisficing Thompson Sampling algorithm (BLASTS) then applies the well-known principle of probability matching in order to select actions [Thompson, 1933, Russo et al., 2018]. While BLASTS demonstrates the desired ability to accommodate an agent designer in recovering a wide spectrum of policies with varying levels of performance and learning efficiency, it is well known that the underlying probability matching principle of Thompson Sampling constitutes a sub-optimal exploration strategy [Russo and Van Roy, 2018a].
In this work, we combine the optimal computation of learning targets via rate-distortion theory with optimal information acquisition. To achieve the latter goal, we generalize the information-directe sampling (IDS) principle of Russo and Van Roy [2] so that the fundamental information ratio captures expected regret and information gain about learning target computed via the Blahut- Arimoto algorithm. As with BLASTS, the resulting algorithms which instantiate this Blahut-Arimoto information-Directeed Sampling principle (BLAIDS) retain single, real-valued hyperparameter through which an agent designer expresses a preference for the balance struck by the resulting learning target. Moreover, just as BLASTS offers generalization of Thompson Sampling capable of more efficiently computing optimal policies, we find that a particular computationally-tracaal instantiation of BLAIDS mirrors this property relative its IDS counterpart. En route deriving BLAIDS, we outline the precise details of the Blahut-Arimoto algorithm itself and connect our setting with various results from the information-theory literature.
The paper proceeds as follows: in Section we offer a general presentation of information-theoreet learning targets for sequential decision-making problems. We then hone in on the nulti-armed bandit setting in Section to carefully study incorporating the value of information when acting in pursuit of an arbitrary learning target. We conclude in Section 4 with corroborating set of computational experiments that demonstrate the efficacy of our approach. Due to space constraints, we relegate background material information theory, related work, and all technical proofs to the appendix.
2 Learning Targets
This section focuses on a general treatment of learning targets via rate-distortion theory, moving beyond the assumptions of Arumugam and Van Roy [2021] and offering further insight into the mathematical details of the Blahut-Arimoto algorithm.
2.1 Problem Formulation
In this section, follow the general problem formulation of Lu et al. [2021] that offers unified treatment of sequential decision-making problems, spanning multi-armed bandits and reinforcement- learning problems [[attimore and Szepesvári, 2020, Sutton and Barto, 1998]. We adopt generic egent-environment interface wherein, at each time period, the agent executes an action A, E A within an environment & which results in associated next observation O.+1 O. This sequential interaction between agent and environment results in an associated history at each timestep H; (Ao. O1,..., A O.) E H representing the action-observation sequence available to the agent upon making its selection of Ar. More formally, we may characterize the overall environment as 3 = (A, O) containing the action set A. observation set O, and the observation function p: H. x A + ((O) that prescribes the distribution over next observations given the current history and action selection:
P(O++IEE H,, A,) P(O++1|
Oct1 p(. Hle, At).
An agent's policy π: H + (AA) encapsulates the relationship between the histories encountered in each timestep H, and the executed action A,. We maintain that actions are independent of the environment conditioned on history, A, 1 H, such that π (a)H.) = P((A, = a aHH,) assigns a probability to each action E A given the history.
2

---

An agent designer expresses preferences across histories via reward function r: H. x A O R such that an agent enjoys reward R r(H,, A,, 02+1) 1) at each timestep. Given any finite time
T-1
horizon T o0, the accumulation of rewards provide a notion of return Σ Re+1- To develop
preferences over behaviors, it is natural to associate with each policy π corresponding expected
return value across the horizon T as V IE
R4+1 E where the expectation integrates
over the randomness in the policy л as well as the observation function p. A trademark across the sequential berisionnmaaing literature is the design of agents that strive to achieve the optimal value within the confines of some policy class 11 S {- H - ((A)), V sup V Notice that when
лE rewards and the distribution of the next observation Oz+1 depend only on the current observation O,, rather than the full history He, we recover the traditional Markov Decision Process [Bellman, 1957, Puterman, 1994] studied throughout the cewtorreeeemt-eeennnne literature [Sutton and Barto, 1998]. Alternatively, when these quantities rely solely upon the most recent action A,, we recover the traditional multi-armed bandit [Lattimore and Szepesvári, 2020J.
2.2 The Curse of Curiosity
While the design of agents in pursuit of optimal policies is perfectly natural object of study, can often occur without regard for the complexity of the environment. In particular, the optimal policy is often a deterministic function of the environment such that, if an agent manages identify the environment, it possesses all requisite information to determine the optimal policy. An agent designer reflects their initial uncertainty about the environment through a prior distribution P(E E :): as the history unfolds, what can be learned from the agents current knowledge of the environment is represented by conditional probabilities IEEE E -(H)). Through this prior distribution, a total of HI(E) bits quantify all of the information needed for identifying the environment. Prior work has demonstrated both theoretically and empirically how it is an agent's s incremental resolution of epistemic uncertainty over the environment & that gives rise the efficient acquisition of these (E)) bits [Chapelle and Li, 2011, Russo and Van Roy, 2016, Osband et al., 201 6a, Agrawal and Jia, 2017, O' O'Donoghue et al., 2018, Osband et al., 2019]. For sufficiently rich and complex environments, however, HE) can become prohibitively large or even infinite, making the pursuit of an optimal policy entirely intractable.
This issue warrants the construction of a more general mechanism whereby an agent designer may express tractable learning targets, alternatives to the optimal solution that, while potentially incurring some degree of suboptimality, fall within the means of a computationally-boundde with highly-complex environment. Lu et al. [2021] introduce this notion of a learning target x as generic random variable and (possibly stochastic) function of the environment E. Their proposed desiderata for the construction of learning target is two-fold: (1) demanding only feasible amount of information from the environment I[E;; x) in order to reconcile x and (2) incurring a bounded degree of performance shortfall by aiming for EVV* - V. where xx is a target policy induced by X- Observe, however, that this treatment of a learning target assumes its provision to the agent before interaction with the environment has begun. Consequently, the burden of specifying a suitable learning target that best balances between the two desiderata falls upon the agent designer. To remedy this, we begin by extending the formulation of Arumugam and Van Roy [2021] and emphasizing rate-distortion theory as a general tool for the design of optimal learning targets.
agent interacting
It is important to re-iterate and clarify that the role of Tx is not to achieve performance that is on par with the optimal x*, but rather to strike an appropriate balance between performance shortfall relative to x* and the ease of learnability; the latter desideratum is accurately captured mathematically via bits of information. As an agent shifts its focus away from ' towards a x that is easier learn (in the information-thhorrtiicc sense used throughout this paper), we anticipate greater data efficiency. That is, an agent should be able to more quickly identify the desired X relative to the requisite amount of time and data needed to identify π.. Naturally, in a complex environment, we expect this data efficiency to be critical and to come at some cost: the sub-optimality of the resulting solution (which we take as the distortion in our rate-distortion framing). An agent designer's willingness to tolerate this sub-optimality stems from the complexity of the environment and an acknowledgement of the potentially intractable amount of data needed to otherwise identify and recover x². The more
3

---

performance shortfall one is willing to tolerate relative to optimal behavior, the more efficiently an agent should be able find such satisficing solution. Russo and Van Roy [2018b] already highlight one example of this phenomenon in the multi-armed bandit setting, where the presence of multiple arms can make pursuit of an e-optimal arm far more data efficient than the optimal arm. From the perspective of the agent designer, one should not incorporate a learning target with the expectation of being competitive with the optimal policy, but rather with the goal of being more data efficient in the acquisition of the learning target relative to that of the optimal policy.
2.3 The Rate-Distortiin Theory of Learning Targets
Rate-distortion theory is a sub-area of information theory that encapsulates the foundations of lossy compression [Shannon, 1959, Berger, 1971, Cover and Thomas, 2012]. Abstractly, rate- distortion theory formulates a lossy compression problem as a constrained optimization in the space of probability kernels or channels, given an information source and a tolerable upper threshold on distortion. The natural goal is to identify a channel that preserves the minimum number of bits from the information source while adhering to the specified distortion upper bound.
More formally, let (Ω, F,F. P) be a probability space and consider a random variable X X + X taking
values on the measurable space (X' X) with an associated marginal distribution Fx(() = ())
that represents information source. Similarly, define the random variable X Ω + X that
takes values (22, X) and corresponds to a channel output. Given known, measurable distortion function d : X x X + IR20 and desired upper bound on distortion D, the rate-distortion function is defined as R(D) = inf XX): quantifying the minimum number of bits (on average)
P
PxREA
that must be communicated from X across a channel in order to adhere to the specified expected distortion threshold D. Here, the infimum is taken over A x AA E X P x__ Px (A x X)
Fx (A) and XX]] S D} representing the set of all joint distributions on (X x X, X x X) whose corresponding marginal distribution on X matches the original information source Ixx while also satisfying the constraint on bounded expected distortion. Intuitively, higher rate corresponds to requiring more bits of information and smaller information loss between X and X, enabling eigher-fidelity reconstruction (lower distortion); conversely, lower rates reflect more substantial information loss, potentially exceeding the tolerance on distortion D. The remainder of this section is devoted to making the mathematical details of this problem precise in our specific context of specifying learning targets. We encourage readers to consult the appendix for the precise details of our notation.
At each timestep, an agent maintains its epistemic uncertainty over the environment via posterior distribution (PE H,). Since the derivation is identical for all timesteps, we suppress time and history from the notation for now and let Pe denote this distribution at any arbitrary timestep. We will take the environment& & and learning target random variables to be associated with measurable spaces (E, S) and (E, X), respectively. Let Pε.x defined on (Σ E, x X) be a joint distribution over environment- target pairs. Furthermore, let d Σ x E + Rgo be known, measurable function that quantifies a notion of loss or distortion that occurs by using a particular realization of the learning target within a specific realization of the environment. We may define the rate-distortion function as
inf R(D)= Pe. PERE)R)
I(PExx)
inf Pe EA
I(EEx))
(1)
= (PEx
and V [T] T H.
(2)
where the infimum is taken over the constrained set of joint probability measures A such that (1) the E marginal of Pε.x matches the given source distribution (2) the expected distortion does not exceed the given threshold De E >0 and (3) the target is conditionally independent of all histories given the environment. These first two conditions are typical in rate-distortion theory while the final condition simply ensures that no history can offer more information about a learning target than what is already provided by the environment. While the distortion function d will eventually be defined so as to quantify the performance shortfall of our learning target, we proceed with the generic,
'Typically, R(D) is defined in terms of the mutual information, however the (equivalent) parameterization via the joint distribution Pe,x will be useful in subsequent derivations.

---

unspecified distortion function for now and assume that RDD) - 0 as D - co. Following from this assumption along with the convexity of mutual information and Gibb's inequality, we may recover the basic facts that RDD) is non-negative, convex, and Nonotonically-decreaati function in its argument [Cover and Thomas, 2012].
The details of computing rate-distortion functions as presented by Arumugam and Van Roy [2021] rely on the classic derivation based on calculus and Lagrange multipliers, under the assumption that the information source and channel output are discrete random variables [Blahut, 1972]. In brief and continuing with the first example of this section, the discrete algorithm proceeds by initializing Po( x)
|x -1, 47 E & and then iterating the following two updates
qk aT) p1(t)pt-1(2 x)
Pk-1(1 x)) x ga (7) exp (-3d(x,
ZEN
where p(a) denotes the information source and 3 is Lagrange multiplier. While discreteness carries computational conveniences for practical implementation, here we offer a more general presentation of the Blahut-Arimoto algorithm for arbitrary environments and learning targets. It is important clarify that the subsequent derivations of this section are classic results in the information-theory literature [Csiszár, 1974, Gray, 2011] and do not represent novel theoretical contributions of this work; that said, we do take our contribution to be distilling such key results from the information-theory literature for broader consumption by the sequential decision-making community and, that end, offer a full presentation for the benefit of readers.
For the purposes of handling this constrained optimization, introduce the following objective with parameter / 2
F(3) inf (T((Px.x) + 3E (d(E, = inf EA
(PP x IPx) + 3B (d(E, x)]) PE,
As noted by Csiszár [1974], F(B) is the largest vertical-axis intercept of line with slope -8 that includes no point above the nate-distottion curve. Moreover, the dite-distortion function can be expressed in terms of this new objective, sweeping over all possible values of B.
Lemma (Lemma 1.2 [Csiszár, 1974)).
R(D) = max max F(8)
$20
The value of 3 that achieves this maximum is characterized as being associated with the distortion threshold D. Conversely, joint distribution Pe,x that achieves the infimum of F(3) has associate rate R(D) T(Px.x) where B is associated with D Ere,x [d(E, A d(E, (CCCx))dPPe.c Ex
Lemma 1 clarifies an important relationship between the parameter and the rate-distortion curve, accommodating computation of the rate-distortion function upon specification of particular /3 values rather than distortion upper bound D; in particular, each 3 corresponds to the slope of a tangent line to the rate-distortion curve such that, given a value of 3, the associated joint distribution that achieves the infimum in F(8) generates the point (D, RD)) on the curve. Per Blahut [1972], computing the infimum in F(B) is handled by an alternating optimization procedure that relies on the following functional:
I (P Qx = DKI. (P'.x Ie x Qx) + -3,,,,,, (d(E,x))
which replaces the marginal distribution over x induced by Pε.x with an alternative distribution Qy. When J (P'xxx Qx 3) is finite, this implies that PE.x < Pg Qx moreover, if Ep,,x [d(E, x)] is finite, then Pg x (x((E, xld(E < oo)) > O. Taken together, these facts imply that for any realization of the environment
(0)s(E)) = / cxp (- Bd(E, x)) (x)
< 00
holds Pg-almost surely. Thus, for any marginal over learning targets Qx we may induce a new joint distribution Qe,x whose corresponding Radon-Nike MakooyNi derivative with respect to P& Q2 given by
dQex = aQ (1)
(3)
dP's x Qx
5

---

While the corresponding marginal of this new joint distribution need not be identical to Qx we can show that our original source distribution Pş is preserved under the corresponding marginal. In particular, for any measurable set A E S, we have
dQex dPp x Qx(E,x)= de x Qx
(Ax
x Qx(E,x)
FXB
Px3
= (OQue(E)
/ /oxp (xx((BB((,x))
dIP's (E) = Pe(A).
where the second line uses the aforementioned integrability conditions to apply Fubini's Theorem. To recover an alternating optimization procedure for minimizing our objective and computing the rate-distortion function, we may leverage the following relationship between the original and new joint distributions:
Lemma 2 (Lemma 1.2 [Csiszár, 1974]. Let Qx be an arbitrary marginal distribution over X- Moreover, let Fx be an arbitrary joint distribution over E, X with an associated marginal distribution Fx and take Ql be the joint distribution as defined Equation Then,
J(Px.x Qx. 8) 2 J [(PE.x: B)
J(Pxx: 2x. 9) 2 xQ 2x.
Lemma 2 prescribes a natural algorithm for the computation of rate-distortion functions. Upon the provision of source distribution over environments F3 and an initial marginal distribution over learning targets Q one may first compute an updated channel distribution Q per Equation 3.
The induced marginal of Qf serves as the next distribution 2 giving rise to another updated channel O Naturally, this process may continue iteratively until convergence. By the second inequality of Lemma 2, the updated channel distributions Q are non-increasing in the objective and, analogously, the induced marginal distribution is also guaranteed to not increase the objective by the first inequality. This procedure is precisely the classic Blahut- Arimooo algorithm [Blahut, 1972, Arimoto, 1972], generalized beyond the assumptions of discrete source and channel output random variables.
2.4 Target Policies for Reinforcement Learning
With the results of the previous section in hand, an agent may, at any timestep, run the Blahut-Arimoto algorithm using its current posterior beliefs over the environment P(E H,) as source distribution in order to compute learning target that optimally negotiates between the information required to learn and the resulting target performance shortfall. In the context of reinforcement tinnforremeen-llammnng problems, this learned target corresponds to a particular target policy मx and, to ensure the latter criterion holds, a natural notion of distortion is the expected squared regret between the optimal and target policies:
- ADD) Σ Li'st
d(E,xl x H.)) T (VV - H. = E
E H,
The final equality follows from a variant of the performance-differeeee lemma [Kakade and Langford, 2002] and is proven for our setting Theorem 1 of Lu et al. [2021]. Unfortunately, while the results of the previous section hold for this particular sequence of rate-distortion functions, the choice of X as a target policy represents an obstacle to practical implementation. In particular, this would imply that the resulting channel of the Blahut-Arimota algorithm would map between realizations of the environment & target policies associated with each possible realization of the target policy Tx would require either an independent
H (AA). Moreover, computation of the distortion
policy-evaluation step to compute the value function //* or demand sampling trajectories of each potential x from the environment in order to leverage the final performance shortfall decomposition shown above.

---

One possible resolution to these issues might include leveraging recent progress in unsupervised skill discovery [Eysenbach et al., 2018] such that potential target policies xx all come from the resulting parameterized policy class. Computing the associated universal value function approximator [Schaul et al., 2015] for this policy class would allow for efficient computation of the distortion function during the rate-distortion optimization. As an alternative, one might further restrict focus to a tabular Markov Decision Process, at which point the target policy in question can be expressed as a finite sequence of action random variables (one per state); it may then be possible to "stitch" Tx from the solutions to each of the state-dependent rate-distortion functions.
For now, we leave the question of how to adaptively compute optimal target policies in computationalllytracaaii manner to future work and, instead, turn our attention the multi-armed bandit setting where we may more feasibly study the coupling of optimal learning targets with optimal information acquisition.
3 Target Actions & The Value of Information
In order to develop a computationally- tracctcc algorithm for combining learning targets with IDS, this section focuses on multi-armed bandit problems where we take the learning target to be a target action the agent aims to identify from the environment.
3.1 Blahut-Arimoto Satisficing Thompson Sampling
We begin by taking closer look at the design of BLASTS and examine the extent to which learning targets computed via the Mlahut-Arimon algorithm are preferable to hand-crafted learning targets. As first observation, we recall that while BLASTS does employ the Blahut-Arimot algorithm as described in the previous section, the function computed by Arumugam and Van Roy [2021] is actually the so-called "plug-in" estimator for the rate-distortion function [Harrison and Kontoyiannis, 2008]; rather than directly using the agent's 's representation of environment uncertainty as an information source, BLASTS draws a fixed number of posterior samples and uses the resulting empirical distribution as an input source to the Blahut-Arimoto algorithm. Such an approach amenable to scenarios where an agent is only able to sample from its belief's over the environment but cannot reliably provide estimates of likelihoods [Osband et al., 2016a, Lu and Van Roy, 2017].
Clearly, as 2 - oo, the empirical distribution converges in probability to the true distribution and yet, implicit in the design of BLASTS is an assumption that a similar convergence statement holds for the plug-in estimator and the true rate-distortion function RDD). Fortunately, Harrison and Kontoyiannis [2008] have already proven general consistency results for the plug-in estimator of the rate-distortion function in two distinct settings of interest to sequential recision-making problems: (1) under a finite action set and (2) when the action set is a compact, separable metric space such that for each realization of the environment E, d(E,)) -) is continuous; naturally, the latter condition ensures consistency even under a continuous action space, although running the Blahut-Arimote algorithm to optimize such a continuous channel output is non-trivial [Dauwels, 2005].
While the previous result is encouraging, it immediately begs the question of how many posterior samples z are needed for the plug-in in estimator R(D) to, with high probability, be an E-accurate approximation of the true rate-distortion function R(D) (D)? While Palaiyanur and Sahai [2008] offer an answer to this question in their study of the uniform continuity of the rate-distortion function for discrete random variables, their analysis and corresponding sample-complextty bounds depend problem-specifie parameter D
min d(E,x) denoting the minimum non-zero distortion (Ex))d((xx)>0
achieved by all environment-targel pairs While this constant does make sense in an information- theoretic context (for instance, under Hamming distortion, D 1), minimizing over all possible environments under a notion of distortion commensurate with expected squared regret engenders exceedingly small values of D. rendering the associated bounds vacuous. To remedy this issue, we consider minor modification to the statement of Lemma 2 by Palaiyanur and Sahai [2008], replacing their more general result that carries an unfavorable dependence on D with a less general result in terms of
D(Ps) = min min d(E, x)
7

---

When the distortion function is aligned with the regret between the optimal action and target action, D(P²) corresponds to the worst-case action gap between the best and second- best actions [Farahmand, 2011, 1, Agrawal and Goyal, 2013, Bellemare et al., 2016) based on the agent's ' current posterior over the environment. It is important note that while our adjustment to Lemma (and its corresponding effect on Lemma 5) of Palaiyanur and Sahai [2008] carries meaningful semantics for our sequential meaisinn-making setting, the proof the modified result still follows exactly as in their original paper', which leverages the uniform continuity of entropy.
Lemma (Lemma [Palaiyanur and Sahai, 2008)). Let & X be discrete random variables. Let Pe denote the agent's 's current posterior over and let Pe be the empirical distribution. If - Pelli S
D(T&), then for any D 2 0.
7 (R(D) ((D)) D(PE) Pe PElli log
E |P& Pe 11
Corollary (Lemma [Palaiyanur and Sahai, 2008J), For any ô E (0, 1), E (0. log(E)) let Ps E A(2) be the current posterior over E. Additionally, let o denote the inverse of the function
Φ: [0,
1 + R where (t)) = tlog
-
2
2
2
log
8 + Σ log(() then P((R(D) R(D)) 2 S
Φ-1 cD(Ps)
While the results discussed so far provide insight into the Blahut-Arimoto algorithm itself, it is worth examining the extent which learning targets computed via dite-distottion theory improve over a hand-crafted learning target. While such an improvement is certainly expected based on the theoretical analyses of [Russo and Van Roy, 2018b, Arumugam and Van Roy, 2021], ], it has not yet been demonstrated empirically. Due to space constraints, we defer a presentation of such empirical results that elucidate the value of computing learning targets via rate-distortion theory to the appendix.
3.2 Blahut-Arimoto Information- Sampling
While BLASTS successful in leveraging optimal learning targets, we consider improving upon the exploration technique used for collecting information about those targets through the algorithmic design principle of cntommtiion-ireette sampling [Russo and Van Roy, 2018a]. Information-directer sampling (IDS) is an abstract objective for sequential decision-making agents where, at each time period, an agent computes a policy based on the current history H, that minimizes the information ratio
Ex EE -R(A))-((A) -
H.
We
min TEA(A)
I(A": A,. O++1 |H, H,)
Here, R(-)) denotes the mean reward associated with input action. In words, the information ratio of a particular policy т E A(A) weighs the squared expected regret of action A, π rela- tive the optimal action A against the expected information gain about A by taking A.. Note that the information gain term I[ Ar, O++1 H, = H,) conditions upon the particular realiza- tion of the agent's history at time period I, H,- Relating this quantity to the more traditional notion of conditional mutual information only requires integrating over the randomness in Hę: [I(A*: Oc+1lHf- H.)] II(A"; Ar, O++1 For our purposes, we consider a modified information ratio that leverages the output of the Blahut-Arimoto algorithm.
In particular, define Blahut-Ariman recipe for efficient exploration with optimal learning targets wherein an agent first uses its current posterior as a source distribution, computing a learning target x via the Blahut-Arimoto algorithm. Subsequently, the agent employs IDS to balance optimal behavior and information gain about this target by minimizing the following information ratio
Iibormation-Dirccte Sampling (BLAIDS) a general
E, 2a)
V ( I(x; A,, O. H. H.)
A.(a) = Ex,x [(x) - R(a)) H,).
Under standard assumption that rewards are bounded in [0, 1] and d(E, x) is function of regret, the d' term that appears in their original bound is equal I.
8

---

where the expectation is with respect to the joint distribution computed by the Brihut-Arimoto algorithm. Observe that the distortion function used here is given by d(E.x H,) = d(E, Ax H1)) = ((()) - R(Ax))²
E, He] where, conditioned on a realization of the environment E, we may compute R(-) [Arumugam and Van Roy, 2021]. One perspective on BLAIDS is that IDS, with its default focus on A", will spend time acquiring too much information relative to BLAIDS that will adaptively guide IDS towards uncovering the minimum number of bits needed to achieve a desired level of sub-optimality. Naturally, BLAIDS is a generalization of IDS since, 8 - oo, the Blahut- Arimoto algorithm computes the optimal action A for each realization of the environment from the input source distribution. Just with IDS, BLAIDS is design principle whose abstract objective must be made explicit in a cimputationally-taactooo algorithm. One standard choice for IDS is leverage a lower bound of mutual information by the variance in rewards [Russo and Van Roy, 10, Nikolov et al., 2018, Dwaracherla et al., 2020, Lu al., 2021]. This results in an upper bound on the per-period information ratio that is suitable for minimization:
manner in order to yield a corresponding
E (A)) ET ee (A.)]
V (T)
(A,) = V E X(AA)x.HH) [H.].
To see how this upper bound lends itself to a camputttionalll-tractabb instantiation of IDS, observe that with posterior samples, the Blahut-Arimote algorithm results in distribution over learning targets conditioned on each posterior sample of the environment p(x = ã|E = e). Denoting the induced marginal over learning targets as (()), we have
v. (A, = a)) - (()))
1 E p(ā ((a)
E. - 1 Σ E, [(A)EE=))
GEA
Using this lower bound, we recover pariance-BLAIDS a computationally-traatii analogue to variance-IDS. Once again, to see that Pariance-BLAIDS generalizes variance-IDS note that as 3 + x. recovery of the optimal action by the Blahut-Arimoto algorithm implies that for any realization of the environment and any ā E A. p(@lE = e) E {0,1); identifying if ā is optimal in that realization of the environment. Consequently, Ep(ā(E)= E.. and q(a) = =2" E where
E - denotes partition of the posterior samples such that a" E A is optimal for all environments e E =a- In the next section, we assess the extent to which variance-BLAIDS improves upon standard variance-IDD IDS through the use of optimal learning targets.
Vex
39
Mauik 111
2200 2000 2700
1100 12300 1500 2200
2000
(a) Optimal 3 values
(b) Satisficing values
(c) Adaptive Be = V
600
S41T5 2-10
.00
BuTTU 2000
300
1988
(1005 2-43
(d) Optimal & values
(e) Satisficing 3 values
(I) Adaptive 3, V/
Figure 1: Regret curves for independent Bernoulli (top) and Gaussian (bottom) bandits with 50 arms.

---

Experiments
In our experimental setup, we examine independent Bernoulli and Gaussian bandit problems, sweep- ing over values of 3 in order to examine the spectrum of policies induced by the various learning targets. Similar to BLASTS, BLAIDS is agnostic to the particular mechanism used for represent- ing an agent's epistemic uncertainty. For our experiments, we found the use of a linear hyper- model [Dwaracherla et al., 2020] to be sufficient when optimized via Adam [Kingma and Ba, 2014] (learning rate of 0.001) with noise variance of 0.1, prior variance of 1.0, and batch size of 1024. We adopt all other hyperparameters of [Arumugam and Van Roy, 2021] for running the
algorithm [James et al., 2018] 2 in each time period and run experiments via Google Colab with GPU. In Figure 1, we report the cumulative regret in each time period across Thompson Sampling (TS), BLASTS, variance-IDS IDS (V-IDS), and variance-Bl BLAIDS (V-BLAIDS) where shading denotes 95% confidence intervals averaged over 10 random trials. For clarity, we split the figures in each problem between those values of B which manage to achieve optimal policy and those which learn a sub-optimal policy.
Our empirical results highlight opportunities for more efficient learning in light of information- directed exploration. Notably, the gap between BLASTS and variance-BLAIDS widens as 3 in- creases, asserting more importance in pursuing a near-optimal learning target. Curiously, while the Bernoulii bandit does show small performance gains relative to variance- when lowering 3. such improvements do not appear in the Gaussian setting and present interesting direction for future work to investigate the nature information structures where learning an optimal policy can be im- proved through automated learning targets. That said, it is worth noting that the prior variance used in our experiments already matches the true variance of the environment and so, under a less-calibrated prior, there might be greater opportunity for variance-BLAIDS to shine over variance-IDS..
As in Arumugam and Van Roy [2021] IJ, we also entertain the idea of an intimate relationship between and the (best) information ratio L min
E. (a)) *EA(A) T(A*;Ar,0++ H.)= We also find that the use of
an adaptive B, Vr yields the best performance in both problem classes for learning an optimal policy. While the existence of meaningful correspondence between 3 and V, seems natural given their respective roles and aligned units (bits per squared unit of regret for the former and squared units of regret per bit for the latter), it is unclear if and when this scaling is correct. On the whole, these results serve as simple, fundamental sanity checks that confirm the importance of prudent information acquisition, even when in pursuit of a learning target besides the optimal action.
5 Conclusion
Learning targets are general mechanism for guiding the information sought out by sequential to meet the demands
decision-making agent. As environments continue to grow in complexity of more challenging real-world tasks, so too will the need for learning targets that fall within the means of computationally--oundee agents. This work falls in with a new direction that leverages rate-distortion theory in order to forge such optimal learning targets and asks how such targets couple with existing methods for optimal information acquisition. Our work confirms that the computationally-tratnn trrccabll approaches for computing optimal learning targets are compatible with the well-studied principle of information-directee sampling. While we have found suitable answers for the multi-armed bandit setting, much remains to be understood about the nature of these learning targets themselves well how extend these algorithms to handle target policies and other richer notions of learning objectives.
Acknowledgments and Disclosure of Funding
Financial support from Army Research Office (ARO) grant 191 is gratefully acknowl- edged.
10

---

References
Shipra Agrawal and Navin Goyal. Further optimal regret bounds for Thompson sampling. In Artificial intelligence and statistics, pages 99-107, 2013.
Shipra Agrawal and Randy Jia. Optimistic posterior sampling reinforcement learning: worst-case regret bounds. In Advances in Neural Information Processing Systems, pages 1184-1194, 2017.
Suguru Arimoto. An algorithm for computing the capacity of arbitrary discrete memoryless channels. IEEE Transactions on Information Theory, 18(1):14-20, 1972.
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.
Mare G Bellemare, Georg Ostrovski, Arthur Guez, Philip Thomas, and Rémi Munos. Increasing the action gap: New operators for reinforcement learning. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 30, 2016.
Richard Bellman. A Markovian decision process. Journal of mathematics and mechanics, pages 679-684, 1957.
Toby Berger. Rate Distortion Theory: A Mathematical Basis for Data Compression. Prentice-Hall, 1971.
Richard Blahut, Computation of channel capacity and rate-distortion functions. IEEE transactions on Information Theory, 18(4):460-473 1972.
Olivier Chapelle and Lihong Li. An empirical evaluation of Thompson sampling. In Advances in neural information processing systems, pages 2249-2255 2011.
Thomas M Cover and Joy Thomas. Elements of information theory. John Wiley & Sons, 2012.
Inre Csiszár. On an extremum problem information theory. Studia Scientiarum Mathematicarum Hungarica, 9, 1974.
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.
Vikranth Dwaracherla, Xiuyuan Lu, Morteza Ibrahimi, Ian Osband, Zheng Wen, and Benjamin Van Roy. Hypermodels for exploration. In International Conference on Learning Representations, 2020.
Benjamin Eysenbach. Abhishek Gupta, Julian Ibarz, and Sergey Levine. Diversity is all you need: Learning skills without a reward function. In International Conference on Learning Representations, 2018.
Amir-massoud Farahmand. Action-gap phenomenon in reinforcement learning. Advances Neural Information Processing Systems, 24: 172-180, 2011.
Robert M. Gray, Entropy and information theory. Springer Science Business Media, 2011.
Matthew T Harrison and Ioannis Kontoyiannis. Estimation of the rate-distortion function. IEEE transactions on information theory, 54(8):3757-3762, 2008.
R. James, C. J. Ellison, and Crutchfield. dit: Python package for discrete information theory. 105/j0ss.007388
The Journal of Open Source Software, 3(25):738, 2018. doi:
Sham Kakade and John Langford. Approximately optimal approximate reinforcement learning. In Proceedings of the Nineteenth International Conference on Machine Learning, pages 267-274, 2002.
Diederik P Kingma and Jimmy Ba. Adam: method for stochastic optimization. arXiv preprint arXiv:1412.6980, 2014.

---

Tor Lattimore and Csaba Szepesvári. Bandit algorithms. Cambridge University Press, 2020.
Xiuyuan Lu and Benjamin Van Roy. Ensemble sampling. In Advances in neural information processing systems, pages 3258-3266, 2017.
Xiuyuan Lu, Benjamin Van Roy, Vikranth Dwaracherla, Morteza Ibrahimi, lan Osband, and Zheng Wen. Reinforcement learning, bit by bit. arXiv preprint arXiv:2 040444 2021.
Nikolay Nikolov, Johannes Kirschner, Felix Berkenkamp, and Andreas Krause. Information-directed exploration for deep reinforcement learning. In International Conference on Learning Representa- tions, 2018.
Ian Osband, Charles Blundell, Alexander Pritzel, and Benjamin Van Roy. Deep exploration via bootstrapped DQN. In Advances in neural information processing systems, pages 4026-4034, 2016a.
lan Osband, Benjamin Van Roy, and Zheng Wen. Generalization and exploration via randomized value functions. In International Conference Machine Learning, pages 2377-2386, 2016b.
Ian Osband, Benjamin Van Roy, Daniel Russo, and Zheng Wen. Deep exploration via randomized value functions. Journal of Machine Learning Research, 20(124):1-66 62, 2019.
Brendan O' D'Donoghue, Ian Osband, Remi Munos, and Volodymyr Mnih. The uncertainty bellman equation and exploration. In International Conference on Machine Learning, pages 3836-3845, 2018.
Hari Palaiyanur and Anant Sahai. On the uniform continuity of the rate-distortion function. In 2008
IEFE International Symposium on Information Theory, pages 857-861. IEBE, 2008
Martin L. Puterman. Markov Decision Poncesses-Dsccreds Stochastic Dynamic Programming. John Wiley & Sons, Inc., New York, NY, 1994.
Daniel Russo and Benjamin Van Roy. Learning to optimize via information-directed sampling. In Advances in Neural Information Processing Systems, pages 1583-1591, 2014.
Daniel Russo and Benjamin Van Roy. An information-thhoortiic analysis of Thompson sampling. The Journal of Machine Learning Research, 17(11:2442-2471, 2016. 2016.
Daniel Russo and Benjamin Van Roy. Learning to optimize via information-directed sampling. Operations Research, 66(1):230-252 2018a.
Daniel Russo and Benjamin Van Roy. Satisficing in time-sensitive bandit learning. arXiv preprint wrXi::100300285, 2018b
Daniel 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.
Tom Schaul, Daniel Horgan, Karol Gregor, and David Silver. Universal value function approximators. In International conference on machine learning, pages 1312-1320. PMLR, 2015.
Claude F. Shannon. Coding theorems for discrete source with a fidelity criterion. IRE Nat. Com. Rec., March 1959, 4:3, 1959.
David Silver, Julian Schrittwieser, Karen Simonyan, Ioannis Antonoglou, Aja Huang, Arthur Guez, Thomas Hubert, Lucas Baker, Matthew Lai, Adrian Bolton, et al. Mastering the game of go without human knowledge. Nature, 550(7676) 2017.
Richard S Sutton and Andrew G Barto. Introduction to reinforcement learning. 1998.
William R Thompson. On the likelihood that one unknown probability exceeds another in view of the evidence of samples. Biometrika, 25(3/4):255-94,, 1933.
12


Reviews:
[{"review_id": "o3YhnCbWFJv", "reviewer": "Reviewer_z9LJ", "summary": "This papers studies the fundamental problem in sequential decision making problems related to exploration. Previous work have used Thomson sampling in these cases however, they are suboptimal.\nThis work uses rate distortion theory and in generalizes previous Blahut-Aritomoto and Information-directed sampling  algorithms with a novel BLAIDS approach.\nI have some suggestions in terms of presentation to improve readability and clarity.", "questions": "", "limitations": "", "rating": 6, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "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": "", "main_review": "Originality\n- Highly relevant problem in decision making\n\nClarity\n- I had a hard time following the paper because in not familiar withe the background. \nI would have like to see a definition of action-gap.\nI would have liked to know more details on IDS.\n\n- I also think the structure of the paper is different from what I'm used to, for example, there are key statements are kind of \"hidden\" in the paper (in between sections and paragraphs). \n\n\"We leave the  question of how to adaptively compute optimal target policies in a computationally-tractable manner to future work and, instead, turn our attention to the multi-armed bandit setting where we may more feasibly study the coupling of optimal learning targets with optimal information acquisition.\"\n\n\"This procedure is precisely the classic Blahut-Arimoto algorithm [Blahut, 1972,Arimoto, 1972], generalized beyond the assumptions of discrete source and channel output random variables.\"\n\n\"We define Blahut-Arimoto Information-Directed Sampling (BLAIDS) as a general recipe for efficient exploration with optimal learning targets wherein an agent first uses its current posterior as a source distribution, computing a learning target χ via the Blahut-Arimoto algorithm.\"\n\n-Maybe you could move Section 2.4 at the end of the paper as Disscussion\n\n\nSignificance\n- The results are presented on multi-armed bandits (MAB) the RL case is not studied in detail.\n- The paper takes theoretical results already proven to the MAB case.\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "No discussion on the topic", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4"}, "extra_text": {}}, {"review_id": "a6_fNTFPh92", "reviewer": "Reviewer_Mktz", "summary": "The paper tackles the problem of learning deliberately suboptimal actions in a bandit setting, with suboptimality being traded off with the amount of information needed from the environment to learn such actions, as formulated in [1]. The main contribution of the work is the combination of the learning target formulation with a learning algorithm based on information directed sampling (BLAIDS), instead of the Thompson sampling algorithm BLAST proposed in [1].", "questions": "", "limitations": "", "rating": 6, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "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": "", "main_review": "Originality: The paper proposes a novel combination of two previous ideas: the computation of the optimal learning targets trading off optimality and information usage using Blahut-Arimoto as recently introduced in [1], and information directed sampling approaches towards learning the target actions. The proposed approach is a natural extension of [1], replacing the Thompson sampling procedure with an IDS procedure instead. Related work is adequately addressed. While not necessarily a surprising result, I believe the proposed algorithm is a valuable contribution in showing that these two ideas can be combined to provide improvements.\n\nQuality and Significance: The submission appears to be technically sound, with experimental evidence that the proposed BLAIDS algorithm outperforming the earlier Thompson sampling based algorithm BLASTS in synthetic bandit settings while also allowing for tradeoffs of suboptimality vs learning speed (as measured by cumulative regret in earlier time periods). While the experiments do validate BLAIDS as a clear improvement over the earlier BLASTS algorithm, the paper would benefit from more thorough experimentation, for example examining how different configurations of the bandit problems influence the performance and tradeoffs of BLAIDS compared to regular IDS, as well as evaluating how general the improvements provided by using an adaptive $\\beta$ are.\n\nClarity: The paper is well written, providing a clear review of how rate-distortion theory can be related relates to trading off information usage and policy optimality as well as a clear presentation of how to integrate IDS with the optimal learning targets. The experimental results are also clearly presented.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4"}, "extra_text": {}}, {"review_id": "_eLCSVtbAnt", "reviewer": "Reviewer_6MK2", "summary": "This paper proposes the use of Blahut-Arimoto algorithm to learn an encoder from the source to the target, where the source is the environment and the target the policy to be recovered under a budget of distortion / suboptimality (this budget can be seen as a bounded-rationality). The output of BA algorithm would be a satisficing (good enough) policy, satisfying the budget constraints but also minimizing the mutual information between the policy and the environment. With this paper, the authors propose an improvement over Blahut-Arimoto Thompson Sampling method by using Information Directed Sampling in combination with Blahut-Arimoto algorithm (to compute target action of corresponding source environment). Finally, they provide an additional version based on the variance of the reward as a tractable approximation of the mutual information denominator.", "questions": "", "limitations": "", "rating": 7, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "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": "", "main_review": "A disclaimer here, i'm reading the paper from the perceptive of someone who would be very interested in exploration and value of information but doesn't have much experience in the underlying theory. Having said that, I find the paper very clearly written and have learned a lot while reviewing it - i appreciate that. The suggestions I make will be more on the side of helping readers like me to make it even more accessible. \n\nI understand the idea behind the target (a random variable that partially identifies the environment) but i'd like to see an example of what a target can be.\n\nI find this work related to active learning however this is not discussed in the paper. Specifically, those two papers seem most relevant :\n[https://arxiv.org/abs/1112.5745](https://arxiv.org/abs/1112.5745)\n[https://arxiv.org/abs/1904.05268](https://arxiv.org/abs/1904.05268) (although they assume observational data i think it can get extended to the interventional case as well)\n\n257: Is \\bar{R} the reward of the optimal action? What's the bar semantics? I understand that it's a random variable which depends on the environment but i'd like to see that part of the text (it helped reading this [https://arxiv.org/pdf/2101.06197.pdf](https://arxiv.org/pdf/2101.06197.pdf) but as i mentioned, my suggestion is to make the paper more self contained).\n\nThe algorithm, if I understand correctly, relies on the expected regret. However, the optimal reward seems like privileged information, unless the designer makes an assumption about access to this information. Or do you assume to compute through sampling from your belief over the environments which sound expensive but more realistic assumption? I'd like to see this point being clarified.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The paper doesn't discuss potential negative societal impact however I think the social impact would be the ones related with the cost of exploration in safe critical scenarios. However, given that this methodology can reason about uncertainty and balance exploration and exploitation accordingly, it can be tuned towards more safe behaviours.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "8"}, "extra_text": {}}, {"review_id": "XpKBP1iz0Hp", "reviewer": "Reviewer_osWU", "summary": "In reinforcement learning, the ideal thing to do would be to learn all of the information there is about the environment, and then use that to execute the optimal policy. However, in practice, it is impossible to learn _all_ of the necessary information in very complicated environments. Thus, we instead would like to define a _learning target_ that only incentivizes learning a relevant subset of information that is useful for acquiring reward. The learning target must be chosen such that (a) it does not require too much information to learn, and (b) the optimal policy given only the information in the learning target has low regret (relative to the optimal policy given arbitrary information).\n\nSo far learning targets have been coded by hand. Ideally we would instead select an appropriate learning target automatically, that outperforms targets coded by hand. The core insight is that constraint (a) is simply lossy compression, where constraint (b) can be thought of as a constraint on the _distortion_ on regret from throwing away some information in the lossy compression. We can then apply standard approaches from rate distortion theory to choose a target that best fits both constraints.\n\nOnce we have selected an appropriate target, we must also choose actions that provide us information about the target. This can be done through _information-directed sampling_, in which we choose actions that minimize the ratio between (expected) regret incurred and information gained about the learning target.\n\nThe authors instantiate this framework in the case of multiarmed bandits, where the learning targets are environment-conditional policies $p(a \\mid \\mathcal{E})$. In the case of zero distortion, the learning target is the optimal environment-conditional policy (which obtains zero regret). As distortion increases, the learning target becomes more and more “smeared” (e.g. in environments where the best and second-best arms are very close in reward, the learning target might put similar probabilities on both arms), making it easier to learn. They show that the resulting algorithm outperforms other alternatives that don’t use automatically generated learning targets and/or information-directed sampling.", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "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": "", "main_review": "The author response made me somewhat more convinced of the benefits of learning targets, and so I have raised my score to a 6.\n\n----\n\nOriginality: To my knowledge the idea of automatically constructing learning targets has not previously been combined with the idea of information-directed sampling. However, the method is quite straightforward: it seems to be as simple as taking BLASTS and replacing the Thompson sampling portion with information-directed sampling. In that sense the work seems fairly incremental. (Indeed, many of the points in the paper have substantial overlap with those made in [Arumugam and Van Roy, 2021].)\n\nQuality: To my knowledge the claims made in the paper are correct, though I did not carefully check the math (note that many of the theorems / lemmas come from other papers and so hopefully should be correct.)\n\nClarity: I found the paper hard to follow due to my lack of background in rate distortion theory. For example, in Section 2.3, the authors simply introduce the rate distortion function, which I initially assumed would be used to quantify distortion in some way, but which actually turns out to be the statement of the constrained optimization problem. (The authors could have mentioned that this was the purpose of the rate distortion function.) More generally, after spending a lot of time understanding the background, the paper made sense to me, but initially I kept getting lost due to small misunderstandings like the one above.\n\n(I would normally not make a big deal out of this, as some amount of background is expected in reading a research paper, but the authors explicitly claim “we do take our contribution to be distilling such key results from the information-theory literature for broader consumption by the sequential decision-making community and, to that end, offer a full presentation for the benefit of readers.”)\n\nSignificance: My main critique of this paper is that it doesn’t seem to deliver on its motivation.\n\nFrom Sections 1-3, my understanding is that the motivation is to produce learning targets that contain less information, so that it is easier for an agent to pick up on the relevant information in complex environments where they cannot possibly learn _all_ of the information. However, as the authors note in lines 200-202, “Moreover, computation of the distortion associated with each possible realization of the target policy would require an independent policy-evaluation step to compute the value function”, which seems like it is incompatible with complex environments (though not necessarily impossible). This is a fundamental issue with the approach (given the motivation) and can’t simply be deferred to future work.\n\nIn terms of experimental results, given the motivation, I would like to see an algorithm presented that runs in a complex environment, where the use of an automatically constructed learning target leads to better performance than the default target of the optimal policy, because when using the default target the agent fails to learn the relevant information.\n\nThe experiments do show that the automatically constructed learning target leads to better performance, but as far as I can tell, this is not because the agent failed to learn the relevant information when given the default learning target, but because the agent learned _too much_ information when given the default learning target. With both the default and automatically constructed learning target, the agent eventually learns the optimal policy: it just takes longer with the default target, presumably because we select actions that continue gathering information that isn’t relevant, which the automatically constructed target gets rid of (since its entire goal is to get rid of information that doesn’t affect the expected regret much).\n\nSo it seems like the actual story in the experiments is “we select actions that prioritize information-gathering too highly; to remedy this we can automatically construct a learning target that removes the irrelevant information, thus preventing our agent from trying to learn it leading to faster convergence”. This is pretty different from the motivation given in the paper (in particular it has nothing to do with how “complex” the environment is).\n\nOf course, I could imagine that the paper had been written with exactly this motivation in mind (the agent tends to acquire too much information, let’s fix that). And indeed it seems like information-directed sampling will sometimes acquire too much information: for example, information-directed sampling will “pay” the same amount of expected regret to distinguish between the best and second-best action, regardless of whether they differ in reward by 0.00001 or by 1, even though in the former case the information hardly matters.\n\nBut then I think there would be other approaches which I would like to see comparisons to. Most obviously, can we try to directly fix the problem with information-directed sampling? Information-directed sampling quantifies the _cost_ of acquiring information, but it doesn’t quantify the _benefit_ of that information. Can we instead have valuable-information directed sampling, which chooses actions that minimize the ratio of expected next-step regret to expected decrease in regret in future timesteps? For example, let $\\pi^*_{H_t}$ be the policy that makes a best guess about $A^*$ given the history $H_t$, and then always takes that action forever, and let $\\overline{V}^{\\pi^*_{H_t}}$ be its value. Then we could quantify:\n\n$Cost = \\mathbb{E}_{\\pi}[\\overline{R}(A^*) - \\overline{R}(A_t) \\mid H_t]$\n\n$Benefit = \\mathbb{E}_{A_t \\sim \\pi, O_t} [ \\overline{V}^{\\pi^*_H} ] - \\overline{V}^{\\pi^*_H}$\n\n(For some reason I can’t seem to subscript the $H$ in the above equation. The first one is supposed to be $\\overline{V}^{\\pi^*_{H_{t+1}}}$ and the second is supposed to be $\\overline{V}^{\\pi^*_{H_t}}$.)\n\nWe could then minimize Cost - Benefit. It seems likely that this will fix the issue where IDS acquires too much information, without requiring the complex machinery from rate distortion theory used in this paper. I would be interested in seeing experimental results from such an approach (using the default learning target of the optimal policy).", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "As mentioned above, there seems to be a mismatch between the motivation and the actual work done, which I would encourage the authors to fix.", "review_text": "", "extra_scores": {"ethical_concerns": "No ethical concerns.", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4"}, "extra_text": {}}, {"review_id": "9R2aRw9fs6q", "reviewer": "Reviewer_pEia", "summary": "**Update after author response and discussion**: I am happy to see most of my assumptions positively confirmed and clarified by the authors, as well as the criticism by other reviewers being sufficiently addressed. Some of my improvements remain valid, but I do not consider them crucial for publication. I therefore stick with my original score but raise my confidence - I am in favor of accepting the paper.\n\n**High-level summary**\n\nThe paper addresses the question of learning to act well in finite-horizon sequential tasks in unknown environments under computational limitations. This requires solving two problems. (1) In principle, full knowledge about the environment allows agents to act optimally. However, actions that lead to large information gain about the environment often come at the expense of incurring low immediate rewards - trading off these two considerations is non-trivial and has been formalized previously via information directed sampling (IDS), which aims to find policies that minimize the ratio between squared expected regret (of the policy compared to the optimal policy) and information gain (ideally leading to small regret and large information gain). (2) Reducing all (epistemic) uncertainty about the environment can incur a considerable amount of exploratory actions, particularly in complex environments. Often, a less informative (lossy) compression of the environment allows for learning policies that perform very well with considerably lower “exploration cost” (which is particularly relevant for computationally bounded agents). Such a compression has been previously introduced under the name ‘learning target’ which is computed via a (stochastic) mapping from the environment to the learning target random variable. A good learning target requires considerably less information (fewer bits) to be extracted from the environment (compared to reducing all uncertainty about the full environment) while at the same time ensuring that policies trained to maximize the learning target achieve good returns in the actual environments. This trade-off between low reduction in performance and high reduction in sample complexity of exploration has recently been formalized via a rate distortion theory, where the distortion is the expected regret between the policy trained on the learning target and the optimal policy (given an observation history), and the rate is the information that needs to be extracted from the environment to reduce uncertainty about the learning target variable sufficiently.\n\n**Concrete summary**\n\nPrevious work (BLASTS) derived an improved Thompson sampling scheme based on learning targets obtained by solving the rate-distortion trade-off via Blahut-Arimoto iterations. While BLASTS provides a principled solution to extract good learning targets, the resulting policies are understood to perform poorly in terms of exploration (increasing informativity of the learning target). The current paper improves upon this by combining IDS (which explores well by taking into account potential information gain and overall performance improvements) with automatically learned targets via Blahut-Arimoto iterations (which solve the rate-distortion trade-off). This leads to a method with a hyper-parameter that allows the designer to put more or less emphasis on keeping the required information acquisition sample complexity low (thus potentially incorporating a range of computational budgets) - the latter of course comes at the cost of potential reductions in performance (returns) of the learned policy compared to an optimal policy (in terms of cumulative regret over the course of learning, but potentially also for the converged solutions if the computational budget is too low). Results are shown for two 50-armed bandits (Bernoulli and Gaussian) where the method compares favorably with other methods (including BLASTS), and on par with IDS on Gaussian bandits.\n\n**Contributions:**\n\n1) Combination of IDS with Blahut-Arimoto learning targets. Both parts are theoretically well motivated and the combination makes sense and leads to a principled theoretical method. To obtain a practical implementation an approximation is needed - the approximation is sensible, though perhaps a bit coarse, but it is theoretically well backed up). Significance: results on the Bernoulli bandit look good, but performance gains compared to IDS don’t carry over to the Gaussian case. Since it remains unclear why, the potential impact remains limited (does the method sound good in theory but easily runs into practical problems, or is there a good reason why we would not expect to see a difference in the Gaussian case?).\n\n2) Solid theoretical foundations - given a constraint on the distortion (corresponding to a value of the hyper-parameter \\beta) there is a theoretical guarantee that the learning target is optimal in the sense that there exists no other learning signal target that achieves the same distortion but requires lower rate (“bits extracted from the environment”) - or dually, given a computational budget (set by inverse \\beta) no other learning target can lead to higher returns. Significance: given the limited empirical results it remains somewhat unclear to which degree the theoretical results carry over in practice - it cannot be ruled out that (slightly) sub-optimal learning targets could lead to better results in particular cases (e.g. leading to more stable learning, easier to find corresponding policies, etc.). This remains to be seen in the future, but having a solid theoretical background is important - even heuristics might benefit from the theoretical insight presented here.\n\n3) Review of (continuous) rate-distortion theory and the necessary background for the method for a general ML/RL audience (non info-theory experts). Significance: important contribution in itself, though the material is still a bit dense and might need further unpacking / illustrations of the key intuitions for e.g. a general RL practitioner audience. Also, the latter target audience might not be convinced to invest time since the method is currently limited to (non-contextual) bandits.", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "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": "", "main_review": "**Originality, Quality, Clarity, Correctness:**\n\nThe paper is well written, though some parts are technically dense (but I don’t see an easy solution to this given the page limitations). Importantly, the paper does a great job of explaining the necessary background (with a great section summarizing continuous rate distortion theory in a way that makes the rest of the manuscript much more accessible), the fundamental problems, and previous solutions to these individual problems. To the best of my knowledge, the proposed method is novel - it mainly consists of combining a recent idea BLASTS with the more widely known IDS. This is clearly pointed out in the text and the combination is sensible, and compared against both previous methods. I have not checked the proofs in detail, but did not spot a result in the main paper that raised my suspicions.\n\n**Verdict:**\n\nOverall the paper addresses a timely and important problem, and provides a very principled solution approach, which I have greatly enjoyed. The main innovation in the paper is the combination of two existing methods, which is somewhat incremental. The paper compensates for this by clearly introducing the problem and providing the necessary background for a broader audience to understand the solution without having to resort to other publications. My main criticism is that results in the Gaussian case are on par, but not better than IDS. It would be very good to know whether that is due to some fundamental problem (from translating the theoretical principles into a practical algorithm), or whether this is somewhat expected for the Gaussian case. Overall I think the material is ready for publication, but given the incremental nature might receive most attention in a smaller sub-community (though I highly appreciate the attempt to make the material accessible to a wider audience). I would like to see a unified manuscript (including IDS, parts of the orig. learning targets paper, and BLASTS) written with the same target audience in mind, and more space for intuitive illustrations of the core concepts - but this would obviously not fit into a conference-format paper.\n\n**Pros:**\n\n * Clearly defined problem, well described partial solutions and their shortcomings, sensible and well explained main innovation.\n * Extensive background section, akin to a mini-review on continuous rate-distortion theory - which is crucial to make the paper accessible to a wider audience.\n * Empirical results show some support of the theoretical claims - the main method seems to work and perform better than previous methods (except for one case).\n\n**Cons:**\n\n * Somewhat incremental approach (given IDS and BLASTS) - but I think there is sufficient novelty to warrant publication (since there are also clear shortcomings of both predecessor methods that are addressed).\n * Applications limited to (non-contextual) bandits for now - extensions to more complex RL problems require major technical innovations/approximations (but this is also clearly discussed in the paper)\n * Empirical results are limited to two simple bandits\n * Comparison with IDS on Gaussian bandits somewhat inconclusive\n\n**Improvements:**\n\n1) It would be good to investigate the reasons for the results compared to IDS on the Gaussian bandit. This could be either a theoretical investigation (are there any reasons why we might expect these results) or an empirical investigation (do other bandit settings lead to similar results, or is this an observation limited to the Gaussian case?). Ideally both.\n\n2) Though space is already tight, it would be nice to show results for more bandits - simply to get a better sense of how well the theory translates into practice.\n\n3) Lemma 1, and perhaps even the Blahut-Arimoto iterations (essentially Lemma 2) would benefit from an illustration.\n\n4) Readers might benefit from an illustration of the main idea early on in the manuscript (this is the main idea that we are going to develop). Perhaps also giving examples of learning targets (and how they could be computed through an optimization) early on would help to set up intuitions.\n\n**Comments:**\n\n * Does the paper (at some stages) assume that the optimal return is known by construction? Would be good to comment on this (where is this assumed, how is this solved in practice).\n * Section 3.2: How is R_bar computed - how does it differ from V_bar introduced earlier? (don’t they both refer to the expected return?\n * Perhaps it is worth pointing out when connecting learning targets to rate distortion that learning targets can be viewed as lossy compressions of the environment which are useful to train policies that perform well in the environment. Since these (lossy) compressions can potentially be much “simpler” than the full environment, they can be determined more easily (higher sample efficiency when exploring).\n * Line 207: IDS first used, but acronym only spelled out later in the text.\n * A bit nitpicky, but would be nice to discuss (in the conclusions) wow exactly would this help with playing Go on a mobile phone - what is the epistemic uncertainty over the environment? The policy of the opponent? What could a hand-crafted learning target be?", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Some limitations are pointed out throughout the text. It would not hurt to have a paragraph at the end of the paper dedicated to current limitations and shortcomings (in terms of the concretely implemented method, including e.g. the mutual info estimation). Societal impact: not applicable.", "review_text": "", "extra_scores": {"ethical_concerns": "No ethical concerns.", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3.5"}, "extra_text": {}}]

Author rebuttal:

Meta-review: After discussions between the authors and reviewers, it appears as though the reviewers have all reached a consensus that this paper is worthy of acceptance, so I am happy to support that consensus.

I want to thank the authors for their detailed responses and thank the reviewers for engaging in discussion with the authors.
Decision: Accept (Poster)