# Elegant elaboration with function invocation

Tesla Zhang  The Pennsylvania State University<EMAIL_ADDRESS>
###### Abstract.

We present an elegant design of the core language in a dependently-typed
lambda calculus with $\delta$-reduction and an elaboration algorithm.

##  1\. Introduction

Throughout this paper, we will use boxes in the following two cases:

  * •

to clarify the precedences of symbols when the formulae become too large.
e.g. $\Gamma\vdash\framebox{$\lambda x.~{}M$}~{}:~{}\framebox{$(y:A)\to
B$}\Leftarrow\framebox{$\lambda x.~{}u$}$.

  * •

to distinguish type theory terms from natural language text.
e.g. we combine a term $a$ with a term $b$ to get a term $a~{}b$.

In the context of practical functional programming languages, functions can be
either primitive (like arithmetic operations for primitive numbers, cubical
primitives [1, §3.2, §3.4, §5.1] such as transp, hcomp, Glue, etc.) or defined
(that have user-definable reduction rules, e.g. by using pattern matching).
The reduction of function applications are known as $\delta$-reduction [2] and
the to-be-reduced terms are called $\delta$-redexes (redex for reducible
expressions).

In general, function definitions may reduce only when fully applied, while
they are also curried, allowing the flexible partial application. So, from the
type theoretical perspective, functions are always unary and function
application as an operation is binary, while in the operational semantics,
function application is n-ary and $\delta$-reduction only works when enough
arguments are supplied. We may use elaboration, a process that transforms a
user-friendly concrete syntax into a compact, type theoretical core language
using type information, to deal with this inconsistency between the intuitive
concrete syntax and the optimal internal representation.

For defined functions, even when they are sometimes elaborated as a
combination of lambdas and case-trees [3] or eliminators [4] (so we can think
of the function syntax as a syntactic sugar of lambdas), the elaborated terms
are related to the implementation detail of the programming language, which we
tend to hide from the users.

To ensure the functions are fully applied, we may check whether sufficient
arguments are supplied every time we want to reduce an application to a
function Elaboration is also helpful here: we could choose an efficient
representation of function application in the core language and elaborate a
user-friendly concrete syntax into it. Consider a term
$\mathrm{\color[rgb]{0.00,0.00,1.00}\definecolor[named]{pgfstrokecolor}{rgb}{0.00,0.00,1.00}max}~{}a~{}b$
where
$\mathrm{\color[rgb]{0.00,0.00,1.00}\definecolor[named]{pgfstrokecolor}{rgb}{0.00,0.00,1.00}max}$
is a function taking two natural numbers and returning the larger one, we
present two styles of function applications in the core language.

  * •

binary application. The syntax definition of application is like
$e::=e_{1}~{}e_{2}$. The above term will be structured as
$\framebox{$\mathrm{\color[rgb]{0.00,0.00,1.00}\definecolor[named]{pgfstrokecolor}{rgb}{0.00,0.00,1.00}max}~{}a$}~{}b$.

  * •

spine-normal form. The syntax definition of application is like
$e::=e_{1}~{}\overline{e}$
($\overline{e}$ is called a spine), where arguments are collected as a list in
application terms. The above term will be structured as-is.

If we choose the binary representation, checking the number of supplied
arguments requires a traversal of the terms, which is an $O(n)$ process where
$n$ is the number of parameters of the applied function (accessing the applied
function from an application term is also $O(n)$).

This is not a problem in spine-normal form representation, where we only need
to check if the size of the arguments is larger than the number of parameters
during $\delta$-reduction. Size comparison is an $O(1)$ process for memory-
efficient arrays. However, inserting extra arguments to the spine is a list
mutation operation, which requires a list reconstruction in a purely
functional setting. The list reconstruction creates a new list with a larger
size and copies the old list with the new argument appended to the end, which
is again an $O(n)$ process.

Similar problems also exist for indexed types [5], where we need the types to
be fully applied to determine the available constructors.

###  1.1. Contributions

We discuss an even more elegant design of application term representation
where neither traversal of terms during reduction nor mutation of the argument
lists during application are needed. We will use both binary application and
spine-normal form to guarantee that the number of supplied arguments always
fits the requirement, and we could always assume function applications to have
sufficient arguments supplied.

We present the syntax (in section 2) and a bidirectional-style elaboration
algorithm (in section 3) which can be adapted to the implementation of any
programming language with $\delta$-reduction.

##  2\. Syntax

We will assume the existence of well-typed function definitions (will be
further discussed in section 3), and focus on lambda calculus terms. Inductive
types and pattern matching are also assumed and omitted.

###  2.1. Core language

The syntax is defined in fig. 2.1.

Core terms have several assumed properties: well-typedness, well-scopedness,
and the functions are exactly-applied – the number of arguments matches
exactly the number of parameters.

$\displaystyle x,y::=$ variable names $\displaystyle A,B,u,v::=$
$\displaystyle\quad\mathrm{\color[rgb]{0.00,0.00,1.00}\definecolor[named]{pgfstrokecolor}{rgb}{0.00,0.00,1.00}f}~{}\overline{u}$
exactly-applied function $\displaystyle\mid$ $\displaystyle\quad x$ reference
$\displaystyle\mid$ $\displaystyle\quad u~{}v$ binary application
$\displaystyle\mid$ $\displaystyle\quad(x:A)\to B$ $\Pi$-type
$\displaystyle\mid$ $\displaystyle\quad\lambda x.~{}u$ lambda abstraction
$\displaystyle\sigma::=$ $\displaystyle\quad\overline{u/x}$ substitution
object Figure 2.1. Syntax of terms

We will assume the substitution operation on core terms, written as
$u~{}[\sigma]$.

######  Example 2.1.

For a function
$\mathrm{\color[rgb]{0.00,0.00,1.00}\definecolor[named]{pgfstrokecolor}{rgb}{0.00,0.00,1.00}f}$
who has two parameters and returns a function with two parameters, the
application
$\mathrm{\color[rgb]{0.00,0.00,1.00}\definecolor[named]{pgfstrokecolor}{rgb}{0.00,0.00,1.00}f}~{}u_{1}~{}u_{2}~{}u_{3}~{}u_{4}$
is structured as
$\framebox{$\framebox{$\mathrm{\color[rgb]{0.00,0.00,1.00}\definecolor[named]{pgfstrokecolor}{rgb}{0.00,0.00,1.00}f}~{}u_{1}~{}u_{2}$}~{}u_{3}$}~{}u_{4}$.
The innermost subterm
$\mathrm{\color[rgb]{0.00,0.00,1.00}\definecolor[named]{pgfstrokecolor}{rgb}{0.00,0.00,1.00}f}~{}u_{1}~{}u_{2}$
is an exactly-applied function and the outer terms are binary applications.

###  2.2. Concrete syntax

The concrete syntax is defined in fig. 2.2. We assume the names to be resolved
in concrete syntax, so we can assume the terms to be well-scoped and
distinguish local references and function references.

The symbol for local references and functions are overloaded because they make
no difference between concrete and core.

$\displaystyle M,N::=$
$\displaystyle\quad\mathrm{\color[rgb]{0.00,0.00,1.00}\definecolor[named]{pgfstrokecolor}{rgb}{0.00,0.00,1.00}f}$
function reference $\displaystyle\mid$ $\displaystyle\quad x$ local reference
$\displaystyle\mid$ $\displaystyle\quad M~{}N$ application $\displaystyle\mid$
$\displaystyle\quad\lambda x.~{}M$ lambda abstraction
Figure 2.2. Concrete syntax tree

In the concrete syntax, applications are always binary.

We do not have $\Pi$-types in concrete syntax because they are unrelated to
application syntax and their type-checking is relevant to the universe type
which is quite complicated.

##  3\. Elaboration

In this section, we describe the process that type-checks concrete terms
against core terms and translates them into well-typed, exactly-applied core
terms.

We define the following operation $\textsf{apply}(u,v)$ to eliminate obviously
reducible core terms:

$\displaystyle\textsf{apply}(\lambda x.~{}u,v)$ $\displaystyle::=u[v/x]$
$\displaystyle\textsf{apply}(u,v)$ $\displaystyle::=u~{}v$

We will use a bidirectional elaboration algorithm [6, 7]. It uses the
following typing judgments, parameterized by a context $\Gamma$:

  * •

$\Gamma\vdash M:A\Leftarrow u$, normally called a checking or an inherit rule.

  * •

$\Gamma\vdash M\Rightarrow u:A$, normally called an inferring or a synthesis
rule.

  * •

$x:A\in\Gamma$, that the context $\Gamma$ contains a local binding $x:A$.

Checking judgments are for introduction rules, while synthesis judgments are
for the formation and elimination rules. The direction of the arrows is
inspired from [7, §6.6.1]. The arrows ($\Leftarrow$ and $\Rightarrow$)
separate the inputs and outputs of the corresponding elaboration procedure:
checking judgments take as input a term in concrete form and its expected type
in core form, and produce as output an elaborated version of the term in core
form; synthesis judgments take as input a term in concrete form and emit its
elaborated form and the inferred type as output.

The context $\Gamma$ contains a list of local bindings (pairs of local
variables and types, written as $x:A$) and a list of functions.

A function is defined with a name and a signature (and a body that we do not
care about in this paper), where the signature tells us about its parameters
and the return type.

###  3.1. Abstraction and application

First of all, we have the basic elaboration rules for type conversion and
local references:

$\displaystyle\displaystyle{\hbox{\hskip
67.91422pt\vbox{\hbox{\hskip-67.91422pt\hbox{\hbox{$\displaystyle\displaystyle\Gamma\vdash
M\Rightarrow u:A$}\hskip
20.00003pt\hbox{\hbox{$\displaystyle\displaystyle\Gamma\vdash
A=_{\beta\eta}B$}}}}\vbox{}}}\over\hbox{\hskip
33.20412pt\vbox{\vbox{}\hbox{\hskip-33.20412pt\hbox{\hbox{$\displaystyle\displaystyle\Gamma\vdash
M:B\Leftarrow u$}}}}}}$ Conv $\displaystyle\displaystyle{\hbox{\hskip
20.01031pt\vbox{\hbox{\hskip-20.0103pt\hbox{\hbox{$\displaystyle\displaystyle
x:A\in\Gamma$}}}\vbox{}}}\over\hbox{\hskip
30.36787pt\vbox{\vbox{}\hbox{\hskip-30.36787pt\hbox{\hbox{$\displaystyle\displaystyle\Gamma\vdash
x\Rightarrow x:A$}}}}}}$ Var

The rules for lambda abstraction and application are quite straightforward:

$\displaystyle\displaystyle{\hbox{\hskip
58.6334pt\vbox{\hbox{\hskip-58.6334pt\hbox{\hbox{$\displaystyle\displaystyle\Gamma,x:A\vdash
M:B[x/y]\Leftarrow u$}}}\vbox{}}}\over\hbox{\hskip
70.01563pt\vbox{\vbox{}\hbox{\hskip-70.01561pt\hbox{\hbox{$\displaystyle\displaystyle\Gamma\vdash\framebox{$\displaystyle\lambda
x.~{}M$}~{}:~{}\framebox{$\displaystyle(y:A)\to
B$}\Leftarrow\framebox{$\displaystyle\lambda x.~{}u$}$}}}}}}$ Lam
$\displaystyle\displaystyle{\hbox{\hskip
93.57423pt\vbox{\hbox{\hskip-93.57423pt\hbox{\hbox{$\displaystyle\displaystyle\Gamma\vdash
M\Rightarrow u:\framebox{$\displaystyle(x:A)\to B$}$}\hskip
20.00003pt\hbox{\hbox{$\displaystyle\displaystyle\Gamma\vdash N:A\Leftarrow
v$}}}}\vbox{}}}\over\hbox{\hskip
71.8008pt\vbox{\vbox{}\hbox{\hskip-71.8008pt\hbox{\hbox{$\displaystyle\displaystyle\Gamma\vdash
M~{}N\Rightarrow\textsf{apply}(u,v):B[v/x]$}}}}}}$ App

###  3.2. Functions

Before continuing to function references, we need to define the notation for
function signature. We define parameters to be a list of local bindings:

$\Delta::=\overline{x:A}$

Then, we assume two operations for every function symbol
$\mathrm{\color[rgb]{0.00,0.00,1.00}\definecolor[named]{pgfstrokecolor}{rgb}{0.00,0.00,1.00}f}$:

  * •

