Satisficing in Time-Sensitive Bandit Learning
Daniel Russo1 and Benjamin Van Roy2

arXiv:1803.02855v1 [cs.LG] 7 Mar 2018

1

Columbia University, djr2174@columbia.edu
2
Stanford University, bvr@stanford.edu

Abstract
Much of the recent literature on bandit learning focuses on algorithms that aim to converge on
an optimal action. One shortcoming is that this orientation does not account for time sensitivity,
which can play a crucial role when learning an optimal action requires much more information
than near-optimal ones. Indeed, popular approaches such as upper-confidence-bound methods
and Thompson sampling can fare poorly in such situations. We consider instead learning a
satisficing action, which is near-optimal while requiring less information, and propose satisficing
Thompson sampling, an algorithm that serves this purpose. We establish a general bound on
expected discounted regret and study the application of satisficing Thompson sampling to linear
and infinite-armed bandits, demonstrating arbitrarily large benefits over Thompson sampling.
We also discuss the relation between the notion of satisficing and the theory of rate distortion,
which offers guidance on the selection of satisficing actions.

1

Introduction

Much of the recent literature on bandit learning focuses on algorithms that aim to converge on an
optimal action. But does that make sense when learning an optimal action requires much more
information than near-optimal ones? The following example illustrates the issue.
Example 1. (Many-Armed Deterministic Bandit) Consider an action set A = {1, . . . , K}.
Each action a ∈ A results in reward θa . We refer to this as a deterministic bandit because the
realized reward is determined by the action and not distorted by noise. The agent begins with a
prior over each θa that is independent and uniform over [0, 1] and sequentially applies actions
A0 , A1 , A2 , . . ., selected by an algorithm that adapts decisions as rewards are observed. As K grows,
it takes longer to identify the optimal action A∗ = argmaxa∈A θa . Indeed, for any algorithm,
P(A∗ ∈ {A0 , . . . At−1 }) ≤ t/K. Therefore, no algorithm can expect to select A∗ within time t  K.
On the other hand, by simply selecting actions in order, with A0 = 1, A1 = 2, A2 = 3, . . ., the agent
can expect to identify an -optimal action within t = 1/ time periods, independent of K.
It is disconcerting that popular algorithms perform poorly when specialized to this simple
problem. Thompson sampling (TS) [17], for example, is likely to sample a new action in each
time period so long as t  K. The underlying issue is most pronounced in the asymptotic regime
of K → ∞, for which TS never repeats any action because, at any point in time, there will be
actions better than those previously selected. A surprisingly simple modification offers dramatic
improvement: settle for the first action a for which θa ≥ 1 − . This alternative can be thought of
as a variation of TS that aims to learn a satisficing action Ã = min{a : θa ≥ 1 − }. We will refer

1

to an algorithm that samples from the posterior distribution of a satisficing action instead of the
optimal action, as satisficing Thompson sampling (STS).
While stylized, the above example captures the essence of a basic dilemma faced in all decision
problems and not adequately addressed by popular algorithms. The underlying issue is time preference. In particular, if an agent is only concerned about performance over an asymptotically long
time horizon, it is reasonable to aim at learning A∗ , while this can be a bad idea if shorter term performance matters and a satisficing action Ã can be learned more quickly. To model time preference
and formalize benefits of STS, we will assess performance in terms of expected
discountedregret,
P∞ t
α
(θ
which for the many-armed deterministic bandit can be written as E
A∗ − θAt ) . The
t=0
constant α ∈ [0, 1] is a discount factor that conveys time preference. It is easy to show, as is done
through Theorem 10 in the appendix, that in the asymptotic regime of K → ∞, TS√experiences
expected discounted regret
√ of 1/2(1 − α), whereas that of STS is bounded above by 1/ 1 − α. For
α close to 1, we have 1/ 1 − α  1/(1 − α), and therefore STS vastly outperforms TS. In fact,
as α approaches 1, the ratio between expected regret of TS and that of STS goes to infinity. This
stylized example demonstrates potential advantages of STS.
This paper develops a general framework for studying satisficing in sequential learning. Satisficing algorithms aim to learn a satisficing action Ã. Building on the work of Russo and Van Roy
[15], we will establish a general information theoretic regret bound, showing that any algorithm’s
expected discounted regret relative to a satisficing action is bounded in terms of the mutual information I(θ; Ã) between the model parameters θ and the satisficing action and a newly defined
information ratio, which measures the cost of information acquired about the satisficing action.
The mutual information I(θ; Ã) can be thought of as the number of bits of information about θ
required to identify Ã, and the fact that the bound depends on this quantity instead of the entropy
of A∗ , as does the bound of [15], allows it to capture the reduction of discounted regret made
possible by settling for the satisficing action.
A natural and deep question concerns the the choice of satisficing action Ã and the limits of
performance attainable via satisficing. An exploration of this question yields novel connections
between sequential learning and rate-distortion theory. In Section, 5 we define a natural ratedistortion function for Bayesian decision making, which captures the minimal information about
θ a decision-maker must acquire in order to reach an -optimal decision. Combining this ratedistortion function with our general regret bound leads to new results and insights. As an example,
while previous information-theoretic regret bounds for the linear bandit problem become vacuous
in contexts with infinite action spaces, our rate-distortion function leads to a strong bound on
expected discounted regret.
We will also study the many-armed bandit problem with noisy rewards. Here, we will consider
a satisficing action Ã = min{a : θa ≥ 1 − } and establish a bound on expected discounted regret
that demonstrates benefits of STS over TS. We will also present computational results that offer
further perspective on the advantages.
Many papers [4, 10, 12] have studied bandit problems with continuous action spaces, where
it is also necessary to learn only approximately optimal actions. However, because these papers
focus on the asymptotic growth rate of regret they implicitly emphasize later stages of learning,
where the algorithm has already identified extremely high performing actions but exploration is
needed to identify even better actions. Our discounted framework instead focuses on the initial
cost of learning to attain good, but not perfect, performance. Recent papers [8, 9] study several
heuristics for a discounted objective, though without an orientation toward formal regret analysis.
The knowledge gradient algorithm of Ryzhov et al. [16] also takes time horizon into account and can
learn suboptimal actions when its not worthwhile to identify the optimal action. This algorithm
tries to directly approximate the optimal Bayesian policy using a one-step lookahead heuristic, but
2

unfortunately there are no performance guarantees for this method. Deshpande and Montanari [7]
consider a linear bandit problem with dimension that is too large relative to the desired horizon.
They propose an algorithm that limits exploration and learns something useful within this short
time frame. Berry et al. [1], Wang et al. [19] and Bonald and Proutiere [2] study an infinite-armed
bandit problem in which it is impossible to identify an optimal action and propose algorithms to
minimizes the asymptotic growth rate of regret. While we will instantiate our general regret bound
for STS on the infinite-armed bandit problem, we use this example mostly to provide a simple
analytic illustration. We hope that the flexibility of STS and our analysis framework allow this
work to be applied to more complicated time-sensitive learning problems

2

Problem Formulation.

