# On Bits and Bandits: Quantifying the Regret-Information Trade-off

Itai Shufaro
Technion
<EMAIL_ADDRESS>
&Nadav Merlis
ENSAE
<EMAIL_ADDRESS>
&Nir Weinberger
Technion
<EMAIL_ADDRESS>&Shie Mannor
Technion, Nvidia Research
<EMAIL_ADDRESS>

###### Abstract

In interactive decision-making tasks, information can be acquired by direct
interactions, through receiving indirect feedback, and from external
knowledgeable sources. We examine the trade-off between the information an
agent accumulates and the regret it suffers. We show that information from
external sources, measured in bits, can be traded off for regret, measured in
reward. We invoke information-theoretic methods for obtaining regret lower
bounds, that also allow us to easily re-derive several known lower bounds. We
then generalize a variety of interactive decision-making tasks with external
information to a new setting. Using this setting, we introduce the first
Bayesian regret lower bounds that depend on the information an agent
accumulates. These lower bounds also prove the near-optimality of Thompson
sampling for Bayesian problems. Finally, we demonstrate the utility of these
bounds in improving the performance of a question-answering task with large
language models, allowing us to obtain valuable insights.

##  1 Introduction

In interactive decision-making tasks, an agent interacts with an environment
by sequentially choosing decisions from a decision space. Subsequently, the
agent receives feedback that usually includes a reward and, optionally, other
types of information. For example, in multi-armed bandits (MAB) [Lattimore and
Szepesvári, 2020], the feedback includes only the reward. In partial
monitoring, however, it only includes a signal, which the agent then needs to
use to indirectly infer the reward [Cesa-Bianchi et al., 2006]. The goal of
the agent in such tasks is to minimize the gap between the accumulated reward
and the reward of the best decision in hindsight, also known as regret.

In these tasks, agents can accumulate information from multiple sources, that
can be categorized into two main types. One is information acquired through
direct interactions and receiving feedback from the task. For example, in
reinforcement learning such information includes visited states, accumulated
rewards, and performed actions. The other type is information provided by
external sources. Such information includes human advice [Najar and Chetouani,
2021], text description generated by large language models [Du et al., 2023,
Hu and Sadigh, 2023], and more. Figure 1 describes a general decision-making
task with external information. Resource allocation is an example of a task
that combines both types of information. In this task, our goal is to route a
process from a mobile device to a server while minimizing energy consumption
and execution time [Zuo and Joe-Wong, 2021]. In this task, we can accumulate
information directly by routing processes and receiving feedback. However, we
also have relevant information that can be obtained from other sources, such
as server specifications, load information, and more.

When we receive information from multiple sources, we can measure the total
information in bits. However, we assess the algorithm’s performance using
regret. Thus, a question arises:

What is the exact relationship between information bits and regret?

Figure 1: Schematic of general interactive decision-making with contextual
information task. Every round, a source of knowledge provides our agent with
information. The agent then makes a decision, that causes the task to generate
an observation and a reward. The observation is revealed to the agent, who
updates his next decision according to the past observations and the
information he received.

###  1.1 Contributions

#### New method for obtaining regret lower bounds.

We introduce a novel information-theoretic method to obtain regret lower
bounds for a wide variety of interactive decision-making problems. This method
uses Fano’s inequality [Cover, 1999] and the construction method introduced by
Yang and Barron [1999] to lower bound the worst-case Bayesian regret. We then
use this method to derive lower bounds for multi-armed bandits, contextual
bandits, and reinforcement learning tasks. This method allows us to lower-
bound both the Bayesian and frequentist regret.

#### Information-theoretic prior-dependent lower bounds

can be obtained using this method. We consider an interactive decision-making
framework that describes general online tasks with contextual information in a
Bayesian setting. We examine the regret of policies with a mutual information
constraint and obtain Bayesian regret lower bounds that depend on the entropy
of our prior. These bounds also show that both Thompson sampling [Russo and
Van Roy, 2016] and information-directed sampling (IDS) [Russo and Van Roy,
2014] are nearly optimal in the Bayesian sense for multi-armed and linear
bandits.

#### Regret-information trade-off.

We use the lower bounds to quantify the relationship between information,
measured in bits, and regret. We show that the presented lower bound, combined
with existing upper bounds, quantifies the relationship between external
information and regret. Furthermore, these bounds quantify the relationship
between information accumulation and regret in online tasks. Finally, we
utilize the trade-off in a question-answering task with large language models,
demonstrating how we can easily utilize this trade-off in online settings.

##  2 Setting and Preliminaries

We introduce a new setting called interactive decision-making in Bayesian
environments, with contextual information. This setting is a Bayesian
adaptation of the frequentist interactive decision-making setting introduced
by Foster et al. [2021]. We denote the set of Borel probability measures over
a locally compact space by $\Delta(\cdot)$. Let $\Pi$ be a compact decision
space and $\mathcal{M}$ be a compact class of models, where each model
$M\in\mathcal{M}$ is a mapping from the decision space to an observation space
$\mathcal{O}$, i.e., $M:\Pi\to\mathcal{O}$. Furthermore, every model $M$ has a
reward function, $R_{M}:\Pi\to\Delta([0,1])$ that maps every decision to a
reward distribution over $[0,1]$. $\mathcal{C}$ is another compact space
called the context space. A task in this setting is defined by the decision
space $\Pi$, the model class $\mathcal{M}$, the context space $\mathcal{C}$,
and the prior $P\in\Delta(\mathcal{M}\otimes\mathcal{C})$. We denote by
$\mu_{M}(\pi)=\mathbb{E}_{x\sim R_{M}(\pi)}[x]$ the mean reward of decision
$\pi$ under model $M$. With a slight abuse of notation, we also denote by
$\mu_{M}(\phi)=\mathbb{E}_{\pi\sim\phi}[\mu_{M}(\pi)]$, the mean reward of a
policy $\phi\in\Delta(\Pi)$ under model $M$.

In a $T$-round game, a random model and context $(M_{t},C_{t})$ are sampled
every round, independently from previous rounds, according to the prior
probability $P$. Before each round starts, the context $C_{t}$ is revealed to
the agent, who determines his policy $p_{t}\in\Delta(\Pi)$ according to the
context and the observed history. Then, a decision $\pi_{t}\sim p_{t}$ is
sampled and an observation $O_{t}\sim M_{t}(\pi_{t})$ is revealed to the
agent. A reward, $r_{t}\sim R_{M_{t}}(\pi_{t})$ is also generated. We denote
the history up to time $t$ as
$\mathcal{H}_{t}=\\{C_{i},\pi_{i},O_{i}\\}_{i=1}^{t}$. We measure the
performance with respect to the best context-dependent decision in hindsight.
This performance metric is called the Bayesian regret and is defined by

$\mathcal{BR}_{P}(T;\\{\pi_{t}\\}_{t=1}^{T})=\sup_{\pi^{*}:\mathcal{C}\to\Pi}\mathbb{E}\left[\sum_{t=1}^{T}\left(R_{M_{t}}(\pi^{*}({c_{t}}))-R_{M_{t}}(\pi_{t})\right)\right]$

where the expectation is taken with respect to the randomness in decisions,
observations, and rewards ($(M_{t},C_{t})\sim P$, $\pi_{t}\sim p_{t}$ and
$r_{t}\sim R_{M_{t}}(\pi_{t})$). We also note that by fixing a single context,
$\left|\mathcal{C}\right|=1$, the setting reduces to regular Bayesian
interactive decision-making. When obvious from the context, $P$ and
$\\{\pi_{t}\\}_{t=1}^{T}$ are omitted. We now show how our setting covers
common decision-making tasks with contextual information.

######  Example 2.1 (Contextual multi-armed bandit with Bernoulli rewards).

We demonstrate how our general framework reduces to the contextual MAB
problem, where the rewards for each arm are Bernoulli random variables. Assume
a finite set of decisions, which are called arms in this setting,
$\Pi=\\{1,2,\dots,A\\}$. Furthermore, assume that the context space is finite
as well, $\mathcal{C}=\\{1,2,\dots,C\\}$. The model class is then given by
$\mathcal{M}=\\{f|f:\Pi\times\mathcal{C}\to[0,1]\\}$, so every model maps
$\left(\pi,C\right)$ to $\mathrm{Bern}(f(\pi,C))$. At each round $t$, a model
and context are sampled $(M_{t},C_{t})\sim P$, and the context is revealed. A
decision $\pi_{t}$ is selected and the observation is the incurred reward,
$r_{t}=O_{t}\sim\mathrm{Bern}(f_{t}(\pi_{t},C_{t}))$.

######  Example 2.2 (Tabular reinforcement learning with a finite horizon).

We also demonstrate how our setting applies to a finite horizon MDP. We
consider a tabular MDP with a finite horizon, which is defined according to
the tuple $(\mathcal{S},\mathcal{A},\mathbb{P},\mathbb{R},H)$. We also assume
the episodic and stationary setting, where we update the policy only at the
beginning of every episode. Additionally, we assume that the reward of every
episode is bounded in $[0,1]$. In this setting, the decision space is all of
the deterministic policies, so
$\Pi=\\{\pi:\mathcal{S}\times\mathcal{H}\to\mathcal{A}\\}$. The model class
$\mathcal{M}$ is defined by the set of all MDPs with the same state space,
action set, and horizon. At every time step, the agent determines a policy and
plays it over the entire horizon. The observation is the trajectories, which
include the visited states, rewards, and actions performed.

#### Covering and packing

Assume a normed space $A$ with metric $d$ induced by the norm, and let
$\epsilon>0$. A set $F\subseteq A$ is called a covering set of $A$ if for all
$a\in A$, there exists $f\in F$ such that $d(a,f)\leq\epsilon$. The
$\epsilon$-covering number of $A$, denoted by $\mathcal{N}(d,A,\epsilon)$, is
the smallest cardinality possible for an $\epsilon$-covering set. A set
$G\subseteq A$ is called a packing set of $A$ if $\forall g_{1},g_{2}\in G$,
$d(g_{1},g_{2})\geq\epsilon$. The $\epsilon$-packing number of $A$ is the
largest possible cardinality for an $\epsilon$-packing set. We define an
$\epsilon$-local set of A as $B(b,\epsilon)=\\{a\in A:d(b,a)\leq\epsilon\\}$,
for every $b\in A$ and $\epsilon>0$. The local packing number, denoted by
$\mathcal{M}^{\mathrm{local}}\left(d,A,\epsilon\right)$, is the largest
$(\epsilon/2)$-packing set of any set $B(b,\epsilon)$, i.e.,

$\displaystyle\mathcal{M}^{\mathrm{local}}\left(d,A,\epsilon\right)=\max\left\\{M:\exists
b\text{ such that the }(\epsilon/2)\text{-packing number of
}B(b,\epsilon)\text{ is }M\right\\}.$

A set $E\subseteq A$ will be called an $\epsilon$-local packing set if
$\exists b$ such that $E$ is an $(\epsilon/2)$-packing set of $B(b,\epsilon)$
and $\left|E\right|=\mathcal{M}^{\mathrm{local}}\left(d,A,\epsilon\right)$.
When $d(x,y)=\left\|x-y\right\|_{p}$ we denote
$\mathcal{M}_{p}(A,\epsilon),\mathcal{N}_{p}(A,\epsilon)$ and
$\mathcal{M}^{\mathrm{local}}_{p}\left(A,\epsilon\right)$ for the
$\epsilon$-packing, $\epsilon$-covering and $\epsilon$-local packing number,
respectively.

#### Additional notations

We denote by $H(X)=\mathbb{E}\left[-\log Q(X)\right]$ the Shannon entropy of a
random variable $X\sim Q$, and with a slight abuse of notation also denote
$H(Q)=H(X)$. Given two jointly distributed random variables, $(X,Y)\sim Q$, we
denote their marginal distributions by $Q(x)$ and $Q(y)$. We also define the
mutual information of two jointly distributed random variables $(X,Y)\sim Q$
as $I(X;Y)=\mathbb{E}\left[\log\left(\frac{Q(X,Y)}{Q(X)Q(Y)}\right)\right]$.
The KL-divergence is defined as $D\left(P,Q\right)=\mathbb{E}_{X\sim
P}\log\frac{P(X)}{Q(X)}$ . Unless stated otherwise, logarithms are assumed to
be in base-2, denoted by $\log$. We also denote $x\gtrsim y$ if there is some
global constant $c>0$ such that $x\geq cy$.

Table 1: Lower bounds for MAB and RL problems, recovered with Theorem 3.5 and Proposition 4.3. Problem | Retrieved lower bound | Optimal?
---|---|---
MAB | $\Omega(\sqrt{KT})$ | Yes
Tabular, episodic and stationary MDP | $\Omega(\sqrt{HSKT})$ | Yes [Zhang et al., 2021]
Linear bandits | $\Omega(\sqrt{dT})$ | No
Lipschitz bandit | $\Omega\left(T^{\frac{d+1}{d+2}}\right)$ | Yes [Kleinberg et al., 2019]
Bayesian MAB | ${\Omega\left(\sqrt{AT\frac{I(\pi^{*};\mathcal{H}_{T})}{\log K}}\right)}$ | First bound
Bayesian contextual MAB | ${\Omega\left(\sqrt{CAT\frac{I(\pi^{*};\mathcal{H}_{T})}{\log K}}\right)}$ | First bound
Bayesian linear bandit | $\Omega\left(\sqrt{dT\frac{I(\pi^{*};\mathcal{H}_{T})}{\log K}}\right)$ | First bound

##  3 Regret Lower Bounds Using Fano’s Inequality

We now introduce a novel approach for obtaining worst-case Bayesian regret
lower bounds, which can be applied to a wide variety of interactive decision-
making tasks. This method can be viewed as an extension of Fano’s inequality
for non-exact recovery [Scarlett and Cevher, 2019] to online problems. We
define worst-case Bayesian regret in the following manner,