$\textsf{params}(\Gamma,\mathrm{\color[rgb]{0.00,0.00,1.00}\definecolor[named]{pgfstrokecolor}{rgb}{0.00,0.00,1.00}f})$
that returns a $\Delta$ that represents the parameters of
$\mathrm{\color[rgb]{0.00,0.00,1.00}\definecolor[named]{pgfstrokecolor}{rgb}{0.00,0.00,1.00}f}$
in $\Gamma$.

  * •

$\textsf{typeOf}(\Gamma,\mathrm{\color[rgb]{0.00,0.00,1.00}\definecolor[named]{pgfstrokecolor}{rgb}{0.00,0.00,1.00}f})$
that returns a term $u$ that represents the type (combining parameters and the
return type) of
$\mathrm{\color[rgb]{0.00,0.00,1.00}\definecolor[named]{pgfstrokecolor}{rgb}{0.00,0.00,1.00}f}$
in $\Gamma$.

We will need a few more operations before introducing the elaboration rules
for functions.

$\textsf{vars}(\Delta)$: extracts the variables (as a list of terms) from
$\Delta$:

$\displaystyle\textsf{vars}(\emptyset)$ $\displaystyle::=\emptyset$
$\displaystyle\textsf{vars}(x:A,\Delta)$
$\displaystyle::=x,\textsf{vars}(\Delta)$

$\textsf{lambda}(u,\Delta)$: generates a lambda abstraction by induction on
$\Delta$:

$\displaystyle\textsf{lambda}(u,\emptyset)$ $\displaystyle::=u$
$\displaystyle\textsf{lambda}(u,\framebox{$x:A,\Delta$})$
$\displaystyle::=\lambda x.~{}\textsf{lambda}(u,\Delta)$

With these two operations, we can define the elaboration rule for functions.
Let
$\Delta=\textsf{params}(\Gamma,\mathrm{\color[rgb]{0.00,0.00,1.00}\definecolor[named]{pgfstrokecolor}{rgb}{0.00,0.00,1.00}f})$,
we have the synthesis rule for function references as in fig. 3.1.

$\displaystyle\displaystyle{\hbox{\hskip
9.375pt\vbox{\hbox{\hskip-9.37498pt\hbox{\hbox{$\displaystyle\displaystyle\mathrm{\color[rgb]{0.00,0.00,1.00}\definecolor[named]{pgfstrokecolor}{rgb}{0.00,0.00,1.00}f}\in\Gamma$}}}\vbox{}}}\over\hbox{\hskip
87.679pt\vbox{\vbox{}\hbox{\hskip-87.679pt\hbox{\hbox{$\displaystyle\displaystyle\Gamma\vdash\mathrm{\color[rgb]{0.00,0.00,1.00}\definecolor[named]{pgfstrokecolor}{rgb}{0.00,0.00,1.00}f}\Rightarrow\textsf{lambda}(\framebox{$\displaystyle\mathrm{\color[rgb]{0.00,0.00,1.00}\definecolor[named]{pgfstrokecolor}{rgb}{0.00,0.00,1.00}f}~{}\textsf{vars}(\Delta)$},\Delta):\textsf{typeOf}(\Gamma,\mathrm{\color[rgb]{0.00,0.00,1.00}\definecolor[named]{pgfstrokecolor}{rgb}{0.00,0.00,1.00}f})$}}}}}}$
Figure 3.1. Elaboration of functions

Here are some examples. Consider the
$\mathrm{\color[rgb]{0.00,0.00,1.00}\definecolor[named]{pgfstrokecolor}{rgb}{0.00,0.00,1.00}max}$
function discussed in section 1, we have the following facts:

$\displaystyle\textsf{params}(\Gamma,\mathrm{\color[rgb]{0.00,0.00,1.00}\definecolor[named]{pgfstrokecolor}{rgb}{0.00,0.00,1.00}max})$
$\displaystyle::=x:\mathrm{\color[rgb]{0.13,0.55,0.13}\definecolor[named]{pgfstrokecolor}{rgb}{0.13,0.55,0.13}Nat},y:\mathrm{\color[rgb]{0.13,0.55,0.13}\definecolor[named]{pgfstrokecolor}{rgb}{0.13,0.55,0.13}Nat}$
$\displaystyle\textsf{typeOf}(\Gamma,\mathrm{\color[rgb]{0.00,0.00,1.00}\definecolor[named]{pgfstrokecolor}{rgb}{0.00,0.00,1.00}max})$
$\displaystyle::=(x:\mathrm{\color[rgb]{0.13,0.55,0.13}\definecolor[named]{pgfstrokecolor}{rgb}{0.13,0.55,0.13}Nat})\to(y:\mathrm{\color[rgb]{0.13,0.55,0.13}\definecolor[named]{pgfstrokecolor}{rgb}{0.13,0.55,0.13}Nat})\to\mathrm{\color[rgb]{0.13,0.55,0.13}\definecolor[named]{pgfstrokecolor}{rgb}{0.13,0.55,0.13}Nat}$

######  Example 3.1.

Concrete term
$\mathrm{\color[rgb]{0.00,0.00,1.00}\definecolor[named]{pgfstrokecolor}{rgb}{0.00,0.00,1.00}max}$.
By the rule in fig. 3.1,

$\displaystyle\textsf{lambda}(\mathrm{\color[rgb]{0.00,0.00,1.00}\definecolor[named]{pgfstrokecolor}{rgb}{0.00,0.00,1.00}max}~{}\textsf{vars}(\Delta),\Delta)$
$\displaystyle=\textsf{lambda}(\framebox{$\mathrm{\color[rgb]{0.00,0.00,1.00}\definecolor[named]{pgfstrokecolor}{rgb}{0.00,0.00,1.00}max}~{}\textsf{vars}(x:\mathrm{\color[rgb]{0.13,0.55,0.13}\definecolor[named]{pgfstrokecolor}{rgb}{0.13,0.55,0.13}Nat},y:\mathrm{\color[rgb]{0.13,0.55,0.13}\definecolor[named]{pgfstrokecolor}{rgb}{0.13,0.55,0.13}Nat})$},\framebox{$x:\mathrm{\color[rgb]{0.13,0.55,0.13}\definecolor[named]{pgfstrokecolor}{rgb}{0.13,0.55,0.13}Nat},y:\mathrm{\color[rgb]{0.13,0.55,0.13}\definecolor[named]{pgfstrokecolor}{rgb}{0.13,0.55,0.13}Nat}$})$
$\displaystyle\text{Expand}~{}\Delta$
$\displaystyle=\textsf{lambda}(\mathrm{\color[rgb]{0.00,0.00,1.00}\definecolor[named]{pgfstrokecolor}{rgb}{0.00,0.00,1.00}max}~{}x~{}y,\framebox{$x:\mathrm{\color[rgb]{0.13,0.55,0.13}\definecolor[named]{pgfstrokecolor}{rgb}{0.13,0.55,0.13}Nat},y:\mathrm{\color[rgb]{0.13,0.55,0.13}\definecolor[named]{pgfstrokecolor}{rgb}{0.13,0.55,0.13}Nat}$})$
Expand vars $\displaystyle=\lambda x.~{}\lambda
y.~{}\mathrm{\color[rgb]{0.00,0.00,1.00}\definecolor[named]{pgfstrokecolor}{rgb}{0.00,0.00,1.00}max}~{}x~{}y$
Expand lambda

Observe that
$\mathrm{\color[rgb]{0.00,0.00,1.00}\definecolor[named]{pgfstrokecolor}{rgb}{0.00,0.00,1.00}max}$
is exactly-applied. The result type is
$\textsf{typeOf}(\Gamma,\mathrm{\color[rgb]{0.00,0.00,1.00}\definecolor[named]{pgfstrokecolor}{rgb}{0.00,0.00,1.00}max})$,
which equals
$(x:\mathrm{\color[rgb]{0.13,0.55,0.13}\definecolor[named]{pgfstrokecolor}{rgb}{0.13,0.55,0.13}Nat})\to(y:\mathrm{\color[rgb]{0.13,0.55,0.13}\definecolor[named]{pgfstrokecolor}{rgb}{0.13,0.55,0.13}Nat})\to\mathrm{\color[rgb]{0.13,0.55,0.13}\definecolor[named]{pgfstrokecolor}{rgb}{0.13,0.55,0.13}Nat}$.

######  Example 3.2.

Concrete term
$\mathrm{\color[rgb]{0.00,0.00,1.00}\definecolor[named]{pgfstrokecolor}{rgb}{0.00,0.00,1.00}max}~{}M$,
assuming $\Gamma\vdash
M:\mathrm{\color[rgb]{0.13,0.55,0.13}\definecolor[named]{pgfstrokecolor}{rgb}{0.13,0.55,0.13}Nat}\Leftarrow
u$. We already know the elaboration result of
$\mathrm{\color[rgb]{0.00,0.00,1.00}\definecolor[named]{pgfstrokecolor}{rgb}{0.00,0.00,1.00}max}$
in example 3.1. By the App rule, since $\textsf{apply}(\framebox{$\lambda
x.~{}\lambda
y.~{}\mathrm{\color[rgb]{0.00,0.00,1.00}\definecolor[named]{pgfstrokecolor}{rgb}{0.00,0.00,1.00}max}~{}x~{}y$},u)\mapsto\framebox{$\lambda
y.~{}\mathrm{\color[rgb]{0.00,0.00,1.00}\definecolor[named]{pgfstrokecolor}{rgb}{0.00,0.00,1.00}max}~{}u~{}y$}$,
the elaborated version of
$\mathrm{\color[rgb]{0.00,0.00,1.00}\definecolor[named]{pgfstrokecolor}{rgb}{0.00,0.00,1.00}max}~{}M$
is $\lambda
y.~{}\mathrm{\color[rgb]{0.00,0.00,1.00}\definecolor[named]{pgfstrokecolor}{rgb}{0.00,0.00,1.00}max}~{}u~{}y$,
typed
$(y:\mathrm{\color[rgb]{0.13,0.55,0.13}\definecolor[named]{pgfstrokecolor}{rgb}{0.13,0.55,0.13}Nat})\to\mathrm{\color[rgb]{0.13,0.55,0.13}\definecolor[named]{pgfstrokecolor}{rgb}{0.13,0.55,0.13}Nat}$.
Observe that
$\mathrm{\color[rgb]{0.00,0.00,1.00}\definecolor[named]{pgfstrokecolor}{rgb}{0.00,0.00,1.00}max}$
is still exactly-applied.

######  Theorem 3.3.

Functions are always exactly-applied in the core language, as promised in
section 1.1.

###### Proof.

We only generate exactly-applied functions in fig. 3.1, and we do not take
arguments away or insert new arguments to function application terms in any
other rules or operations. ∎

##  4\. Conclusion

We have discussed an elegant core language design with $\delta$-redexes with
an elaboration algorithm. With this design, wherever in the compiler, we can
assume any given $\delta$-redexes to be exactly-applied. Appending extra
arguments to an application term results in a binary application term to a
non-function (as in example 2.1).

###  4.1. Implementation

The discussed core language design is implemented in two proof assistants:

  * •

Arend [8]. There is an abstract class DefCallExpression that generalizes all
sorts of definition invocations, including functions, data types,
constructors, etc. These expressions are always exactly-applied. The source
code is hosted on GitHub 111 See https://github.com/JetBrains/Arend.

  * •

Aya [9]. Similar to Arend, there is an interface CallTerm in Aya. The source
code is also hosted on GitHub 222 See https://github.com/aya-prover/aya-dev.

In the implementations, there is one extra complication: invocations to
constructors of inductive types have access to the parameters of the inductive
type.

###  4.2. Related work

The notion of $\delta$-reduction was discussed in [2], but the
$\delta$-redexes are represented in binary application form. Exactly-applied
$\delta$-redexes are discussed in [10, 3], but they did not discuss
elaboration. The idea of separating spine-normal function application and
binary application also appeared in an early work on LISP [11, §6], where
spines referred to as rails and binary application referred to as pairs, but
they also did not discuss elaboration.

In the elaboration of Lean 2 [12], functions are transformed into lambdas and
recursors (and they refer to the corresponding redexes as $\beta$-redexes and
$\iota$-redexs [12, §3.3], respectively). This design is not friendly for
primitive functions that only work when fully applied.