An agent sequentially chooses actions (At )t∈N0 from the action set A and observes the corresponding
outcomes (Yt )t∈N0 ⊂ Y. The agent associates a reward R(y) with each outcome y ∈ Y. Let
Rt ≡ R(Yt ) denote the reward corresponding to outcome Yt . The outcome Yt in period t depends
on the chosen action At , idiosyncratic randomness associated with that time step, and a random
variable θ that is fixed over time. Formally, there is a known system function g, and an iid sequence
of disturbances (Wt )t∈N0 such that
Yt = g(At , θ, Wt ).
The disturbances Wt are independent of θ, and have a known distribution. This is without loss of
generality, as uncertainty about g and the distribution of Wt could be included in the definition of
θ. From this, we can define
µ(a, θ) = E[R (g(a, θ, Wt )) |θ]
to be the expected reward of an action a under parameter θ. Ours can be thought of as a Bayesian
formulation, in which the distribution of θ represents the agent’s prior uncertainty about the true
characteristics of the system, and conditioned on θ, the remaining randomness in Yt represents
idiosyncratic noise in observed outcomes.
The history available when selecting action At is Ht−1 = (A0 , Y0 , . . . , At−1 , Yt−1 ). The agent
selects actions according to a policy, which is a sequence of functions ψ = (ψt )t∈N0 , each mapping
a history and an exogenous random variable ξ to an action, with At = ψt (Ht−1 , ξ) for each t.
Throughout the paper, we use ξ to denote some random variable that is independent of θ and the
disturbances (Wt )t∈N0 .
Let R∗ = supa∈A µ(a, θ) denote the supremal reward, and let A∗ ∈ argmaxa∈A µ(a, θ) denote
the true optimal action, when this maximum exists. As a performance metric, we consider expected
discounted regret of a policy ψ is defined by
Regret(α, ψ) = Eψ

"∞
X

#

αt (R∗ − Rt ) ,

t=0

which measures a discounted sum of the expected performance gap between an omniscient policy
which always chooses the optimal action A∗ the policy ψ which selects the actions (At )t∈N0 . This
deviates from the typical notion of expected regret in its dependence on a discount factor α ∈ [0, 1].
Regular expected regret corresponds to the case of α = 1. Smaller values of α convey time preference
by weighting gaps in nearer-term performance higher than gaps in longer-term performance.
The definition above compares regret relative to the optimal action A∗ and corresponding reward
∗
R . It is useful to also consider performance loss relative to a less stringent benchmark. We define

3

the satisficing regret at level D ≥ 0 to be
ψ

SRegret(α, ψ, D) = E

"∞
X

#
t

∗

α (R − D − Rt ) .

t=0

This measures regret relative to an action that is near-optimal, in the sense that it yields expected
reward R∗ − D, which is within D of optimal. This notation was chosen due to the connection we
develop with rate-distortion theory, where D typically denotes a tolerable level of “distortion” in a
lossy compression scheme. Of course, for all D ≥ 0,
Regret(α, ψ) = SRegret(α, ψ, D) +

D
1−α

and so one can easily translate between bounds on regret and bounds on satisficing regret. However, directly studying satisficing regret helps focus our attention on the design of algorithms that
purposefully avoid the search for exactly optimal behavior in order to limit exploration costs.
Additional Notation. Before beginning, let us first introduce some additional notation. We
denote the entropy of a random variable X by H(X), the Kullback-Leibler divergence between
probability distributions P and Q by D(P ||Q), and the mutual information between two random
variables X and Y by I(X; Y ). We will frequently be interested in the conditional mutual information I(X; Y |Ht−1 ).
We sometimes denote by Et [·] = E[·|Ht−1 ] the expectation operator conditioned on the history
up to time t and similarly define Pt (·) = P(·|Ht−1 ). The definitions of entropy and mutual information depend on a base measure. We use Ht (·) and It (· , ·) to denote entropy and mutual-information
when the base-measure is the posterior distribution Pt . For example, if X is and Z are discrete
random variables taking values in a sets X and Z,
Pt (X = x, Z = z)
Pt (X = x, Z = z) log
It (X; Z) =
.
Pt (X = x)Pt (Z = z)
x∈X z∈Z


X X



Due to its dependence on the realized history Ht−1 , It (X; Z) is a random variable. The standard
definition of conditional mutual information integrates over this randomness, and in particular,
E[It (X; Z)] = I(X; Z|Ht−1 ).

3

Satisficing Actions.

We will consider learning a satisficing action Ã instead of an optimal action A∗ . The idea is to target
a satisficing action that is near-optimal yet easy to learn. The information about θ required to learn
an action Ã is captured by I(θ; Ã), while the performance loss is E[R∗ − R̃], where R̃ = µ(Ã, θ). For
Ã to be easy to learn relative to A∗ , we want I(θ; Ã)  I(θ; A∗ ). We will motivate this abstract
notion through several examples.
Our first example addresses the many-armed deterministic bandit, as discussed in Section 1.
Example 2 (first satisfactory arm). Consider the infinite-armed deterministic bandit of Section
1. For this problem, the prior of A∗ is uniformly distributed across a large number K of actions,
and I(θ; A∗ ) = H(A∗ ) = log K. Consider a satisficing action Ã = min{k|θk ≥ R∗ − }, which
represents the first action that attains reward within  of the optimum R∗ = maxk θk . As K → ∞,
I(θ; A∗ ) → ∞. But I(θ; Ã) remains finite, as in this limit Ã converges weakly to a geometric
random variable, with I(θ; Ã) = H(Ã) = −((1 − ) log(1 − ) +  log())/.
4

The next example involves reducing the granularity of a discretized action space.
Example 3 (discretization). Consider a linear bandit with A ⊂ Rp and µ(a, θ) = a> θ for an
unknown vector θ. Suppose that θ ∼ N (0, I) and A consists of K vectors spread out uniformly
along boundary of the d-dimensional unit sphere {a ∈ Rp : kak2 = 1}. The optimal action A∗ =
argmaxa∈A a> θ is then uniformly distributed over A, and therefore I(θ; A∗ ) = H(A∗ ) = log K. As
K → ∞, it takes an enormous amount of information to exactly identify A∗ . The results of [13]
become vacuous in this limit. Consider a satisficing action Ã that represents a coarser version of
A∗ . In particular, for M  K, let Ã consist of M vectors spread out uniformly along boundary
of the d-dimensional unit sphere, with M chosen such that for each element of A there is a close
approximation in Ã. Let Ã = argmaxa∈Ã θ> a. This can be viewed as a form of lossy-compression,
for which H(Ã)  H(A∗ ) while E[R∗ − R̃] remains small.
In the previous two examples, θ determined Ã, and therefore I(θ; Ã) = H(Ã). We now consider
an example in which I(θ; Ã) is controlled by randomly perturbing the satisficing action. Here,
I(θ; Ã) can be small even though H(Ã) is large.
Example 4 (random perturbation). Consider again the linear bandit from the previous example.
An alternative satistficing action Ã results from optimizing a perturbed objective Ã ∈ argmaxa∈A aT (θ+
Z) where Z ∼ N (0, (/p)2 I). Since Z is not observable, it is not possible in this case to literally learn
Ã. Instead, we consider learning to behave in a manner indistinguishable from Ã. The variance
of Z is chosen such that E[R∗ − R̃] = . Moreover, it can be shown that I(Ã; θ) ≤ I(θ + Z; θ) =
p log(1 + p2 /2 ) and therefore, the information required about θ is bounded independently of the
number of actions.