$\inf_{\\{\pi_{t}\\}_{t=1}^{T}}\sup_{\nu\in\Delta(\mathcal{M}\times\mathcal{C})}\mathcal{BR}_{\nu}(T;\\{\pi_{t}\\}_{t=1}^{T})\equiv\mathcal{BR}^{*}(T).$

To lower bound the worst-case Bayesian regret we use Fano’s inequality.

######  Theorem 3.1 (Fano’s inequality, Theorem 2.10 of [Cover, 1999]).

Let $X,Y\sim Q$ be two jointly distributed random variables, where $X$ can
take values over a finite set, whose cardinality is $\mathcal{X}$. Let
$\hat{X}=f(Y)$ for some $f$ be an estimator of $X$. Then the following holds
for all $f$,

$\mathbb{P}(X\neq\hat{X})\geq 1-\frac{I(X;Y)+1}{\log\mathcal{X}}.$ (1)

Fano’s inequality can be used to lower-bound the error in hypothesis testing
problems. Thus, to utilize Fano’s inequality, we need to reduce our problem
from regret minimization to hypothesis testing. We assume access to some set
$\Phi=\\{\phi_{1},\dots,\phi_{K}\\}$ of (possibly stochastic) decisions such
that for some $\epsilon>0$, $\mathbb{E}_{M\sim
P}[\left|\mu_{M}(\phi_{i})-\mu_{M}(\phi_{j})\right|]\geq\epsilon$, for all
$i\neq j$. From Markov’s inequality, we have that for any
$\phi\in\Delta(\Pi)$,

$\sup_{i}\mathbb{E}_{M\sim
P}[\left|\mu_{M}(\phi_{i})-\mu_{M}(\phi)\right|]\geq\epsilon\sup_{i}\mathbb{P}\left(\left|\mu_{M}(\phi_{i})-\mu_{M}(\phi)\right|\geq\epsilon\right).$
(2)

Now, instead of lower-bounding the regret, we lower-bound the error
probability. This reduces our problem from regret minimization to hypothesis
testing. We also assume that a metric $\rho$ exists such that
$\mathbb{E}[\left|\mu_{M}(\psi)-\mu_{M}(\phi)\right|]\geq\rho(\phi,\psi)$ for
all $\psi,\phi\in\Delta(\Pi)$. Using Theorem 3.1, we can lower-bound the
prediction error. This results in the following proposition.

######  Proposition 3.2.

For any algorithm, prior $P$, a decision set
$\Phi_{K}=\\{\phi_{1},\dots,\phi_{K}\\}\subseteq\Delta(\Pi)$ and for all
$\epsilon>0$ such that $\rho(\phi_{i},\phi_{j})\geq\epsilon$ for all $i\neq
j$,

$\displaystyle\frac{\mathcal{BR}_{P}(T)}{T\epsilon}\geq
1-\frac{I(V;\mathcal{H}_{T})+1}{\log K}$ (3)

where $V$ is the index of the best decision in hindsight from the set $\Phi$.

Proposition 3.2 allows us to lower-bound the Bayesian regret using a specific
set of decisions. We suggest a method for selecting the decision set $\Phi$,
which provides a general approach for obtaining regret lower bounds. We divide
our analysis into finite, parametric with infinite decisions, and non-
parametric decision spaces. To make the lower bound in Equation 3 tighter, we
should select the largest value of $K$ that satisfies the requirements for a
given $\epsilon>0$. Thus, for finite decision spaces, we choose $\Phi$ to be
an $\epsilon$-local packing set of the decision simplex, $\Delta(\Pi)$,
according to $\rho$, under $P$. Thus, we have
$K={\mathcal{M}}^{\mathrm{loc}}(\rho,\Delta(\Pi),\epsilon)$. Similarly, for
parametric decision spaces with infinite decisions, we choose $\Phi$ to be an
$\epsilon$-local packing set of the decision set, $\Pi$, i.e.,
$K={\mathcal{M}}^{\mathrm{loc}}(\rho,\Pi,\epsilon)$. Yang and Barron [1999]
have obtained a relationship between the local and global packing numbers,
which we state in Lemma 3.3.

######  Lemma 3.3 (Lemma 3 of Yang and Barron [1999]).

For any space $A$ with metric $d$ and for all $\epsilon>0$,

$\log{\mathcal{M}}\left(d,A,\frac{\epsilon}{2}\right)-\log{\mathcal{M}}(d,A,\epsilon)\leq\log{\mathcal{M}}^{\mathrm{loc}}(d,A,\epsilon).$

For non-parametric decision spaces, we use an $\epsilon$-global packing set of
our decision space $\Pi$, which means that $K=\mathcal{M}(\rho,\Pi,\epsilon)$.
After selecting $\Phi$, we need to handle $I(V;\mathcal{H}_{T})$. This can be
achieved using the following theorem.

######  Theorem 3.4 (Yang and Barron [1999]).

Under the assumptions and notations of Proposition 3.2, if $\Pi$ is a
parametric decision space then

$I(V;\mathcal{H}_{T})\lesssim 2\epsilon^{2}T.$

If $\Pi$ is a non-parametric decision space then

$I(V;\mathcal{H}_{T})\leq\inf_{\delta>0}\left(\log\mathcal{N}_{2}\left(\Pi,\sqrt{\delta}\right)+T\delta\right).$

Theorem 3.4 allows us to obtain upper bounds for the mutual information.
Furthermore, it provides us with a relationship between the global and local
packing numbers. Combining Theorem 3.4, Proposition 3.2 and the selection of
$\Phi$, results in the following Proposition.

######  Theorem 3.5.

Let there be a Bayesian interactive decision-making problem as defined in
Section 2, and let $\epsilon>0$. If $\Pi$ is a finite decision space,

$\frac{\mathcal{BR}^{*}(T)}{T\epsilon}\gtrsim
1-\frac{2\epsilon^{2}T+1}{\log\mathcal{M}(\rho,\Delta(\Pi),\epsilon/2)-\log\mathcal{M}(\rho,\Delta(\Pi),\epsilon)}.$
(4)

If $\Pi$ is an infinite parametric decision space,

$\frac{\mathcal{BR}^{*}(T)}{T\epsilon}\gtrsim
1-\frac{2\epsilon^{2}T+1}{\log\mathcal{M}(\rho,\Pi,\epsilon/2)-\log\mathcal{M}(\rho,\Pi,\epsilon)}.$
(5)

If $\Pi$ is a non-parametric decision space,

$\frac{\mathcal{BR}^{*}(T)}{T\epsilon}\geq
1-\frac{\inf_{\delta>0}\left(\log\mathcal{N}_{2}\left(\Pi,\sqrt{\delta}\right)+T\delta\right)+1}{\log\mathcal{M}(\rho,\Pi,\epsilon)}.$
(6)

To obtain regret lower bounds, all we need are the values of the packing and
covering numbers of the decision space. Then, we simply need to select a value
of $\epsilon$ such that the left-hand side of Equations 4, 5 or 6 is
$\frac{1}{2}$ (or any other positive constant). In Appendix C we demonstrate
this, by deriving regret lower bounds for several known online problems, which
are summarized in Table 1. Moreover, this method can be used to obtain lower
bounds for the frequentist regret, due to the mini-max theorem, which states
that the worst-case Bayesian regret is equal to the mini-max frequentist
regret [Lattimore and Szepesvári, 2019]. More detailed proofs and explanations
are provided in Appendix C.

##  4 Information Theoretic Bayesian Regret Lower Bounds

Russo and Van Roy [2014, 2016] showed that the regret of Thompson sampling and
IDS can be upper bounded by the mutual information.

######  Theorem 4.1 (Propositions 2,4 of [Russo and Van Roy, 2014] and
Propositions 1,5 of [Russo and Van Roy, 2016])).

In the multi-armed bandit with $K$ arms setting, the regret of Thompson
sampling and information-directed sampling can be upper bounded by
$O(\sqrt{KTI(\pi^{*};\mathcal{H}_{T})})$. Furthermore, if the rewards are a
linear function of the decisions, and the decisions are vectors in
$\mathbb{R}^{d}$, then the regret is upper bounded by
$O\left(\sqrt{dTI(\pi^{*};\mathcal{H}_{T})}\right)$.

Intuitively, in information-theoretic terms, mutual information quantifies the
amount of information one random variable contains about another one [Cover,
1999]. This means that mutual information can be utilized to measure the
information that is aggregated from various sources using a common measure of
bits. Theorem 4.1 shows that we can upper bound the regret when provided with
an upper bound for that number of bits. We can now ask the converse question:
What is the lower bound of the worst-case Bayesian regret, given
$I(\pi^{*};\mathcal{H}_{T})\leq R$? The following proposition answers this
question, for problems with a finite decision space.

######  Proposition 4.2.

Let $R\leq H(\pi^{*})$ be given. Assume that the Bayesian decision problem has
a finite decision space of size $K$, such that $I(\pi^{*};\mathcal{H}_{T})\leq
R$. Then the worst-case Bayesian regret can be lower bounded by
$\Omega\left(\sqrt{TK\frac{R}{\log K}}\right)$. If $\
\Pi\subset\mathbb{B}_{2}^{d}$ and the rewards are a linear function of the
decisions, then the worst-case Bayesian regret can be lower bounded by
$\Omega\left(\sqrt{Td\frac{R}{\log K}}\right)$.

The proof of Proposition 4.2 utilizes Lemma D.3. This lemma introduces an
upper bound for the mutual information, similar to Theorem 3.4, that takes
into account the constraint. The rest of the proof follows a similar structure
to the proof of Theorem 3.5, substituting the tighter bound into Equation 4.
This yields the following Proposition.

######  Proposition 4.3.

Let $R\leq H(\pi^{*})$ be given. Assume that the Bayesian decision problem has
a finite decision space of size $K$, such that $I(\pi^{*};\mathcal{H}_{T})\leq
R$. Then,

$\frac{\mathcal{BR}^{*}(T)}{T\epsilon}\gtrsim
1-\frac{2\epsilon^{2}T\frac{R}{\log
K}+1}{\log\mathcal{M}_{1}(\Delta(\Pi),\epsilon/2)-\log\mathcal{M}_{1}(\Delta(\Pi),\epsilon)}$
(7)

The rest of the proof follows by selecting the appropriate value of
$\epsilon$. Detailed proofs are found in Appendix D. Now, we can quantify the
relationship between information and regret using Theorem 4.1 and Proposition
4.2. Proposition 4.2 states that when more bits of information can be
accumulated, due to the properties of the environment or the agent, more
regret will be suffered. We now consider two agents in a contextual MAB
environment, with $K$ arms. The first agent ignores the contextual information
and plays each context independently. Thus, for this agent, the mutual
information between the optimal policy $\pi^{*}$ and the history
$\mathcal{H}_{T}$ is $I_{1}(\pi^{*};\mathcal{H}_{T})\leq\log K$. The second
agent utilizes the information in an efficient manner, which reduces the
uncertainty in the optimal arm, leading to $I_{2}(\pi^{*};\mathcal{H}_{T})\leq
1$. The amount of contextual information provided is
$\log\left(\frac{K}{2}\right)$ bits. From Proposition 4.2 and Theorem 4.1 we
know that the optimal behavior of the regret is
$\Theta\left(\sqrt{TI(\pi^{*};\mathcal{H}_{T}})\right)$ (omitting terms that
depend on the size of the decision space). Thus, the regret of the first agent
is $\sqrt{T\log K}$ while for the second one, it is $\sqrt{T}$. Thus,
$\log\left(\frac{K}{2}\right)$ bits of external information can be traded with
$\sqrt{T}\left(\sqrt{\log K}-1\right)$ regret.

(a) Bayesian regret

(b) Accumulated information

Figure 2: (a) The Bayesian regret and (b) the accumulated information in bits
for Thompson sampling under three different priors over the same bandit
structure. The entropy of each prior is described in the legend. The shadowed
areas correspond to 2-sigma error bars.

We can also quantify the relationship between information accumulation and
regret. Suppose we have two algorithms in the MAB setting, with 16 arms and a
prior such that $H(\pi^{*})=4$. During the first 10 episodes, one algorithm
accumulates 2 bits of information, while the other accumulates a single bit.
In the subsequent 100 episodes, both algorithms accumulate the remaining bits.
Since the first algorithm accumulated 2 bits initially, it suffers a regret of
$\sqrt{200}$ in these 100 episodes. The second algorithm suffers a regret of
$\sqrt{300}$ since it needs to accumulate 3 additional bits. Thus, the second
algorithm suffers more regret, even though both accumulate the same number of
bits by the end.

##  5 Experiments

###  5.1 Stochastic Bayesian bandit

We begin by demonstrating the trade-off in a simple Bayesian MAB problem. In
this problem, our model space contains $K$ possible models. The decision space
of the problem also contains $K$ decisions, which are called arms. The mean of
all arms in every model is $0.5(1-\varepsilon)$, except for one arm for which
the mean is $0.5(1+\varepsilon)$. The optimal arm is different for every
model. The reward of each arm is Bernoulli distributed. We also fix
$K=8,\varepsilon=0.1$. We choose this setting since all of the problems have
the same structure. Thus, any difference in regret stems from differences in
the prior. In the first experiment, we compare the Bayesian regret obtained by
Thompson sampling with different priors for every problem. This experiment
allows us to isolate the effect of the total bits on the regret. Results are
presented in Figure 2. We see that when fewer bits of information can be
accumulated, fewer regret is suffered.