###  4.3. Acknowledgments

We would like to thank Marisa Kirisame, Ende Jin, Qiantan Hong, and Zenghao
Gao for their comments and suggestions on the draft versions of this paper.

## References

  * [1] Andrea Vezzosi, Anders Mörtberg and Andreas Abel  “Cubical Agda: A Dependently Typed Programming Language with Univalence and Higher Inductive Types” Preprint available at https://staff.math.su.se/anders.mortberg/papers/cubicalagda2.pdf, 2020
  * [2] Werner Kluge  “Abstract Computing Machines: A Lambda Calculus Perspective”  Springer Science & Business Media, 2006
  * [3] Jesper Cockx and Andreas Abel  “Elaborating Dependent (Co)Pattern Matching”  In _Proc. ACM Program. Lang._ 2.ICFP New York, NY, USA: Association for Computing Machinery, 2018  DOI: 10.1145/3236770
  * [4] Healfdene Goguen, Conor McBride and James McKinna  “Eliminating Dependent Pattern Matching”  In _Algebra, Meaning, and Computation: Essays dedicated to Joseph A. Goguen on the Occasion of His 65th Birthday_ Berlin, Heidelberg: Springer Berlin Heidelberg, 2006, pp. 521–540  DOI: 10.1007/11780274_27
  * [5] Tesla Zhang  “A Simpler Encoding of Indexed Types”  In _Proceedings of the 6th ACM SIGPLAN International Workshop on Type-Driven Development_ , TyDe ’21  Republic of Korea: ACM, 2021  DOI: 10.1145/3471875.3472991
  * [6] Thierry Coquand  “An algorithm for type-checking dependent types”  In _Science of Computer Programming_ 26.1-3 Elsevier, 1996, pp. 167–177
  * [7] Thierry Coquand, Yoshiki Kinoshita, Bengt Nordström and Makoto Takeyama  “A simple type-theoretic language: Mini-TT”  In _From Semantics to Computer Science; Essays in Honour of Gilles Kahn_ , 2009, pp. 139–164
  * [8] Group for Dependent Types and HoTT  “The Arend Proof Assistant”, https://arend-lang.github.io, 2015
  * [9] Aya developers  “The Aya Proof Assistant”, https://www.aya-prover.org, 2021
  * [10] Semyon Aleksandrovich Nigiyan and Tigran Valery Khondkaryan  “On canonical notion of $\delta$-reduction and on translation of typed $\lambda$-terms into untyped $\lambda$-terms”  In _Proceedings of the YSU A: Physical and Mathematical Sciences_ 51.1 (242), 2017, pp. 46–52
  * [11] Brian Cantwell Smith  “Reflection and Semantics in LISP”  In _Proceedings of the 11th ACM SIGACT-SIGPLAN Symposium on Principles of Programming Languages_ , POPL ’84  Salt Lake City, Utah, USA: Association for Computing Machinery, 1984, pp. 23–35  DOI: 10.1145/800017.800513
  * [12] Leonardo Moura, Jeremy Avigad, Soonho Kong and Cody Roux  “Elaboration in Dependent Type Theory”, 2015  arXiv:1505.04324 [cs.LO]


# Budgeted Multi-Armed Bandits with
Asymmetric Confidence Intervals

Marco Heyden, Vadim Arzamasov, Edouard Fouché, Klemens Böhm
Karlsruhe Institute of Technology
Karlsruhe, Germany
{marco.heyden, vadim.arzamasov, edouard.fouche<EMAIL_ADDRESS>

###### Abstract

We study the stochastic Budgeted Multi-Armed Bandit (MAB) problem, where a
player chooses from $K$ arms with unknown expected rewards and costs. The goal
is to maximize the total reward under a budget constraint. A player thus seeks
to choose the arm with the highest reward-cost ratio as often as possible.
Current state-of-the-art policies for this problem have several issues, which
we illustrate. To overcome them, we propose a new upper confidence bound (UCB)
sampling policy, $\omega$-UCB, that uses asymmetric confidence intervals.
These intervals scale with the distance between the sample mean and the bounds
of a random variable, yielding a more accurate and tight estimation of the
reward-cost ratio compared to our competitors. We show that our approach has
logarithmic regret and consistently outperforms existing policies in synthetic
and real settings.

##  1 Introduction

In the stochastic Multi-Armed Bandit (MAB) problem, a player repeatedly plays
one of $K$ arms and receives a corresponding random reward. The goal is to
maximize the cumulative reward by playing the arm with the highest expected
reward as often as possible. The expected rewards are initially unknown, so
the player must balance trying arms to learn their expected rewards
(exploration) versus using the current information to play arms with known
high expected rewards (exploitation).

In the stochastic Budgeted MAB problem [13], a player must consider not only
the potential rewards but also the associated random costs for each arm. The
player chooses arms until the available budget is exhausted. Budgeted MABs
model real-world situations such as the selection of a cloud service provider
[1], energy-efficient task selection for battery-powered embedded devices
[14], bid optimization [6, 7, 4], or optimizing advertising on social media.

######  Example 1 (Social media advertising).

Consider a retail company that wants to advertise products on a social network
platform. The retail company provides to the platform an advertisement
campaign consisting of multiple ads, as well as an advertisement budget. Each
time a user clicks on an ad (an arm), the platform charges the retail company
(a cost). Within the given budget, the retailer wants to find the ads which
maximize the likelihood of a subsequent purchase (a reward). Both the reward
and the cost are random variables since they depend on the actions of users
and the competition from other advertisers. A Budgeted MAB algorithm can help
to find the most promising ads in real time.

A variety of policies has been proposed to address the Budgeted MAB problem.
Section 3 provides a summary. Many policies extend ideas from traditional
multi-armed bandit algorithms, in which the costs of arms are assumed to be
constant, including Thompson Sampling [20] and Upper Confidence Bound (UCB)
sampling [21]. Several studies [19, 22, 21, 15, 16] indicate that UCB-sampling
policies perform well in practice, in particular when the budget is small.

UCB-sampling policies continuously update an upper bound of the ratio of the
expected rewards and costs of each arm, and play the arm with the highest
upper bound. We distinguish between three types: Some policies [15, 16, 21]
compute the bound from the ratio of the sample average reward and average cost
plus some uncertainty-related term (cf. Eq. (1), left). We call this type
“united” (u). Other policies [21, 3, 22] divide the reward’s upper confidence
bound by the cost’s lower confidence bound (LCB) (cf. Eq. (1), right). We
refer to this type as “composite” (c). There also are “hybrid” (h) policies
[21, 19] that combine the united and composite types.

$\textit{UCB}_{u}=\frac{\textit{average reward}}{\textit{average
cost}}+\textit{uncertainty}\quad\quad\textit{UCB}_{c}=\frac{\textit{average
reward}+\textit{uncertainty}}{\textit{average cost}-\textit{uncertainty}}$ (1)

However, all of the current policies have at least one of the following
issues:

  * (i1)

Over-optimism: The policy often computes UCB that are too tight.

  * (i2)

Over-pessimism: The policy often computes UCB that are too loose.

  * (i3)

Invalid values: Negative or undefined UCB occur if the cost’s lower confidence
bound in Eq. (1) becomes negative or zero. This can happen, for instance, when
computing the lower confidence bound of an arm’s expected cost with
Hoeffding’s inequality [21, 19].

To illustrate (i1) and (i2), we randomly parameterized 10 000 Bernoulli reward
and cost distributions and sampled from them. We used these samples to compute
99% confidence intervals of the reward-cost ratio using several state-of-the-
art UCB-sampling policies. The left plot of Figure 1 shows the share of cases
when the expected reward-cost ratio exceeds (i.e., violates) its UCB. Values
above 1% indicate overly tight bounds. The right plot shows the UCB of the
reward-cost ratio divided by its expectation, with higher values indicating
looser bounds. Existing united policies (u) tend to suffer from issue (i1),
hybrid approaches suffer from either of both issues, and issue (i2) mainly
affects the composite approach (c).

To address (i1) and (i2), some approaches provide a hyperparameter that allows
to adjust the confidence interval manually [21]. However, setting such a
hyperparameter is difficult in practice since it depends on the unknown mean
and variance of the reward and cost distributions. To address issue (i3),
current approaches set the UCB of the ratio to infinity [21] or the cost LCB
to a small positive value [19]. These heuristic solutions largely ignore the
information already acquired about the cost distribution and tend to cause
either (i1) or (i2).

Figure 1: Issues of existing work

#### Contributions

(1) We derive asymmetric confidence intervals for bounded random variables.
These intervals have the same range as the random variable and scale with the
distance between the sample mean and the boundaries. Our formula generalizes
Wilson’s score interval for binomial proportions [18] to arbitrary bounded
random variables. (2) We introduce a policy called $\omega$-UCB, which
leverages these confidence intervals to address issues (i1)–(i3). We also
propose an extension of $\omega$-UCB, called $\omega^{*}$-UCB, that uses the
observed sample variances of the arms’ rewards and cost to further tighten the
UCB. (3) We prove that our policy has logarithmic regret. (4) We conduct
experiments on typical settings found in the literature and real-world social
network advertising data to compare the performance of $\omega$-UCB and
$\omega^{*}$-UCB against state-of-the-art policies. Our results demonstrate
that both policies have substantially lower regret than the competitors for
both small and large budgets. (5) We share the code of our experiments.111
https://github.com/heymarco/OmegaUCB

##  2 Problem definition

We focus on a stochastic setting with $K$ arms. Each arm $k$ has continuous or
discrete reward and cost distributions with unknown expected values
$\mu_{k}^{r}\in[0,1)$ and $\mu_{k}^{c}\in(0,1]$, respectively. At time $t$ a
player chooses an arm $k_{t}\in\\{1,\dots,K\\}$ and observes the reward
$r_{t}\in[0,1]$ and the cost $c_{t}\in[0,1]$. We assume that the arms are
independent and that rewards and costs observed at different time steps are
independent and identically distributed (iid). This is consistent with
previous work [19, 20, 21, 15, 16]. We do not make any assumptions about the
correlation between rewards and costs of the same arm. The game ends after
$T_{B}$ plays that exhaust the available budget $B$.

Let $\mathds{1}_{k}(k_{t})$ be the indicator function:
$\mathds{1}_{k}(k_{t})=1$ iff $k_{t}=k$, else $\mathds{1}_{k}(k_{t})=0$. The
number of plays, and the sample average of rewards and costs of arm $k$ at
time $T$ are:

$n_{k}(T)=\sum_{t=1}^{T}\mathds{1}_{k}(k_{t})\qquad\bar{\mu}_{k}^{r}(T)=\frac{1}{n_{k}(T)}\sum_{t=1}^{T}\mathds{1}_{k}(k_{t})r_{t}\qquad\bar{\mu}_{k}^{c}(T)=\frac{1}{n_{k}(T)}\sum_{t=1}^{T}\mathds{1}_{k}(k_{t})c_{t}$
(2)

The player aims to maximize the total expected reward
$\mathbb{E}\sum_{t=1}^{T_{B}}r_{t}$. Assume without loss of generality that
arm $k=1$ has the highest ratio ${\mu_{k}^{r}}/{\mu_{k}^{c}}$ among all arms.
According to [19, 20, 21, 15, 16], maximizing the expected total reward is
roughly equivalent to minimizing the (pseudo)-regret:

$\text{Regret}=\sum_{i=1}^{K}\mu_{k}^{c}\Delta_{k}\mathbb{E}[n_{k}(T_{B})],\qquad\textrm{where~{}}\Delta_{k}=\frac{\mu_{1}^{r}}{\mu_{1}^{c}}-\frac{\mu_{k}^{r}}{\mu_{k}^{c}}$
(3)

##  3 Related work

Tran-Thanh et al. [13] introduced the Budgeted MAB problem and proposed an
$\epsilon$-first policy. KUBE and Fractional KUBE policies [14] handle
Budgeted MAB problems with deterministic costs; UCB-BV1 [8] addresses discrete
random costs. Later solutions [19, 20, 21, 15, 16] adapted concepts from
traditional MABs, such as Upper Confidence Bound (UCB) [2] or Thompson
sampling [11, 12] and can deal with continuous random costs. However, the one
policy based on Thompson sampling, BTS [20], requires transforming continuous
rewards and costs into Bernoulli-samples. As a result, the policy disregards
information about the variance of rewards and costs, causing over-pessimism
(i2) when the variance of the reward or cost distribution is small. MRCB [19]
deals with the challenge of playing multiple arms in each time step; when
playing only one arm at a time, the policy becomes m-UCB [21] that is similar
to our policy. However, m-UCB relies on Hoeffding’s inequality, which does not
take the distance between a random variable’s sample mean and boundaries into
account. All these policies either have issues (i1)–(i3) [21, 19, 16, 15, 20],
are not designed for continuous random costs [14, 8, 20], or have been shown
to perform inferior to others [13, 8, 14].

Policy | Ref.
---|---
$\varepsilon$-first | [13]
KUBE | [14]
UCB-BV1 | [8]
PD-BwK | [3]
Budget-UCB | [19]
BTS | [20]
MRCB | [22]
m-UCB | [21]
b-greedy | [21]
c-UCB | [21]
i-UCB | [21]
KL-UCB-SC+ | [15]
UCB-SC+ | [16]

Year | Type | Compared
---|---|---
2010 | – | $\crossproduct$
2012 | – | $\crossproduct$
2013 | h | $\crossproduct$
2013 | c | $\crossproduct$
2015 | h | $\checkmark$
2015 | – | $\checkmark$
2016 | c | –
2017 | c | $\checkmark$
2017 | – | $\checkmark$
2017 | h | $\checkmark$
2017 | u | $\checkmark$
2017 | u | –
2018 | u | $\checkmark$

Figure 2: Empirical performance of different Budgeted MAB policies according
to related work

Figure 2 provides a compilation of existing head-to-head empirical comparisons
between various policies. Upwards pointing triangles indicate that the policy
in the corresponding row outperformed the policy in the corresponding column
in the respective paper, while downward pointing triangles indicate the
opposite. Circles represent cases where both policies performed similarly,
while horizontal lines indicate that the policies have not been compared. One
sees that KUBE [14] outperforms $\epsilon$-first [13], while UCB-BV1 [8] and
BTS[19] outperform KUBE. UCB-BV1 is inferior to more recent policies [20, 19,
15, 16]. BTS [20], b-greedy [21], and {i, c, m}-UCB [21] outperform PD-BwK
[3]. We will compare our policy to the best performing existing policies —
BTS, Budget-UCB, {i, c, m}-UCB, b-greedy, and UCB-SC+.

##  4 Our policy

We now detail our policy $\omega$-UCB and analyze it theoretically.

###  4.1 $\omega$-UCB

$\omega$-UCB starts by playing each arm once. At each subsequent time step
$t$, the policy chooses the arm $k_{t}$ with the highest upper confidence
bound of the ratio of the expected reward $\mu^{r}_{k}$ to the expected cost
$\mu_{k}^{c}$. Let $\omega_{k+}^{r}(\alpha,t)$ denote the upper confidence
bound of $\mu^{r}_{k}$ for a confidence level $1-\alpha$. Similarly,
$\omega_{k-}^{c}(\alpha,t)$ is the lower confidence bound of $\mu_{k}^{c}$.
$\omega$-UCB chooses $k_{t}$ according to:

$k_{t}=\operatorname*{arg\,max}_{k\in[K]}\Omega_{k}(\alpha,t),\qquad\text{where
}\Omega_{k}(\alpha,t)=\frac{\omega_{k+}^{r}(\alpha,t)}{\omega_{k-}^{c}(\alpha,t)}$
(4)

Unlike other policies that rely on the same principle [21, 19, 22, 3],
$\omega$-UCB calculates asymmetric confidence bounds that we derive in the
following Theorem.

######  Theorem 1 (Asymmetric confidence interval for bounded random
variables).