4

A General Regret Bound.

This section provides a general discounted regret bound and a new information-theoretic analysis
technique. The first subsection introduces an alternative to the information ratio of Russo and
Van Roy [15], which is more appropriate for time-sensitive online learning problems. The following
subsection establishes a general discounted regret bound in terms of this information ratio.

4.1

A New Information Ratio.

First, we make a simplification to the information ratio Et [R∗ − Rt ]2 /It (A∗ ; (At , Yt )) defined by
Russo and Van Roy [15]. That expression depends on the history Ht−1 and hence is a random
variable. In this paper, we observe that this can be avoided, and instead take as a starting point a
simplified form of the information ratio that integrates out all randomness. In particular, we study
E[R∗ − Rt ]2
.
I(A∗ ; (At , Yt ) | Ht−1 )

(1)

Uniform bounds on the information ratio of the type established in past work [3, 11, 15] imply
those on (1). Precisely, if Et [R∗ − Rt ]2 /It (A∗ ; (At , Yt )) is bounded by λ ∈ R almost surely (i.e for
any history Ht−1 ), then (1) is bounded by λ since
E[R∗ − Rt ]2 ≤ E[Et [R∗ − Rt ]2 ] ≤ E[λIt (A∗ ; (At , Yt ))] = λI(A∗ ; (At , Yt )|Ht−1 ).
A more important change comes from measuring information about a benchmark action Ã, which
could be defined as in the examples in the previous section, rather than with respect to the optimal
5

action A∗ . For a benchmark action Ã we consider the single period information ratio
E[R̃ − Rt ]2
I(Ã; (At , Yt ) | Ht−1 )
where R̃ = µ(Ã, θ). This ratio relates the current shortfall in performance relative to the benchmark
action Ã to the amount of information acquired about the benchmark action. We study the
discounted average of these single period information ratios, defined for any policy ψ as




2

Γ Ã, ψ = (1 − α )

∞
X

!

α

2t

t=0

E[R̃ − Rt ]2
,
I(Ã; (At , Yt )|Ht−1 )

(2)

where the actions (At )t∈N0 are chosen under ψ. The square in the discount factor α is consistent
with the problem’s original discount rate, since E[αt (R̃ − Rt )]2 = α2t E[R̃ − Rt ]2 .

4.2

General Regret Bound.

The following theorem bounds the expected discounted regret of any algorithm, or policy, ψ in
terms of the information ratio (2).
Theorem 1. For any policy ψ, any D ≥ 0 and any Ã = f (θ, ξ) where ξ is independent of the
disturbances (Wt )t∈N0 , if E[µ(Ã, θ)] ≥ R∗ − D, then

SRegret(α, ψ, D) ≤

v 

u
u Γ Ã, ψ I(Ã; θ)
t

1 − α2

.

Proof. We first show that the mutual information between Ã and θ bounds the expected accumulation of mutual-information between Ã and observations (At , Yt )t∈N0 . By the chain rule for mutual
information, for any T ,
T
X

I(Ã; (At , Yt ) | Ht−1 ) =

t=0

T
X

I(Ã; (At , Yt ) | A0 , Y0 , . . . , At−1 , Yt−1 )

t=0

= I(Ã; HT )
≤ I(Ã; (θ, HT ))
= I(Ã; θ) + I(Ã; FT |θ)
= I(Ã; θ)
where the final inequality uses that, conditioned on θ, Ã is independent of HT . Taking the limit as
T → ∞ implies
∞
X

I(Ã; (At , Yt ) | Ht−1 ) ≤ I(Ã; θ),

t=0

where, the infinite series is assured to converge by the non-negativity of mutual information. Now,
let
E[R̃ − Rt ]2
Γt ≡
I(Ã; (At , Yt )|Ht−1 )

6

denote the information ratio at time t under the benchmark action Ã and actions {At : t ∈ N0 }
chosen according to ψ. Then
SRegret(α, ψ, D) = E

"∞
X

#
t

∗

α (R − D − Rt )

=

t=0

∞
X

h

αt E R̃ − Rt,At

i

t=0

=

∞ p
X

q

α2t Γt I(Ã; (At , Yt )|Ht−1 )

t=0

≤

v
v
u∞
u∞
uX
uX
2t
t
α Γt t I(Ã; (At , Yt )|Ht−1 )

≤

v"
#q
u ∞
u X
t
2t
α Γt I(Ã; θ)

=

v 

u
u Γ Ã, ψ I(Ã; θ)
t

t=0

t=0

t=0

1 − α2

,

where the first inequality follows from the Cauchy-Schwarz inequality and the second was established earlier in this proof.
An immediate consequence of this bound on satisficing regret is the discounted regret bound

Regret(α, ψ) ≤

E[R∗ − R̃]
+
1−α

v 

u
u Γ Ã, ψ I(Ã; θ)
t

1 − α2

.

(3)

This bound decomposes regret into the sum of two terms; one which captures the discounted
performance shortfall of the benchmark action Ã relative to A∗ , and one which bounds the additional
regret incurred while learning to identify Ã. Breaking things down further, the mutual information
I(θ; Ã) measures how much information the decision-maker must acquire in order to implement
the action Ã, and the information ratio measures the regret incurred in gathering this information.
It is worth highlighting that for any given action process, this bound holds simultaneously for all
possible choices of Ã, and in particular, it holds for the Ã minimizing the right hand side of (3).

5

Connections With Rate Distortion Theory.

This section considers the optimal choice of satisfactory action Ã and develops connections with
the theory of rate-distortion in information theory. We construct a natural rate-distortion function
for Bayesian decision making in the next subsection. Subsection 5.2 then develops a general regret
bound that depends on this rate-distortion function.

5.1

A Rate Distortion Function for Bayesian Decision Making.

In information-theory, the entropy of a source characterizes the length of an optimal lossless encoding. The celebrated rate-distortion theory [6, Chapter 10] characterizes the number of bits required
for an encoding to be close in some loss metric. This theory resolves when it is possible to to derive
a satisfactory lossy compression scheme while transmitting far less information than required for

7

a lossless compression. The rate-distortion function for a random variable X with domain X with
respect to a loss function ` : X̂ × X → R is
R(D) = min I(X̂; X)

(4)

E[`(X̂, X)] ≤ D

s.t.

where the minimum is taken the choice of random variables X̂ with domain X̂ , and I(X; X̂) denotes
the mutual information between X and X̂. One can view this optimization problem as specifying
a conditional distribution P (X̂ ∈ ·|X) that minimizes the information X̂ uses about X among all
choices incurring average loss less than D.
We will explore a powerful link with sequential Bayesian decision-making, where the ratedistortion function characterizes the minimal amount of new information the decision–maker must
gather in order make a satisfactory decision. Typically (4) is applied in the context of representing
X as closely as possible by X̂, and the loss function is taken to be something like the squared
distance or total variation distance between the two. For our purposes, we replace X with θ,
and X̂ with a benchmark action Ã. The interpretation is that Ã = f (θ; ξ) is a function of the
unknown parameter θ and some exogenous randomness ξ that offers a similar reward to playing
A∗ but hopefully can be identified using much less information about θ. We specify a loss function
` : A × Θ → R measuring the single period regret from playing a under θ:
`(a, θ) = max
µ(a0 , θ) − µ(a, θ).
0
a ∈A