The next experiment is performed under the same setting. Now we assume a
uniform prior and compare three different bandit algorithms - EXP3 [Lattimore
and Szepesvári, 2020], APS [Xu and Zeevi, 2023], and Thompson sampling
[Thompson, 1933]. We also estimate the bits of accumulated information for
each algorithm. Results are presented in Figure 3. We can now see how
measuring the accumulated bits of information also quantifies the relationship
in regret between different bandit algorithms. Additional experimental details
are provided in Appendix E.

(a) Bayesian regret

(b) Accumulated information

Figure 3: (a) The Bayesian regret and (b) the accumulated information in bits
for three different bandit algorithms, under the same bandit structure and a
uniform prior. The bandit algorithms used are described in the legend. The
shadowed areas correspond to 2-sigma error bars.

###  5.2 Question Answering with Large Language Models

In the following experiment, we show how the regret-information trade-off can
be utilized in a practical setting. We consider a sequential multiple choice
question-answering (MCQA) task, where every round we need to provide an answer
for a question, out of four possible answers. We also have access to two large
language models (LLM), where one has significantly more parameters than the
other. Every turn we need to choose which LLM should answer the question. As
contextual information, every round we are provided with the question,
possible answers, and the output of the small LLM for the given prompt. We
receive a positive reward of 1 for answering the question correctly. If we
choose to deploy the large LLM we incur a negative reward of 0.1. Our goal is
to minimize the accumulated regret.

Since the LLM outputs a probability distribution over tokens, we can measure
the information the small LLM will gain after answering the question, in bits.
We prompt the small LLM with the question and possible answers, which returns
scores for each token. We take the scores corresponding only for the tokens
[A, B, C, D], each corresponding to a different answer, and use them to get a
distribution over these tokens. The number of information bits is the KL
divergence between this distribution and the uniform one. Now we create a
bits-based policy, which deploys the large LLM only if the mutual information
is below some threshold. This policy queries the large LLM only when a
substantial amount of bits can be acquired. We compare the mean regret over a
horizon of 200 steps between this policy, and one that randomly selects which
LLM to use. The selected threshold value for the bits-based policy also
ensures that we query the large LLM the same number of times as the random
policy.

We run the experiment described above with the following specifications. To
generate the multiple-choice questions, we used the MMLU dataset, which
contains multiple-choice questions in a variety of topics, such as algebra,
business, etc. [Hendrycks et al., 2021a, b].

Table 2: Mean regret for both policies for a horizon of 200 episodes, under different deployment percentages of the large LLM. The left column denotes the percentage of queries to the large LLM. We report the standard error of the mean. % Large LLM | Bits-based | Random
---|---|---
$50\%$ | $\mathbf{30.1\pm 0.5}$ | $32.5\pm 0.2$
$70\%$ | $\mathbf{22.7\pm 0.5}$ | $24.8\pm 0.1$
$90\%$ | $\mathbf{15.5\pm 0.3}$ | $17.1\pm 0.2$
Figure 4: Regret of random and bits-based selection in the MCQA with LLMs
task. The random and bits-based policies were allowed to use the large LLM for
only 90% of the episodes. Both policies were evaluated across 10 different
seeds, with the same questions. The shadowed areas correspond to 2-sigma error
bars.

200 questions were randomly selected in advance, which we used to evaluate
both agents with 10 different seeds while maintaining the same questions and
order. We then repeated this process for 10 different randomly generated sets
of questions. We used Mistral 7B Jiang et al. [2023] for the small LLM, and
Mixtral 7Bx8 [Jiang et al., 2024] for the large one. For both models, 4-bit
quantization [Dettmers and Zettlemoyer, 2023] and flash attention Dao et al.
[2022] were applied. Figure 4 compares the random and the bits-based policy
for one randomly generated set of questions. Table 2 describes the mean regret
of every policy under a different number of large LLM deployments. From the
results, we see that deciding whether to query the large LLM or not using bits
is better than random selection. Furthermore, this improvement becomes more
significant as we increase the number of deployments allowed. This
demonstrates how we can easily utilize the quantification of information in
bits in online settings. Additional details are provided in Appendix E. Code
is available at https://github.com/itaishufaro/bitsandbandits.

##  6 Related Work

#### Bayesian setting:

In the Bayesian setting, prior information is assumed to be expressed as a
probability distribution, called the prior. New information is then
incorporated using Bayesian inference to update the prior probability,
resulting in a posterior distribution. Bayesian algorithms have been
extensively studied in multiple online decision-making problems such as multi-
armed bandits [Russo and Van Roy, 2014, Kaufmann et al., 2012] and
reinforcement learning [Guez et al., 2012, Ghavamzadeh et al., 2016]. Upper
bounds for Bayesian algorithms have been proved for both the frequentist
[Kaufmann et al., 2011] and Bayesian settings [Russo and Van Roy, 2014, 2016].
Prior dependent regret bounds for Bayesian algorithms have also been studied
[Bubeck and Liu, 2013, Russo and Van Roy, 2014]. Previous studies have
explored prior-dependent lower bounds for Bayesian regret, but these are
constrained to specific forms of priors, such as Gaussian priors [Atsidakou et
al., 2024].

#### Contextual information:

In the contextual setting, information is revealed to the agent before every
round, which can be leveraged to minimize regret. This framework has gathered
attention within both the bandit [Bietti et al., 2021] and reinforcement
learning frameworks [Klink et al., 2020, Modi and Tewari, 2020]. The contexts
can be selected arbitrarily by an adversary [Beygelzimer et al., 2011, Chu et
al., 2011] or generated from some prior probability distribution, similarly to
the Bayesian setting [Hao et al., 2020, May et al., 2012]. Bayesian algorithms
have also been adapted to the arbitrary context setting [Agrawal and Goyal,
2013]. Furthermore, the type of information provided to the learner can expand
beyond the contextual information provided directly [Schneider and Zimmert,
2024]. Our work introduces a contextual Bayesian setting framework that covers
a wide variety of interactive decision-making tasks.

#### Information-theoretic methods

have been employed to derive upper bounds for various online tasks. Russo and
Van Roy [2016] introduced an information-theoretic method for establishing
Bayesian regret upper bound for Thompson sampling in the multi-armed bandit
setting, which depends on the entropy of the prior. This approach was also
used to design new Bayesian algorithms that utilize mutual information called
information-directed sampling (IDS) [Russo and Van Roy, 2014]. IDS and the
information-theoretic method it utilizes were also extended to other tasks
such as contextual bandits [Neu et al., 2022], sparse linear bandits [Hao et
al., 2021], non-stationary bandits [Min and Russo, 2023, Liu et al., 2023],
reinforcement learning [Lu and Van Roy, 2019], non-linear control [Kakade et
al., 2020], partial monitoring [Lattimore and Szepesvári, 2019], and other
online optimization problems [Liu et al., 2018, Dong et al., 2019, Lattimore
and Gyorgy, 2021, Russo and Van Roy, 2018]. The bounds presented in works such
as [Russo and Van Roy, 2016, 2014, Neu et al., 2022] are based on the upper
bounding of the information ratio. Our work uses a different approach, which
obtains nearly matching prior-dependent lower bounds for Thompson sampling and
information-directed sampling (IDS). Furthermore, these bounds can be applied
beyond the bandit setting. Seldin et al. [2011] used a different information-
theoretic method. They utilized PAC-Bayes bounds to obtain information-
theoretic upper bounds on the per-round regret, that depend on mutual
information.

##  7 Conclusion and Future Work

We introduce a general setting that embeds contextual information in a
Bayesian setting. We showed that the regret can be lower bounded by
$\Omega\left(\sqrt{TKI(\pi^{*};\mathcal{H}_{T})/\log K}\right)$. Combining
this result with known upper bounds, this quantifies the relationship between
a-priori external information and regret. Furthermore, in online settings
these bounds quantify the relationship between online information accumulation
and regret. We also utilized this trade-off in an MCQA task with LLMs,
demonstrating that the aforementioned quantification can be easily used in an
online setting.

The general setting we introduced is relevant not only to the bandit setting,
but also to general sequential decision problems. A central assumption in our
analysis is that exogenous information can be gathered regardless of the
process history. However, this assumption may be violated in general
sequential decision process where the action itself may have ramifications on
the quality, quantity and cost of the exogenous information.

Our work only covers the Bayesian setting, and our definition of the measure
of information relies on it. In other settings, such as adversarial learning
[Neu and Olkhovskaya, 2020] or frequentist settings. Finally, and importantly,
with the increasing prevalence of LLMs, and foundation models in general,
building solid foundations as well as practical algorithms for using prior
knowledge in sequential decision-making is an important research endeavor that
may be built upon the foundations that are laid in this paper.