Let $X$ be a random variable bounded in the interval $[m,M]$, with unknown
expected value $\mu\in[m,M]$ and variance $\sigma^{2}$. Let $z$ denote the
number of standard deviations required to achieve $1-\alpha$ confidence in
coverage of the standard normal distribution. Let $\bar{\mu}$ be the sample
mean of $n$ iid samples of $X$. Then,

$\Pr[\mu\not\in\left[\omega_{-}(\alpha),\omega_{+}(\alpha)\right]]\leq\alpha,\quad\textrm{with~{}}\omega_{\pm}(\alpha)=\frac{B}{2A}\pm\sqrt{\frac{B^{2}}{4A^{2}}-\frac{C}{A}},$
(5)

where

$A=n+z^{2}\eta,\quad B=2n\bar{\mu}+z^{2}\eta(M+m),\quad
C=n\bar{\mu}^{2}+z^{2}\eta Mm,\quad\textrm{and}$ (6)
$\eta=\frac{\sigma^{2}}{(M-\mu)(\mu-m)}\textrm{ if }\mu\in(m,M),\quad\textrm{
and }\eta=1\textrm{ if }\mu\in\\{m,M\\}.$ (7)

###### Proof.

See Appendix 8.1. ∎

According to the Bhatia-Davis inequality [5],
$0\leq\sigma^{2}\leq(M-\mu)(\mu-m)$, and hence $\eta\in[0,1]$. For the special
case of Bernoulli random variables, $\eta=1$, $m=0$, $M=1$, and Theorem 1
recovers Wilson’s original confidence interval for Binomial proportions [18].
However, this theorem is more flexible than Wilson’s original method. It
enables tighter confidence intervals for non-Bernoulli costs or rewards, by
setting $\eta<1$ when a variance estimate is available. Our experiments will
demonstrate that this flexibility leads to a significant improvement in
performance.

The following theorem connects $\Omega_{k}(\alpha,t)$ and the confidence level
of the ratio ${\mu_{k}^{r}}/{\mu_{k}^{c}}$.

######  Theorem 2 (UCB for ratio of expected values of two random variables).

Let $R$ and $C$ be two independent bounded random variables with expected
values $\mu^{r}\geq 0$ and $\mu^{c}>0$. Let $\omega_{+}^{r}(\alpha)\geq 0$
denote the upper confidence bound of $R$ and $\omega_{-}^{c}(\alpha)>0$ the
lower confidence bound of $C$ as given in Theorem 1. Let
$\Omega(\alpha)={\omega_{+}^{r}(\alpha)}/{\omega_{-}^{c}(\alpha)}$. Then,

$\Pr[\frac{\mu^{r}}{\mu^{c}}>\Omega(\alpha)]\leq\alpha$ (8)

###### Proof.

See Appendix8.2. ∎

A UCB-sampling policy that keeps the parameter $\alpha$ constant leads to
linear regret in the worst case. This is because such a policy will eventually
stop exploring arms that may have high costs and low rewards in the beginning.
To avoid this problem, $\omega$-UCB decreases the value of $\alpha$ as the
time $t$ progresses, similarly to the UCB1-policy [2]. This adaptive approach
helps to ensure continued exploration of arms and guarantees sub-linear
regret. The following theorem introduces the scaling law and relates it to the
confidence level.

######  Theorem 3 (Time-adaptive confidence interval).

For an arm $k$, let $\mu_{k}^{r}$ be its expected reward, $\mu_{k}^{c}$ its
expected cost, and $\Omega_{k}(\alpha,t)$ the upper confidence bound for
${\mu_{k}^{r}}/{\mu_{k}^{c}}$, as in Eq. (4). For $\rho,t>0$, and
$\alpha(t)<1-\sqrt{1-t^{-\rho}}$ it holds that

$\Pr[\Omega_{k}(\alpha,t)\geq\frac{\mu_{k}^{r}}{\mu_{k}^{c}}]\geq
1-\alpha(t),$ (9)

that is, the upper confidence bound holds asymptotically almost surely.

###### Proof.

See Appendix 8.3. ∎

With $\alpha(t)<1-\sqrt{1-t^{-\rho}}$, the confidence level approaches $1$ as
time $t$ goes to infinity. This encourages exploration of arms that are played
less frequently. Moreover, it establishes a logarithmic dependence between $z$
in Theorem 1 and $t$, i.e., $z_{\rho}(t)=\sqrt{2\rho\log t}$, which will be
useful in our regret analysis. The next section analyzes the worst-case regret
of $\omega$-UCB. To simplify notation, we abbreviate $\Omega(\alpha,t)$ as
$\Omega(t)$, $\omega_{k-}^{c}(\alpha,t)$ as $\omega_{k-}^{c}(t)$, and
$\omega_{k+}^{r}(\alpha,t)$ as $\omega_{k+}^{r}(t)$ in our regret analysis.

###  4.2 Regret analysis

In this section, we bound the expected number of suboptimal plays
$\mathbb{E}[n_{k}(\tau)]$ before some time step $\tau$ and use this analysis
to derive the regret bound of $\omega$-UCB (cf. Theorem 5).

######  Theorem 4 (Number of suboptimal plays).

For $\omega$-UCB, the expected number of plays of a suboptimal arm $k>1$
before time step $\tau$, $\mathbb{E}[n_{k}(\tau)]$, is upper-bounded by

$\begin{split}\mathbb{E}[n_{k}(\tau)]\leq
1+n_{k}^{*}(\tau)+\xi(\tau,\rho),\end{split}$ (10)

where

$\xi(\tau,\rho)=\left(\tau-K\right)\left(2-\sqrt{1-\tau^{-\rho}}\right)-\operatorname{\sum_{t=K+1}^{\tau}}\sqrt{1-t^{-\rho}},$
(11)
$n_{k}^{*}(\tau)=\frac{8\rho\log\tau}{\delta_{k}^{2}}\max\left\\{\frac{\eta_{k}^{r}\mu_{k}^{r}}{1-\mu_{k}^{r}},\frac{\eta_{k}^{c}(1-\mu_{k}^{c})}{\mu_{k}^{c}}\right\\},\quad\delta_{k}=\frac{\Delta_{k}}{\Delta_{k}+\frac{1}{\mu_{k}^{c}}},$
(12)

and $K$ and $\Delta_{k}$ are defined as before, cf. Section 2.

###### Proof.

Appendix 8.4 contains the proof of the theorem. The derivation of $\delta_{k}$
is in Appendix 8.5. ∎

Lemma 4 in [21] allows us to derive worst-case regret of $\omega$-UCB from
Theorem 4.

######  Theorem 5 (Worst-case regret).

Define $\tau_{B}=\left\lfloor{2B}/{\min_{k\in[K]}\mu_{k}^{c}}\right\rfloor$
and $\Delta_{k},n_{k}^{*}(\tau_{B})$, and $\xi(\tau_{B},\rho)$ as before. For
any $\rho>0$, the regret of $\omega$-UCB is upper-bounded by

$\text{Regret}\leq\sum_{k=2}^{K}\Delta_{k}\left(1+n_{k}^{*}(\tau_{B})+\xi(\tau_{B},\rho)\right)+\mathcal{X}(B)\sum_{k=2}^{K}\Delta_{k}+\frac{2\mu_{1}^{r}}{\mu_{1}^{c}},$
(13)

where $\mathcal{X}(B)$ is in
$\mathcal{O}\left(\frac{B}{\mu_{min}^{c}}e^{-0.5B\mu_{min}^{C}}\right)$.

###### Proof.

Lemma 4 of [21] provides a policy-independent regret expression for Budgeted
MAB policies:

$\text{Regret}\leq\sum_{k=2}^{K}\Delta_{k}\mathbb{E}[n_{k}(\tau_{B})]+\mathcal{X}(B)\sum_{k=2}^{K}\Delta_{k}+\frac{2\mu^{r}_{1}}{\mu_{1}^{c}},\quad\tau_{B}=\left\lfloor\frac{2B}{\min_{k\in[K]}\mu_{k}^{c}}\right\rfloor$
(14)

Substituting $\mathbb{E}[n_{k}(\tau_{B})]$ in Eq. (14) with the result from
Theorem 4 completes the proof. ∎

Last, we derive the asymptotic worst-case regret of $\omega$-UCB. When
$0<\rho<1$, the regret grows by a fractional power. When $\rho\geq 1$, in
turn, it is logarithmic.

######  Theorem 6 (Asymptotic regret).

The regret of $\omega$-UCB is in

$\mathcal{O}\left(B^{1-\rho}\right)\textrm{ for }0<\rho<1,\quad\textrm{and
in}\quad\mathcal{O}(\log B)\textrm{ for }\rho\geq 1.$ (15)

###### Proof.

See Appendix 8.7. ∎

##  5 Experimental Setup