As a result
E[`(Ã, θ)] = E[R∗ − µ(Ã, θ)].
We come to the rate-distortion function
R(D) := min I(Ã; θ)
s.t.

(5)

∗

E[R − µ(Ã, θ)] ≤ D.

As before, the minimum above is taken over the choice of random variable Ã taking values in A.
That is, the minimum is taken over all conditional probability distributions P(Ã ∈ ·|θ) specifying
a distribution over actions as a function of θ. Since the choice Ã = A∗ is always feasible, for all
D>0
R(D) ≤ I(A∗ ; θ) = H(A∗ )
where H(A∗ ) denotes the entropy of the optimal action. Rate distortion is never larger than entropy,
but it may be small even if the entropy of A∗ is infinite.
The following, somewhat artificial, example explicitly links communication with decision-making
and may help clarify the role of the rate-distortion function R(D).
Example 5. A military command center waits to hear from an outpost before issuing orders.
The outpost, stationed close to the conflict, determines its message based on a wealth of nuanced
information – at the level of readouts from weather sensors and full transcripts of intercepted enemy
communication. The command post could make very complicated decisions as a function of the
detailed information it receives, with the possibility of specifying commands at the level of individual
troops and equipment. How much must decision quality degrade if decisions are based only on coarser
information? At an intuitive level, the outpost only needs to communicate surprising revelations
that are important to reaching a satisfactory decision. As a result, our answer can depend in a
complicated way on the extent to which the outpost’s observations are predictable apriori and the
8

extent to which decision quality is reliant on this information. The rate-distortion function precisely
quantifies these effects.
To map this problem onto our formulation of the rate-distortion function, take θ to consist
of all information observed by the outpost, Ã to be the order issued by the command center, and
the rewards to indicate whether the orders led to a successful outcome. The mutual information
I(Ã; θ) captures the average amount of information the outpost must send in order for Ã to be
implemented. The goal is to develop a plan for placing orders that requires minimal communication
from the outpost among all plans that degrade the chance of success by no more than D.

5.2

Uniformly Bounded Information Ratios.

The general regret bound in Theorem 1 has a superficial relationship to the rate-distortion function
R(D) through its dependence on the mutual information I(Ã; θ) between the benchmark action
and the true parameter θ. Indeed, for a benchmark action Ã attaining the rate-distortion limit,
I(Ã; θ) = R(D) and we attain a regret

bound that depends explicitly on the rate-distortion level.
However, the information ratio Γ Ã, ψ also depends on the choice of benchmark action, and may
be infinite for a poor choice.
This second dependence on Ã does not appear in rate-distortion theory, and reflects a fundamental distinction between communication problems and sequential learning problems. Indeed, a
key feature enabling the sharp results of rate distortion theory is that no bit of information is more
costly to send and receive than others; the question is to what extent useful communication is possible while many fewer bits of information on average. By contrast, sequential learning agents must
explore to uncover information and the cost per unit of information uncovered may vary widely
depending
 on which pieces of information are sought. This is accounted for by the information
ratio Γ Ã, ψ , which roughly captures the expected cost, in terms of regret incurred, per bit of
information acquired about the benchmark action.
Despite this, regret bounds in terms of rate-distortion apply in many important cases. Theorem
1, which is an immediate consequence of Theorem 1, provides a general bound of this form. Roughly,
the uniform information ratio ΓU in the theorem reflects something about quality of the feedback
the agent receives when exploring; it means that for any choice of benchmark action Ã there is
a sequential learning strategy that learns about Ã with cost per bit of information less than ΓU .
The next section applies this result to online linear optimization, where several possible uniform
information ratio bounds are possible depending on the problems precise feedback structure.
Theorem 2. Suppose there is a uniform bound on the information ratio




ΓU := sup inf Γ Ã, ψ < ∞.
Ã

ψ

Then, for any D ≥ 0 there exists a policy ψ under which
s

SRegret(α, ψ, D) ≤

6

ΓU R(D)
.
1 − α2

Application to Online Linear Optimization.

Consider a special case of our formulation: the problem of learning to solve a linear optimization
problem. Precisely, suppose expected rewards follow the linear model E[Rt |θ, At ] = θ> At where

9

h

i

At ∈ A ⊂ Rp , θ ∈ Rp , and Rt ∈ − 12 , 12 almost surely. We will consider several natural forms a
feedback Yt the decision-maker may receive.
In each case, uniform bounds on the information ratio hold for satisficing Thompson sampling.
STS denote the strategy that randomly samples an action at each
More precisely, for any Ã let ψÃ
time t by probability matching with respect to Ã, i.e. P(At ∈ ·|Ht−1 ) = P(Ã ∈ ·|Ht−1 ). Applying
STS ) ≤ λ, where λ depends on the
the same proofs as in [15] yields bounds of the form Γ(Ã; ψÃ
problem’s feedback structure but not the choice of benchmark action. Now, let us choose Ã to
attain the rate distortion limit (5), so I(Ã; θ) = R(D) and E[R∗ − µ(Ã; θ)] ≤ D. We denote by
STS satisficing Thompson sampling with respect to this choice of satisfactory action.
ψD
Full Information. Suppose Rt = A>
t Zt for a random vector Zt with E[Zt |θ, Ht−1 ] = θ. This is
an extreme point of our formulation, where all information is revealed without active exploration.
STS ; Ã) ≤ 1/2 and hence
For all Ã, the information ratio is bounded as Γ(ψÃ
s
STS
SRegret(α, ψD
, D) ≤

R(D)
.
2(1 − α2 )

Bandit Feedback. Suppose the agent only observes the reward the action she chooses (Yt =
Rt ). This is the so-called linear bandit problem. For all Ã, the information ratio is bounded as
STS ; Ã) ≤ p/2. This gives the regret bound
Γ(ψÃ
s
STS
SRegret(α, ψD
, D) ≤

R(D)p
.
2(1 − α2 )

p
Semi-Bandit Feedback. Assume again that Rt = A>
t Zt for all a. Take the action set A ⊂ {0, 1}
Pp
to consist of binary vectors where i=1 ai ≤ m for all a ∈ A. Upon playing action At = a, the
agent observes Zt,i for every component {i ∈ {1, ..., m} : ai = 1} that was active in a. We make the
additional assumption that the components of Zt are independent conditioned on Ht−1 . Then, for
STS ; Ã) ≤ p/2m and hence
all Ã, the information ratio is bounded as Γ(ψÃ

s
STS
SRegret(α, ψD
, D)

≤

R(D)(p/m)
.
2(1 − α2 )

By following the appendix of [15], each of these result can be extended gracefully to settings
where noise distributions are sub-Gaussian. For example, suppose θ follows a multivariate Gaussian
distribution, and the reward at time t is Rt = θ> At +Wt where Wt is a zero mean Gaussian random
variable. Then, if the variance of rewards E[(θ> a + W − E[θ]> a)2 ] ≤ σ 2 is bounded by some σ 2 for
all a, the previous bounds on the information ratio scale by a factor of σ.
The next theorem considers an explicit choice of satisfactory action Ã. This yields a computationally efficient version of STS as well as explicit upper bounds on the rate-distortion function. As
above, consider the case where θ ∼ N (µ, Σ) follows a multivariate Gaussian prior and reward noise
is Gaussian. We study the optimizer Ã = argmaxa∈A ha, θ + ξi of a randomly perturbed objective.
The small perturbation controls the mutual information between Ã and θ without substantially
degrading decision quality. It is easy to implement probability matching with respect to Ã whenever linear optimization problems over Ã are efficiently solvable. In particular, if µt = E[θ | Ht−1 ]
and Σt = E[(θ − µt )(θ − µt )> | Ht−1 ] denote the posterior mean and covariance matrix, which are
efficiently computable using Kalman filtering, then by sampling θ̂t ∼ N (µt , Σt ) and ξˆt ∼ N (0, Σξ )
and setting At = argmaxa∈A ha, θ̂t + ξˆt i one has P(At ∈ · | Ht−1 ) = P(Ã ∈ · | Ht−1 ).
10

The result in the next theorem assumes the action set is contained within an ellipsoid {x ∈
: x> Q−1 x ≤ 1} and the resulting bound displays a logarithmic dependence on the eigenvalues
of Q. Precisely, note that the trace of the matrix Q, or sum of its eigenvalues, provides one natural
measure of the size of the ellipsoid. Our result also depends on the covariance matrix Σ through
the Trace(QΣ). To understand this, consider applying similarity transforms to the parameter and
action vectors so that θ0 = Σ−1/2 θ is isotropic and the set of action vectors is A0 = {Σ1/2 a : a ∈ A}.
This transformed action space is contained in the ellipsoid {x : x> Q0−1 x ≤ 1}, where Q0 = Σ1/2 QΣ.
Then Trace(Q0 ) = Trace(QΣ) provides a measure of the size of this ellipsoid.
Rp

Theorem 3. Suppose A is a compact subset of the ellipsoid A ⊂ {x ∈ Rp : x> Q−1 x ≤ 1} for some
real symmetric matrix Q and suppose θ ∼ N (µ, Σ) follows a p–dimensional multivariate Gaussian
distribution. Set
Ã = argmaxha , θ + ξi
a∈A

where ξ is independent of θ and ξ ∼

N (0, β 2 Σ).
h

p

For β = D/ Trace(QΣ),

i

E hθ , Ãi ≥ E [hθ , A∗ i] − D
and

p
Trace(QΣ)
R(D) ≤ I(Ã; θ) ≤ log 1 +
.
2
D2
Proof. By Jensen’s inequality












E[hÃ , θ + ξi] = E maxha , θ + ξi ≥ E maxha , θi = E hA∗ , θi] .
a∈A

a∈A

This implies
h

∗



i



E [hA , θi] − E hÃ , θi ≤ E[hÃ , ξi] ≤ E maxha , ξi ≤ E
a∈A

#

"

max

x :kxkQ−1 ≤1

ha , ξi = E [kξkQ ]

where the final equality uses the explicit formula for the maximum of a linear function over an
ellipsoid. Now,
E [kξkQ ] ≤

q

E[ξ > Qξ] =

q

E[Trace(ξ > Qξ)] =

q

Trace(QE[ξξ > ]) =

q

β 2 Trace(QΣ) = D.

Next we derive the bound on mutual information. We have
I(Ã; θ) ≤ I(θ + W ; θ) = H(θ + W ) − H(θ + W |θ)
= H(θ + W ) − H(W )
=

1
log
2

det(Σ + β 2 Σ)
det(β 2 Σ)

!

!

=
=
=

1
det((1 + β 2 )Σ)
log
2
det(β 2 Σ)


p
1
log 1 + 2
2
β


p
Trace(QΣ)
log 1 +
2
D2

where det(·) denotes the determinant of a matrix. Here the first inequality uses the data processing
inequality, the third equality uses the explicit form the entropy of a multivariate Gaussian (H(θ) =
1
p
2 log (2πe det(Σ))) and the penultimate equality uses that det(cΣ) = c det(Σ) for any scalar c.
11

7

Application to the Infinite-Armed bandit.

This section considers a generalization of the deterministic infinite-armed bandit problem in the
introduction that allows for noisy observations and non-uniform priors. The action space is
A = {1, 2, . . .}. We assume Rt ∈ [0, 1] almost surely and Yt = Rt , meaning the agent only observes rewards. The mean reward of action a is µ(θ, a) = θa where the prior distribution of θa is
independent with support [0, 1]. We will this problem by specializing our general framework and
results.

7.1

STS for the Infinite-Armed Bandit Problem.

We consider the simple satisficing action defined in the introduction: Ã = min{a ∈ A : θa ≥
R∗ − D}. Rather than continue to explore until identifying the optimal action A∗ , we will settle
for the first 1 action known to yield reward within D of optimal.
We study satisficing Thompson sampling where actions are selected by probability matching
with respect to Ã. Note that an algorithm for this problem must decide whether to sample a
previously tested action – and if so which one to sample – or whether to try out an entirely new
action. Let At = {A0 , . . . , At−1 } denote the set of previously sampled actions. STS may sample an
untested action At ∈
/ A, and does so with probability
P(At ∈
/ At |Ht−1 ) = P(Ã ∈
/ At |Ht−1 ).
equal to the posterior probability no satisfactory action has yet been sampled. The remainder of
the action probabilities are allocated among previously tested actions, with
P(At = a|Ht−1 ) = P(Ã = a|Ht−1 )

∀a ∈ At .

There is a simple algorithmic implementation of STS that mirrors computationally efficient
implementations of Thompson sampling (TS). At time t, TS selects a random action At via probability matching with respect to A∗ . Algorithmically, this is usually accomplished by first sampling
θ̂t ∼ P(θ ∈ ·|Ht−1 ) and solving for At ∈ argmaxa∈A µ(a, θ̂t ). Similarly, we can implement STS by
sampling and approximately optimizing a posterior sample. Over each tth period, STS selects an
action At as follows:
1. For each a ∈ At , sample θ̂a ∼ P(θa ∈ ·|Ht−1 )
n

2. Let τ̂ = min τ ∈ {1, . . . , t − 1} : µ(At , θ̂t ) ≥ 1 − D

o

3. If τ̂ is not null set At = Aτ . Otherwise, play an untested action At ∈
/ At .
Note that D ≥ 0 is supplied to the algorithm as a tolerance parameter. When D = 0, STS is
equivalent to TS. Otherwise, STS attributes preference to selecting previously selected actions,
which can yield substantial benefit in the face of time preference.
1

Of course, there is nothing crucial about this ordering on actions. We can equivalently construct a randomized
order in which actions are sampled; for each realization of the random variable ξ, let πξ : N0 → N0 be a permutation,
and take Ã = min{πξ (a) : θa ≥ 1 − D}.

12

7.2

Information Ratio Analysis of the Infinite-Armed Bandit.

The following theorem provides an discounted regret bound for STS in the infinite armed bandit.The
result follows from bounding the problems information ratio and the mutual information I(Ã; θ)
and applying the general regret bound of Theorem 1. This requires substantial additional analysis,
the details of which are until Subsection 7.4.
Theorem 4. Consider the the infinite-armed bandit with noisy observations, and let Ã = min{a ∈
STS . Then,
A : θa ≥ 1 − D}. Denote the STS policy with respect to Ã by ψD
I(Ã; θ) ≤ 1 + log(1/δ)

and





STS
Γ Ã, ψD
≤ 6 + 4/δ + (2/δ) log



1
1 − α2



where δ = P(θa ≥ 1 − D). Together with Theorem 1 this implies
STS
SRegret(α, ψD
, D) ≤

v


u
1
u 6 + 4/δ + (2/δ) log
(1 + log(1/δ))
t
1−α2

1 − α2
s

= Õ 

7.3



1/δ 
.
1 − α2

Computational Examples.

We close with a simple computational illustration of the potential benefits afforded by STS. We consider two many-armed bandit problems, and demonstrate that per-period regret of STS diminishes
much more rapidly than that of TS over early time periods.
We consider problems with 250 actions, where the mean reward θa associated with each action
a ∈ {1, . . . , 250} is independently sampled uniformly from [0, 1]. We first consider the manyarmed deterministic bandit, for which there is no observation noise. Figure 1(a) presents perperiod regret of TS and STS over 500 time periods, averaged over 5000 simulations, each with an
independently sampled problem instance. STS is applied with tolerance parameter 0.05. We next
consider incorporating observation noise. In particular, instead of observing θa , after selecting an
action a, we observe a binary reward that is one with probability θa . Figure 1(b) displays the
results of this experiment.

Figure 1: TS versus STS for the (a) many-armed deterministic bandit and (b) many-armed bandit
with observation noise.

13

7.4

Proof of Theorem 4.

Our proof will use the following fact, which is stated as Fact 9 in [15].
Fact 1. For any distributions P and Q such that that P is absolutely continuous with respect to
Q, any random variable X : Ω → X and any g : X → R such that sup g − inf g ≤ 1,
r

EP [g(X)] − EQ [g(X)] ≤

1
D (P ||Q),
2

where EP and EQ denote the expectation operators under P and Q.
We begin by showing the mutual information bound stated as part of Theorem 4.
Lemma 5 (Mutual Information Bound). Let δ = P(θa ≥ 1 − D). Then
I(Ã; θ) ≤ 1 + log (1/δ) .
Proof. Since Ã = min{a ∈ A : θa ≥ 1 − D} is a deterministic function of θ, we have I(Ã; θ) =
H(Ã) = H(N ) where N ∼ Geom(δ) is a geometric random variable. This implies
I(Ã; θ) = H (N )
= −
= −

∞
X
k=1
∞
X

δ(1 − δ)k−1 log(δ(1 − δ)k−1 )
δ(1 − δ)k−1 log(δ) −

k=1

=

∞
X

∞
X

δ(1 − δ)k−1 log((1 − δ)k−1 )

k=1

P(N = k) log(1/δ) − log(1 − δ)

k=1

=
≤
=

δ(1 − δ)k−1 (k − 1)

k=1

1
(E[N ] − 1)
log(1/δ) + log
1−δ



δ
1−δ
log(1/δ) + log 1 +
1−δ
δ



1−δ
δ
log(1/δ) +
1−δ
δ
1 + log(1/δ).


=

∞
X



Throughout the remainder of the proof we use the notation
Γt =

Et [θÃ − θAt ]2
.
It (Ã; (At , Yt ))

This represents the expected one-step information ratio in period t under the posterior measure
P(·|Ht−1 ). The next lemma shows that the cumulative information ratio can be bounded by the
expected discounted average of these one-step information ratios.
Lemma 6 (Relating the information ratio to the one-step-information-ratio).
Γ



STS
Ã, ψD



2

≤ (1 − α )

∞
X
t=0

14

α2t E[Γt ]

Proof. We have


E[R̃ − Rt ] = E θÃ − θAt







= E Et θÃ − θAt
"

r

p







#

Γt It Ã; (At , Yt )

= E
r

≤



h

E[Γt ] E It Ã; (At , Yt )
r

i




E[Γt ] I Ã; (At , Yt ) | Ht−1 .

=
Then, by the definition of the information ratio




2

Γ Ã, ψ = (1 − α )

∞
X

α

2t

t=0

E[R̃ − Rt ]2
I(Ã; (At , Yt )|Ht−1 )

!
2

≤ (1 − α )

∞
X

α2t E[Γt ].

t=0

The next lemma provides a bound on the one-step information ratio.
Lemma 7.
Γt ≤ 2|At | + 2/δ
where At = ∪t−1
s=1 {As } is the set of actions that were sampled before period t, and δ ≡ P(θi ≥ 1 − D)
is the prior probability an arm is D–optimal.
Proof. Define
L ≡ E[θi |θi ≥ 1 − D] − E[θi ]
and
δ ≡ P(θi ≥ 1 − D).
Here δ is the probability an unsampled arm is D–optimal, and L is the difference between the
expected reward of a D–optimal arm and that of an arm sampled uniformly at random. In the
case where θi ∼ Unif(0, 1), δ = D and L = (1 − D)/2.
We can write expected regret as
Et [θÃ − θAt ] =

X

Pt (Ã = a)Et [θa |Ã = a] −

=

Pt (At = a)Et [θa ]

a∈A

a∈A

X

X





Pt (Ã = a) Et [θa |Ã = a] − Et [θa ]

a∈At

+

X

Pt (Ã = a)Et [θa |Ã = a] −

a∈A
/ t

=

X

X

Pt (At = a)Et [θa ]

a∈A
/ t









Pt (Ã = a) Et [θa |Ã = a] − Et [θa ] + Pt (Ã ∈
/ At )(E[θa |θa ≥ 1 − D] − E[θa ])

a∈At

=

X

Pt (Ã = a) Et [θa |Ã = a] − Et [θa ] + Pt (Ã ∈
/ At )L .
|

a∈At

|

{z

}

∆t,1

{z

∆t,2

}

This decomposes regret into the sum of two terms: one which captures the regret due to suboptimal
selection within the set of previously sampled actions At , and one due to the remaining possibility
15

that none of the sampled actions are D–optimal. The proof develops a similar decomposition for
mutual information, and then lower bounds both terms.
Let Yt,a = g(a, θ, Wt ) denote the outcome that would have been realized from a choice of action
a at time t. We can express mutual information as follows:
It (Ã; (At , Yt )) =

X

Pt (At = a)It (Ã; Yt |At = a)

a∈A

=

X

X

Pt (Ã = a)It (Ã; Yt,a ) +

a∈At

Pt (Ã = a)It (Ã; Yt,a |At = a)

a∈A
/ t

Let us focus on the second sum, which captures the information acquired due to sampling previously
untested actions a ∈
/ At . Such an action provides information about Ã, since if Ã ∈
/ At and
θa ≥ 1 − D, then a is the first sampled action to be sufficiently close to optimal and Ã = a. Using
the shorthand Pt (X) = Pt (X ∈ ·) to denote the posterior distribution of a random variable X, we
have that for an untested action a ∈
/ At
It (Ã; Yt,a |At = a) =



X







Pt Ã = ã | At = a D Pt (Yt,a | Ã = ã) || Pt (Yt,a )

ã∈A













≥ Pt Ã = a | At = a D Pt (Yt,a | Ã = a) || Pt (Yt,a )

= Pt Ã = a | At = a D (Pt (Yt,a | θa ≥ 1 − D) || Pt (Yt,a ))








≥ 2Pt Ã = a | At = a (Et [θa | θa ≥ 1 − D] − Et [θa ])2
= 2Pt Ã = a | At = a L2












= 2Pt Ã ∈
/ At Pt Ã = a | At = a, Ã ∈
/ At L2
= 2Pt Ã ∈
/ At δL2 .
The second inequality uses Fact 1. This implies
X



Pt (Ã = a)It (Ã; Yt,a |At = a) ≥ 2Pt Ã ∈
/ At

2

δL2 .

a∈A
/ t

Next, following the proof of Proposition 3 of Russo and Van Roy [15] shows
X

Pt (Ã = a)It (Ã; Yt,a ) =

a∈At

X

Pt (Ã = a)

a∈At

≥

X

X





D Pt (Yt,a | Ã = ã) || Pt (Yt,a )

ã∈A
2





Pt (Ã = a) D Pt (Yt,a | Ã = a) || Pt (Yt,a )

a∈At

≥ 2

X

2



Pt (Ã = a)2 Et [θa |Ã = a] − Et [θa ]

a∈At

2



≥



2 X
Pt (Ã = a) Et [θa |Ã = a] − Et [θa ] 
|At | a∈A
t

where the second inequality uses Fact 1. Therefore
2





2 X
It (Ã; (At , Yt )) ≥
Pt (Ã = a) Et [θa |Ã = a] − Et [θa ]  + 2Pt (Ã ∈
/ At )2 δL2 ,
|
{z
}
|At | a∈A
t

|

{z

Gt,1

16

}

Gt,2

is lower bounded by the sum of two terms: one which captures the information gain due to refining knowledge about previously sampled actions, and one that captures the expected information
gathered about previously unexplored actions.
To bound the information ratio we’ll separately consider two cases. If ∆t,1 ≥ ∆t,2 , then
Et [θÃ − θAt ]2
4(∆t,1 )2
(2∆t,1 )2
≤
= 2|At |.
≤
Gt,1 + Gt,2
Gt,1
It (Ã; (At , Yt ))
If instead ∆t,1 < ∆t,2 , then
Et [θÃ − θAt ]2
4(∆t,2 )2
2
(2∆t,2 )2
≤
= .
≤
G
+
G
G
δ
It (Ã; (At , Yt ))
t,1
t,2
t,2
This shows

Et [θÃ − θAt ]2
≤ 2|At | + 2/δ.
It (Ã; (At , Yt ))

Combining this result with Lemma 6 gives the bound


STS
Γ Ã, ψD



≤ (1 − α2 )

∞
X

α2t E [Γt ]

t=0
2

≤ 2/δ + 2(1 − α )

∞
X

α2t E[|At |].

t=0

To use this result, we begin by bounding E[|At |].
Lemma 8. |A0 | = 0 and for each T ∈ {1, 2, . . .}, E[|AT |] ≤ 2 + log(T )/δ.
Proof. Let τk = min{t ≤ T ||At | ≥ k} denote the first period before T in which k actions have been
sampled. Then
E[|AT |] = E[|Aτk |] + E[|AT | − |Aτk |]
≤ E[|Aτk |] + E[|Aτk +T | − |Aτk |]
≤ k+E

τk +T
X−1

1(At ∈
/ At )

t=τk

= k+E
= k+E
= k+

TX
−1
s=0
TX
−1

P(Aτk +s ∈
/ Aτk +s |Hτk +s )
P(Ã ∈
/ Aτk +s |Hτk +s )

s=0
TX
−1

P(Ã ∈
/ Aτk +s )

s=0

≤ k + T P(Ã ∈
/ Aτk )
= k + T P(Geom(δ) > k)
= k + T (1 − δ)k
≤ k + T e−δk .
17

Choosing k = dlog(T )/δe ≤ 1 + log(T )/δ, implies
E[|AT |] ≤ 2 + log(T )/δ.

The next technical lemma shows
Appendix B.

P∞

t=1 γ

−t log(t)

= O((1/γ) log(1/γ)). The proof is given in

Lemma 9. For any γ ∈ (0, 1),
∞
X

γ

−t

t=1

1
1
1 + log
log(t) ≤
1−γ
1−γ






.

Finally we can conclude with the proof of Theorem 4. As shown before,


STS
Γ Ã, ψD



≤ (1 − α2 )

∞
X

α2t E [Γt ]

t=0

≤ 2/δ + 2(1 − α2 )

∞
X

α2t E[|At |].

t=0

By Lemma 8 and Lemma 9 we find
(1 − α2 )

∞
X

α2t E[|At |] ≤ (1 − α2 )

t=0

∞
X

α2t (2 + log(t)/δ)

t=1

≤ 3 + (1/δ)(1 − α2 )

∞
X

α2t log(t)

t=1

1
≤ 3 + (1/δ) 1 + log
1 − α2






.

This implies
Γ



STS
Ã, ψD



1
≤ 6 + 4/δ + (2/δ) log
1 − α2




1
= O (1/δ) log
1 − α2






and concludes the proof of Theorem 4.

8

Closing Remarks

We have put forth a way of thinking about satisficing in bandit learning. The per-period regret of
an algorithm that learns a satisficing action Ã does not converge to zero, but the time required can
often be far less than what it would be to learn an optimal action A∗ . Intuitively, this advantage
stems from the fact that the mutual information I(θ; Ã), which can be thought of as the number
of bits of information about the model required to learn Ã, can be far less than I(θ; A∗ ).
Satisficing plays a particularly important role when there is a satisficing action Ã for which
I(θ; Ã)  I(θ; A∗ ) and the agent exhibits time preference, valuing near-term over long-term rewards. To express this in terms of a formal objective, we considered expected discounted regret. We
also introduced satisficing Thompson sampling, and established results pertaining to infinite-armed
and linear bandits demonstrating that this variant of Thompson sampling captures benefits of targeting a satisficing action. There remain opportunities for further work to treat broader classes of
problems and explore the impact that these ideas can have on practical applications.
18

Acknowledgments.
The second author was generously supported by a research grant from Boeing and a Marketing
Research Award from Adobe. A special thanks is owed to David Tse, who played an important
role in the early stages of this work. It was David who first emphasized that bounds based on
entropy can be vacuous and pointed us to references on rate-distortion theory. We also thank Tor
Lattimore for thoughtful comments on an early draft of this work.

A

Analysis of the Infinite-Armed Deterministic Bandit.

Theorem 10. For all α ∈ [0, 1], under Thompson sampling in the infinite-armed deterministic
bandit,
"∞
#
X
1
t
∗
E
α (R − θAt ) =
.
2(1 − α)
t=0
√
Under satisficing Thompson sampling with tolerance  = 1 − α in the infinite-armed deterministic
bandit,
#
"∞
X
1
t
∗
α (R − θAt ) ≤ √
E
.
1
−α
t=0
Proof. In every period t, TS samples a new action At ∈
/ {A1 , ..., At−1 }, which generates expected
reward E[θAt ] = E[θ1 ] = 1/2. The optimal expected reward is 1, and therefore the expected
discounted-regret of TS is
∞
X
1
αt (1 − 1/2) =
.
2(1 − α)
t=0
Now, let us analyze satisficing Thompson sampling. Let τ = min{t : θAt ≥ 1 − } denote the fist
time it sampled a –optimal action. Then,
E

"∞
X

#

αt (R∗ − θAt )

= E

"∞
X

#

αt (1 − θAt )

t=0

t=0

" "τ −1
X

= E E
"

= E E
"

= E E
"

= E E

t=0
"τ −1
X
t=0
"τ −1
X
t=0
"τ −1
X

t

α (1 − θAt ) +

∞
X

##
t

α (1 − θAt ) τ

t=τ
t

α E[1 − θa |θa ≤ 1 − ] +

∞
X

##
t

α E[1 − θa |θa ≥ 1 − ] τ

t=τ
t

α (1/2 + /2) +

∞
X

##
t

α (/2) τ

t=τ
t

α (1/2) +

t=0

∞
X

##
t

α (/2) τ

t=0

(1 − ατ )

= E
+
2(1 − α) 2(1 − α)


1

≤
+
.
2 2(1 − α)




The inequality above follows from the calculation
τ

E[1 − α ] = 1 −

∞
X
t=0

(1 − )t αt = 1 −

1 − α(1 − ) − 
1−α

=
≤
.
1 − α(1 − )
1 − α(1 − )

19

(6)

The final bound of

B

p

1/(1 − α) follows by choosing the minimizer ∗ =

√
1 − α of equation (6).

Proof of Lemma 9.

Proof.
∞
X

γ −t log(t) ≤

t=1

∞
X

e−(1−γ)t log(t)

t=1

=
∗

≤
=
≤
=
≤

∞
X

e−(1−γ)t log(t)

t=2
ˆ
∞

e−(1−γ)x log(x + 1)dx
1
ˆ ∞


1
u
−u
e log
+ 1 du
1−γ 1
1−γ
ˆ ∞


 ˆ ∞

1
1
−u
−u
1 + log
e du +
e log(u)du
1−γ
1−γ
ˆ ∞ 1


 1

1
1
−u
1 + log
(1/e) +
e log(u)du
1−γ
1−γ
1



1
1
1 + log
1−γ
1−γ

where the last step uses a numerical approximation to the indefinite integral
ˆ ∞
e−u log(u)du ≈ .22
1

along with the fact that 1/e + .22 ≈ .57 < 1.
The inequality (*) uses that for any t ≥ 2
ˆt
−(1−γ)t

e

e−(1−γ)x log(x + 1)

log(t) ≤
t−1

since e−(1−γ)x is decreasing in x and log(x) is increasing in x.

20

References
[1] D. A. Berry, R. W. Chen, A. Zame, D. C. Heath, and L. A. Shepp. Bandit problems with
infinitely many arms. The Annals of Statistics, 25(5):2103–2116, 1997.
[2] T. Bonald and A. Proutiere. Two-target algorithms for infinite-armed bandits with Bernoulli
rewards. In C. J. C. Burges, L. Bottou, M. Welling, Z. Ghahramani, and K. Q. Weinberger,
editors, Advances in Neural Information Processing Systems 26, pages 2184–2192. Curran
Associates, Inc., 2013.
[3] S. Bubeck and R. Eldan. Multi-scale exploration of convex functions and bandit convex optimization. arXiv preprint arXiv:1507.06580, 2015.
[4] S. Bubeck, R. Munos, G. Stoltz, and C. Szepesvári. X -armed bandits. Journal of Machine
Learning Research, 12:1655–1695, June 2011.
√
[5] S. Bubeck, O. Dekel, T. Koren, and Y. Peres. Bandit convex optimization: T regret in one
dimension. arXiv preprint arXiv:1502.06398, 2015.
[6] T.M. Cover and J.A. Thomas. Elements of information theory. John Wiley & Sons, 2012.
[7] Y. Deshpande and A. Montanari. Linear bandits in high dimension and recommendation
systems. In Communication, Control, and Computing (Allerton), 2012 50th Annual Allerton
Conference on, pages 1750–1754. IEEE, 2012.
[8] A. Francetich and D. M. Kreps. Choosing a good toolkit, I: Formulation, heuristics, and
asymptotic properties. preprint, 2016.
[9] A. Francetich and D. M. Kreps. Choosing a good toolkit, II: Simulations and conclusions.
preprint, 2016.
[10] R. Kleinberg, A. Slivkins, and E. Upfal. Multi-armed bandits in metric spaces. In Proceedings
of the 40th ACM Symposium on Theory of Computing, 2008.
[11] Fang Liu, Swapna Buccapatnam, and Ness Shroff. Information directed sampling for stochastic
bandits with graph feedback. arXiv preprint arXiv:1711.03198, 2017.
[12] P. Rusmevichientong and J.N. Tsitsiklis. Linearly parameterized bandits. Mathematics of
Operations Research, 35(2):395–411, 2010.
[13] D. Russo and B. Van Roy. Learning to optimize via posterior sampling. Mathematics of
Operations Research, 39(4):1221–1243, 2014.
[14] D. Russo and B. Van Roy. Learning to optimize via information-directed sampling. In
Z. Ghahramani, M. Welling, C. Cortes, N. D. Lawrence, and K. Q. Weinberger, editors, Advances in Neural Information Processing Systems 27, pages 1583–1591. Curran Associates,
Inc., 2014.
[15] D. Russo and B. Van Roy. An information-theoretic analysis of Thompson sampling. Journal
of Machine Learning Research, 17(68):1–30, 2016.
[16] I.O. Ryzhov, W.B. Powell, and P.I. Frazier. The knowledge gradient algorithm for a general
class of online learning problems. Operations Research, 60(1):180–195, 2012.
21

[17] W.R. Thompson. On the likelihood that one unknown probability exceeds another in view of
the evidence of two samples. Biometrika, 25(3/4):285–294, 1933.
[18] Aristide CY Tossou, Christos Dimitrakakis, and Devdatt P Dubhashi. Thompson sampling
for stochastic bandits with graph feedback. In AAAI, pages 2660–2666, 2017.
[19] Y. Wang, J.-Y. Audibert, and R. Munos. Algorithms for infinitely many-armed bandits. In
D. Koller, D. Schuurmans, Y. Bengio, and L. Bottou, editors, Advances in Neural Information
Processing Systems 21, pages 1729–1736. Curran Associates, Inc., 2009.

22