## References

  * Lattimore and Szepesvári [2020] Tor Lattimore and Csaba Szepesvári.  _Bandit algorithms_.  Cambridge University Press, 2020.
  * Cesa-Bianchi et al. [2006] Nicolo Cesa-Bianchi, Gábor Lugosi, and Gilles Stoltz.  Regret minimization under partial monitoring.  _Mathematics of Operations Research_ , 31(3):562–580, 2006.
  * Najar and Chetouani [2021] Anis Najar and Mohamed Chetouani.  Reinforcement learning with human advice: a survey.  _Frontiers in Robotics and AI_ , 8:584075, 2021.
  * Du et al. [2023] Yuqing Du, Olivia Watkins, Zihan Wang, Cédric Colas, Trevor Darrell, Pieter Abbeel, Abhishek Gupta, and Jacob Andreas.  Guiding pretraining in reinforcement learning with large language models.  In _International Conference on Machine Learning_ , pages 8657–8677. PMLR, 2023.
  * Hu and Sadigh [2023] Hengyuan Hu and Dorsa Sadigh.  Language instructed reinforcement learning for human-ai coordination.  In _International Conference on Machine Learning_ , pages 13584–13598. PMLR, 2023.
  * Zuo and Joe-Wong [2021] Jinhang Zuo and Carlee Joe-Wong.  Combinatorial multi-armed bandits for resource allocation.  In _2021 55th Annual Conference on Information Sciences and Systems (CISS)_ , pages 1–4. IEEE, 2021.
  * Cover [1999] Thomas M Cover.  _Elements of information theory_.  John Wiley & Sons, 1999.
  * Yang and Barron [1999] Yuhong Yang and Andrew Barron.  Information-theoretic determination of minimax rates of convergence.  _Annals of Statistics_ , pages 1564–1599, 1999.
  * Russo and Van Roy [2016] Daniel Russo and Benjamin Van Roy.  An information-theoretic analysis of thompson sampling.  _Journal of Machine Learning Research_ , 17(68):1–30, 2016.
  * Russo and Van Roy [2014] Daniel Russo and Benjamin Van Roy.  Learning to optimize via information-directed sampling.  _Advances in Neural Information Processing Systems_ , 27, 2014.
  * Foster et al. [2021] Dylan J Foster, Sham M Kakade, Jian Qian, and Alexander Rakhlin.  The statistical complexity of interactive decision making.  _arXiv preprint arXiv:2112.13487_ , 2021.
  * Zhang et al. [2021] Zihan Zhang, Xiangyang Ji, and Simon Du.  Is reinforcement learning more difficult than bandits? a near-optimal algorithm escaping the curse of horizon.  In _Conference on Learning Theory_ , pages 4528–4531. PMLR, 2021.
  * Kleinberg et al. [2019] Robert Kleinberg, Aleksandrs Slivkins, and Eli Upfal.  Bandits and experts in metric spaces.  _Journal of the ACM (JACM)_ , 66(4):1–77, 2019.
  * Scarlett and Cevher [2019] Jonathan Scarlett and Volkan Cevher.  An introductory guide to fano’s inequality with applications in statistical estimation.  _arXiv preprint arXiv:1901.00555_ , 2019.
  * Lattimore and Szepesvári [2019] Tor Lattimore and Csaba Szepesvári.  An information-theoretic approach to minimax regret in partial monitoring.  In _Conference on Learning Theory_ , pages 2111–2139. PMLR, 2019.
  * Xu and Zeevi [2023] Yunbei Xu and Assaf Zeevi.  Bayesian design principles for frequentist sequential learning.  In _International Conference on Machine Learning_ , pages 38768–38800. PMLR, 2023.
  * Thompson [1933] William R Thompson.  On the likelihood that one unknown probability exceeds another in view of the evidence of two samples.  _Biometrika_ , 25(3-4):285–294, 1933.
  * Hendrycks et al. [2021a] Dan Hendrycks, Collin Burns, Steven Basart, Andy Zou, Mantas Mazeika, Dawn Song, and Jacob Steinhardt.  Measuring massive multitask language understanding.  _Proceedings of the International Conference on Learning Representations (ICLR)_ , 2021a.
  * Hendrycks et al. [2021b] Dan Hendrycks, Collin Burns, Steven Basart, Andrew Critch, Jerry Li, Dawn Song, and Jacob Steinhardt.  Aligning ai with shared human values.  _Proceedings of the International Conference on Learning Representations (ICLR)_ , 2021b.
  * Jiang et al. [2023] Albert Q. Jiang, Alexandre Sablayrolles, Arthur Mensch, Chris Bamford, Devendra Singh Chaplot, Diego de las Casas, Florian Bressand, Gianna Lengyel, Guillaume Lample, Lucile Saulnier, Lélio Renard Lavaud, Marie-Anne Lachaux, Pierre Stock, Teven Le Scao, Thibaut Lavril, Thomas Wang, Timothée Lacroix, and William El Sayed.  Mistral 7b, 2023.
  * Jiang et al. [2024] Albert Q. Jiang, Alexandre Sablayrolles, Antoine Roux, Arthur Mensch, Blanche Savary, Chris Bamford, Devendra Singh Chaplot, Diego de las Casas, Emma Bou Hanna, Florian Bressand, Gianna Lengyel, Guillaume Bour, Guillaume Lample, Lélio Renard Lavaud, Lucile Saulnier, Marie-Anne Lachaux, Pierre Stock, Sandeep Subramanian, Sophia Yang, Szymon Antoniak, Teven Le Scao, Théophile Gervet, Thibaut Lavril, Thomas Wang, Timothée Lacroix, and William El Sayed.  Mixtral of experts, 2024.
  * Dettmers and Zettlemoyer [2023] Tim Dettmers and Luke Zettlemoyer.  The case for 4-bit precision: k-bit inference scaling laws.  In _International Conference on Machine Learning_ , pages 7750–7774. PMLR, 2023.
  * Dao et al. [2022] Tri Dao, Dan Fu, Stefano Ermon, Atri Rudra, and Christopher Ré.  Flashattention: Fast and memory-efficient exact attention with io-awareness.  _Advances in Neural Information Processing Systems_ , 35:16344–16359, 2022.
  * Kaufmann et al. [2012] Emilie Kaufmann, Olivier Cappé, and Aurélien Garivier.  On bayesian upper confidence bounds for bandit problems.  In _Artificial intelligence and statistics_ , pages 592–600. PMLR, 2012.
  * Guez et al. [2012] Arthur Guez, David Silver, and Peter Dayan.  Efficient bayes-adaptive reinforcement learning using sample-based search.  _Advances in neural information processing systems_ , 25, 2012.
  * Ghavamzadeh et al. [2016] Mohammad Ghavamzadeh, Yaakov Engel, and Michal Valko.  Bayesian policy gradient and actor-critic algorithms.  _Journal of Machine Learning Research_ , 17(66):1–53, 2016.
  * Kaufmann et al. [2011] Emilie Kaufmann, Olivier Cappé, and Aurélien Garivier.  On the efficiency of bayesian bandit algorithms from a frequentist point of view.  In _Neural Information Processing Systems (NIPS)_. Curran Associates Red Hook, NY, 2011.
  * Bubeck and Liu [2013] Sébastien Bubeck and Che-Yu Liu.  Prior-free and prior-dependent regret bounds for thompson sampling.  _Advances in neural information processing systems_ , 26, 2013.
  * Atsidakou et al. [2024] Alexia Atsidakou, Branislav Kveton, Sumeet Katariya, Constantine Caramanis, and Sujay Sanghavi.  Logarithmic bayes regret bounds.  _Advances in Neural Information Processing Systems_ , 36, 2024.
  * Bietti et al. [2021] Alberto Bietti, Alekh Agarwal, and John Langford.  A contextual bandit bake-off.  _Journal of Machine Learning Research_ , 22(133):1–49, 2021.
  * Klink et al. [2020] Pascal Klink, Hany Abdulsamad, Boris Belousov, and Jan Peters.  Self-paced contextual reinforcement learning.  In _Conference on Robot Learning_ , pages 513–529. PMLR, 2020.
  * Modi and Tewari [2020] Aditya Modi and Ambuj Tewari.  No-regret exploration in contextual reinforcement learning.  In _Conference on Uncertainty in Artificial Intelligence_ , pages 829–838. PMLR, 2020.
  * Beygelzimer et al. [2011] Alina Beygelzimer, John Langford, Lihong Li, Lev Reyzin, and Robert Schapire.  Contextual bandit algorithms with supervised learning guarantees.  In _Proceedings of the Fourteenth International Conference on Artificial Intelligence and Statistics_ , pages 19–26. JMLR Workshop and Conference Proceedings, 2011.
  * Chu et al. [2011] Wei Chu, Lihong Li, Lev Reyzin, and Robert Schapire.  Contextual bandits with linear payoff functions.  In _Proceedings of the Fourteenth International Conference on Artificial Intelligence and Statistics_ , pages 208–214. JMLR Workshop and Conference Proceedings, 2011.
  * Hao et al. [2020] Botao Hao, Tor Lattimore, and Csaba Szepesvari.  Adaptive exploration in linear contextual bandit.  In _International Conference on Artificial Intelligence and Statistics_ , pages 3536–3545. PMLR, 2020.
  * May et al. [2012] Benedict C May, Nathan Korda, Anthony Lee, David S Leslie, and Nicolo Cesa-Bianchi.  Optimistic bayesian sampling in contextual-bandit problems.  _Journal of Machine Learning Research_ , 13(6), 2012.
  * Agrawal and Goyal [2013] Shipra Agrawal and Navin Goyal.  Thompson sampling for contextual bandits with linear payoffs.  In _International conference on machine learning_ , pages 127–135. PMLR, 2013.
  * Schneider and Zimmert [2024] Jon Schneider and Julian Zimmert.  Optimal cross-learning for contextual bandits with unknown context distributions.  _Advances in Neural Information Processing Systems_ , 36, 2024.
  * Neu et al. [2022] Gergely Neu, Iuliia Olkhovskaia, Matteo Papini, and Ludovic Schwartz.  Lifting the information ratio: An information-theoretic analysis of thompson sampling for contextual bandits.  _Advances in Neural Information Processing Systems_ , 35:9486–9498, 2022.
  * Hao et al. [2021] Botao Hao, Tor Lattimore, and Wei Deng.  Information directed sampling for sparse linear bandits.  _Advances in Neural Information Processing Systems_ , 34:16738–16750, 2021.
  * Min and Russo [2023] Seungki Min and Daniel Russo.  An information-theoretic analysis of nonstationary bandit learning.  In _International Conference on Machine Learning_ , pages 24831–24849. PMLR, 2023.
  * Liu et al. [2023] Yueyang Liu, Benjamin Van Roy, and Kuang Xu.  Nonstationary bandit learning via predictive sampling.  In _International Conference on Artificial Intelligence and Statistics_ , pages 6215–6244. PMLR, 2023.
  * Lu and Van Roy [2019] Xiuyuan Lu and Benjamin Van Roy.  Information-theoretic confidence bounds for reinforcement learning.  _Advances in Neural Information Processing Systems_ , 32, 2019.
  * Kakade et al. [2020] Sham Kakade, Akshay Krishnamurthy, Kendall Lowrey, Motoya Ohnishi, and Wen Sun.  Information theoretic regret bounds for online nonlinear control.  _Advances in Neural Information Processing Systems_ , 33:15312–15325, 2020.
  * Liu et al. [2018] Fang Liu, Swapna Buccapatnam, and Ness Shroff.  Information directed sampling for stochastic bandits with graph feedback.  In _Proceedings of the AAAI Conference on Artificial Intelligence_ , volume 32, 2018.
  * Dong et al. [2019] Shi Dong, Tengyu Ma, and Benjamin Van Roy.  On the performance of thompson sampling on logistic bandits.  In _Conference on Learning Theory_ , pages 1158–1160. PMLR, 2019.
  * Lattimore and Gyorgy [2021] Tor Lattimore and Andras Gyorgy.  Mirror descent and the information ratio.  In _Conference on Learning Theory_ , pages 2965–2992. PMLR, 2021.
  * Russo and Van Roy [2018] Daniel Russo and Benjamin Van Roy.  Satisficing in time-sensitive bandit learning.  _arXiv preprint arXiv:1803.02855_ , 2018.
  * Seldin et al. [2011] Yevgeny Seldin, Peter Auer, John Shawe-taylor, Ronald Ortner, and François Laviolette.  Pac-bayesian analysis of contextual bandits.  _Advances in neural information processing systems_ , 24, 2011.
  * Neu and Olkhovskaya [2020] Gergely Neu and Julia Olkhovskaya.  Efficient and robust algorithms for adversarial linear contextual bandits.  In _Conference on Learning Theory_ , pages 3049–3068. PMLR, 2020.
  * Wu [2020] Yihong Wu.  Information-theoretic methods for high-dimensional statistics.  _Lecture notes, Yale University, New Haven, CT_ , 2020.
  * Gottlieb et al. [2017] Lee-Ad Gottlieb, Aryeh Kontorovich, and Robert Krauthgamer.  Efficient regression in metric spaces via approximate lipschitz extension.  _IEEE Transactions on Information Theory_ , 63(8):4838–4849, 2017.
  * Iacono and Boyd [2017] Roberto Iacono and John P Boyd.  New approximations to the principal real-valued branch of the lambert w-function.  _Advances in Computational Mathematics_ , 43:1403–1436, 2017.

##  Appendix A Table of Notations

Table 3: Commonly used notations throughout the paper and the appendix. Notations | Description
---|---
$\Pi$ | The decision space.
$\mathcal{M}$ | The model class.
$\mathcal{O}$ | The observation space.
$\mathcal{C}$ | The context space.
$\pi$ | A decision.
$R_{M}(\pi)$ | reward distribution according to decision $\pi$ on model $M$.
$\mu_{M}(\pi)$ | mean reward according to decision $\pi$ on model $M$.
$P$ | Prior probability of the task.
$\pi^{*}_{M}$ | The optimal decision for a model $M$.
$\mathcal{H}_{t}$ | The total accumulated history up to round $t$
| (including observations and contexts).
$p_{t}$ | Policy selected at round $t$.
$r_{t}$ | Reward sampled at time $t$.
$\rho$ | A norm that lower bounds the difference in reward means.

##  Appendix B Useful Properties of Covering Numbers

######  Definition B.1 (Covering and packing numbers).

Let $H$ be a normed space, and let $d(\cdot,\cdot)$ be the metric induced by
the norm. Let $\epsilon>0$.

  * •

A set $C\subset H$ is said to be a covering set of $H$ if for all $h\in H$
there is $c\in C$ such that $d(h,c)\leq\epsilon$.

  * •

The covering number is defined as

$\mathcal{M}(d,\epsilon,H)=\max\left\\{m:\exists C,\left|C\right|=m\text{ and
$C$ is a covering set of $H$}\right\\}.$

If $d(x,y)=\left\|x-y\right\|_{p}$, we denote it by
$\mathcal{M}_{p}(\epsilon,H)$.

  * •

A set $C\subset H$ is said to be a packing set of $H$ if for all $h\in H$
there is $c\in C$ such that $d(h,c)\geq\epsilon$.

  * •

The packing number is defined as

$\mathcal{N}(d,\epsilon,H)=\min\left\\{m:\exists C,\left|C\right|=m\text{ and
$C$ is a packing set of $H$}\right\\}.$

If $d(x,y)=\left\|x-y\right\|_{p}$, we denote it by
$\mathcal{N}_{p}(\epsilon,H)$.

  * •

We now define $B(\theta,\epsilon)=\\{\theta^{\prime}\in
H:d(\theta^{\prime},\theta)\leq\varepsilon\\}$. $C$ is an $\epsilon$ local
packing set of $B(\theta,\epsilon)$ if $\forall\theta^{\prime}\in B$,
$\exists\theta^{\prime\prime}\in C$ such that
$d(\theta^{\prime},\theta^{\prime\prime})\leq\frac{\epsilon}{2}$.

  * •

The local packing number is defined as

$\mathcal{M}^{\mathrm{loc}}(d,\epsilon,H)=\max\left\\{m:\exists
B(\theta,\varepsilon),\text{such that $C$ is an }\epsilon-\text{covering of
$B$ and }\left|C\right|=m\right\\}.$

######  Lemma B.1.

The following properties hold:

  * •

(Theorem 14.2 of Wu [2020]) For any subset of dimension $d$ that is contained
in $\mathbb{B}_{1}^{d}$ the covering number $\mathcal{N}_{2}(\epsilon)$ obeys
$\log\mathcal{N}_{2}(\epsilon)=\Theta(d\log(1/\epsilon))$. This includes the
probability simplex with $d$ variables and $\mathbb{B}_{d}^{2}$.

  * •

(Lemma 6 of Gottlieb et al. [2017]) The covering of functions from $[0,1]^{d}$
to $[0,1]$ that are $L$-Lipschitz is given by
$\log\mathcal{N}_{2}(\epsilon)=\Theta\left((L/\epsilon)^{d}\right)$.

  * •

(Theorem 14.1 of Wu [2020]) Under the same norms, for the same set,

$\mathcal{M}(\epsilon/2)\leq\mathcal{N}(\epsilon)\leq\mathcal{M}(\epsilon)$

##  Appendix C Proofs for Section 3

###  C.1 Proof of Proposition 3.2

###### Proof.

We write

$\displaystyle\mathcal{BR}^{*}(T)$
$\displaystyle=\sup_{\nu}\inf_{\pi_{1},\dots,\pi_{T}}\mathbb{E}_{M\sim\nu}\left[\sum_{t=1}^{T}(\mu_{M}(\pi^{*})-\mu_{M}(\pi_{t}))\right]$
$\displaystyle\geq\sup_{\nu}\inf_{\pi_{1},\dots,\pi_{T}}\epsilon
T\mathbb{P}_{\nu}\left(\sum_{t=1}^{T}(\mu_{M}(\pi^{*})-\mu_{M}(\pi_{t}))\geq\epsilon
T\right)$ $\displaystyle\geq\epsilon
T\sup_{\nu}\inf_{\pi_{1},\dots,\pi_{T}}\mathbb{P}_{\nu}\left(\forall
t:\mu_{M}(\pi^{*})-\mu_{M}(\pi_{t})\geq\epsilon\right)$
$\displaystyle\geq\epsilon
T\sup_{\nu}\sup_{k\in\\{1,\dots,K\\}}\mathbb{P}\left(\forall
t:\left|\mu_{M}(\phi_{k})-\mu_{M}(\pi_{t})\right|\geq\epsilon\right)$
$\displaystyle\geq\epsilon
T\sup_{\nu}\sup_{k\in\\{1,\dots,K\\}}\mathbb{P}\left(\forall
t:\rho(\phi_{k},\pi_{t})\geq\epsilon\right)$ $\displaystyle\geq\epsilon
T\left(1-\frac{I(V;\mathcal{H}_{T})+1}{\log K}\right)\,,$

where the last inequality follows from Fano’s inequality (Theorem 3.1). ∎