This section presents the experimental setup used to evaluate the policies. We
introduce the MAB settings, followed by the configurations of $\omega$-UCB and
its competitors. We conducted the experiments on a server with 32 cores, each
running at 2.0 GHz, and 128 GB of RAM.

###  5.1 Budgeted MAB settings

We use MAB settings based on synthetic and real data, which we describe
separately. Each setting comprises a specific combination of reward and cost
distributions, and the number of arms $K$. See Table 1 for a summary of the
evaluation settings.

#### Synthetic Data.

Previous studies on Budgeted Multi-Armed Bandits (MABs) have used synthetic
settings with rewards and costs drawn from discrete (Bernoulli or Generalized
Bernoulli with possible outcomes $\\{0.0,0.25,0.5,0.75,1.0\\}$) or continuous
(Beta) distributions [19, 21, 16, 15]. These studies typically generate
parameters randomly within a given range [21, 19, 20, 22] and use 10 to 100
arms [19, 20, 21, 22, 16]. We follow this approach and set the parameter
ranges to those used in related work.

#### Social-media advertisement data.

We also evaluate our policy in a social media advertisement scenario described
in Example 1. We use real-world data from [9]. It contains information about
different ads based on their target gender (female or male) and age category
(30–34, 34–39, 40–44, 45–49), along with the number of displays and clicks,
the total cost, and the number of purchases. We group the ads by target gender
and age category, resulting in 19 “advertisement campaigns” (Budgeted MAB
settings). Each campaign has between 2 and 93 ads (arms). We compute the
expected rewards $\mu_{k}^{r}$ and costs $\mu_{k}^{c}$ of each ad as the
average revenue per click and average cost per click, respectively. We model
both discrete and continuous rewards and costs. For the discrete case, we
sample rewards and costs from two Bernoulli distributions with expected values
of $\mu_{k}^{r}$ and $\mu_{k}^{c}$, respectively. In the continuous case, we
use a Beta distribution and sample the distribution parameters from a uniform
distribution with a range of (0, 5). We then adjust one of the parameters to
ensure that the expected values of rewards and costs match $\mu_{k}^{r}$ and
$\mu_{k}^{c}$.

Table 1: Our evaluation settings Type | Distribution | Parameters | K | Used in | Id
---|---|---|---|---|---
Synthetic | Bernoulli | $\mathcal{U}(0,1)$ | 10 | [20, 21] | S-Br-10
50 | [21] | S-Br-50
100 | [19, 20] | S-Br-100
Generalized Bernoulli | $\mathcal{U}(0,1)$ | 10 | [20, 22] | S-GBr-10
50 | [22] | S-GBr-50
100 | [20] | S-GBr-100
Beta | $\mathcal{U}(0,5)$ | 10 | [21, 22] | S-Bt-10
50 | [21, 22] | S-Bt-50
100 | [19] | S-Bt-100
Facebook | Bernoulli | given | $[2,97]$ | – | FB-Br
Beta | randomized | $[2,97]$ | – | FB-Bt

###  5.2 Budgeted MAB policies

We test the performance of two variants of our policy: $\omega$-UCB and
$\omega^{*}$-UCB. The $\omega$-UCB variant uses a fixed value of $\eta=1$ for
rewards and costs. The $\omega^{*}$-UCB uses $\eta_{k}^{r}=\eta_{k}^{c}=1$ as
default but estimates their values from data once arm $k$ has been played
sufficiently many times ($n_{k}(T)\geq 30$),

$\bar{\eta}_{k}=\frac{\bar{\sigma}_{k}^{2}}{(M-\bar{\mu}_{k})(\bar{\mu}_{k}-m)},$
(16)

where bars refer to sample estimates as before. We experiment with two values
of the hyperparameter $\rho$: $\rho=1$ and $\rho={1}/{4}$. The former is the
minimum value for which we have proven logarithmic regret. The latter has
performed well in our sensitivity study, as we will demonstrate in Section
6.2.

We compare the performance of our policy to several other state-of-the-art
Budgeted MAB policies, including BTS, Budget-UCB, i-UCB, c-UCB, m-UCB,
b-greedy, and UCB-SC+. We set the hyperparameters for each competitor to the
values recommended in their respective papers. Appendix 8.8 features details
about the policies and their hyperparameters.

##  6 Results

To observe the asymptotic behavior of the policies, we set the budget $B$ to
$1.5\cdot 10^{5}$ times the minimum expected cost. We report the average
results over 100 independent repetitions and use the repetition index as the
seed for the random number generator. Since in each repetition of the
experiment, we draw the expected cost $\mu_{k}^{c}$ and expected reward
$\mu_{k}^{r}$ uniformly at random, we normalize the budget in our graphs.
Section 6.1 compares the performance of our policy and its competitors.
Section 6.2 examines the sensitivity of $\omega$-UCB and $\omega^{*}$-UCB to
the hyperparameter $\rho$. Note that some graphs (the ones in Figure 3) omit
confidence intervals for better accessibility. The complete graphs with 95%
confidence intervals are available in Appendix 8.9.

###  6.1 Performance of Budgeted MAB policies

#### Synthetic Bernoulli.

Figure 3(a) shows the regret of the policies for Bernoulli-distributed rewards
and costs. Blue lines display results for $\omega$-UCB, while grey lines stand
for other policies. We do not present $\omega^{*}$-UCB in this experiment
since its results are almost identical to $\omega$-UCB. $\omega$-UCB and BTS
achieve logarithmic regret and demonstrate better asymptotic behavior than
other methods. Although m-UCB, c-UCB, and i-UCB may outperform $\omega$-UCB
with $\rho=1$ for small budgets, their regret grows rapidly as the budget
increases, indicating poor asymptotic behavior. For $K=50$ and $K=100$, our
policy has lower regret than BTS. BTS outperforms $\omega$-UCB with $\rho=1$
only on the 10-armed bandit. $\omega$-UCB with $\rho={1}/{4}$ outperforms all
other policies on small and large budgets and regardless of $K$. Comparing
$\rho=1/4$ with $\rho=1$, it seems that the former balances exploration and
exploitation more effectively than the latter, leading to lower regret across
all our experiments.

#### Synthetic Generalized Bernoulli and synthetic Beta.

Figure 3(b) shows the regret of the policies for rewards and costs drawn from
Generalized Bernoulli distributions and Figure 3(c) for Beta distributed
rewards and costs. Besides $\omega$-UCB, we also present the results for
$\omega^{*}$-UCB which estimates $\eta_{k}^{r}$ and $\eta_{k}^{c}$ from the
observed sample variance of rewards and costs. $\omega$-UCB and
$\omega^{*}$-UCB with $\rho={1}/{4}$ outperform their competitors, except for
$K=100$ in the Beta bandit where m-UCB performs comparable. We further notice
that BTS is not competitive in this evaluation setting, likely because the
policy cannot account for the (often very small) variance of the sampled Beta
distributions. Our $\omega^{*}$-UCB policy is advantageous in such cases.

(a) Settings S-Br-$\\{10,50,100\\}$

(b) Settings S-GBr-$\\{10,50,100\\}$

(c) Settings S-Bt-$\\{10,50,100\\}$

(d) Setting FB-Br

(e) Setting FB-Bt

(f) Example kde of $\mu_{k}^{r},\mu_{k}^{c}$

Figure 3: Evaluation results; refer to Figure 5 in Section 8.9 for graphs with
confidence intervals

#### Social-media advertisement data.

Figure 3(d) and Figure 3(e) show the results of our study on social-media
advertisement data [9]. On this real world data set, our default choice of
$\rho={1}/{4}$ outperforms all other competitors. $\rho=1/4$ also outperforms
$\rho=1$ significantly, although both choices show good asymptotic behavior.
Further, the advertisement data settings seem to be easier for some
competitors (BTS, KL-UCB-SC+) and harder for others (i,c,m-UCB). The likely
cause is that the distribution of expected rewards and costs between arms is
non-uniform: costs are biased towards 1, and rewards are biased towards the
boundaries of $[0,1]$, as the kde plot for the MAB with $K=33$ in Figure 3(f)
illustrates exemplary. Last, we observe that $\omega^{*}$-UCB has lower regret
than $\omega$-UCB, although the effect is not as prominent as in the synthetic
settings.

###  6.2 Sensitivity study

We investigate the performance difference between $\omega$-UCB and
$\omega^{*}$-UCB, as well as the sensitivity of our policy with respect to the
hyperparameter $\rho$. The results based on our synthetic settings (cf. Table
1) are shown in Figure 4. $\omega$-UCB and $\omega^{*}$-UCB perform best with
$\rho={1}/{4}$ when rewards and costs follow Bernoulli distributions. Both
policies achieve comparable performance in this case. It appears that
estimating $\eta$ (which is known to be 1 in Bernoulli bandits) does not
result in a performance decrease of $\omega^{*}$-UCB compared to $\omega$-UCB.
Also, even though $\rho={1}/{8}$ works well for $\omega$-UCB when rewards and
costs follow a generalized Bernoulli or Beta distribution, $\rho={1}/{4}$
remains a near-optimal choice for $\omega^{*}$-UCB. Based on these results, we
recommend using $\omega^{*}$-UCB with $\rho={1}/{4}$ as a default.

Figure 4: Sensitivity study showing the regret w.r.t. different choices of
$\rho$

##  7 Conclusions

We have presented a new approach for Budgeted MABs called $\omega$-UCB. It
combines UCB sampling with asymmetric confidence intervals to address issues
of existing approaches. Our interval generalizes Wilson’s score interval to
arbitrary bounded random variables. An extension of our approach,
$\omega^{*}$-UCB, tracks the variance of the reward and cost distributions on
the fly to tighten the confidence intervals. This leads to even better
performance when rewards or costs are continuous. Our analysis shows that
$\omega$-UCB achieves logarithmic regret for $\rho\geq 1$, while
$\rho={1}/{4}$ performed best in our experiments. In the future, we plan to
extend our approach to the non-stationary setting where the reward and cost
distributions change over time. This is particularly relevant in scenarios
like online advertising, where companies want to promote their products and
services continuously.

## Acknowledgments and Disclosure of Funding

This work was supported by the DFG Research Training Group 2153: “Energy
Status Data — Informatics Methods for its Collection, Analysis and
Exploitation”.

## References

  * [1] Danilo Ardagna, Barbara Panicucci, and Mauro Passacantando.  A game theoretic formulation of the service provisioning problem in cloud systems.  In WWW, pages 177–186. ACM, 2011.
  * [2] Peter Auer, Nicolò Cesa-Bianchi, and Paul Fischer.  Finite-time Analysis of the Multiarmed Bandit Problem.  Mach. Learn., 47(2-3):235–256, 2002.
  * [3] Ashwinkumar Badanidiyuru, Robert Kleinberg, and Aleksandrs Slivkins.  Bandits with Knapsacks.  In FOCS, pages 207–216. IEEE Computer Society, 2013.
  * [4] Orna Agmon Ben-Yehuda, Muli Ben-Yehuda, Assaf Schuster, and Dan Tsafrir.  Deconstructing Amazon EC2 Spot Instance Pricing.  ACM Trans. Economics and Comput., 1(3):16:1–16:20, 2013.
  * [5] Rajendra Bhatia and Chandler Davis.  A better bound on the variance.  American Mathematical Monthly, 107(4):353–357, 2000.
  * [6] Christian Borgs, Jennifer T. Chayes, Nicole Immorlica, Kamal Jain, Omid Etesami, and Mohammad Mahdian.  Dynamics of bid optimization in online advertisement auctions.  In WWW, pages 531–540. ACM, 2007.
  * [7] Tanmoy Chakraborty, Eyal Even-Dar, Sudipto Guha, Yishay Mansour, and S. Muthukrishnan.  Selective Call Out and Real Time Bidding.  In WINE, volume 6484 of Lecture Notes in Computer Science, pages 145–157. Springer, 2010.
  * [8] Wenkui Ding, Tao Qin, Xu-Dong Zhang, and Tie-Yan Liu.  Multi-Armed Bandit with Budget Constraint and Variable Costs.  In AAAI, volume 27, pages 232–238. AAAI Press, 2013.
  * [9] Madis Lemsalu.  Facebook ad campaign, 2017.  howpublished: Kaggle (https://www.kaggle.com/madislemsalu/facebook-ad-campaign).
  * [10] HM Schöpf and PH Supancic.  On Bürmann’s theorem and its application to problems of linear and nonlinear heat transfer and diffusion.  The Mathematica Journal, 16:1–44, 2014.
  * [11] 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.
  * [12] William Robin Thompson.  On the Theory of Apportionment.  American Journal of Mathematics, 57:450, 1935.
  * [13] Long Tran-Thanh, Archie C. Chapman, Enrique Munoz de Cote, Alex Rogers, and Nicholas R. Jennings.  Epsilon-First Policies for Budget-Limited Multi-Armed Bandits.  In AAAI, volume 24. AAAI Press, 2010.
  * [14] Long Tran-Thanh, Archie C. Chapman, Alex Rogers, and Nicholas R. Jennings.  Knapsack Based Optimal Policies for Budget-Limited Multi-Armed Bandits.  In AAAI, volume 26, pages 1134–1140. AAAI Press, 2012.
  * [15] Ryo Watanabe, Junpei Komiyama, Atsuyoshi Nakamura, and Mineichi Kudo.  KL-UCB-Based Policy for Budgeted Multi-Armed Bandits with Stochastic Action Costs.  IEICE Trans. Fundam. Electron. Commun. Comput. Sci., 100-A(11):2470–2486, 2017.
  * [16] Ryo Watanabe, Junpei Komiyama, Atsuyoshi Nakamura, and Mineichi Kudo.  UCB-SC: A Fast Variant of KL-UCB-SC for Budgeted Multi-Armed Bandit Problem.  IEICE Trans. Fundam. Electron. Commun. Comput. Sci., 101-A(3):662–667, 2018.
  * [17] E.T. Whittaker and G.N. Watson.  A course of modern analysis; an introduction to the general theory of infinite processes and of analytic functions.  Cambridge University Press, Cambridge, 4 edition, 2020.  Pages: 208 Section: 7 tex.key: Theorem 7.3 (Bürmann’s theorem).
  * [18] Edwin B. Wilson.  Probable Inference, the Law of Succession, and Statistical Inference.  Journal of the American Statistical Association, 22(158):209–212, 1927.
  * [19] Yingce Xia, Wenkui Ding, Xu-Dong Zhang, Nenghai Yu, and Tao Qin.  Budgeted Bandit Problems with Continuous Random Costs.  In ACML, volume 45 of JMLR Workshop and Conference Proceedings, pages 317–332. JMLR.org, 2015.
  * [20] Yingce Xia, Haifang Li, Tao Qin, Nenghai Yu, and Tie-Yan Liu.  Thompson Sampling for Budgeted Multi-Armed Bandits.  In IJCAI, pages 3960–3966. AAAI Press, 2015.
  * [21] Yingce Xia, Tao Qin, Wenkui Ding, Haifang Li, Xudong Zhang, Nenghai Yu, and Tie-Yan Liu.  Finite budget analysis of multi-armed bandit problems.  Neurocomputing, 258:13–29, 2017.
  * [22] Yingce Xia, Tao Qin, Weidong Ma, Nenghai Yu, and Tie-Yan Liu.  Budgeted Multi-Armed Bandits with Multiple Plays.  In IJCAI, pages 2210–2216. IJCAI/AAAI Press, 2016.

##  8 Appendix

###  8.1 Proof of Theorem 1

Recall Theorem 1: See 1

###### Proof.

Using the central limit theorem and Bhatia-Davis inequality, we follow similar
steps as [18]. We first handle the case where $\mu\in(m,M)$. We then address
the edge cases $\mu=m$ and $\mu=M$.

#### Case $\mu\in(m,M)$.

The central limit theorem states that for a large enough sample size,
$\bar{\mu}$ approximately follows a normal distribution with mean $\mu$ and
variance $\frac{\sigma^{2}}{n}$. I.e.,

$\bar{\mu}\sim\mathcal{N}\left(\mu,\sqrt{\frac{\sigma^{2}}{n}}\right)\
\Longleftrightarrow\
\frac{\bar{\mu}-\mu}{\sqrt{\frac{\sigma^{2}}{n}}}\sim\mathcal{N}(0,1).$ (17)

Therefore, $\bar{\mu}$ likely falls into an interval that is centered around
$\mu$ and scaled by $\sigma$. The value $z$ is the number of standard
deviations such that $\bar{\mu}$ falls out of the corresponding confidence
interval with a probability of $\alpha$.

$\Pr[\bar{\mu}\not\in\left[\mu-\frac{\sigma}{\sqrt{n}}z,\mu+\frac{\sigma}{\sqrt{n}}z\right]]=\alpha$
(18)

Next, we apply the Bhatia-Davis inequality [5] to express $\sigma$ as a
function of $\mu$. It states that $\sigma^{2}\leq(M-\mu)(\mu-m)$. Hence there
exists a factor $\eta\in[0,1]$ such that

$\sigma^{2}=\eta(M-\mu)(\mu-m).$ (19)

This gives us an expression for the interval bounds in Eq. (18) that is
quadratic w.r.t. $\mu$:

$(\bar{\mu}-\mu)^{2}=\frac{\sigma^{2}}{n}z^{2}=\frac{\eta(M-\mu)(\mu-m)}{n}z^{2}$
(20)

Solving Eq. (20) for $\mu$ yields the endpoints $\omega_{-}(\alpha)$ and
$\omega_{+}(\alpha)$ of our confidence interval:

$\Pr[\mu\not\in\left[\omega_{-}(\alpha),\omega_{+}(\alpha)\right]]=\alpha$
(21)

with

$\omega_{-}(\alpha),\omega_{+}(\alpha)=\frac{B}{2A}\pm\sqrt{\frac{B^{2}}{4A^{2}}-\frac{C}{A}}$
(22)

and

$A=n+z^{2}\eta,\quad B=2n\bar{\mu}+z^{2}\eta(M+m),\quad
C=n\bar{\mu}^{2}+z^{2}\eta Mm.$ (23)

#### Cases $\mu=m$ and $\mu=M$.

For $\mu=m$ (the case for $\mu=M$ is analogous), the probability that $\mu$ is
not in the confidence interval $[\omega_{-}(\alpha),\omega_{+}(\alpha)]$ is
zero, which is less than $\alpha$. Additionally, we have
$\sigma^{2}=(M-\mu)(\mu-m)=0$, which implies that Eq. (19) holds for any
choice of $\eta$. However, since $\mu$ is an unknown quantity, we can never be
certain that $\mu=m$ based on some sample from $X$. In the worst-case
scenario, $X$ is a random variable that takes only extreme values, i.e.,
$X\in\\{m,M\\}$, with $\mu$ greater than and approximately equal to $m$. In
this case, $\eta=1$ by definition. Hence, we define $\eta=1$ for
$\mu\in{m,M}$. Combining the special case that $\mu\in\\{m,M\\}$ with the
result from the previous paragraph gives Theorem 1.

Our interval is a generalization of Wilson’s score interval for Binomial
proportions [18]. One can recover its original formulation by setting
$\eta=1,m=0,M=1$. We refer to Section 4.1 for a more in-depth discussion of
our result. ∎

###  8.2 Proof of Theorem 2

Recall Theorem 2: See 2

###### Proof.

Define the following independent events:

$E1\coloneqq\mu^{r}>\omega^{r}_{+}(\alpha)\quad
E2\coloneqq\mu^{c}<\omega^{c}_{-}(\alpha)$ (24)

We decompose $\Pr[\frac{\mu_{1}}{\mu_{2}}>\Omega(\alpha)]$ using $E1$ and
$E2$:

$\begin{split}\Pr[\frac{\mu^{r}}{\mu^{c}}>\Omega(\alpha)]&=\Pr[\frac{\mu^{r}}{\mu^{c}}>\frac{\omega_{+}^{r}(\alpha)}{\omega_{-}^{c}(\alpha)}]\\\
&\leq 1-\Pr[\neg E1\cap\neg E2]=1-\Pr[\neg E1]\Pr[\neg E2]\\\
&=\Pr[E1]+\Pr[E2]-\Pr[E1]\Pr[E2]\\\ &\leq\Pr[E1]+\Pr[E2]\end{split}$ (25)

From Theorem 1 and by the symmetry of the normal distribution,
$\Pr[E1]=\Pr[E2]=\frac{1}{2}\alpha$. Therefore,

$\Pr[\frac{\mu^{r}}{\mu^{c}}>\Omega(\alpha)]\leq\alpha$ (26)

∎

###  8.3 Proof of Theorem 3

Recall Theorem 3:

See 3

###### Proof.

We start from Theorem 1 and equate the confidence level $1-\alpha$ of the
individual reward and cost distributions to the number of standard deviations
$z$. This involves the cumulative density function (cdf) of the standard
normal distribution. We then replace the cdf with an approximation that has a
closed form solution for $z$. Our choice of $z$ cancels out the exponential
term in this approximation, similar to the UCB1-policy [2]. Last, we apply
Theorem 2 to obtain the final result.

#### Step 1.

We relate the confidence level $1-\alpha(t)$ at time $t$ to the cumulative
density function of the standard normal distribution:

$1-\frac{\alpha(t)}{2}=\frac{1}{2}\left(1+\text{erf}\left(\frac{z}{\sqrt{2}}\right)\right)$
(27)

Solving for $\alpha(t)$ yields:

$\alpha(t)=1-\mathrm{erf}\left(\frac{z}{\sqrt{2}}\right)$ (28)

#### Step 2.

We now replace the error function $\text{erf}\left(\frac{z}{\sqrt{2}}\right)$
in the equation above with a series expansion based on Bürmann’s theorem [10,
17]; we summarize all but the first addend in a remainder term
$\gamma\left(\frac{z}{\sqrt{2}}\right)>0$. This term has a maximum of
$\gamma(0.71)\approx 0.0554$ and approaches 0 for larger $z$:

$\alpha(t)=1-\left(\sqrt{1-\exp{-\frac{z^{2}}{2}}}+\gamma\left(\frac{z}{\sqrt{2}}\right)\right)$
(29)

Omitting the $\gamma$-term gives an upper bound for $\alpha(t)$:

$\alpha(t)<1-\sqrt{1-\exp{-\frac{z^{2}}{2}}}$ (30)

#### Step 3.

Next, we choose $z$ as a function of $\log t$ and $\rho>0$,
$z_{\rho}(t)=\sqrt{2\rho\log t}$. This results in a time-increasing confidence
level $1-\alpha(t)$:

$\Pr[\mu\not\in\left[\omega_{-}(\alpha(t)),\omega_{+}(\alpha(t))\right]]\leq\alpha(t)\text{
with }\alpha(t)<1-\sqrt{1-t^{-\rho}}$ (31)

#### Step 4.

Applying Theorem 2 gives

$\Pr[\frac{\mu_{k}^{r}}{\mu_{k}^{c}}>\Omega_{k}(\alpha,t)]\leq\alpha(t)\text{
with }\alpha(t)<1-\sqrt{1-t^{-\rho}}.$ (32)

The complementary event, $\Omega_{k}(\alpha,t)\geq\mu_{k}^{r}/\mu_{k}^{c}$,
holds with a probability of at least $1-\alpha(t)$,

$\Pr[\Omega_{k}(\alpha,t)\geq\frac{\mu_{k}^{r}}{\mu_{k}^{c}}]\geq
1-\alpha(t)\text{ with }\alpha(t)<1-\sqrt{1-t^{-\rho}},$ (33)

which is the result given in Theorem 3.

∎

###  8.4 Proof of Theorem 4

Recall Theorem 4:

See 4

###### Proof.

The proof starts with a general expression for the number of plays of a
suboptimal arm $k>1$, where $\mathds{1}\\{\cdot\\}$ denotes the indicator
function.

$n_{k}(\tau)\leq
1+\operatorname{\sum_{t=K+1}^{\tau}}\mathds{1}\left\\{\Omega_{k}(t)\geq\Omega_{j}(t),\forall
j\neq i\right\\}\leq
1+\operatorname{\sum_{t=K+1}^{\tau}}\mathds{1}\left\\{\Omega_{k}(t)\geq\Omega_{1}(t)\right\\}$
(34)

This is upper-bounded by

$\displaystyle n_{k}(\tau)$ $\displaystyle\leq
1+\operatorname{\sum_{t=K+1}^{\tau}}\bigg{[}\mathds{1}\left\\{\Omega_{k}(t)\geq\Omega_{1}(t),\Omega_{1}(t)<\frac{\mu_{1}^{r}}{\mu_{1}^{c}}\right\\}+\mathds{1}\left\\{\Omega_{k}(t)\geq\Omega_{1}(t),\Omega_{1}(t)\geq\frac{\mu_{1}^{r}}{\mu_{1}^{c}}\right\\}\bigg{]}$
(35) $\displaystyle\leq
1+\operatorname{\sum_{t=K+1}^{\tau}}\bigg{[}\mathds{1}\left\\{\Omega_{1}(t)<\frac{\mu_{1}^{r}}{\mu_{1}^{c}}\right\\}+\mathds{1}\left\\{\Omega_{k}(t)\geq\frac{\mu_{1}^{r}}{\mu_{1}^{c}}\right\\}\bigg{]}$
(36)

The expected number of plays $\mathbb{E}[n_{k}(\tau)]$ is given by the
probabilities of the individual events:

$\mathbb{E}[n_{k}(\tau)]\leq
1+\operatorname{\sum_{t=K+1}^{\tau}}\bigg{[}\underbrace{\Pr\left\\{\Omega_{1}(t)<\frac{\mu_{1}^{r}}{\mu_{1}^{c}}\right\\}}_{\Pr[A]}+\underbrace{\Pr\left\\{\Omega_{k}(t)\geq\frac{\mu_{1}^{r}}{\mu_{1}^{c}}\right\\}}_{\Pr[B]}\bigg{]}.$
(37)

We now evaluate the sum in the equation above.

#### Sum of $\Pr[A]$.

We apply Theorem 2:

$\operatorname{\sum_{t=K+1}^{\tau}}\Pr[A]<\operatorname{\sum_{t=K+1}^{\tau}}\left[1-\sqrt{1-t^{-\rho}}\right]=(\tau-K)-\operatorname{\sum_{t=K+1}^{\tau}}\sqrt{1-t^{-\rho}}$
(38)

#### Sum of $\Pr[B]$.

For this step, let us first introduce a helpful lemma: Lemma 1 bounds
$\Pr[\Omega_{k}(t)\geq\mu_{1}^{r}/\mu_{1}^{c}]$ after a minimum number of
plays $n_{k}^{*}(\tau)$, which grows logarithmic with $\tau$.

######  Lemma 1.

Define $\delta_{k}=\frac{\Delta_{k}}{\Delta_{k}+1/\mu_{k}^{c}}$ and
$n_{k}^{*}(\tau)$ as follows:

$n_{k}^{*}(\tau)=\frac{8\rho\log\tau}{\delta_{k}^{2}}\max\left\\{\frac{\eta_{k}^{r}\mu_{k}^{r}}{1-\mu_{k}^{r}},\frac{\eta_{k}^{c}(1-\mu_{k}^{c})}{\mu_{k}^{c}}\right\\}$
(39)

The following inequality holds whenever $n_{k}(t)\geq n_{k}^{*}(\tau)$:

$\Pr[\Omega_{k}(t)\geq\frac{\mu_{1}^{r}}{\mu_{1}^{c}}]<1-\sqrt{1-\tau^{-\rho}}$
(40)

Appendix 8.6 contains the proof of Lemma 1. See Appendix 8.5 for the
derivation of $\delta_{k}$.

The lemma allows to decompose $\operatorname{\sum_{t=K+1}^{\tau}}\Pr[B]$ into
“initial plays” ($n_{k}(t)<n_{k}^{*}(\tau)$) and “later plays” ($n_{k}(t)\geq
n_{k}^{*}(\tau)$):

$\operatorname{\sum_{t=K+1}^{\tau}}\Pr[B]=\operatorname{\sum_{t=K+1}^{\tau}}\Pr\left\\{\Omega_{k}(t)\geq\frac{\mu_{1}^{r}}{\mu_{1}^{c}}\right\\}=n_{k}^{*}(\tau)+\operatorname{\sum_{t=K+1}^{\tau}}\Pr\left\\{\Omega_{k}(t)\geq\frac{\mu_{1}^{r}}{\mu_{1}^{c}},n_{k}(\tau)\geq
n_{k}^{*}(\tau)\right\\}$ (41)

We now apply Lemma 1 to evaluate the sum in above equation,

$\operatorname{\sum_{t=K+1}^{\tau}}\Pr[B]\leq
n_{k}^{*}(\tau)+\operatorname{\sum_{t=K+1}^{\tau}}\left[1-\sqrt{1-\tau^{-\rho}}\right]=n_{k}^{*}(\tau)+(\tau-K)\left(1-\sqrt{1-\tau^{-\rho}}\right).$
(42)

Inserting the results of Eq. (38) and Eq. (42) in Eq. (37) yields a bound on
$\mathbb{E}[n_{k}(\tau)]$:

$\displaystyle\mathbb{E}[n_{k}(\tau)]\leq
1+n_{k}^{*}(\tau)+\underbrace{\left(\tau-K\right)\left(2-\sqrt{1-\tau^{-\rho}}\right)-\operatorname{\sum_{t=K+1}^{\tau}}\sqrt{1-t^{-\rho}}}_{\xi(\tau,\rho)}$
(43)

∎

###  8.5 Derivation of Proportional $\delta$-gap

Let $\delta_{k}$ be the proportional $\delta$-gap of arm $k$. It measures how
much one must increase $\mu_{k}^{r}$ and decrease $\mu_{k}^{c}$ in order to
make arm $k$ have the same reward-cost ratio as arm 1, or in other words, to
bridge the suboptimality gap $\Delta_{k}$ between arm $k$ and arm 1. The
$\delta$-gap is proportional to the possible increase in rewards (decrease in
costs) without violating their range $[0,1]$. We start our derivation with Eq.
(44), which states this mathematically.

$\frac{\mu_{k}^{r}+\delta_{k}(1-\mu_{k}^{r})}{\mu_{k}^{c}-\delta_{k}\mu_{k}^{c}}=\frac{\mu_{1}^{r}}{\mu_{1}^{c}}$
(44)

Rearranging the equation yields

$\frac{\mu_{1}^{r}}{\mu_{1}^{c}}-\frac{\mu_{k}^{r}}{\mu_{k}^{c}}=\delta_{k}\left(\frac{\mu_{1}^{r}}{\mu_{1}^{c}}-\frac{\mu_{k}^{r}}{\mu_{k}^{c}}+\frac{1}{\mu_{k}^{c}}\right).$
(45)

Now, recall the definition of an arm’s suboptimality,
$\Delta_{k}=\frac{\mu_{1}^{r}}{\mu_{1}^{c}}-\frac{\mu_{k}^{r}}{\mu_{k}^{c}}$,
and solve for $\delta_{k}$:

$\delta_{k}=\frac{\Delta_{k}}{\Delta_{k}+\frac{1}{\mu_{k}^{c}}}$ (46)

###  8.6 Proof of Lemma 1

Recall Lemma 1: See 1

###### Proof.

The proof is structured in four steps. First, we derive an expression for the
maximum deviation between the observed sample mean and the unknown expected
value of an arm’s rewards and costs that we use later on. Second, we decompose
the probability $\Pr[\Omega_{k}(t)\geq\mu_{1}^{r}/\mu_{1}^{c}]$. Third, we
evaluate the decomposed probabilities for cases where $n_{k}(t)$ is
sufficiently large, that is, $n_{k}(t)\geq n_{k}^{*}(\tau)$. Finally, we
recombine the decomposed probabilities to obtain the final result.

#### Deviation between sample mean and expected value.

Let $\bar{\mu}_{k}(t)$ be the sample mean and $\mu_{k}$ the expected value of
arm $k$’s rewards or costs at time $t$. To quantify the deviation between mean
$\bar{\mu}_{k}(t)$ and $\mu_{k}$ we start from Eq. (20) (central limit
theorem) and set $[m,M]=[0,1]$ and $n=n_{k}(t)$):