###  C.2 Proof of Theorem 3.5

###### Proof.

We provide proof for three different scenarios.

  * •

First scenario, finite $\Pi$. For this scenario, we choose $\Phi$ to be a
local packing set of the decisions simplex $\Delta(\Pi)$, so
$K=\mathcal{M}^{\mathrm{loc}}(\rho,\Delta(\Pi),\epsilon)$. Applying this
selection of set, and using Equation 3 we have that

$\displaystyle\frac{\mathcal{BR}^{*}(T)}{\epsilon T}\geq
1-\frac{1+I(V;\mathcal{H}_{T})}{\log\mathcal{M}^{\mathrm{loc}}(\rho,\Delta(\Pi),\epsilon)}.$
(8)

Applying Theorem 3.4 we have that $I(V;\mathcal{H}_{T})\leq 2\epsilon^{2}T$.
Furthermore, from Lemma 3.3, we have that
$\log\mathcal{M}^{\mathrm{loc}}(\rho,\Delta(\Pi),\epsilon)\geq\log\mathcal{M}(\rho,\Delta(\Pi),\epsilon/2)-\log\mathcal{M}(\rho,\Delta(\Pi),\epsilon)$.
Substituting this back into Equation 8,

$\displaystyle\frac{\mathcal{BR}^{*}(T)}{\epsilon T}\geq
1-\frac{1+2\epsilon^{2}T}{\log\mathcal{M}(\rho,\Delta(\Pi),\epsilon/2)-\log\mathcal{M}(\rho,\Delta(\Pi),\epsilon)}.$

  * •

Second scenario, infinite-parametric $\Pi$. For this scenario, we choose
$\Phi$ to be a local packing set of the decision space $\Pi$, so
$K=\mathcal{M}^{\mathrm{loc}}(\rho,\Pi,\epsilon)$. Applying this selection of
set, and using Equation 3 we have that

$\displaystyle\frac{\mathcal{BR}^{*}(T)}{\epsilon T}\geq
1-\frac{1+I(V;\mathcal{H}_{T})}{\log\mathcal{M}^{\mathrm{loc}}(\rho,\Pi,\epsilon)}.$
(9)

Applying Theorem 3.4 we have that $I(V;\mathcal{H}_{T})\leq 2\epsilon^{2}T$.
Furthermore, from Lemma 3.3, we have that
$\log\mathcal{M}^{\mathrm{loc}}(\rho,\Pi,\epsilon)\geq\log\mathcal{M}(\rho,\Pi,\epsilon/2)-\log\mathcal{M}(\rho,\Pi,\epsilon)$.
Substituting this back into Equation 9,

$\displaystyle\frac{\mathcal{BR}^{*}(T)}{\epsilon T}\geq
1-\frac{1+2\epsilon^{2}T}{\log\mathcal{M}(\rho,\Pi,\epsilon/2)-\log\mathcal{M}(\rho,\Pi,\epsilon)}.$

  * •

Third scenario, non-parametric $\Pi$. For this scenario, we choose $\Phi$ to
be a global packing set of the decision space $\Pi$, so
$K=\mathcal{M}(\rho,\Pi,\epsilon)$. Applying this selection of set, and using
Equation 3 we have that

$\displaystyle\frac{\mathcal{BR}^{*}(T)}{\epsilon T}\geq
1-\frac{1+I(V;\mathcal{H}_{T})}{\log\mathcal{M}(\rho,\Pi,\epsilon)}.$ (10)

Applying Theorem 3.4 we have that
$I(V;\mathcal{H}_{T})\leq\inf_{\delta>0}\left(\log\mathcal{N}_{2}\left(\Pi,\sqrt{\delta}\right)+T\delta\right)$.
Substituting this back into Equation 10,

$\displaystyle\frac{\mathcal{BR}^{*}(T)}{\epsilon T}\geq
1-\frac{1+\inf_{\delta>0}\left(\log\mathcal{N}_{2}\left(\Pi,\sqrt{\delta}\right)+T\delta\right)}{\log\mathcal{M}(\rho,\Pi,\epsilon)}.$

∎

###  C.3 Proofs for Additional Lower Bounds

######  Lemma C.1.

For any algorithm, there exists a Bayesian decision-making task with a finite
decision such that the regret can be lower bounded by
$\Omega(\sqrt{\left|\Pi\right|T})$.

###### Proof.

We focus on the set $\Delta(\Pi)$ and note that it is a parametric set. We
also see that for all decisions $\phi,\psi\in\Pi$ we have that

$\mathbb{E}[\left|\mu_{M}(\phi)-\mu_{M}(\psi)\right|]\gtrsim\left\|\phi-\psi\right\|_{1}.$

Hence, in this scenario, we can take $\rho(x,y)=\left\|x-y\right\|_{1}$.
Furthermore, using Lemma B.1 we have that

$\log\mathcal{M}_{1}\left(\epsilon/2,\Delta(\Pi)\right)-\log\mathcal{M}_{1}\left(\epsilon,\Delta(\Pi)\right)=\Theta\left(\left|\Pi\right|\right).$

Substituting this into Equation 4 we obtain that

$\frac{\mathcal{BR}^{*}(T)}{\epsilon T}\gtrsim
1-\frac{1+2\epsilon^{2}T}{\left|\Pi\right|}.$

Now we fix $\epsilon$ such that
$\frac{2\epsilon^{2}T}{\left|\Pi\right|}=\frac{1}{2}$. More specifically, we
set $\epsilon=\frac{1}{4}\sqrt{\frac{\left|\Pi\right|}{T}}$ which yields

$\frac{\mathcal{BR}^{*}(T)}{\epsilon
T}\gtrsim\frac{1}{2}\sqrt{\left|\Pi\right|T}$

which concludes our proof. ∎

The results for multi-armed bandits, contextual bandits, and tabular MDPs are
shown by substituting $\left|\Pi\right|=A,CA$ and $SAH$ respectively.

######  Lemma C.2.

For any algorithm, the exists a Bayesian decision-making task with
$\Pi\subseteq\mathbb{B}_{2}^{d}$, where the reward means are a linear function
of the decisions, such that the regret can be lower bounded by
$\Omega(\sqrt{dT})$.

###### Proof.

Similarly to Lemma C.1, we have $\rho(x,y)=\left\|x-y\right\|_{1}$. We focus
on the set $\mathbb{B}_{2}^{d}$ and note that it is a parametric set.
Furthermore, using Lemma B.1 we have that

$\log\mathcal{M}_{1}\left(\epsilon/2,\mathbb{B}_{2}^{d}\right)-\log\mathcal{M}_{1}\left(\epsilon,\mathbb{B}_{2}^{d}\right)=\Theta\left(d\right).$

Substituting this into Equation 5 we obtain that

$\frac{\mathcal{BR}^{*}(T)}{\epsilon T}\gtrsim 1-\frac{1+2\epsilon^{2}T}{d}.$

Now we fix $\epsilon$ such that $\frac{2\epsilon^{2}T}{d}=\frac{1}{2}$. More
specifically, we set $\epsilon=\frac{1}{4}\sqrt{\frac{d}{T}}$ which yields

$\frac{\mathcal{BR}^{*}(T)}{\epsilon T}\gtrsim\frac{1}{2}\sqrt{dT}$

which concludes our proof. ∎

In the Lipshitz bandit setting, $\Pi$ is some metric space with metric $\rho$
and $\mathcal{M}=\mathcal{M}_{\mathcal{F}}$, where

$\mathcal{F}=\\{f:\Pi\to[0,1]|f\text{ is $1$-Lipschitz w.r.t }\rho\\}.$

Furthermore, we assume that there exists some $d$ such that
$\mathcal{M}_{\rho}(\epsilon,\Pi)\gtrsim\epsilon^{-d}$. Additionally, we know
from Lemma B.1 that $\log\mathcal{N}_{2}(\epsilon,\Pi)\lesssim\epsilon^{d}$.
We now provide a regret lower bound for Lipschitz bandits.

######  Lemma C.3.

The regret lower bound for the Lipschitz bandit is
$\Omega\left(T^{\frac{d+1}{d+2}}\right)$.

###### Proof.

Due to Lemma B.1, the covering and packing number can now be bounded by

$\displaystyle\log\mathcal{N}_{2}\left(\sqrt{\frac{2}{\delta}},\Pi\right)$
$\displaystyle\lesssim\left(\frac{2}{\delta}\right)^{d/2}$
$\displaystyle\log\mathcal{M}_{\rho}(\epsilon,\Pi)$
$\displaystyle\gtrsim{\epsilon}^{-d}.$

Substituting this into Equation 6,

$\displaystyle\frac{\mathcal{BR}^{*}(T)}{\epsilon T}$ $\displaystyle\gtrsim
1-\left({1+\left(\frac{2}{\delta}\right)^{d/2}+T\delta}\right)\epsilon^{d}.$

We choose $\delta=2^{\frac{d}{d+2}}T^{-\frac{2}{d+2}}$. This yields that

$\frac{\mathcal{BR}^{*}(T)}{\epsilon T}\gtrsim
1-\left(1+(2T)^{\frac{d}{d+2}}\right)\epsilon^{d}.$

Selecting $\epsilon=\left(2T\right)^{-\frac{1}{d+2}}4^{-\frac{1}{d}}$ yields

$\displaystyle\mathcal{BR}^{*}(T)$ $\displaystyle\gtrsim
2^{-\frac{1}{d+2}}4^{-\frac{1}{d}}T^{\frac{d+1}{d+2}}-o(1)$

which yields the expected (and optimal) bound. ∎

We now present the following theorem, which shows that the worst-case Bayesian
regret is equal to the mini-max frequentist regret.

######  Theorem C.4 (Theorem 1 of Lattimore and Szepesvári [2019]).

$\inf_{\\{\pi_{i}\\}_{i=1}^{T}}\sup_{r_{1},\dots,r_{t}}\max_{\pi^{*}\in\Pi}\mathbb{E}\left[\sum_{t=1}^{T}\left(r_{t}(\pi^{*})-r_{t}(\pi_{t})\right)\right]=\sup_{\nu}\inf_{\\{\pi_{i}\\}_{i=1}^{T}}\max_{\pi^{*}\in\Pi}\mathbb{E}\left[\sum_{t=1}^{T}\left(r_{t}(\pi^{*})-r_{t}(\pi_{t})\right)\right]$

This theorem then states that, without any constraints on the prior, the
worst-case Bayesian regret is equal to the mini-max regret. This means that
any lower bound derived for the Bayesian regret can also be applied to the
frequentist one.

##  Appendix D Proofs for Section 4

We begin by defining the W-Lambert function and supplying useful properties of
it.

######  Definition D.1.

The Lambert W-function is $W:[-1,\infty]\to[-1,\infty]$ is the inverse
function to $x2^{x}$. This means that for all $x\geq 0$, $y=x2^{x}$ if and
only if $W(y)=x$.

We now state the following useful property of the W-Lambert function.

######  Lemma D.1 (Equation 21 of [Iacono and Boyd, 2017]).

$W(x)=\Theta\left(\log\left(\frac{x}{\log x}\right)\right)$

We begin by proving the following useful lemma.

######  Lemma D.2.

Assume a finite decision space with $n$ decisions. Then the highest $L_{1}$
norm of every decision in the set, under the mutual information constraint of
$I(\pi^{*};\mathcal{H}_{T})\leq R\leq H(\pi^{*})$ is at most
$\Theta\left(\frac{R}{\log n}\right)$.

###### Proof.

We begin by noting that the mutual information can be written as
$I(\pi^{*};\mathcal{H}_{T})=D\left(P^{\pi^{*}\mid\mathcal{H}_{T}},P^{\pi^{*}}\right)$.
Thus, the constrained decision space becomes the decisions space under the KL
constraint, which can be written as

$\sum_{i}\phi(i)\log\frac{\phi(i)}{P(i)}\leq R.$

Thus, we have that

$\phi^{*}\log\frac{\phi^{*}}{p}\leq R$

we re-parameterize $\psi=\frac{\phi^{*}}{p}$ and obtain

$p\psi\log\psi\leq R.$

Hence,

$\psi\leq 2^{W(R/p)}=\Theta\left(\frac{R}{p\log\left(R/p\right)}\right).$

We substitute $\phi^{*}$ into the expression,

$\phi^{*}\leq\Theta\left(\frac{R}{\log\left(R/p\right)}\right)=\Theta\left(\frac{R}{\log
n}\right).$

∎

We now state the following lemma that explains how we can use the results of
Lemma D.2 to Equation 4.

######  Lemma D.3.

Under the assumptions and notations of Proposition 3.2, and under the
constraint of $I(\pi^{*};\mathcal{H}_{T})\leq R\leq H(\pi^{*})$, the following
holds.

$I(V;\mathcal{H}_{T})\lesssim 2T\frac{R}{\log K}\epsilon^{2}.$

###### Proof.

The proof follows a similar analysis to the proof of Theorem 3.4, which is
provided in Yang and Barron [1999]. We denote $E$ as the space of the
constrained distributions. We now have

$\displaystyle I(V;\mathcal{H}_{T})$ $\displaystyle\leq T\max_{p_{1},p_{2}\in
E}D\left(p_{1},p_{2}\right)$ $\displaystyle\lesssim T\frac{R}{\log
K}\max_{p_{1},p_{2}\in E}\left\|p_{1}-p_{2}\right\|_{2}^{2}$
$\displaystyle\leq T\frac{R}{\log K}\epsilon^{2}.$

where the second inequality follows from D.2. ∎

As a corollary from Lemma D.3, we obtain the following.

######  Corollary D.4 (Proposition 4.3).

Let there be a Bayesian interactive decision-making problem as defined in
Section 2, with a finite decision space $\Pi$, where $\left|\Pi\right|=K$.
Then,