$(\bar{\mu}_{k}(t)-\mu_{k})^{2}\leq\frac{\eta_{k}\mu_{k}(1-\mu_{k})}{n_{k}(t)}z^{2}$
(47)

The above inequality holds with the same probability as our confidence
interval since it is the basis of the confidence interval derivation.222This
observation is commonly known as “interval equality principle”. This allows us
to bound the deviation between sample mean and expected value, denoted
$\varepsilon_{k}(t)$, for our choice of $z_{\rho}(t)=\sqrt{2\rho\log t}$:

$\Pr[\lvert\bar{\mu}_{k}(t)-\mu_{k}\rvert>\varepsilon_{k}(t)]\leq\alpha(t)\text{
with }\varepsilon_{k}(t)=\sqrt{\frac{2\eta_{k}\mu_{k}(1-\mu_{k})\rho\log
t}{n_{k}(t)}}\text{ and }\alpha(t)<1-\sqrt{1-t^{-\rho}}$ (48)

Whenever we refer to $\varepsilon_{k}(t)$ w.r.t. rewards or costs we use the
notations $\varepsilon_{k}^{r}(t)$ and $\varepsilon_{k}^{c}(t)$.

#### Decomposition of $\Pr[\Omega_{k}(t)\geq{\mu_{1}^{r}}/{\mu_{1}^{c}}]$.

Next, we decompose the probability that
$\Omega_{k}(t)\geq{\mu_{1}^{r}}/{\mu_{1}^{c}}$. The decomposition is analogous
to the one in the proof of Theorem 2 and thus omitted here:

$\displaystyle\Pr[\Omega_{k}(t)\geq\frac{\mu_{1}^{r}}{\mu_{1}^{c}}]$
$\displaystyle=\Pr[\frac{\omega_{k+}^{r}(t)}{\omega_{k-}^{c}(t)}\geq\frac{\mu_{1}^{r}}{\mu_{1}^{c}}]=\Pr[\frac{\omega_{k+}^{r}(t)}{\omega_{k-}^{c}(t)}\geq\frac{\mu_{k}^{r}+(1-\mu_{k}^{r})\delta_{k}}{\mu_{k}^{c}-\mu_{k}^{c}\delta_{k}}]$
(49)
$\displaystyle\leq\Pr[\omega_{k+}^{r}(t)\geq\mu_{k}^{r}+(1-\mu_{k}^{r})\delta_{k}]+\Pr[\omega_{k-}^{c}(t)\leq\mu_{k}^{c}-\mu_{k}^{c}\delta_{k}]$
(50)

For the next step, note that if $\mu_{k}^{r}\leq\omega_{k+}^{r}(t)$ (and
$\mu_{k}^{c}\geq\omega_{k-}^{c}(t)$), we have that
$\mu_{k}^{r}-\bar{\mu}^{r}_{k}(t)\leq\varepsilon^{r}_{k}(t)$ (and
$\bar{\mu}^{c}_{k}(t)-\mu_{k}^{c}\leq\varepsilon_{k}^{c}(t)$). This allows us
to rewrite the terms in Eq. (50) as follows:

$\begin{split}\Pr[\omega_{k+}^{r}(t)\geq\mu_{k}^{r}+(1-\mu_{k}^{r})\delta_{k}]&=\Pr[\mu_{k}^{r}+(1-\mu_{k}^{r})\delta_{k}-\bar{\mu}^{r}_{k}(t)\leq\varepsilon_{k}^{r}(t)]\\\
&=\Pr[\bar{\mu}^{r}_{k}(t)-\mu_{k}^{r}\geq(1-\mu_{k}^{r})\delta_{k}-\varepsilon_{k}^{r}(t)]\end{split}$
(51)
$\begin{split}\Pr[\omega_{k-}^{c}(t)\leq\mu_{k}^{c}-\mu_{k}^{c}\delta_{k}]&=\Pr[\bar{\mu}^{c}_{k}(t)-(\mu_{k}^{c}-\mu_{k}^{c}\delta_{k})\leq\varepsilon_{k}^{c}(t)]\\\
&=\Pr[\mu_{k}^{c}-\bar{\mu}^{c}_{k}(t)\geq\mu_{k}^{c}\delta_{k}-\varepsilon_{k}^{c}(t)]\end{split}$
(52)

In the next two paragraphs, we evaluate Eq. (51) (confidence bound of rewards)
and Eq. (52) (confidence bound of costs). We combine both results afterwards.

#### Evaluation of Eq. (51) for $n_{k}(t)\geq n_{k}^{*,r}(\tau)$.

We now consider the cases in which the number of times arm $k$ was played is
at least logarithmic w.r.t. $\tau$, i.e., $n_{k}(t)\geq n_{k}^{*,r}(\tau)$
with