$\frac{\mathcal{BR}^{*}(T)}{T\epsilon}\gtrsim
1-\frac{2\epsilon^{2}T\frac{R}{\log
K}+1}{\log\mathcal{M}_{1}(\Delta(\Pi),\epsilon/2)-\log\mathcal{M}_{1}(\Delta(\Pi),\epsilon)}$

###### Proof.

The proof follows immediately by utilizing Lemma D.3 and using the fact that
in this scenario, $\rho(x,y)=\left\|x-y\right\|_{1}$, similarly to the proof
in Lemma C.1. ∎

###  D.1 Proof of Proposition 4.2

###### Proof.

We begin by denoting the polytope space given the mutual information
constraint as $\Delta_{R}$. We first see that

$\log\mathcal{M}_{1}(\epsilon/2,\Delta_{R})-\log\mathcal{M}_{1}(\epsilon,\Delta_{R})=\Theta\left(K\right).$

Substituting this into Equation 7,

$\frac{\mathcal{BR}^{*}(T)}{T\epsilon}\gtrsim 1-\frac{2T\frac{R}{\log
K}\epsilon^{2}+1}{K}.$

Selecting $\epsilon=\frac{1}{4}\sqrt{\frac{RK}{T\log K}}$ we now have that

$\mathcal{BR}^{*}(T)\gtrsim\frac{1}{2}\sqrt{TK\frac{R}{\log K}}$

We present the proof for the linear case. Now,

$\log\mathcal{M}_{1}(\epsilon/2,\Delta_{R})-\log\mathcal{M}(\epsilon,\Delta_{R})=\Theta\left(d\right).$

So now we have

$\frac{\mathcal{BR}^{*}(T)}{T\epsilon}\gtrsim 1-\frac{2T\frac{R}{\log
K}\epsilon^{2}+1}{d}$

selecting $\epsilon=\frac{1}{4}\sqrt{\frac{Rd}{T\log K}}$ we now have that

$\mathcal{BR}^{*}(T)\gtrsim\frac{1}{2}\sqrt{\frac{dTR}{\log K}}.$

∎

######  Corollary D.5.

For a $K$-Bayesian MAB, the regret can be lower bounded by
$\Omega\left(\sqrt{KT\frac{I(\pi^{*};\mathcal{H}_{T})}{\log K}}\right)$. If
the MAB is also linear, then the lower bound becomes
$\Omega\left(\sqrt{dT\frac{I(\pi^{*};\mathcal{H}_{T})}{\log K}}\right)$. For a
Contextual MAB with $C$ contexts, the lower bound becomes
$\Omega\left(\sqrt{KCT\frac{I(\pi^{*};\mathcal{H}_{T})}{\log K}}\right)$.

##  Appendix E Experiments Details

Figure 5: The prompting done for the LLMs in our experiments. The question is
preceded by "Answer the following question:". Following this, the options are
presented and to improve accuracy, the LLM is requested to output only the
letter for the correct answer. Then, for the next round’s prompt, we add the
LLM’s answer and feedback.

###  E.1 Bayesian Bandit Experiments

The mutual information for the experiments in this setting is estimated using
the KL divergence between the output probability distribution of every
algorithm with the prior probability, $D\left(p_{t},P^{\pi^{*}}\right)$. This
is an estimator of the mutual information, similar to the one used by Seldin
et al. [2011]. The mutual information was then calculated according to
$D\left(p_{t},P^{\pi^{*}}\right)$, where $p_{t}$ is the real posterior. In our
problem, the posterior update is done in the following manner.

$\displaystyle P(\pi^{*}=i\mid\mathcal{H}_{t})$
$\displaystyle=\frac{P(\mathcal{H}_{t}\mid i)P(i)}{P(\mathcal{H}_{t})}$
$\displaystyle=\frac{P(\mathcal{H}_{t}\mid
i)P(i)}{\sum_{j}P(\mathcal{H}_{t}\mid i)P(i)}$

where

$\displaystyle P(\mathcal{H}_{t}\mid i)$
$\displaystyle=\left(\frac{1+\epsilon}{2}\right)^{N_{s,i}}\left(\frac{1-\epsilon}{2}\right)^{N_{f,i}}\prod_{j\neq
i}\left[\left(\frac{1-\epsilon}{2}\right)^{N_{s,j}}\left(\frac{1+\epsilon}{2}\right)^{N_{f,j}}\right],$

and $N_{s_{i}}$ is the number of successful pulls (pulls that received reward
1) of arm $i$. $N_{f,i}$ is the number of failed pulls of arm $i$.

In both bandit experiments, we used 200 random seeds. Each random seed
considers both the randomness in the problem generated (since the bandit
problem is generated via a prior) and the randomness during the algorithm’s
execution. We then reported in each graph the standard error for both the
regret and mutual information, which is given by
$\mathrm{err}=\frac{2\sigma}{\sqrt{n}}$ where $\sigma$ is the standard
deviation and $n$ is the number of seeds.

###  E.2 MCQA with LLM Experiment

For the second experiment, we used two different LLMs. The first is Mistral 7B
Jiang et al. [2023], an LLM with 7.3B parameters. The second is Mixtral 8x7B
Jiang et al. [2024]. The architecture of this model is the same as Mistral 7B,
but it uses 8 of them and a mixture of experts approach to select which one to
use. For both models, we use 4bit quantization of type nf4 Dettmers and
Zettlemoyer [2023]. In every round, we queried the LLM with all previous
prompts along with a prompt that consists of the following structure: "Answer
the following question: [question]? These are the possible answers [options].
Please output only the letter for the correct answer." Using the LLM’s output
we obtain a probability distribution over the tokens of the possible answers
[A,B,C,D]. We then selected the answer according to this distribution and
received feedback as to whether the answer was correct or not. The feedback
was also added to the prompt. The entire procedure is described in Figure 5.

We repeated this process for 10 different question seeds. For each question
seed, a different set of 200 questions was selected. Both policies were
evaluated on each set for 10 different seeds, so 100 random seeds were used
for this experiment. Figure 4 describes the behavior of both policies across
10 different seeds but using the same question seed. Table 2 reports the
results across all 100 seeds.

###  E.3 Compute Specifications

The bandits experiment is performed on a CPU and does not require special
compute workers. The experiments using Mistral 7B were evaluated using a
machine with RTX4090. The experiments using Mixtral 8x7B were done using a
machine with 3xA40.

###  E.4 Dataset and Models License

The MMLU dataset Hendrycks et al. [2021a, b] is available under the MIT
license. Mistral 7B Jiang et al. [2023] and Mixtral 8x7B Jiang et al. [2024]
are both available under the Apache license 2.0.


# Hand Gesture Recognition Based on a Nonconvex Regularization

Jing Qin  Department of Mathematics
University of Kentucky
Lexington, KY 40506, USA
<EMAIL_ADDRESS>
Joshua Ashley and Biyun Xie  Department of Electrical and Computer Engineering
University of Kentucky
Lexington, KY 40506, USA
<EMAIL_ADDRESS>

###### Abstract

Recognition of hand gestures is one of the most fundamental tasks in human-
robot interaction. Sparse representation based methods have been widely used
due to their efficiency and low demands on the training data. Recently,
nonconvex regularization techniques including the $\ell_{1-2}$ regularization
have been proposed in the image processing community to promote sparsity while
achieving efficient performance. In this paper, we propose a vision-based hand
gesture recognition model based on the $\ell_{1-2}$ regularization, which is
solved by the alternating direction method of multipliers (ADMM). Numerical
experiments on binary and gray-scale data sets have demonstrated the
effectiveness of this method in identifying hand gestures.

###### Index Terms:

Hand gesture recognition, human-robot interaction, sparsity, nonconvex
regularization, alternating direction method of multipliers

##  I Introduction

Human-robot interaction has become a popular research topic which can be
integrated into and revolutionize almost every aspect of our lives. Similar to
human-human interaction, there are many ways for humans to express their
intentions or emotions in human-robot interaction, which can be classified
into two categories: verbal and nonverbal communications [1]. Nonverbal
communication further includes facial expressions [2], gestures [3], proxemics
[4], and eye gazes [5]. Verbal communication has the advantage of simplicity,
convenience, and clearness. Nonverbal communication, however, is an essential
interaction way for scenarios where verbal communication is not available,
such as noisy environments and long-range interaction [6]. Even when verbal
communication is available, nonverbal communication can also be used as a
considerable augmentation of verbal communication, which will make the
interaction more lively. A socially intelligent robot typically has the
capacity of understanding human intentions through nonverbal communication to
improve the effectiveness, efficiency, and human-friendless in human-robot
interaction. In particular, hand gestures serve as a natural and intuitive way
to assist interaction between humans and robots. Therefore, recognition of
hand gestures plays a key role in a variety of human-robot interaction
applications.

There are mainly two types of hand gesture recognition. For the first type,
glove-based hand gesture recognition, hand gestures are recorded using a data
glove, and the position of each finger joint can be obtained accordingly. For
the other type, vision-based hand gesture recognition, hand gestures are
captured using cameras. Compared with data gloves, camera-based capture
systems are much cheaper and easier to use. Besides, wearing gloves will cause
difficulty for some hand operations, such as clenching fists. In this paper,
we will focus on vision-based hand gesture recognition.

In pattern recognition, sparse representation has shown its great power in
compressing and processing high-dimensional data. Specifically, we assume that
the object to be recognized can be sparsely represented as a linear
combination of atoms in a redundant dictionary, which implies a large portion
of coefficients are zeros. In order to find this sparse representation, we can
resort to sparsity based regularization techniques. For example,
$\ell_{1}$-regularization has been applied to dictionary-based action
recognition [7] and its local version has been proposed for gesture
recognition [8]. Sparsity-based methods typically improve interpretability and
compressibility of data, which enable detection discriminative and avoid over-
fitting. Recently, the nonconvex $\ell_{1-2}$ regularization has shown to
promote higher sparsity and achieve better performance than its $\ell_{1}$
counterpart in image reconstruction [9, 10] and in logistic regression [11].
In light of this, we propose a novel $\ell_{1-2}$-regularized hand gesture
recognition model, which is then solved by applying the alternating direction
method of multipliers (ADMM). Each resultant subproblem has a closed-form
solution which leads to computational efficiency. Note that the proposed
sparsity-based model is not a trivial generalization of that in [12], which
considers an inequality constrained $\ell_{1}$-minimization problem different
from our proposed model. In addition, we will take advantage of various
features, including binary segmented images, histograms of oriented gradients
(HOG) [13] and local binary patterns (LBP) [14]. HOG uses the distribution of
intensity gradients along various orientations to describe local object
appearance and shape within an image. By contrast, LBP exploits local binary
patterns over an image. In pattern recognition, HOG and LBP have been shown to
be effective and robust feature descriptors for object detection [15]. To
verify the effectiveness of the proposed method, we test two sets of hand
gesture images in binary or gray scales. Performance of the method in terms of
recognition rate and running time under various settings of training samples
are reported. We also make discussions on parameter selection, cell size in
HOG and LBP, identification metric, and comparison between $\ell_{1}$ and
$\ell_{1-2}$.

The rest of this paper is organized as follows. In Section II, we provide a
brief introduction of sparse representation based models. In Section III, we
propose a novel hand gesture recognition algorithm based on the nonconvex
$\ell_{1-2}$ regularization. Numerical experiments on two realistic data sets
of hand gestures and the results are discussed in Section IV. Finally,
conclusions of this research and future work are presented in Section V.

##  II Sparse Representation Based Models

Throughout the paper, we use boldface lowercase letters to denote vectors and
boldface uppercase letters to denote matrices. For $p\in\mathbb{N}$, the
$\ell_{p}$-norm of a vector $\mathbf{x}\in\mathbb{R}^{n}$ is defined as
$\lVert\mathbf{x}\rVert_{p}=(\sum_{i=1}^{n}|x_{i}|^{p})^{1/p}$.

Assume that a test vector $\mathbf{b}\in\mathbb{R}^{m}$ can be sparsely
represented as a linear combination of columns in a dictionary $\Phi$, i.e.,
there exists $\mathbf{x}\in\mathbb{R}^{n}$ with small
$\lVert\mathbf{x}\rVert_{0}$ such that $\mathbf{b}=\Phi\mathbf{x}$. Here
$\lVert\mathbf{x}\rVert_{0}$ is the number of nonzero components in
$\mathbf{x}$ and can describe the sparsity of the vector $\mathbf{x}$. Since
the dictionary is redundant, the image size is much smaller than the number of
images in the dictionary, i.e., $m\ll n$, which results in infinitely many
solutions to the linear system $\Phi\mathbf{x}=\mathbf{b}$. To guarantee a
unique solution, we consider the $\ell_{0}$ minimization problem of the form

$\min_{\mathbf{x}\in\mathbb{R}^{n}}\lVert\mathbf{x}\rVert_{0}\quad\mbox{s.t.}\quad\Phi\mathbf{x}=\mathbf{b}.$

However, this problem is NP-hard which can be relaxed to the convex $\ell_{1}$
minimization

$\min_{\mathbf{x}\in\mathbb{R}^{n}}\lVert\mathbf{x}\rVert_{1}\quad\mbox{s.t.}\quad\Phi\mathbf{x}=\mathbf{b}.$

To further enforce sparsity on the solution, we consider the $\ell_{1-2}$
minimization

$\min_{\mathbf{x}\in\mathbb{R}^{n}}\lVert\mathbf{x}\rVert_{1-2}\quad\mbox{s.t.}\quad\Phi\mathbf{x}=\mathbf{b},$
(1)

where
$\lVert\mathbf{x}\rVert_{1-2}=\lVert\mathbf{x}\rVert_{1}-\beta\lVert\mathbf{x}\rVert_{2}$.
It has empirically shown that the choice of $\beta$ does not make significant
impact on the performance. Thus we fix $\beta=1$ to reduce the number of
tuning parameters throughout the paper. Note that $\ell_{1-2}$ is not a vector
norm in $\mathbb{R}^{n}$ since the triangle inequality and positive
definiteness cannot be guaranteed. Connections and comparisons between the
$\ell_{1-2}$ regularization and its $\ell_{1}$ counterpart can be referred to
[10, 11].

##  III Proposed Method

Recognition of hand gestures plays an important role in the human-robot
interaction. In particular, vision-based recognition methods aim to identify
the gesture pattern from a dictionary (also known as library) of images that
is most similar to the test image. Each hand image in the dictionary is called
an _atom_.

###  III-A Dictionary Construction

There are many types of dictionaries that can be used for gesture recognition,
where each atom can characterize one or multiple features of an image. One
simple example is to use binary segmented images as atom images which
separates the hand from the background. However, once we reshape each image as
a column vector, a sparse representation of atoms may not be sufficient to
describe the image geometric information. To further take local geometry into
consideration, we can create a dictionary of HOG or LBP features (see Section
IV for more details).

In the continuous setting, each image can be considered as a function
$f:\Omega\to\mathbb{R}$ where $\Omega\subseteq\mathbb{R}^{2}$ is a closed set
with Dirichlet type of boundaries, e.g., $\Omega=[a,b]\times[c,d]$. Suppose
that $f$ can be sparsely represented by the set of atoms
$\\{v_{1},\ldots,v_{n}\\}$ where each atom image $v_{i}:\Omega\to\mathbb{R}$,
meaning that coefficients $c_{1},\ldots,c_{n}$ exist with
$f(x,y)=\sum_{i=1}^{n}c_{i}v_{i}(x,y)$ and the number of nonzero coefficients
$c_{i}$’s is small. If we restrict the domain of this function on a grid, then
sparse representation of a discrete image in terms of discrete atoms still
holds locally which implies that sparse representation in the feature space
can still be preserved. In this work, we adopt three types of dictionaries
using binary or gray-scale segmented images, HOG and LBP features.

###  III-B $\ell_{1-2}$-Regularized Recognition Method

Starting from this section, we will consider discrete images, i.e., each image
is treated as a matrix. Given $n$ atoms of size $\sqrt{m}\times\sqrt{m}$, we
reshape each image as a column vector by columnwise stacking and then
concatenate them to form a dictionary
$D=[\mathbf{d}_{1},\ldots,\mathbf{d}_{n}]\in\mathbb{R}^{m\times n}$.
Similarly, the test image $\mathbf{b}$ is reshaped as a column vector.

Suppose there are $L$ classes in the dictionary $D$ corresponding to $L$
gestures, i.e., the dictionary $D$ can be partitioned as
$D=\bigcup_{i=1}^{L}D_{i}$ each $D_{i}\in\mathbb{R}^{m\times n_{i}}$ such that
$D_{i}$ and $D_{j}$ have disjoint columns for $i\neq j$ and
$n_{1}+\ldots+n_{L}=n$. Without loss of generality, let $\bf{A}$ be one such
sub-dictionary $D_{i}$. If the partition is not available, we can apply fast
data clustering algorithms such as $k$-means.

Next, we intend to find a sparse representation of the test data $\mathbf{b}$
with respect to the dictionary $\bf{A}$, i.e., finding $\mathbf{x}$ with the
smallest number of nonzero elements such that $\bf{A}\mathbf{x}=\mathbf{b}$.
First, we normalize the columns of $A$ so that every column has a unit
$\ell_{2}$-norm. Then we consider the $\ell_{1-2}$-regularized sparse recovery
model

$\min_{\mathbf{x}}\frac{1}{2}\lVert\bf{A}\mathbf{x}-\mathbf{b}\rVert_{2}^{2}+\lambda\lVert\mathbf{x}\rVert_{1-2}.$
(2)

Here $\lambda>0$ is a regularization parameter. Different from the linear
constrained model (1), the unconstrained model (2) considers the presence of
noise. By the change of variable, (2) can be written as

$\min_{\mathbf{x},\mathbf{y}}\frac{1}{2}\lVert\bf{A}\mathbf{x}-\mathbf{b}\rVert_{2}^{2}+\lambda\lVert\mathbf{y}\rVert_{1-2}\quad\mbox{s.t.}\quad\mathbf{x}=\mathbf{y}.$

To solve this minimization problem, we define the augmented Lagrange function
as follows

$\mathcal{L}=\frac{1}{2}\lVert\bf{A}\mathbf{x}-\mathbf{b}\rVert_{2}^{2}+\lambda\lVert\mathbf{y}\rVert_{1-2}+\frac{\rho}{2}\lVert\mathbf{x}-\mathbf{y}+\widehat{\mathbf{y}}\rVert_{2}^{2}.$

Here $\rho>0$ is a tuning parameter which controls the convergence speed.
Following the framework of ADMM, we alternate the minimization of
$\mathcal{L}$ with respect to $\mathbf{x}$ and $\mathbf{y}$, respectively.
Notice that the subproblem $\operatorname*{argmin}_{\mathbf{x}}\mathcal{L}$ is
a least-square problem which can be converted to solving its normal equation.
Hence we obtain the following updating scheme