$n_{k}^{*,r}(\tau)=\frac{2\rho\log\tau}{\delta_{k}^{2}(1-\kappa)^{2}}\frac{\eta_{k}^{r}\mu_{k}^{r}}{1-\mu_{k}^{r}},\quad\text{for
any }\kappa\in(0,1).$ (53)

In those cases,
$\varepsilon_{k}^{r}(t)\leq(1-\kappa)\delta_{k}(1-\mu_{k}^{r})$. One can
verify this by inserting $n_{k}^{*,r}(\tau)$ in the definition of
$\varepsilon_{k}^{r}(t)$, cf. Eq. (48). This gives the following inequality
for the right side of Eq. (51):

$\Pr[\omega_{k+}^{r}(t)\geq\mu_{k}^{r}+(1-\mu_{k}^{r})\delta_{k}]\leq\Pr[\bar{\mu}^{r}_{k}(t)-\mu_{k}^{r}\geq\kappa(1-\mu_{k}^{r})\delta_{k}]$
(54)

Last, we compute the number of standard deviations $z^{*}$ that corresponds to
a deviation between $\bar{\mu}^{r}_{k}(t)$ and $\mu_{k}^{r}$ of at maximum
$\kappa(1-\mu_{k}^{r})\delta_{k}$ based on Eq. (47). In particular, we solve
the right-most inequality in the expression below:

$(\bar{\mu}^{r}_{k}(t)-\mu_{k}^{r})^{2}\leq\frac{\eta_{k}^{r}\mu_{k}^{r}(1-\mu_{k}^{r})}{n_{k}(\tau)}{z^{*}}^{2}\leq\frac{\eta_{k}^{r}\mu_{k}^{r}(1-\mu_{k}^{r})}{n_{k}^{*,r}(\tau)}{z^{*}}^{2}\leq(\kappa(1-\mu_{k}^{r})\delta_{k})^{2}$
(55)

With our choice of $n_{k}^{*,r}(\tau)$, this yields
$z^{*}=\left(2\rho\log\tau\kappa^{2}(1-\kappa)^{-2}\right)^{\frac{1}{2}}$.
Inserting $z^{*}$ in Eq. (30) (upper bound for $\alpha(t)$) results in the
following bound:

$\Pr[\omega_{k+}^{r}(t)\geq\mu_{k}^{r}+(1-\mu_{k}^{r})\delta_{k}]<\frac{1}{2}\left(1-\sqrt{1-\tau^{-\frac{\kappa^{2}\rho}{(1-\kappa)^{2}}}}\right)$
(56)

#### Evaluation of Eq. (52) for $n_{k}(t)>n_{k}^{*,c}(\tau)$.

Again, we consider the cases in which the number of times arm $k$ was played
is at least logarithmic in $\tau$, i.e., $n_{k}(t)\geq n_{k}^{*,c}(\tau)$ with

$n_{k}^{*,c}(\tau)=\frac{2\rho\log\tau}{\delta_{k}^{2}(1-\kappa)^{2}}\frac{\eta_{k}^{c}(1-\mu_{k}^{c})}{\mu_{k}^{c}},\quad\kappa\in(0,1).$
(57)

In those cases, $\varepsilon_{k}^{c}(t)\leq(1-\kappa)\delta_{k}\mu_{k}^{c}$.
Following analogous steps as in the previous paragraph yields Eq. (58):

$\Pr[\omega_{k-}^{c}(t)\leq\mu_{k}^{c}-\mu_{k}^{c}\delta_{k}]<\frac{1}{2}\left(1-\sqrt{1-\tau^{-\frac{(1-\kappa)^{2}\rho}{\kappa^{2}}}}\right)$
(58)

#### Obtaining the final result.

With the results in Eq. (56) and Eq. (58) we can finally evaluate Eq. (49). A
choice of $\kappa=0.5$ and

$n_{k}^{*}(\tau)=\frac{8\rho\log\tau}{\delta_{k}^{2}}\max\left\\{\frac{\eta_{k}^{r}\mu_{k}^{r}}{1-\mu_{k}^{r}},\frac{\eta_{k}^{c}(1-\mu_{k}^{c})}{\mu_{k}^{c}}\right\\}$
(59)

yields the bound given in Lemma 1:

$\Pr[\Omega_{k}(t)\geq\frac{\mu_{1}^{r}}{\mu_{1}^{c}}]<1-\sqrt{1-\tau^{-\rho}},\quad
n_{k}(t)\geq n_{k}^{*}(\tau)$ (60)

∎

###  8.7 Proof of Theorem 6

Recall Theorem 6: See 6

###### Proof.

First note that the latter two terms and $n_{k}^{*}(\tau_{B})$ in Eq. (13) are
in $\mathcal{O}(\log B)$ [21]. Next we show that $\xi(\tau_{B},\rho)$ is in
$\mathcal{O}(\log B)$ for $\rho\geq 1$ and in $\mathcal{O}(B^{1-\rho})$ for
$0<\rho<1$.

We exploit two inequalities in our proof; the latter is based on the integral
test for convergence and holds for continuous, positive, decreasing functions.

$\sqrt{1-t^{-\rho}}\geq 1-t^{-\rho},\quad t\geq 1,\rho>0$ (61)
$\sum_{t=K+1}^{\tau_{B}}t^{-\rho}\leq(K+1)^{-\rho}+\int_{t=K+1}^{\tau_{B}}t^{-\rho}\
dt$ (62)

We use Eq. (61) to obtain an integrable expression for the sum in
$\xi(\tau_{B},\rho)$. We replace the sum with an integral-based upper bound as
in Eq. (62):

$\displaystyle\xi(\tau_{B},\rho)$
$\displaystyle=\left(\tau_{B}-K\right)\left(2-\sqrt{1-\tau_{B}^{-\rho}}\right)-\sum_{t=K+1}^{\tau_{B}}\sqrt{1-t^{-\rho}}$
(63)
$\displaystyle\leq\left(\tau_{B}-K\right)\left(2-\sqrt{1-\tau_{B}^{-\rho}}\right)-\sum_{t=K+1}^{\tau_{B}}1-t^{-\rho}$
(64)
$\displaystyle=\left(\tau_{B}-K\right)\left(1-\sqrt{1-\tau_{B}^{-\rho}}\right)+\sum_{t=K+1}^{\tau_{B}}t^{-\rho}$
(65)
$\displaystyle\leq\left(\tau_{B}-K\right)\left(1-\sqrt{1-\tau_{B}^{-\rho}}\right)+(K+1)^{-\rho}+\int_{t=K+1}^{\tau_{B}}t^{-\rho}\
dt$ (66)

Next, we evaluate the integral for the cases $\rho=1$ and $\rho\neq 1$.

#### Case 1: $\rho=1$.

$\displaystyle\xi(\tau_{B},\rho)\leq\left(\tau_{B}-K\right)\left(1-\sqrt{1-\tau_{B}^{-1}}\right)+(K+1)^{-1}+\log\tau_{B}-\log(K+1)$
(67)

For $\rho=1$, the first term in above equation converges, so
$\xi(\tau_{B},\rho=1)$ is in $\mathcal{O}(\log B)$. This implies that the
overall regret of $\omega$-UCB is in $\mathcal{O}(\log B)$ for $\rho=1$.

#### Case 2: $\rho\neq 1$.

$\displaystyle\xi(\tau_{B},\rho)\leq\left(\tau_{B}-K\right)\left(1-\sqrt{1-\tau_{B}^{-\rho}}\right)+(K+1)^{-\rho}+\frac{1}{1-\rho}\left(\tau_{B}^{1-\rho}-(K+1)^{1-\rho}\right)$
(68)

For $\rho>1$, $\xi(\tau_{B},\rho)$ converges and thus the overall regret is in
$\mathcal{O}(\log B)$. For $0<\rho<1$, one can show that $\xi(\tau_{B},\rho)$
is in $\mathcal{O}(B^{1-\rho})$. Hence, the regret of $\omega$-UCB is in
$\mathcal{O}(B^{1-\rho})$ for $0<\rho<1$.

To summarize, the regret of our policy is in $\mathcal{O}(B^{1-\rho})$ for
$0<\rho<1$ and in $\mathcal{O}(\log B)$ for $\rho\geq 1$. ∎

###  8.8 Summary of related UCB approaches

Table 2 summarizes our direct competitors and how they compute
$\Omega_{k}(t)$.

Table 2: Overview of our competitors Policy | $\Omega_{k}(t)$ | Comment
---|---|---
BTS [20] | $\frac{\textrm{sample from }\mathrm{Beta}(\alpha_{r}(t),\beta_{r}(t))}{\textrm{sample from }\mathrm{Beta}(\alpha_{c}(t),\beta_{c}(t))}$ | $\alpha_{r}(t)=n_{k}(t)\bar{\mu}^{r}_{k}(t)+1$
$\beta_{r}(t)=n_{k}(t)+2-\alpha_{r}(t)$
$\alpha_{c}(t)=n_{k}(t)\bar{\mu}^{c}_{k}(t)+1$
$\beta_{c}(t)=n_{k}(t)+2-\alpha_{c}(t)$
Discretization of con-
tinuous values
m-UCB [21] | $\frac{\min\\{\bar{\mu}^{r}_{k}(t)+\varepsilon_{k}(t),1\\}}{\max\\{\bar{\mu}^{c}_{k}(t)-\varepsilon_{k}(t),0\\}}$ | $\varepsilon_{k}(t)=\alpha\sqrt{\frac{\log(t-1)}{n_{k}(t)}}$
Recommendation: $\alpha=2^{-4}$
c-UCB [21] | $\frac{\bar{\mu}^{r}_{k}(t)}{\bar{\mu}^{c}_{k}(t)}+\frac{\varepsilon_{k}(t)}{\bar{\mu}^{c}_{k}(t)}$ | $\varepsilon_{k}(t)=\alpha\sqrt{\frac{\log(t-1)}{n_{k}(t)}}$
Recommendation: $\alpha=2^{-3}$
i-UCB [21] | $\frac{\bar{\mu}^{r}_{k}(t)}{\bar{\mu}^{c}_{k}(t)}+\varepsilon_{k}(t)$ | $\varepsilon_{k}(t)=\alpha\sqrt{\frac{\log(t-1)}{n_{k}(t)}}$
Recommendation: $\alpha=2^{-2}$
Budget UCB [19] | $\frac{\bar{\mu}^{r}_{k}(t)}{\bar{\mu}^{c}_{k}(t)}+\frac{\varepsilon_{k}(t)}{\bar{\mu}^{c}_{k}(t)}\left(1+\frac{\min\\{\bar{\mu}^{r}_{k}(t)+\varepsilon_{k}(t),1\\}}{\max\\{\bar{\mu}^{c}_{k}(t)-\varepsilon_{k}(t),\lambda\\}}\right)$ | $\varepsilon_{k}(t)=\sqrt{\frac{\log(t-1)}{n_{k}(t)}}$
$\lambda>0$: minimum cost
UCB-SC+ [16] | $\begin{array}[]{ll}\frac{\bar{\mu}^{r}_{k}(t)+\alpha_{k}(t)\bar{\mu}^{c}_{k}(t)}{\bar{\mu}^{c}_{k}(t)-\alpha_{k}(t)\bar{\mu}^{r}_{k}(t)},&\mbox{if }\bar{\mu}^{c}_{k}(t)^{2}>\frac{\log\frac{t}{n_{k}(t)}}{2n_{k}(t)}\\\ \infty,&\mbox{else}\end{array}$ | $\alpha_{k}(t)=\sqrt{\frac{\log\frac{t}{n_{k}(t)}}{2\kappa n_{k}(t)-\log\frac{t}{n_{k}(t)}}}$
with $\kappa=\bar{\mu}^{r}_{k}(t)^{2}+\bar{\mu}^{c}_{k}(t)^{2}$

###  8.9 Evaluation results with confidence intervals

(a) Settings S-Br-$\\{10,50,100\\}$

(b) Settings S-GBr-$\\{10,50,100\\}$

(c) Settings S-Bt-$\\{10,50,100\\}$

(d) Setting FB-Br

(e) Setting FB-Bt

(f) Example kde of $\mu_{k}^{r},\mu_{k}^{c}$

Figure 5: Evaluation results with 95% confidence intervals