$\left\\{\begin{aligned} \mathbf{x}&\leftarrow(\bf{A}^{T}\bf{A}+\rho
I)^{-1}(\bf{A}^{T}\mathbf{b}+\rho(\mathbf{y}-\widehat{\mathbf{y}}));\\\
\mathbf{y}&\leftarrow\operatorname{prox}_{\theta\lVert\cdot\rVert_{1-2}}(\mathbf{x}+\widehat{\mathbf{y}});\\\
\widehat{\mathbf{y}}&\leftarrow\mathbf{x}-\mathbf{y}+\widehat{\mathbf{y}},\end{aligned}\right.$
(3)

where $\theta=\frac{\lambda}{\rho}$. To accelerate the computation, we apply
the Cholesky factorization of the matrix $\bf{A}^{T}\bf{A}+\rho
I=\bf{L}\bf{L}^{T}$ with $\bf{L}$ a lower triangular matrix and thereby the
update of $\mathbf{x}$ becomes

$\mathbf{x}\leftarrow\bf{L}^{-T}(\bf{L}^{-1}(\bf{A}^{T}\mathbf{b}+\rho\mathbf{y}-\rho\widehat{\mathbf{y}})).$
(4)

where $\bf{L}^{-1}$ is the inverse of the matrix $\bf{L}$, and $\bf{L}^{-T}$
is the transpose of $\bf{L}^{-1}$. Moreover, the proximal operator of a
function $f$ is defined as
$\operatorname{prox}_{f}(\mathbf{v})=\operatorname*{argmin}_{\mathbf{u}}\frac{1}{2}\lVert\mathbf{u}-\mathbf{v}\rVert_{2}^{2}+f(\mathbf{u})$.
Note that the proximal operator of $\ell_{1-2}$ can be expressed as [11]:

$\operatorname{prox}_{\theta\lVert\cdot\rVert_{1-2}}(\mathbf{x}+\widehat{\mathbf{y}})=\mathbf{z}+\frac{\theta\mathbf{z}}{\lVert\mathbf{z}\rVert_{2}},$
(5)

where
$\mathbf{z}=\operatorname{shrink}(\mathbf{x}+\widehat{\mathbf{y}},\theta)$ and
the shrinkage operator is defined componentwise

$[\operatorname{shrink}(\mathbf{u},\mu)]_{i}=\operatorname*{sign}(u_{i})\max\\{|u_{i}|-\mu,0\\}$

for $i=1,2,\ldots,n$. Here $u_{i}$ is the $i$-th component of the vector
$\mathbf{u}$. The algorithm terminates if either the relative change of two
consecutive estimates of $\mathbf{x}$ reaches the preassigned tolerance, i.e.,

$\lVert\mathbf{x}^{(j+1)}-\mathbf{x}^{(j)}\rVert_{2}/\lVert\mathbf{x}^{(j)}\rVert_{2}<tol$
(6)

where $\mathbf{x}^{(j)}$ is the estimate of $\mathbf{x}$ after $j$ iterations,
or the maximal number of allowed iterations is achieved. From this step, we
get the optimal coefficient vector $\mathbf{x}^{*}$ of $\mathbf{b}$ with
respect to the dictionary $\bf{A}$. Furthermore, we let $\mathbf{x}_{i}^{*}$
be the solution to (2) when $\bf{A}=D_{i}$.

To identify the most similar gesture class, we adopt two types of
identification metrics for classification. One metric uses the $\ell_{2}$-norm
residual for each class given by

$r_{i}(\mathbf{b})=\lVert\mathbf{b}-D_{i}\mathbf{x}_{i}^{*}\rVert_{2},\quad
i=1,\ldots,L,$ (7)

where $\mathbf{x}_{i}^{*}$ is obtained in the previous set with
$\bf{A}=D_{i}$. Alternatively, we compare the cosine similarity between
$\mathbf{b}$ and $D_{i}\mathbf{x}_{i}^{*}$ and define the identification
metric as

$r_{i}(\mathbf{b})=1-\cos(\mathbf{b},D_{i}\mathbf{x}_{i}^{*}),\quad
i=1,\ldots,L.$ (8)

Here cosine similarity is defined as
$\cos(\mathbf{u},\mathbf{v})=\frac{\lVert\mathbf{u}\rVert_{2}\cdot\lVert\mathbf{v}\rVert_{2}}{\langle\mathbf{u},\mathbf{v}\rangle}$
where $\langle\cdot,\cdot\rangle$ is the dot product of two vectors. Finally,
we predict the class that $\mathbf{b}$ belongs to by finding the minimum
identification metric

$identity(\mathbf{b}):=\operatorname*{argmin}_{1\leq i\leq
L}r_{i}(\mathbf{b}).$ (9)

Other similarity metrics could be used to define $r_{i}(\mathbf{b})$ while it
may take more computational time. The entire algorithm is summarized in
Algorithm 1, which can be extended to recognize multiple test data points in
parallel.

Algorithm 1 Nonconvex $\ell_{1-2}$-Regularized Recognition

Inputs: a dictionary with partition $D=\cup_{i=1}^{L}D_{i}$, test data
$\mathbf{b}$, parameters $\lambda,\rho>0$, maximum number of inner loops
$N_{in}$, tolerance $tol$ for the stopping criterion

Outputs: class label of $\mathbf{b}$

for $i=1,2,\ldots,L$ do

Initialize $\mathbf{x}=\mathbf{0}$

for $j=1,2,\ldots,N_{in}$ do

Update $\mathbf{x}$ via (4)

Update
$\mathbf{y}=\operatorname{prox}_{\theta\lVert\cdot\rVert_{1-2}}(\mathbf{x}+\widehat{\mathbf{y}})$
via (5)

$\widehat{\mathbf{y}}\leftarrow\mathbf{x}-\mathbf{y}+\widehat{\mathbf{y}}$

Exit the inner loop if (6) is met.

end for

$\mathbf{x}_{i}^{*}=\mathbf{x}$

Calculate $r_{i}(\mathbf{b})$ via (7) or (8).

end for

Find the class label of $\mathbf{b}$ via (9).

##  IV Numerical Experiments

In this section, we will test the proposed Algorithm 1 on one binary and one
gray-scale data sets of hand gesture images. To quantify the performance, we
use the recognition rate that is defined as the ratio of the correctly
recognized labels out of the entire test set. To make comparison fair, we
randomly select the test and atom images from the data set and take the
average performance of 50 trials by default. There are three types of feature
vectors being used: (1) raw feature vectors that are generated by reshaping
each image as a vector via column-wise stacking; (2) reshaped HOG feature
vectors with the cell size $k\times k$; (3) reshaped LBP feature vectors with
the cell size $k\times k$. Both HOG and LBP extractions are implemented in
Matlab. By default, the parameters of Algorithm 1 are set as
$\rho=1000,\lambda=1$. The maximum number of inner loops is set as 20 and the
tolerance in (6) is $tol=10^{-4}$. The cell size for both HOG and LBP is set
as $k=8$. Note that even with the same cell size, HOG and LBP features do not
have the same dimension. All experiments were run in Matlab R2019a on a
desktop computer with Intel CPU i9-9960X RAM 64GB and GPU Dual Nvidia Quadro
RTX5000 with Windows 10 Pro.

###  IV-A Experiment 1: Binary Data

The first set of data is downloaded from [16]. Specifically, there are three
hand gestures in the database: fist, open-hand, and two-finger, which have
2003, 2010 and 2005 images, respectively. Each image is binary of the size
$150\times 150$. We select 10 images randomly from each gesture class and
select $Nt$ images from the rest as the atoms in the test dictionary. Fig. 1
displays one sample image for each type of gestures.

|  |
---|---|---
Figure 1: Sample images in a binary dictionary. From left to right: fist, open
hand, two fingers.

We set the number of atoms in the test dictionary as $Nt=100,150,200,250$,
respectively. The recognition rates for all cases are shown in Table I. One
can see that HOG type of features yields the best performance. In the
meanwhile, since each image is piecewise constant with limited texture-like
patterns, LBP performs the worst which agrees with the fact that LBP features
favor the texture patterns [17]. When the number of atoms is larger than 300,
the proposed method can achieve almost perfect recognition. Comparison of
average running time for each case is shown in Fig. 2. With the fixed cell
size $8\times 8$, the dimension of each HOG feature is 10404 while 19116 for
that of each LBP feature which explains why LBP spends the most running time.

TABLE I: Recognition rates on a binary dictionary. Feature $\backslash$ Atom No. | 100 | 150 | 200 | 250
---|---|---|---|---
raw | 0.8060 | 0.8453 | 0.8800 | 0.8953
HOG | 0.9080 | 0.9393 | 0.9520 | 0.9667
LBP | 0.7373 | 0.7633 | 0.8053 | 0.8460
Figure 2: Running time comparison for a binary dictionary.

###  IV-B Experiment 2: Gray-Scale Data

In the second experiment, we download the HGM-4 multi-cameras dataset [18]
from https://data.mendeley.com/datasets/jzy8zngkbg/1. In particular, we choose
five classes of images corresponding to the hand gestures that express the
five letters: A, B, C, D and W. Each class of the original database has 40
atom images, each of size $160\times 90$. To ensure a sparse representation of
atoms from the dictionary, we generate 67 additional images corresponding to
those five gestures using a Logitech RGB webcam of resolution $1280\times
720$. A simple interface is developed to allow a user to classify and record
gestures on their own using this webcam. All gestures are done with a
whiteboard backdrop to reduce noise and help normalize the dataset. One set of
such high-resolution images are shown in Fig. 3. All newly generated images
are resized to $160\times 90$. Thus far, we get a dataset with five classes,
and the numbers of images within each class are distributed as 54, 52, 54, 54,
53. Furthermore, we expand the dataset by making four types of image rotations
for each image in Matlab: clockwise/counterclockwise rotation by one/two
degrees. Image rotation is illustrated in Fig. 5. Note that rotation could
bring zero boundary artifacts for large angles. Next we randomly select 10
test images from each class, and randomly select $Nt$ atom images from the
rest of the class to form a test dictionary. We select $Nt=50,100,150,200$. A
collection of five test gray-scale images are shown in Fig. 4. In Table II, we
list recognition rates for various numbers of atoms in each class of the
dictionary using various types of features. One can see that HOG performs best
most of the time and has a great advantage for small training sets. Raw
feature in gray scale performs slightly better than LBP in this case due to
the limited texture-like patterns. If the number of atoms is larger than 250,
then all those three features yield almost perfect recognition. Running time
for each test case is illustrated in Fig. 6. With the fixed cell size $8\times
8$, HOG feature vector has the smallest dimension among all the three feature
types which indicates HOG takes the least running time and yields the best
performance on average.

|  |  |  |
---|---|---|---|---
(a) A | (b) B | (c) C | (d) D | (e) W
Figure 3: Sample gesture images. The gestures from left to right correspond to the letters: A, B, C, D and W. |  |  |  |
---|---|---|---|---
(a) A | (b) B | (c) C | (d) D | (e) W
Figure 4: Sample raw images in the gray-scale dictionary. The gestures from left to right correspond to the letters: A, B, C, D and W. |  |  |  |
---|---|---|---|---
Figure 5: Image rotation. From left to right: original image, rotated by $1^{\circ}$, $-1^{\circ}$, $2^{\circ}$ and $-2^{\circ}$. Positive angles correspond to counterclockwise rotation and negative angles correspond to clockwise rotation. TABLE II: Recognition rates on a gray-scale dictionary. Feature $\backslash$ Atom No. | 50 | 100 | 150 | 200
---|---|---|---|---
raw | 0.7124 | 0.9100 | 0.9756 | 0.9956
HOG | 0.7360 | 0.9140 | 0.9832 | 0.9972
LBP | 0.7140 | 0.8940 | 0.9664 | 0.9936
Figure 6: Running time comparison for a gray-scale dictionary.

###  IV-C Discussions

In this section, we discuss selection of parameters, cell size in HOG/LBP
feature extraction and identification criteria. In addition, we make a remark
about the comparison of $\ell_{1}$ and $\ell_{1-2}$ in our method.

#### Parameter Selection

In Algorithm 1, $\lambda$ is a regularization parameter which controls the
balance between the data fidelity and the sparsity. The larger the parameter
$\lambda$ is, higher sparsity is enforced to the desired vector $\mathbf{x}$
but with larger residual error. In other words, if the test image is very
similar to one atom in the test dictionary, then we could choose a large value
for $\lambda$. In the $\mathbf{x}$-update (4), $\rho$ can be set as a large
number to penalize the high sparsity so that the objective function decays
fast. The number of inner loops could be set to be a small integer when it
decays fast. Further, if the background is not removed, then the recognition
could be sensitive to the parameter selection. As one illustrative example,
Fig. 7 has the ground truth gesture “D” which can be mistakenly recognized as
“C” with HOG/LBP features of cell size $16\times 16$ unless we choose the
parameters $\lambda=\rho=1$ and $N_{in}=100$. Here we use the HGM-4 database
as in Section IV-B with 200 images in each class. In this case, we can either
preprocess the test image by removing the background or tune parameters
carefully.

Figure 7: One example that is sensitive to parameter selection.

#### Cell Size in HOG and LBP

The cell size in HOG and LBP feature extraction influences the running time of
Algorithm 1 and its performance on parameter-sensitive test images, e.g., Fig.
7. There is a trade-off between computational cost and recognition accuracy.
Large cell sizes will yield low-dimensional features and thereby alleviate the
computational burden, which however may cause inaccuracies in local
description and reduce the recognition rate. Dimensions for various types of
features in our experiments are listed in Table III. A cell of size $k\times
k$ for both HOG and LBP features in the range 8$\sim$28 works in most
situations.

TABLE III: Dimensions of Various Feature Vectors $k$ | 8 | 12 | 16 | 20
---|---|---|---|---
image size $150\times 150$
HOG | 10404 | 4356 | 2304 | 1296
LBP | 19116 | 8496 | 4779 | 2891
image size $160\times 90$
HOG | 6840 | 2592 | 1296 | 756
LBP | 12980 | 5369 | 2950 | 1888

#### Identification Metric

Two types of identification metrics are introduced in the paper, including
$\ell_{2}$-norm based residual (7) and cosine similarity based metric (8).
According to our numerical experiments, these two metrics achieve almost the
same recognition performance. However, it is worth noting that (7) may result
in a very large number while (8) is always between 0 and 1. To avoid numerical
instability issues, (8) could be a top choice.

#### Comparison of $\ell_{1}$ and $\ell_{1-2}$ regularizations

The $\ell_{1-2}$-regularization
$\lVert\cdot\rVert_{1}-\beta\lVert\cdot\rVert_{2}$ can be reduced to the
$\ell_{1}$-regularization when $\beta=0$, and it is also related to the
iterative reweighted $\ell_{1}$ (IRL1) [19, 20] by choosing a special
weighting scheme. Our vast experiments have shown that $\ell_{1-2}$
regularization performs slight better than $\ell_{1}$ in the same algorithmic
framework especially with LBP features. For instance, Table IV shows the
recognition rates for Algorithm 1 with $\ell_{1}$ and $\ell_{1-2}$
regularizations and LBP features using the same data and parameter setting as
in Section IV-B. This phenomenon can be interpreted by the fact that both
regularizations could lead to the solutions with same sparsity level, which
will not significantly impact the recognition. Nevertheless, $\ell_{1-2}$ will
converge to a local minimizer faster than $\ell_{1}$ and thus is more
efficient when only a few training data is available.

TABLE IV: Recognition rate comparison for $\ell_{1}$ and $\ell_{1-2}$ Atom No. | 50 | 100 | 150 | 200
---|---|---|---|---
$\ell_{1}$ | 0.6620 | 0.8940 | 0.9640 | 0.9920
$\ell_{1-2}$ | 0.6640 | 0.8980 | 0.9640 | 0.9940

##  V Conclusions and Future Work

Vision-based hand gesture recognition has been widely in a lot of human-robot
interaction applications. When there are only a limited number of training
samples available, it becomes challenging to accurately detect the class of a
given hand gesture image. In this paper, we propose a novel hand gesture
recognition approach based on the nonconvex $\ell_{1-2}$ regularization to
improve the performance. Compared to the $\ell_{1}$-regularization,
$\ell_{1-2}$-regularization in the form of the difference of two vector norms
can further promote sparsity which can enhance the prediction accuracy and/or
achieve fast convergence to a local minimizer. To solve the
$\ell_{1-2}$-regularized recognition model, we apply the ADMM framework which
leads to two subproblems at each iteration. One subproblem is a least-square
problem that has a closed-form solution by solving its normal equation. The
other is reduced to the proximal operator of the $\ell_{1-2}$ regularizer
which can be expressed by the shrinkage operator. To make the proposed method
robust, we consider three types of features, including raw images in either
binary or gray scale, HOG and LBP features. Numerical experiments on two data
sets with various settings have shown the proposed effectiveness. In the
future work, we will explore hybrid types of features by concatenating
multiple features such as fusion of HOG and LBP, compare $\ell_{1}$ and
$\ell_{1-2}$ regularizations in more settings, and extend the proposed
framework to solve other related recognition problems, e.g., arm gesture
recognition.

## ACKNOWLEDGMENTS

The research of Qin is supported by the NSF grant DMS-1941197 and the research
of Ashley and Xie is supported by Woodrow W. Everett, Jr. SCEEE Development
Fund in cooperation with the Southeastern Association of Electrical
Engineering Department Heads.

## References

  * [1] A. Aly and A. Tapus, “A model for synthesizing a combined verbal and nonverbal behavior based on personality traits in human-robot interaction,” in _2013 8th ACM/IEEE International Conference on Human-Robot Interaction (HRI)_ , 2013, pp. 325–332.
  * [2] M. Wu, W. Su, L. Chen, Z. Liu, W. Cao, and K. Hirota, “Weight-adapted convolution neural network for facial expression recognition in human-robot interaction,” _IEEE Transactions on Systems, Man, and Cybernetics: Systems_ , 2019.
  * [3] J.-Y. Chang, A. Tejero-de Pablos, and T. Harada, “Improved optical flow for gesture-based human-robot interaction,” in _2019 International Conference on Robotics and Automation (ICRA)_ , 2019, pp. 7983–7989.
  * [4] P. Patompak, S. Jeong, I. Nilkhamhang, and N. Y. Chong, “Learning proxemics for personalized human–robot social interaction,” _International Journal of Social Robotics_ , pp. 1–14, 2019.
  * [5] A. Saran, S. Majumdar, E. S. Short, A. Thomaz, and S. Niekum, “Human gaze following for human-robot interaction,” in _2018 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS)_ , 2018, pp. 8615–8621.
  * [6] P. Barattini, C. Morand, and N. M. Robertson, “A proposed gesture set for the control of industrial collaborative robots,” in _2012 IEEE RO-MAN: The 21st IEEE International Symposium on Robot and Human Interactive Communication_ , 2012, pp. 132–137.
  * [7] Q. Qiu, Z. Jiang, and R. Chellappa, “Sparse dictionary-based representation and recognition of action attributes,” in _2011 International Conference on Computer Vision_. IEEE, 2011, pp. 707–714.
  * [8] Y. He, G. Li, Y. Liao, Y. Sun, J. Kong, G. Jiang, D. Jiang, B. Tao, S. Xu, and H. Liu, “Gesture recognition based on an improved local sparse representation classification algorithm,” _Cluster Computing_ , vol. 22, no. 5, pp. 10 935–10 946, 2019.
  * [9] P. Yin, Y. Lou, Q. He, and J. Xin, “Minimization of $\ell_{1-2}$ for compressed sensing,” _SIAM Journal on Scientific Computing_ , vol. 37, no. 1, pp. A536–A563, 2015.
  * [10] Y. Li, J. Qin, Y.-L. Hsin, S. Osher, and W. Liu, “s-SMOOTH: Sparsity and Smoothness Enhanced EEG Brain Tomography,” _Frontiers in neuroscience_ , vol. 10, 2016.
  * [11] J. Qin and Y. Lou, “$L_{1-2}$ Regularized Logistic Regression,” in _2019 53rd Asilomar Conference on Signals, Systems, and Computers_. IEEE, 2019, pp. 779–783.
  * [12] W. Miao, G. Li, Y. Sun, G. Jiang, J. Kong, and H. Liu, “Gesture recognition based on sparse representation,” _International Journal of Wireless and Mobile Computing_ , vol. 11, no. 4, pp. 348–356, 2016.
  * [13] M. R. William T. Freeman, “Orientation Histograms for Hand Gesture Recognition,” MERL - Mitsubishi Electric Research Laboratories, Cambridge, MA 02139, Tech. Rep. TR94-03, Dec. 1994. [Online]. Available: https://www.merl.com/publications/TR94-03/
  * [14] T. Ojala, M. Pietikäinen, and D. Harwood, “A comparative study of texture measures with classification based on featured distributions,” _Pattern recognition_ , vol. 29, no. 1, pp. 51–59, 1996.
  * [15] M. Ghorbani, A. T. Targhi, and M. M. Dehshibi, “HOG and LBP: Towards a robust face recognition system,” in _2015 Tenth International Conference on Digital Information Management (ICDIM)_. IEEE, 2015, pp. 138–141.
  * [16] S. Goyal, “Hand gesture recognition database,” 2020. [Online]. Available: https://www.kaggle.com/ds/625998
  * [17] T. J. Alhindi, S. Kalra, K. H. Ng, A. Afrin, and H. R. Tizhoosh, “Comparing LBP, HOG and deep features for classification of histopathology images,” in _2018 international joint conference on neural networks (IJCNN)_. IEEE, 2018, pp. 1–7.
  * [18] V. T. Hoang, “HGM-4: A new multi-cameras dataset for hand gesture recognition,” _Data in Brief_ , vol. 30, p. 105676, 2020.
  * [19] E. J. Candes, M. B. Wakin, and S. P. Boyd, “Enhancing sparsity by reweighted $\ell_{1}$ minimization,” _Journal of Fourier analysis and applications_ , vol. 14, no. 5-6, pp. 877–905, 2008.
  * [20] W. Guo, Y. Lou, J. Qin, and M. Yan, “A novel regularization based on the error function for sparse recovery,” _Journal of Scientific Computing_ , vol. 87, no. 1, pp. 1–22, 2021.