Chen, Lyu, Wang and Zhou

Fairness-aware NRM with Demand Learning

Fairness-aware Network Revenue Management with Demand Learning

Xi Chen ††thanks: Author names listed in alphabetical order. Leonard N. Stern
School of Business, New York University, New York, NY 10012, USA,
<EMAIL_ADDRESS>Jiameng Lyu Yau Mathematical Sciences Center, Tsinghua
University, Beijing 100084, China<EMAIL_ADDRESS>Yining Wang
Naveen Jindal School of Management, University of Texas at Dallas, Richardson,
TX 75080, USA<EMAIL_ADDRESS>Yuan Zhou Yau Mathematical Sciences
Center, Tsinghua University, Beijing 100084, China<EMAIL_ADDRESS>
In addition to maximizing the total revenue, decision-makers in lots of
industries would like to guarantee fair consumption across different resources
and avoid saturating certain resources. Motivated by these practical needs,
this paper studies the price-based network revenue management problem with
both demand learning and fairness concern about the consumption across
different resources. We introduce the regularized revenue, i.e., the total
revenue with a fairness regularization, as our objective to incorporate
fairness into the revenue maximization goal. We propose a primal-dual-type
online policy with the Upper-Confidence-Bound (UCB) demand learning method to
maximize the regularized revenue. We adopt several innovative techniques to
make our algorithm a unified and computationally efficient framework for the
continuous price set and a wide class of fairness regularizers. Our algorithm
achieves a worst-case regret of $\mathcal{\widetilde{O}}(N^{5/2}\sqrt{T})$,
where $N$ denotes the number of products and $T$ denotes the number of time
periods. Numerical experiments in a few NRM examples demonstrate the
effectiveness of our algorithm for balancing revenue and fairness. network
revenue management, demand learning, fairness, regret analysis, linear bandit

##  1 Introduction

Network revenue management, as a fundamental and important model in revenue
management, has been successfully applied in lots of industries, such as
online retailing, airline, hotel (Talluri et al. 2004, Klein et al. 2020).
Classical research on NRM aims to maximize the total revenue over $T$ time
periods under resource constraints assuming the demand function is known. See,
for example, the seminal works of Gallego and Van Ryzin (1997), Jasin (2014),
Maglaras and Meissner (2006).

In practice, there are two main challenges in adopting NRM models. First, the
demand function in NRM is usually unknown, which needs to be learned on the
fly. Second, in addition to maximizing the total revenue, many retailers would
like to guarantee fair consumption across different resources and avoid
saturating certain resource types. As summarized in (Bateni et al. 2022),
fairness is an important concern in two cases. First, many platforms (e.g., in
healthcare or public utility sectors) are under the obligation to ensure
fairness. Second, even those profit-seeking platforms also need to take
fairness into consideration, because to maximize the long-term revenue, a
platform should keep long-term cooperation with different resource suppliers.
Ensuring fairness across different resource suppliers will help keep a good
collaboration relationship. Let us provide two examples to illustrate the
importance of fairness constraints in revenue management applications:

Online Retailing: In an NRM model for the online retailing industry, a
retailer decides prices for products and each product consumes several types
of resources. Different resources are provided by different suppliers, and it
is also possible that one supplier could provide more than one type of
resources. If one supplier terminates the cooperation, certain products may no
longer be able to be produced. Therefore, to maximize long-term revenue and
guarantee no product is out of stock, the retailer should keep good
relationship with all resource suppliers. To this end, it is essential to
ensure profit fairness across different suppliers. Indeed, only paying
attention to the revenue maximization may cause an “unfair” scenario in which
some suppliers earn a lot but the shares of others are small.

Airline Ticketing: For an airline company, it needs to make decisions on the
prices of products (e.g., multileg airlines) subject to resource constraints
(i.e., the capacity constraint of each flight), taking into consideration the
fact that customers’ realized demand for the products change with prices
charged accordingly. Since a multileg airline may involve several flights
between different cities, if one leg of flight between two cities is
saturated, all the products that include this leg will be out of stock no
matter how many seats are available on the other flight legs. As a result,
saturation in just a few flights not only will cause the waste of the capacity
but also cannot meet the need of the passengers, which in turn leads to
passenger dissatisfaction. Therefore, taking the fairness across different
resources into consideration will help airline companies avoid saturating
flight legs and eventually improve passenger satisfaction.

As shown in the above examples, the fairness objective is often measured in
the sense of the whole selling season and cannot be decomposed as an additive
objective at each time period. In this paper, we adopt several different
metrics that are applied to the average resource consumption vector to measure
its fairness. For example, the fairness on resource consumption could be
measured by the minimum element of the average resource consumption vector,
which is the famous max-min fairness metric extensively studied in economics
and resource allocation literature, also included as a special case of the
weighted max-min fairness metric studied in this paper. In some cases it may
also be desirable to consume the resources at similar rates, which can be
incentivized by our range fairness metric. In addition to the above two
examples, we propose several more practically useful fairness metrics. We
further identify a wide class of fairness metrics (including all the above
examples) with quite mild assumptions. All the fairness metrics in the class
can be incorporated in our learning and doing framework. Please refer to
Section 2.1 for more details.

The main contribution of this paper is a dynamic pricing algorithm that
simultaneous learns the unknown demand function and optimizes the composite
objective concerning both the NRM revenue and the fairness metric. For any
fairness metric included in the class mentioned above, our algorithm achieves
a regret at most $\mathcal{\widetilde{O}}(N^{5/2}\sqrt{T})$ (where $N$ is the
number of products and $T$ is the selling horizon, see Theorem 6.1 for more
details). Below we discuss the various technical challenges and our
contributions that overcome them in details.

###  1.1 Main technical challenges

There are several technical challenges to tackle the NRM problem with fairness
concern and demand learning. First, the fairness metrics are all applied to
the average resource consumption vector, which is a global objective
calculated across all time periods. There is also a global unreplenishable
inventory constraint for the resources. The _global objective and constraint_
are usually difficult for sequential decision making problems since the
decisions at each time step have to be well coordinated to jointly optimize
the fairness metric and satisfy the inventory constraint. Second, the problem
becomes even harder when the demand function is unknown to the retailer and
the retailer has to balance the _exploration vs. exploitation_ trade-off with
only learned information or estimated demand. Here, “exploration” means that
the retailer needs to explore different prices in order to learn the unknown
demand function on the run, and “exploitation” means that the retailer needs
to exploit the near-optimal price to simultaneously gain revenue and achieve
the global fairness objective. Finally, we aim at designing a _computationally
efficient_ algorithm (i.e., that runs in polynomial time) to minimize the
regret (i.e., the cost of learning and sequential decision making) about the
revenue and the fairness metric.

Compared with the work of Balseiro et al. (2020), the fact that demand curves
are unknown in our problem lead to several specific technical hurdles that
require novel solutions. In particular, we have the following challenges:

  1. 1.

In (Balseiro et al. 2020), the dual problem is unconstrained, leading to
complex dual space shapes and unbounded penalty vectors. This causes two
problems: first, with dual spaces having complex shapes, the dual update steps
may not have closed forms or be solved efficiently for general fairness-
induced penalty functions. More importantly, with penalty vectors being
unbounded the regret of the problem becomes unbounded as well because of the
uncertainty exhibited in the estimated demand functions, rendering bandit
learning algorithms impractical.

  2. 2.

With uncertainty quantified in the estimated demand functions, solving the
primal update steps becomes computationally intractable as the objective
functions are not necessarily concave any more. Novel algorithms and analysis
are required to solve such non-concave problems efficiently and rigorously.

###  1.2 Our contributions

We are able to address the above challenges with several technical
innovations. At a higher level, our algorithm combines the primal-dual-type
online policy proposed by Balseiro et al. (2020) with the Upper-Confidence-
Bound (UCB) method, where the former solves the fairness-aware online
allocation problem with the _known_ demand function and the latter is a widely
adopted principle to balance the exploration and exploitation trade-off in
many online learning algorithms. However, this combination is not black-box
style and we make novel technical contributions in the design and analysis of
our algorithm. Moreover, we also introduce new algorithmic ingredients to make
sure that our algorithm is computationally efficient. In contrast, most of the
online learning algorithms for linear demand models (and even the linear
bandit algorithm, LinUCB (Abbasi-Yadkori et al. 2011)) do not guarantee a
polynomial time complexity. Below, we describe our main technical
contributions in more details.

First, instead of using the UCB of the objective function in the usual online
learning and decision making algorithms, we make decisions according to the
UCB of the specially designed _adjusted reward function_. While our adjusted
reward function involves the revenue, it does not directly include the
fairness metric (as it is not obvious how to decompose such a global metric to
each individual time period, as discussed previously). Instead, we include a
carefully designed term in the adjusted reward function to relate it to the
dual variable. This term, together with our update rule of the dual variable,
helps optimize the fairness metric in a global fashion and reflects the
inventory constraint at the same time.

Second, to control the estimation error of the adjusted reward during
learning, we need to design a bounded domain for the dual parameter (i.e., the
dual space). In contrast, Balseiro et al. (2020) adopt an unbounded dual space
which is unfriendly to the analysis of our learning process, as illustrated in
the first bullet point in the previous section. By adopting a bounded domain
for the dual parameter, we able able to upper bound the estimation errors as
well, leading to correct regret scalings. An additional benefit of our new
dual space is that due to its simpler shape, we are able to employ a closed-
form dual update rule (Algorithm 2, Section 5) for _any_ fairness metric. In
contrast, Balseiro et al. (2020) may only achieve this for selected fairness
metrics and the dual update in our algorithm is much simplified.

Third, the regret analysis (especially the analysis related to the dual
variable) greatly relies on the magnitude of our model parameter estimations.
While the natural (regularized) least-squares estimator may not provide the
desired bound, we employ an additional convex program $\mathcal{M}_{t}$ to
compute a set of bounded model estimates. This $\mathcal{M}_{t}$ program is
also helpful to guarantee the concavity the estimated (adjusted) revenue
function so that we may computationally efficiently find its maximizer which
crucially connects to the decision we will make at each time step.

Finally, to achieve computational efficiency, we innovatively adopt an
$\ell_{\infty}$-norm confidence radius instead of the usual $\ell_{2}$-norm
confidence radius when computing the Upper Confidence Bounds so that we are
able to maximize the UCB of the adjusted revenue function in polynomial time.
Also, by reducing the $\mathcal{M}_{t}$ program to a linear program with
infinitely many constraints, we design a polynomial-time separation oracle and
invoke the Ellipsoid method to efficiently solve the $\mathcal{M}_{t}$
program. Both ingredients help our algorithm to achieve the polynomial time
complexity that addresses the second bullet point of technical challenges
mentioned in the previous section.

For the first 3 technical contributions, we provide more concrete explanations
at the end of Section 3, after the introduction of notations and the algorithm
description. For the last item, please refer to Section 4.1 and Section 4.2
for more details.

###  1.3 Related Works

In the section, we introduce three streams of literature related to our paper:
network revenue management (NRM) with known demand function, revenue
management (RM) with demand learning, and fairness in operations management.
And we discuss how our paper is appropriately placed into contemporary
literature by giving comparisons with closely-related existing works.

NRM with known demand function. A large body of the price-based network
revenue management literature focuses on the case in which the seller knows
the underlying demand function in advance. And it is known that the optimal
pricing policy of this case can be computed using dynamic programming (DP).
However, the well-known curse of dimensionality of DP makes the optimal
pricing policy computationally intractable. As a result, many works in the
literature have investigated on developing algorithms that are computationally
efficient with a superior revenue performance. The seminal work by Gallego and
Van Ryzin (1994, 1997) proposed a simple but powerful heuristics.
Specifically, they solve the optimal price of the fluid approximation model
which is a deterministic analog of the DP and choose a static price every
time. And their approach achieves an $\mathcal{O}(\sqrt{T})$ regret. Jasin
(2014) introduced an improvement to the static pricing policy by resolving the
static price periodically according to the remaining inventory, and attained
$\mathcal{O}(\log T)$ regret bound. Recently, Wang and Wang (2022) proved that
the resolving heuristics can achieve $\mathcal{O}(1)$ regret as compared to
the optimal policy of the DP.

RM with demand learning. There is a large body of literature focusing on the
price-based revenue management with demand learning, which are either without
inventory constraints (see, e.g., (Den Boer 2014, Den Boer and Zwart 2014,
Keskin and Zeevi 2014, 2017, Bu et al. 2022) and references therein) or with
inventory constraints (see, e.g., (Besbes and Zeevi 2009, Wang et al. 2014,
Chen et al. 2014, Ferreira et al. 2018, Miao et al. 2021)). For dynamic
pricing problems without inventory constraints, we refer the readers to (Den
Boer 2015) for a detailed review. For price-based revenue management problems
with inventory constraints, there are two streams of literature, either
considering the nonparametric demand model (Wang et al. 2014, Chen and Shi
2019, Chen et al. 2019, Miao and Wang 2021) or the parametric demand model
(see discussion below). Since our paper considers a parametric demand
function, we mainly investigate the literature on the revenue management
problem with inventory constraints and the parametric model. There are three
main approaches for tackling the learning-while-doing challenge.

The first approach is using the Explore-Then-Commit strategy, which separates
the exploration phase and exploitation phases. This simple strategy has been
widely used in online learning tasks, and Besbes and Zeevi (2009, 2012) and
Chen et al. (2014) applied this strategy to the NRM problem and Chen et al.
(2014) achieved $\mathcal{O}(\sqrt{T})$ regret assuming the strong concavity
of the revenue function.

The second approach is using Thompson sampling to address the exploration-
exploitation trade-off. Ferreira et al. (2018) introduced Thompson sampling
into network revenue management and considered both discrete price model and
continuous price set with the linear demand model. They obtained a Bayesian
regret $\mathcal{\widetilde{O}}(\sqrt{T})$ instead of the worst-case regret.
The most important step in their algorithm for the continuous price set is to
solve a quadratic program, which is not guaranteed to be a convex problem and
not clear how to be solved efficiently.

The third approach is incorporating the Optimism in the Face of Uncertain
principle into the primal-dual optimization framework. This approach is
closely related to the Bandit-with-Knapsack (BwK) model (Badanidiyuru et al.
2013), which introduces global resource constraints into the multi-armed
bandit. Agrawal and Devanur (2019) further generalized BwK to bandit with
global convex constraints and concave objective. The work by Agrawal and
Devanur (2016), which considered BwK in the linear bandit setting, can be
applied to the NRM problem with the discrete price. However, in the continuous
price setting, the regret and the running time will exponentially dependent on
the number of products due to the discretization procedure. Miao et al. (2021)
considered the NRM problem with continuous price and generalized linear model.
To tackle the high computational complexity due to the continuous price set,
they designed a UCB solver to reduce the original optimization problem to the
price optimization problem of an ordinary NRM problem by randomly sampling a
vector on the unit sphere and using it to linearize the $\ell_{2}$-norm-based
UCB term. However, the price optimization problem might still be non-convex
and difficult to solve despite this reduction.

Our work is closely related to (Agrawal and Devanur 2016) and (Miao et al.
2021). However, there are several significant differences. First, the primal-
dual framework in (Agrawal and Devanur 2016) and (Miao et al. 2021) do not
consider the fairness regularizer and their algorithms do not directly work in
our setting. With the fairness concerns, our algorithm adopts very different
primal and dual updates, which requires a different analysis. Second, as
compared to the random sampling method in (Miao et al. 2021), we introduce the
$\ell_{\infty}$-norm-based UCB term (Section 4.2) which is not only simpler to
calculate, but also only sacrifices an $\mathcal{O}(\sqrt{N})$ factor in the
regret. In contrast, even without the fairness consideration, the regret of
(Miao et al. 2021) for the NRM problem is
$\mathcal{\widetilde{O}}(N^{3.5}\sqrt{T})$, about $N$ times our regret. Third,
we introduce a feasibility program $\mathcal{M}_{t}$ (Section 4.1) to make
sure the estimated revenue function is concave and computationally easy to
optimize. We are able to combine the above new techniques to derive a
computationally efficient low-regret learning-while-doing algorithm for the
NRM problem with fairness concerns.

Fairness in operations. With the development of data-driven algorithms in
machine learning and operations, there is a growing concern about
discrimination and unfairness. As a result, the fairness issue has been well
studied in the machine learning literature, e.g., fair classification (Dwork
et al. 2012, Agarwal et al. 2018, Jang et al. 2022) and fair online learning
(Joseph et al. 2016, Liu et al. 2017, Jabbari et al. 2017, Gupta and Kamble
2021, Kandasamy et al. 2020, Baek and Farias 2021). We refer the interested
readers to the surveys of fairness in machine learning (Corbett-Davies and
Goel 2018, Mehrabi et al. 2021, Hutchinson and Mitchell 2019). And we mainly
focus on the fairness issue in operations problem, which has also attracted a
lot of attention (Bonald et al. 2006, Chen and Wang 2018, Ma et al. 2020,
Kallus and Zhou 2021, Kallus et al. 2022, Zhang et al. 2022).

Static resource allocation is one of earlier fields in operations that takes
different fairness metrics into consideration (Bansal and Sviridenko 2006,
Bertsimas et al. 2011, Elzayn et al. 2019, Donahue and Kleinberg 2020, Cai et
al. 2021, Bateni et al. 2022). Among many fairness metrics, a widely-
acknowledged fairness notion, max-min fairness (Nash Jr 1950) that maximizes
the minimum resource allocation, has been widely applied (Bansal and
Sviridenko 2006, Bertsimas et al. 2011). The fairness notion considered in our
paper includes the max-min fairness as a special case and (please refer to
Section 2.1 for more details). Another fairness metric that has been well
studied is proportional fairness (Azar et al. 2010, Vlasiou et al. 2014,
Bateni et al. 2022), which maximizes the overall utility of rate allocations
via a logarithmic utility function.

There is a vast body of literature considering the fairness in online
allocation problem with inventory constraints (with _known_ demand models)
(Elzayn et al. 2019, Ma et al. 2020, Balseiro et al. 2020, Chen et al. 2021a),
where the decision-maker must take an action upon each arriving request and
generates a reward and the consumption of resources. The related works by
Balseiro et al. (2020), Chen et al. (2021a) considered both fairness and
revenue management. The policy in the work by Chen et al. (2021a) achieves a
$\mathcal{O}(\sqrt{T})$ bound for the cumulative unfairness and a bounded
revenue regret. Balseiro et al. (2020) considered revenue maximization and
fairness resource allocation simultaneously by introducing the regularized
online allocation problem. Since our work is most related to (Balseiro et al.
2020), we have thoroughly discussed the technical differences in the
introduction section above and we will present the comparison more concretely
in Section 3. We also note that (Balseiro et al. 2020) works for the fairness-
aware NRM problem in a _quantity-based_ setting, where the decision-maker must
irrevocably accept or reject each arriving request given limited resources (a
special case of the online allocation problem studied in their paper). In
contrast, we study the NRM problem in the _price-based_ setting where the
decision-maker has to decide the prices that influence the demand and the
demand has always to be met (as long as permitted by the resource
constraints). To the best of our knowledge, our work is the first to consider
the fairness objective in the price-based NRM problem.

Another related line of works study the fairness in dynamic pricing (Cohen et
al. 2022, 2021, Chen et al. 2021b, Li and Jain 2016, Kallus and Zhou 2021).
These works focus on the price fairness, ensuring the prices are similar for
different groups and stable over time.

###  1.4 Notations

The vectors throughout this paper are all column vectors. We denote the set
$\\{1,2,\dots,N\\}$ by $[N]$ for any $N\in\mathbb{N}$. For vectors
$a,b\in\mathbb{R}^{N}$, we use $a\leq b$ ($a\geq b$ respectively) to denote
$a_{i}\leq b_{i}$ ($a_{i}\geq b_{i}$ respectively) for all $i\in[N]$. We use
$[x_{t}]_{i}$ to denote the $i$-th element of the vector $x_{t}$. For
$x\in\mathbb{R}^{N}$ and $\Lambda\in\mathbb{R}^{N\times N}$, we define the
following norms: $\|x\|_{1}:=\sum_{i=1}^{N}|x_{i}|$,
$\|x\|_{2}:=(\sum_{i=1}^{N}x_{i}^{2})^{1/2}$,
$\|x\|_{\infty}:=\max_{i\in[N]}x_{i}$, and
$\|x\|_{\Lambda}:=\sqrt{x^{\top}\Lambda x}$.

We use $\mathbf{I}_{N}$ to denote the identity matrix of order $N$. For
$A\in\mathbb{R}^{M\times N}$, we define the following matrix norms:
$\|A\|_{F}:=\sum_{i,j}A_{ij}^{2}$,
$\|A\|_{2}:=\mathrm{sup}_{\|x\|_{2}=1}\|Ax\|_{2}$,
$\|A\|_{\infty}:=\mathrm{sup}_{\|x\|_{\infty}=1}\|Ax\|_{\infty}$ and it is
easy to obtain $\|A\|_{\infty}=\max_{i\in[M]}\sum_{j=1}^{N}|A_{ij}|$. For
square matrix $A\in\mathbb{R}^{N\times N}$, we use $\lambda_{\mathrm{max}}(A)$
to denote the largest eigenvalue of $A$. For a symmetric matrix
$A\in\mathbb{R}^{N\times N}$, we use $A\preceq 0$ to represent that $A$ is
negative semi-definite. We use $[B|\alpha]$ to denote the augmented matrix by
adding $\alpha\in\mathbb{R}^{N}$ to the right of the matrix
$B\in\mathbb{R}^{N\times N}$ as a new column.

We use the big-$\mathcal{O}$ notation $f(T)=\mathcal{O}(g(T))$ to denote that
$\limsup_{T\to\infty}f(T)/g(T)\leq+\infty$. We use
$\mathcal{\widetilde{O}}(\cdot)$ to further omit the logarithmic dependency on
$N$, $M$, and $T$.

###  1.5 Organization

The remainder of this paper is organized as follows. In Section 2, we
formulate our problem by introducing the model assumptions and performance
measure; we also give plenty of examples of the fairness regularizers to
illustrate the potential guidance our paper might bring to the practical
scenarios. In Section 3, we present our algorithm and discuss the high-level
ideas of the algorithm design. Then we discuss reward and demand estimation
(Section 4) and the design of the mirror descent solver (Section 5) in
details, which are two key building blocks of our algorithm. In Section 6, we
present and prove the main theorem that upper bounds the regret of our
algorithm. To demonstrate the empirical performance of our policy, we conduct
several numerical experiments and present the results in Section 7. In the
end, we give a summary of our paper in Section 8. The proofs of most technical
lemmas and the additional experimental results are included in the
supplementary materials.

##  2 Model Description and Assumptions

In an NRM model with $N$ types of products and $M$ types of resources, a
retailer sells $N$ types of products during a selling season with $T$ time
periods. Each product is defined as a combination of $M$ types of
unreplenishable resources by the consumption matrix $A\in\mathbb{R}^{M\times
N}$, where $A_{ij}$ means that selling one unit of the type-$i$ product
consumes $A_{ij}$ unit of the type-$j$ resource. At each time period $t$, the
retailer must determine the prices for the $N$ products, i.e., the price
vector $p_{t}\in\mathbb{R}^{N}_{+}$. The retailer then observes the consumer’s
demand vector $d_{t}\in\mathbb{R}^{N}_{+}$ which is realized from an unknown
underlying demand function $D(p_{t})$, and finally consumes the resources
according to the consumption matrix $A$. The retailer needs to choose the
prices during the selling season to accomplish the following 3 goals:

  1. 1.

to gradually learn the underline demand function $D(p_{t})$ from the observed
demands,

  2. 2.

to maximize the total revenue based on the learned information and given the
unreplenishable resource inventory,

  3. 3.

to balance the consumption of the different types of resources via maximizing
the fairness regularizer $\phi(\cdot)$, which will be defined soon.

More specifically, the initial inventory levels of the $M$ resources are
$I_{0}=(I_{0,1},\dots,I_{0,M})^{\top}\in\mathbb{R}^{M}_{+}$. At the end of
time $t$, the inventory levels become $I_{t}=I_{t-1}-Ad_{t}$ for
$t=1,2,3,\dots$. For convenience we also define the normalized inventory level
$\gamma=(\gamma_{1},\dots,\gamma_{M})^{\top}:=I_{0}/T$, which is the average
amount of resources that can be used at a time period.

For simplicity, we assume that the price range for each product is
$[\underline{p},\overline{p}]$ and the retailer has to choose $p_{t}$ in the
price set $\mathcal{P}$ at each time $t$. The price set $\mathcal{P}$ can
either be $[\underline{p},\overline{p}]^{N}$ or a discrete subset in
$[\underline{p},\overline{p}]^{N}$. For brevity, we focus on the case
$\mathcal{P}=[\underline{p},\overline{p}]^{N}$, which is much more
challenging. One can easily adapt our algorithm and analysis to the discrete
price set.

The realized demand $d_{t}$ is a random variable centered at $D(p_{t})$, i.e.,

$d_{t}=D(p_{t})+\varepsilon_{t}$

where $\varepsilon_{t}$ is a zero-mean noise variable (see Assumption 2.2 for
the more precise statement). We consider the linear demand function (which is
the most commonly analyzed demand model in literature, e.g., (Keskin and Zeevi
2014) and (Ferreira et al. 2018))

$D(p_{t})=\alpha+Bp_{t},$

where $\alpha\in\mathbb{R}^{N}$ and $B\in\mathbb{R}^{N\times N}$ are the model
parameters unknown to the retailer. For convenience, we also denote these
unknown parameters by
$\theta=(\alpha,B)\in\Theta\subseteq\mathbb{R}^{N^{2}+N}$, where $\Theta$ is
the parameter space.

The revenue collected by the retailer at time $t$ is
$r_{t}=\Braket{d_{t},p_{t}}$. We also denote the corresponding expected
revenue by

$r(p_{t}):=\mathbb{E}[r_{t}|p_{t}]=\Braket{p_{t},D(p_{t})}.$

The objective of the retailer is to design a policy
$\pi=(\pi_{1},\dots,\pi_{T})$ with $\pi_{t}:\mathcal{H}_{t}\mapsto p_{t}$
(where $\mathcal{H}_{t}=\\{p_{s},d_{s}\\}_{s<t}$ is the historical prices and
demands before time $t$) to satisfy the inventory constraint $I_{t}\geq 0$ for
all $t\in\\{1,2,\dots,T\\}$ and maximize the following expected total revenue
plus the fairness regularizer on resource consumption:

$\mathbb{E}\left[\sum_{t=1}^{T}r(p_{t})+T\phi\left(\frac{1}{T}\sum_{t=1}^{T}Ad_{t}\right)\right].$

Below in Section 2.1 we will discuss more about the fairness regularizer
$\phi(\cdot)$; in Section 2.2 we introduce some standard assumptions on the
linear demand model and define the regret that our online policy aims to
minimize.

###  2.1 Fairness Regularizer $\phi(\cdot)$: Assumptions and Examples

The fairness on resource consumption is measured by the regularizer
$\phi\left(\frac{1}{T}\sum_{t=1}^{T}Ad_{t}\right)$ (i.e., the regularizer
function $\phi(\cdot)$ applied to the average resource consumption vector).

Throughout this paper we impose the following assumptions on $\phi(\cdot)$.

  1. 1.

$\phi(s)$ is $L$-Lipschitz continuous with respect to the
$\|\cdot\|_{\infty}$-norm on its effective domain, i.e.,
$|\phi(s_{1})-\phi(s_{2})|\leq L\|s_{1}-s_{2}\|_{\infty}$ for any
$s_{1},s_{2}\leq\gamma$.

  2. 2.

There exists $\overline{\phi}$ such that $0\leq\phi(s)\leq\overline{\phi}$ for
all $0\leq s\leq\gamma$.

  3. 3.

$\phi(s)$ is concave.

In the following, we present several regularizers satisfying the above
assumptions as examples. We will use $s=\frac{1}{T}\sum_{t=1}^{T}Ad_{t}$ and
$s_{i}$ refers to the average consumption of the type-$i$ resource.

Example 1: Weighted Max-min Fairness Regularizer. The first example is rooted
in the famous max-min fairness guarantee, which has been well studied in the
literature on static resources allocation (Bansal and Sviridenko 2006,
Bertsimas et al. 2011). The idea behind the max-min fairness guarantee is to
promote fairness by maximizing the minimum resource allocation. In our paper,
we consider the following weighted max-min fairness regularizer to promote
fairness in resource consumption. It is worthy to note that the max-min
regularizer in (Balseiro et al. 2020) can be seen as a special case of our
weighted max-min regularizer by setting the parameters correspondingly.

Formally, we define the weighted max-min fairness regularizer as
$\phi(s):=\lambda\min_{i}(w_{i}s_{i})$, where $\lambda$ is the parameter to
balance between the total revenue goal and the fairness objective, and in the
online retailing setting the parameter $w_{i}$ could be selected as the
revenue of the resource supplier due to the consumption of one unit type $i$
resource.

Example 2: Group Max-min Fairness Regularizer. We may divide the different
types of resources into groups and only focus on promoting the minimum
consumption of each resource group. In practice, each supplier may provide
several types of resources (which naturally forms a group) and the group max-
min fairness would be useful if we wish to guarantee fairness among the
suppliers.

Formally, we define the group max-min fairness regularizer as
$\phi(s):=\lambda\min_{i}((U\widetilde{s})_{i})$,111In general, we may combine
the grouping operation with any fairness regularizer satisfying the Assumption
2.1 to obtain a group version of the fairness regularizer, but for simplicity,
we only present the group version of the weighted max-min regularizer here.
where $\widetilde{s}=(w_{1}s_{1},\cdots,w_{m}s_{m})^{\top}$, $w_{i}$ is
similarly defined as in Example 1, and $U\in\mathbb{R}^{K\times M}$ is a
$0$-$1$ matrix describing the grouping scheme. In particular, we require that
in each column there is exactly $1$ non-zero element and in each row there is
at least $1$ non-zero element, where a simple example of $U$ is as follows,

$U=\begin{bmatrix}1&0&1&0\\\ 0&1&0&1\end{bmatrix}.$

In this example, there are two resource suppliers. The first supplier provides
the type-$1$ and the type-$3$ resources and the second supplier provides the
type-$2$ and the type-$4$ resources.

Example 3: Range Fairness Regularizer. Range is a fundamental statistical
quantity that measures the difference between the highest and the lowest value
of a population. The Range fairness regularizer provides incentive to minimize
the range among the entries of the weighted average consumption vector
$\widetilde{s}=(w_{1}s_{1},\cdots,w_{m}s_{m})^{\top}$.

Formally, we define the range fairness regularizer as
$\phi(s):=\lambda(\min_{i}(w_{i}s_{i})-\max_{i}(w_{i}s_{i})+\max_{i}(w_{i}\gamma_{i}))$,
where $-[\min_{i}(w_{i}s_{i})-\max_{i}(w_{i}s_{i})]$ is the range of
$\widetilde{s}$ and $\max_{i}(w_{i}\gamma_{i})$ is introduced to guarantee the
positiveness of the regularizer. When $w_{i}$ is chosen to be per-unit revenue
of the type-$i$ resource supplier, the range fairness regularizer can be
applied to promote the revenue fairness across different suppliers; when
$w_{i}=1/\gamma_{i}$, this regularizer can evaluate the evenness of resource
availability and help to avoid the pre-mature saturation of a few resource
types.

Example 4: Load Balancing Regularizer. We finally present the load-balancing
regularizer proposed in Balseiro et al. (2020). The regularizer is defined as
$\phi(s):=\lambda(\min_{i}((\gamma_{i}-s_{i})/\gamma_{i})$, which measures the
minimum relative resource availability, and also helps to make sure that no
resource is too demanded.

###  2.2 Model Assumptions and Performance Measure

Throughout this paper we impose the following assumptions on the demand model
$d_{t}=\alpha+Bp_{t}+\varepsilon_{t}$:

  1. 1.

The noise $\\{\varepsilon_{t}\\}_{t=1}^{T}$ is a martingale difference
sequence adapted to the filtration $\\{\mathcal{F}_{t}\\}_{t=1}^{T}$ where
$\mathcal{F}_{t}=\\{p_{1},d_{1},\cdots,p_{t},d_{t},p_{t+1}\\}$, i.e.,
$\mathbb{E}[\varepsilon_{t}|\mathcal{F}_{t-1}]=0$.

  2. 2.

There exists $\overline{d}$ such that $d_{t}\leq\overline{d}$ almost surely
for all $t\in\\{1,2,\dots,T\\}$.

  3. 3.

The underlying true parameter $B$ in the linear demand model is negative
definite; 222$B$ is is negative definite (not necessarily symmetric) if for
any $z\in\mathbb{R}^{n}$, it holds that $z^{\top}Bz<0$. there exists $L_{B}$
(with $L_{B}\geq 1$) such that
$\sqrt{\alpha_{i}^{2}+\|B^{\top}e_{i}\|^{2}_{2}}\leq L_{B}$ for every
$i\in[N]$, where $e_{i}$ is the $i$-th unit vector and $B^{\top}e_{i}$ is the
$i$-th row of $B$.

All items in Assumption 2.2 are quite standard in literature. The third item
is usually seen in papers focusing on the linear demand model (see, e.g.,
(Keskin and Zeevi 2014, Ferreira et al. 2018, Bu et al. 2022)). By the
definition $r(p_{t})=\Braket{d_{t},p_{t}}$ and according to Assumption 2.2, we
may upper bound $r(p_{t})$ by $\overline{r}:=N\overline{p}\overline{d}$.

We now discuss the performance measure for the retailer’s policy. We would
like to compare the objective value achieved by the retailer with the optimal
_offline_ policy, i.e., the one that knows all the model parameters $\theta$:

$\displaystyle
J_{\mathrm{opt}}:=\max_{\pi=(\pi_{1},\dots,\pi_{T})}\mathbb{E}\left[\sum_{t=1}^{T}r(p_{t})+T\phi\left(\frac{1}{T}\sum_{t=1}^{T}Ad_{t}\right)\right]\qquad\text{s.t.~{}}\sum_{t=1}^{T}Ad_{t}\leq
T\gamma~{}~{}a.s.$ (1)

$J_{\mathrm{opt}}$ upper bounds the objective value achieved by any _online_
policy (i.e., the one without access to $\theta$). In light of this, we define
the regret of a policy $\pi$ up to time horizon $T$ as

$\displaystyle\mathcal{R}(T)$
$\displaystyle:=J_{\mathrm{opt}}-\mathbb{E}\left[\sum_{t=1}^{T}r(p_{t})+T\phi\left(\frac{1}{T}\sum_{t=1}^{T}Ad_{t}\right)\right].$
(2)

Note that solving the exact value of $J_{\mathrm{opt}}$ is quite complicated
due to the stochastic nature and adaptivity available to choose
$\pi_{1},\pi_{2},\dots,\pi_{T}$ in sequence. We now introduce the following
fluid model which is the deterministic and non-adaptive analogue of
$J_{\mathrm{opt}}$ and easier to analyze.

$\displaystyle
J_{\mathrm{D}}:=\max_{p_{1},\dots,p_{T}\in[\underline{p},\overline{p}]^{N}}\left[\sum_{t=1}^{T}r(p_{t})+T\phi\left(\frac{1}{T}\sum_{t=1}^{T}AD(p_{t})\right)\right]\qquad\text{s.t.~{}}\sum_{t=1}^{T}AD(p_{t})\leq
T\gamma.$ (3)

We assert that there exists an optimal solution
$\\{p^{*}_{1},p_{2}^{*},\dots,p^{*}_{T}\\}$ to $J_{\mathrm{D}}$ such that
$p^{*}_{1}=p_{2}^{*}=\dots=p^{*}_{T}=p^{*}$, since otherwise, we can set
$p_{t}=p^{\prime}=\frac{1}{T}\sum_{t=1}^{T}p^{*}_{t}$ for every $t$, and the
objective value of $\\{p_{1}^{\prime},p_{2}^{\prime},\dots,p_{T}^{\prime}\\}$
becomes no smaller due to the concavity of $r(p)$ (since $r(p)=\langle
p,\alpha+Bp\rangle$ and $B$ is negative definite by Assumption 2.2) and
Jenson’s inequality. Therefore we have the following equivalent definition of
$J_{\mathrm{D}}$.

$\displaystyle
J_{\mathrm{D}}=\max\limits_{p\in[\underline{p},\overline{p}]^{N}}\quad\left[Tr(p)+T\phi\left(AD(p)\right)\right]\qquad\text{s.t.~{}}AD(p)\leq\gamma.$
(4)

We denote $p^{*}$ by the optimal solution to Eq. (4).

The following proposition shows that the fluid model $J_{\mathrm{D}}$ is an
upper bound of $J_{\mathrm{opt}}$, and its proof is deferred to the
supplementary materials.

###### Proposition 2.1

$\displaystyle{J_{\mathrm{opt}}\leq J_{\mathrm{D}}}$.

By Proposition 2.1, we upper bound the regret of any policy $\pi$ as follows,
which will serve as the starting point of the analysis of our proposed policy.

$\displaystyle\mathcal{R}(T)\leq
T[r(p^{*})+\phi(AD(p^{*}))]-\mathbb{E}\left[\sum_{t=1}^{T}r(p_{t})+T\phi\left(\frac{1}{T}\sum_{t=1}^{T}Ad_{t}\right)\right].$
(5)

##  3 Primal-dual Type Algorithm with Demand Learning

The pseudo-code of our main algorithm is given in Algorithm 1. To better
introduce our algorithm design, we first imagine that the demand function were
known and only explain the primal-dual framework. We then add the learning
component for the demand function and address the additional challenges raised
due to the unknown demand.

Algorithm 1 Primal-dual + UCB for fairness-aware NRM with demand learning

1: Initialize the dual variable $\mu_{1}=(0,\cdots,0)\in\mathbb{R}^{M}$.

2:for $t=1,2,\dots,T$ do

3: Compute the regularized least-squares estimator
$(\widehat{\alpha}_{t},\widehat{B}_{t})\in\argmin_{(\alpha,B)}\left\\{(N+1)(\|\alpha\|_{2}^{2}+\|B\|_{F}^{2})+\sum_{s<t}\|d_{s}-(\alpha+Bp_{s})\|_{2}^{2}\right\\}.$
(6)

4: Find $(\widecheck{\alpha}_{t},\widecheck{B}_{t})$ around
$(\widehat{\alpha}_{t},\widehat{B}_{t})$ such that $\widecheck{B}_{t}$ is
negative semi-definite by solving the program
$\displaystyle(\widecheck{\alpha}_{t},\widecheck{B}_{t})\in\mathcal{M}_{t}:=\left\\{(\widetilde{\alpha},\widetilde{B}):\|(\widetilde{\mathcal{B}}-\widehat{\mathcal{B}}_{t})^{\top}e_{i}\|_{\Lambda_{t}}\leq\kappa,\|\widetilde{\mathcal{B}}^{\top}e_{i}\|_{2}\leq
2L_{B}~{}\forall
i\in[N]\text{~{}and~{}}\widetilde{B}+\widetilde{B}^{\top}\preceq 0\right\\},$
(7) where we define the block matrices
$\widetilde{\mathcal{B}}:=[\widetilde{B}|\widetilde{\alpha}]$ and
$\widehat{\mathcal{B}}_{t}:=[\widehat{B}_{t}|\widehat{\alpha}_{t}]$ ($e_{i}$
is the $i$-th canonical basis vector), $\Lambda_{t}$ and $\kappa$ are defined
in Eqs. (20,21) respectively. In the rare case when Eq. (7) is infeasible, we
arbitrarily choose $(\widecheck{\alpha}_{t},\widecheck{B}_{t})$ as long as
$\widecheck{B}_{t}$ is negative semi-definite and
$\|\widecheck{B}_{t}^{\top}e_{i}\|_{2}\leq 2L_{B}~{}\forall i\in[N]$ (e.g.,
set $\widecheck{B}_{t}=0$).

5: Obtain $\widecheck{D}_{t}(p)=\widecheck{\alpha}_{t}+\widecheck{B}_{t}p$ and
$\widecheck{r}_{t}(p)=\Braket{p,\widecheck{D}_{t}(p)}$ to estimate $D(p)$ and
$r(p)$ respectively.

6: Update the primal variables  $\displaystyle
p_{t}\in\argmax_{p\in[\underline{p},\overline{p}]^{N}}\left\\{{\widecheck{r}_{t}(p)-\mu_{t}^{\top}A\widecheck{D}_{t}(p)+2\Delta_{t}^{f}(p)}\right\\},\qquad
s_{t}\in\argmax_{-\gamma\leq
s\leq\gamma}\left\\{\phi(s)+\mu_{t}^{\top}s\right\\},$ (8) where
$2\Delta_{t}^{f}(p)$ is the confidence radius of the _adjusted reward_
estimation $[\widecheck{r}_{t}(p)-\mu_{t}^{\top}A\widecheck{D}_{t}(p)]$ which
will be constructed later in Eq. (23).

7: Charge the price $p_{t}$, observe the demand $d_{t}$, consume resources
$Ad_{t}$ and update the inventory level $I_{t}=I_{t-1}-Ad_{t}$ (the algorithm
stops whenever any resource is depleted).

8: Obtain an estimated subgradient of dual function $\mathfrak{q}(\cdot)$ at
$\mu_{t}$: $\widecheck{g}_{t}=-A\widecheck{D}_{t}(p_{t})+s_{t}$.

9: Update the dual variable by invoking the mirror descent solver
$\varsigma^{D}$ (Definition 3.1):
$\displaystyle\mu_{t+1}=\varsigma^{D}(\mu_{t},\widecheck{g}_{t};\mathcal{D},\eta),$
(9) where we set $\eta=\sqrt{\frac{C_{1}}{C_{2}T}}$ ($C_{1}$ and $C_{2}$ are
also defined in Definition 3.1) and
$\displaystyle\mathcal{D}:=\\{\mu\in\mathbb{R}^{M}\mid\|\mu\|_{1}\leq
C\\},\qquad
C:=L+((\overline{r}+\overline{\phi})/\underline{\gamma}),\qquad\underline{\gamma}:=\min_{i\in[M]}\gamma_{i}.$
(10)

10:end for

Given the demand function $D(\cdot)$, thanks to Proposition 2.1, we may use
the fluid model $J_{\mathrm{D}}$, which upper bounds $J_{\mathrm{opt}}$, to
calculate an upper estimation of the regret of any online policy.333Indeed,
this relaxation would not ruin our aimed $\widetilde{\mathcal{O}}(\sqrt{T})$
regret, as the difference between $J_{\mathrm{D}}$ and $J_{\mathrm{opt}}$ is
also $\widetilde{\mathcal{O}}(\sqrt{T})$ for the network revenue management
problem either without (Gallego and Van Ryzin 1997) or with the fairness
concern (as we will see later in this paper). We now focus on the primal
formulation of the fluid model, and rewrite it with an auxiliary variable $s$.

$\displaystyle\mathfrak{p}^{*}$
$\displaystyle:=\max\limits_{p\in[\underline{p},\overline{p}]^{N}}\\{r(p)+\phi\left(AD(p)\right)\
\ \text{s.t.}\ \ AD(p)\leq\gamma\\}$ (11)
$\displaystyle~{}=\max\limits_{p\in[\underline{p},\overline{p}]^{N},-\gamma\leq
s\leq\gamma}\\{r(p)+\phi\left(AD(p)\right)\ \ \text{s.t.}\ \ AD(p)=s\\}.$

Note that we deliberately impose a lower bound constraint $s\geq-\gamma$ in
the new formulation. This does not change the optimal value of the program
since $AD(p)$ is entry-wise non-negative for non-negative $A$ and $D(p)$.

We then transform primal formulation to an unconstrained optimization problem
using the Lagrangian dual method. By the well-known weak duality, we have that

$\displaystyle\mathfrak{p}^{*}$
$\displaystyle=\max_{p\in[\underline{p},\overline{p}]^{N},-\gamma\leq
s\leq\gamma}\min_{\mu\in\mathbb{R}^{M}}\left\\{r(p)+\phi\left(s\right)-\mu^{\top}AD(p)+\mu^{\top}s\right\\}$
$\displaystyle\leq\min_{\mu\in\mathbb{R}^{M}}\max_{p\in[\underline{p},\overline{p}]^{N},-\gamma\leq
s\leq\gamma}\left\\{r(p)+\phi\left(s\right)-\mu^{\top}AD(p)+\mu^{\top}s\right\\}.$
(12)

In light of this, we define the dual function

$\displaystyle\mathfrak{q}(\mu):=\max_{p\in[\underline{p},\overline{p}]^{N},-\gamma\leq
s\leq\gamma}\left\\{r(p)+\phi\left(s\right)-\mu^{\top}AD(p)+\mu^{\top}s\right\\}=r^{\sharp}(A^{\top}\mu)+(-\phi)^{*}(\mu),$
(13)

where for every $\mu\in\mathbb{R}^{M}$ we define

$\displaystyle
r^{\sharp}(A^{\top}\mu):=\max_{p\in[\underline{p},\overline{p}]^{N}}\left\\{r(p)-\mu^{\top}AD(p)\right\\}$
(14)

and the convex conjugate (following the convention, e.g., Chapter 3 in (Boyd
et al. 2004))

$\displaystyle(-\phi)^{*}(\mu):=\max_{-\gamma\leq
s\leq\gamma}\left\\{\phi(s)+\mu^{\top}s\right\\}.$ (15)

By Eq. (12), for every $\mu\in\mathbb{R}^{M}$, we have that

$\displaystyle\mathfrak{p}^{*}\leq\mathfrak{q}(\mu).$ (16)

In the primal-dual framework, we iteratively optimize the primal variables
$p,s$ (Line 6)444When optimizing $p$, we need to deal with the upper
confidence bounds of the estimated quantities, which will be explained soon.
and the dual variable $\mu$ (Line 9). When updating the dual variable at Line
9, we use the mirror descent method with the help of a mirror descent solver
$\varsigma^{D}$ defined as follows.

######  Definition 3.1 (Mirror Descent Solver)

A mirror descent solver
$\varsigma^{D}(\mu_{t},\widecheck{g}_{t};\mathcal{D},\eta)$ takes
$\mu_{t}\in\mathcal{D}$ and $\widecheck{g}_{t}$ as input and returns the
updated dual variable $\mu_{t+1}\in\mathcal{D}$ at each time $t$. For a
sequence of input $\\{\widecheck{g}_{t}\\}$ and the initial dual variable
$\mu_{1}$, if we repeatedly apply $\varsigma^{D}$ and produce a sequence of
dual variables $\\{\mu_{t}\\}$. The solver makes sure that for all
$\mu\in\mathcal{D}$,

$\sum_{t=1}^{T}\left\langle\mu_{t},\widecheck{g}_{t}\right\rangle\leq\sum_{t=1}^{T}\left\langle\mu,\widecheck{g}_{t}\right\rangle+\frac{C_{1}}{\eta}+C_{2}\eta
T,$ (17)

where $C_{1}$ and $C_{2}$ are constants that only depend on $\mathcal{D}$.

In other words, the mirror descent solver should generate a sequence
$\\{\mu_{t}\\}$ to minimize
$\sum_{t=1}^{T}\left\langle\cdot,\widecheck{g}_{t}\right\rangle$ against any
stationary benchmark with the regret at most $C_{1}/\eta+C_{2}\eta T$.

The above-described primal-dual framework is similar to (and inspired by) the
algorithm proposed in (Balseiro et al. 2020). However, the key differences are
two folds explained as follows.

Demand Learning. In contrast to the known demand function in (Balseiro et al.
2020), the demand function is not known to the decision-maker beforehand in
our setting. Our algorithm learns the parameterized demand function from
historical data via the regularized least-squares estimate (Line 3). We then
solve another convex program (Line 4) to make sure the estimated parameters
$(\widecheck{\alpha},\widecheck{B})$ are bounded and $\widecheck{B}$ is
negative semi-definite. Finally, we use the Upper Confidence Bound of the
_adjusted reward function_
$[\widecheck{r}_{t}(p)-\mu_{t}^{\top}A\widecheck{D}_{t}(p)]$ (Line 6) to
compute the primal update. We will explain this in more details in Section 4.

An additional feature of our demand estimator is that the reward Upper
Confidence Bound is defined based on the $\ell_{\infty}$-norm of
$\Lambda_{t}^{-1/2}\widetilde{p}_{t}$ where the $\ell_{2}$-norm is usually
adopted in the linear bandit literature. Together with the convex program
solved in Line 4, our definition of the reward Upper Confidence Bound renders
the primal update a combination of a few convex optimization problems (Eq.
(8)) that can be efficiently solved, which will be further explained in
Section 4.2.555On the downside, we sacrifice an $\mathcal{O}(\sqrt{N})$ factor
in the regret bound. However, we view this degradation relatively small
compared to the existing $\mathcal{O}(N^{2})$ factor which seems necessary in
the regret due to the $N^{2}$ parameters in $B$ to learn.

A New Dual Space. The dual space $\mathcal{D}$ is a crucial component in the
design of the mirror descent solver $\varsigma^{D}$ and affects the regret
analysis. Balseiro et al. (2020) adopt a dual space
$\mathcal{D}^{\mathrm{Bal.}}=\\{\mu\in\mathbb{R}^{M}~{}|~{}\sup_{a\leq\gamma}{\phi(a)+\mu^{\top}a}\\}$
which might have different shapes for difference fairness regularizer
$\phi(\cdot)$. The fundamental reason that we cannot directly adopt
$\mathcal{D}^{\mathrm{Bal.}}$ in our problem, however, is the unboundedness of
$\mathcal{D}^{\mathrm{Bal.}}$ which would lead to an unbounded regret due to
the unbounded estimation error of the adjusted reward
$[\widecheck{r}_{t}(p)-\mu_{t}^{\top}A\widecheck{D}_{t}(p)]$ during the
learning process (see Eq. (25) for more details). To deal with this issue, we
construct a novel, simply and uniformly shaped, and bounded dual space (Eq.
(10)). We prove that our dual space encompasses all potential stationary
benchmark dual variables $\overline{\mu}$ which is necessary for the desired
$\widetilde{\mathcal{O}}(\sqrt{T})$ regret.

Thanks to the newly constructed dual space, an extra benefit enjoyed by our
algorithm is that, together with a carefully chosen variant of the
exponentiated gradient descent ($\mathrm{EG}\pm$) algorithm as the mirror
descent solver, we are able to obtain a _uniform_ and _closed-form_ update of
the dual variables for _all_ fairness regularizers. In contrast, Balseiro et
al. (2020) have to design the dual update step on a case-by-case basis for the
fairness regularizers. Also, the closed-form update improves the computational
efficiency of the algorithm and is a desired feature in (Balseiro et al. 2020)
that is partially achieved for a few selected fairness regularizers.

##  4 Demand and Reward Estimation

The regularized least-squares estimator (Line 3 of Algorithm 1) for demand
parameters is frequently used in the linear bandit literature (see, e.g.,
(Dani et al. 2008, Rusmevichientong and Tsitsiklis 2010, Abbasi-Yadkori et al.
2011)). However, as mentioned before, we need to work with the upper
confidence bound of a specially defined _adjusted reward function_. Also, we
employ an additional step (Line 4) to make sure the estimated parameters
$(\widecheck{\alpha},\widecheck{B})$ are bounded, which is crucial to the
regret analysis (more specifically, the analysis of the mirror descent
solver). Line 4 also guarantees the negative semi-definiteness of
$\widecheck{B}$; when computing the Upper Confidence Bound for the estimation,
we innovatively use an $\ell_{\infty}$-norm confidence radius instead of the
usual $\ell_{2}$-norm confidence radius – both ingredients help the algorithm
to compute the upper confidence bound _in polynomial time_. We will show how
to computationally efficiently find
$(\widecheck{\alpha},\widecheck{B})\in\mathcal{M}_{t}$ (Line 4) and implement
the UCB-type primal update (Line 6) in Section 4.1 and Section 4.2
respectively.

To explain our Upper Confidence Bound method in more details, we first
introduce some notations. For convenience, we define the stopping time

$\tau=\max\left\\{t:\min_{i}I_{t,i}>0,t\leq T\right\\},$

which is the last time period when the inventory levels of all resources
remain positive. Most of our analysis will be done only for time periods up to
$\tau$. We define

$\displaystyle f_{t}(p):=r(p)-\mu_{t}^{\top}AD(p)$ (18)

to be the _adjusted reward function_ at price $p$ and with respect to
$\mu_{t}$. Note that this corresponds to the optimization objective in Eq.
(14) when $\mu=\mu_{t}$. Our estimation for $f_{t}(p)$ is

$\displaystyle\widecheck{f}_{t}(p):=\widecheck{r}_{t}(p)-\mu_{t}^{\top}A\widecheck{D}_{t}(p),$
(19)

which corresponds to the first part in the optimization objective of $p_{t}$
in Eq. (8). We also define estimators with regard to
$(\widehat{\alpha}_{t},\widehat{B}_{t})$ as

$\widehat{D}_{t}(p)=\widehat{\alpha}_{t}+\widehat{B}_{t}p,\qquad\widehat{r}_{t}(p)=\Braket{p_{t},\widehat{D}_{t}(p)},\qquad\widehat{f}_{t}(p):=\widehat{r}_{t}(p)-\mu_{t}^{\top}A\widehat{D}_{t}(p).$

Bounding the estimation errors. We now derive the estimation errors of
$\widehat{D}_{t},\widehat{r}_{t},\widehat{f}_{t}$ and
$\widecheck{D}_{t},\widecheck{r}_{t},\widecheck{f}_{t}$, as well as their
corresponding upper confidence bounds. For any price vector $p$, we let
$\widetilde{p}:=(p,1)$, and then introduce the _regularized information
matrix_ at time $t$ to be

$\displaystyle\Lambda_{t}:=(N+1)\cdot\mathbf{I}_{N+1}+\sum_{s<t}\widetilde{p}_{s}\widetilde{p}_{s}^{\top}.$
(20)

Let

$\displaystyle\kappa:=2\sqrt{2\overline{d}^{2}(N+1)\ln\left(NT(1+\overline{p}^{2}T)\right)+2(N+1)L_{B}^{2}},\qquad\text{and}$
(21)
$\displaystyle\Delta_{t}^{D}(p):=\sqrt{N+1}\kappa\|\Lambda_{t}^{-1/2}\widetilde{p}_{t}\|_{\infty}\qquad\text{and}\qquad\Delta_{t}^{r}(p):=\sqrt{N+1}N\overline{p}\kappa\|\Lambda_{t}^{-1/2}\widetilde{p}_{t}\|_{\infty}$
(22)

to be the confidence radii of $\widehat{r}_{t}(p)$ and $\widehat{D}_{t}(p)$
respectively. Note that here we use
$\|\Lambda_{t}^{-1/2}\widetilde{p}_{t}\|_{\infty}$ instead of the
$\ell_{2}$-norm confidence radius
$\|\Lambda_{t}^{-1/2}\widetilde{p}_{t}\|_{2}$ commonly seen in literature. We
finally define

$\displaystyle\Delta_{t}^{f}(p):=\Delta_{t}^{r}(p)+\|\mu_{t}\|_{1}\cdot\|A\|_{\infty}\Delta_{t}^{D}(p)$
(23)

to be the confidence radius for the adjusted reward estimator
$\widehat{f}_{t}$. We utilize the famous Confidence Ellipsoid Lemma in
(Abbasi-Yadkori et al. 2011) to analyze our $\ell_{\infty}$-type confidence
region, and have the following lemma. Our lemma states that the confidence
radii defined above (Eq. (22) and Eq. (23)) hold with overwhelming
probability.

###### Lemma 4.1

With probability at least $(1-\mathcal{O}\left(T^{-1}\right))$, for all
$t\leq\tau$ and all $p\in[\underline{p},\overline{p}]$, we have

$\|\widehat{D}_{t}(p)-D(p)\|_{\infty}\leq\Delta_{t}^{D}(p),\qquad\left|\widehat{r}_{t}(p)-r(p)\right|\leq\Delta_{t}^{r}(p),\qquad\text{and}\qquad|\widehat{f}_{t}(p)-f_{t}(p)|\leq\Delta_{t}^{f}(p).$

As we will later show in Lemma 4.7, with probability at least
$(1-\mathcal{O}\left(T^{-1}\right))$, we are able to find a feasible
$(\widecheck{\alpha}_{t},\widecheck{B}_{t})\in\mathcal{M}_{t}$ in Line 4.
Combining the definition of $\mathcal{M}_{t}$ and Lemmas 4.1 and 4.7, we have
the following corollary.

###### Corollary 4.2

With probability at least $(1-\mathcal{O}\left(T^{-1}\right))$, for all
$t\leq\tau$ and all $p\in[\underline{p},\overline{p}]$, we have

$\|\widecheck{D}_{t}(p)-D(p)\|_{\infty}\leq
2\Delta_{t}^{D}(p),\qquad\left|\widecheck{r}_{t}(p)-r(p)\right|\leq
2\Delta_{t}^{r}(p),\qquad\text{and}\qquad|\widecheck{f}_{t}(p)-f_{t}(p)|\leq
2\Delta_{t}^{f}(p).$

The program $\mathcal{M}_{t}$. Note that by Lemma 4.1,
$\widehat{D}_{t},\widehat{r}_{t},\widehat{f}_{t}$ already serve as good
estimators. However, in the rest part of the algorithm (as well as the
analysis), we will mainly work with
$\widecheck{D}_{t},\widecheck{r}_{t},\widecheck{f}_{t}$, which are defined
based on $(\widecheck{\alpha}_{t},\widecheck{B}_{t})$ derived by solving the
program $\mathcal{M}_{t}$ in Line 4 of Algorithm 1. This is due to the
following two requirements.

  1. 1.

The analysis of the mirror descent solver requires an upper bound on the
estimated gradient $\|\widecheck{g}_{t}\|_{\infty}$ which relies on the bound
of $\max_{i}\|\widecheck{B}_{t}^{\top}e_{i}\|_{2}$ (Eqs. (31,32)).

  2. 2.

The primal update (Eq. (8)) involves maximizing $\widecheck{r}_{t}$, a
quadratic form of $\widecheck{B}_{t}$, which can be efficiently optimized only
when $\widecheck{B}_{t}$ is negative semi-definite so that $\widecheck{r}_{t}$
is concave.

By solving the program $\mathcal{M}_{t}$, we find
$(\widecheck{\alpha}_{t},\widecheck{B}_{t})$ that simultaneously satisfies the
above two requirements and stays close to
$(\widehat{\alpha}_{t},\widehat{B}_{t})$ (in terms of the
$\|\cdot\|_{\Lambda_{t}}$ norm). In this way, we facilitate both the regret
analysis and the efficient computation of the algorithm. Please refer to
Sections 4.1 and 4.2 for the efficient implementations of solving
$\mathcal{M}_{t}$ and the primal update respectively.

UCB of the adjusted reward function. When the desired event in Corollary 4.2
happens, we define

$\displaystyle\overline{f}_{t}(p):=\widecheck{f}_{t}(p)+2\Delta_{t}^{f}(p)$
(24)

and have that $f_{t}(p)\leq\overline{f}_{t}(p)$ for all $t\leq\tau$ and
$p\in[\underline{p},\overline{p}]$. Note that $\overline{f}_{t}(\cdot)$ is
exactly the optimization objective of $p_{t}$ (at Line 6 of Algorithm 1),
which is indeed an Upper Confidence Bound (UCB) of the maximization objective
in $r^{\sharp}(\cdot)$ (Eq. (14), namely $f_{t}(\cdot)$).

Since $\|\mu_{t}\|_{1}\in\mathcal{D}$ for all $t\in[T]$ and
$\mathcal{D}=\\{\mu\in\mathbb{R}^{M}\mid\|\mu\|_{1}\leq C\\}$, we further
upper bound $\Delta_{t}^{f}(p)$ by

$\Delta_{t}^{f}(p)\leq\Delta_{t}^{r}(p)+C\|A\|_{\infty}\Delta_{t}^{D}(p).$
(25)

Therefore, we set

$\displaystyle\Delta_{t}(p):=\Delta_{t}^{r}(p)+\max\\{C\|A\|_{\infty},1\\}\Delta_{t}^{D}(p)$
(26)

to upper bound all the confidence radii $\Delta_{t}^{r}(p)$,
$\Delta_{t}^{D}(p)$ and $\Delta_{t}^{f}(p)$.

Bounding the total estimation error. In our regret analysis, we will relate
the regret incurred at time $t$ to the confidence radii at price $p_{t}$ at
the time (which aligns with the general Upper Confidence Bound principle –
bounding the regret by the confidence radii of the selected actions). And thus
we will be interested in the summation of the estimation errors. The following
lemma adapts the celebrated Elliptical Potential Lemma (see, e.g., Theorem
11.7 in (Cesa-Bianchi and Lugosi 2006) and Lemma 9 in (Dani et al. 2008)) to
upper bound the total estimation error.

###### Lemma 4.3

With probability $1$, we have the following upper bound for the total
estimation error:

$\displaystyle\sum_{t=1}^{\tau}\Delta_{t}\left(p_{t}\right)$
$\displaystyle\leq\mathcal{O}\left(\sqrt{N+1}\kappa\max\\{\overline{p},1\\}(N\overline{p}+\max\\{C\|A\|_{\infty},1\\})\right)\times\sqrt{NT\log(N+1+\overline{p}^{2}T)},$

where only a universal constant is hidden in the $\mathcal{O}(\cdot)$
notation.

###  4.1 Solving $\mathcal{M}_{t}$ via Ellipsoid Method

In this subsection, we describe how to implement Line 4 and find a feasible
solution to $\mathcal{M}_{t}$ in polynomial time via the Ellipsoid method. The
main lemma of this subsection is Lemma 4.7.

We first introduce the definition of a separation oracle for a convex set $K$,
which is closely related to the Ellipsoid method.

######  Definition 4.4 (Separation Oracle)

For a closed convex set $K\subseteq\mathbb{R}^{n}$, a _separation oracle_ for
$K$, namely $\mathrm{SEP}_{K}$, is an algorithm that takes a point
$x\in\mathbb{R}^{n}$ as input and correctly decides whether $x\in K$. In the
case that $x\not\in K$, the separation oracle also returns a hyperplane that
separates $x$ from $K$. The hyperplane may be characterized by its norm vector
$c\in\mathbb{R}^{n}$ such that $c^{\top}x>c^{\top}y$ for all $y\in K$.

The ellipsoid method reduces a convex program feasibility problem to the
construction of an efficient separation oracle for the corresponding convex
body. The following lemma characterizes such a reduction. The lemma is a
simplification of the Theorem 3.2.1 in (Grötschel et al. 2012) modulo the
numerical error due to the arithmetic operations on real numbers.666The
numerical error analysis is often tedious but straightforward, which is also
the case in this subsection. Therefore, we choose to omit this part and
emphasize the main algorithmic idea more clearly.

###### Lemma 4.5

Suppose we could perform exact arithmetic operations on real numbers. Let
$\mathrm{Ball}(x,r)$ denote the closed ball with radius $r$ and centered at
$x\in\mathbb{R}^{n}$. Given a closed convex set $K\subseteq\mathbb{R}^{n}$,
suppose that there exist $R,r>0$ such that $K\subseteq\mathrm{Ball}(x_{0},R)$
and $\mathrm{Ball}(x_{1},r)\subseteq K$ for some
$x_{0},x_{1}\in\mathbb{R}^{n}$. Given $R$, $r$, $x_{0}$, and a separation
oracle for $K$, namely $\mathrm{SEP}_{K}$, the Ellipsoid method will return a
point in $K$ using $\mathcal{O}(n^{2}\log(R/r))$ calls to the separation
oracle and $\mathrm{poly}(n,\log(R/r))$ arithmetic operations.

It is easy to verify that our $\mathcal{M}_{t}$ is a closed convex set in
$\mathbb{R}^{N\times(N+1)}$. To apply Lemma 4.5 to $\mathcal{M}_{t}$, we first
upper and lower bound the shape of $\mathcal{M}_{t}$ as follows.

###### Lemma 4.6

Given the desired event described in Lemma 4.1, we have that

$\mathcal{M}_{t}\subseteq\mathrm{Ball}(\widehat{\mathcal{B}}_{t},\kappa\sqrt{N})\qquad\text{and}\qquad\mathrm{Ball}([B-T^{-2}\cdot\mathbf{I}_{N}|\alpha],T^{-4})\subseteq\mathcal{M}_{t},$

where we treat the matrices $\widehat{\mathcal{B}}_{t}$ and
$[B-T^{-2}\cdot\mathbf{I}_{N}|\alpha]$ as $N\times(N+1)$-dimensional vectors.

The separation oracle. It remains to design the separation oracle
$\mathrm{SEP}_{\mathcal{M}_{t}}$. Given
$\widetilde{\mathcal{B}}=[\widetilde{B}|\widetilde{\alpha}]$, we need to
verify the following two types of constraints specified in the definition of
$\mathcal{M}_{t}$ (Eq. (7)).

  * •

$\|(\widetilde{\mathcal{B}}-\widehat{\mathcal{B}}_{t})^{\top}e_{i}\|_{\Lambda_{t}}\leq\kappa,\forall
i\in[N]$. This condition can be verified for each $i\in[N]$ by straightforward
computation. When the condition is not met for some $i\in[N]$, we have that
$\kappa<\|(\widetilde{\mathcal{B}}-\widehat{\mathcal{B}}_{t})^{\top}e_{i}\|_{\Lambda_{t}}=\|\Lambda_{t}^{1/2}(\widetilde{\mathcal{B}}-\widehat{\mathcal{B}}_{t})^{\top}e_{i}\|_{2}$,
and there exists
$c=\frac{\Lambda_{t}^{1/2}(\widetilde{\mathcal{B}}-\widehat{\mathcal{B}}_{t})^{\top}e_{i}}{\|\Lambda_{t}^{1/2}(\widetilde{\mathcal{B}}-\widehat{\mathcal{B}}_{t})^{\top}e_{i}\|_{2}}$
such that

$c^{\top}\Lambda_{t}^{1/2}(\widetilde{\mathcal{B}}-\widehat{\mathcal{B}}_{t})^{\top}e_{i}>\kappa\geq
c^{\top}\Lambda_{t}^{1/2}(\mathcal{B}^{\prime}-\widehat{\mathcal{B}}_{t})^{\top}e_{i}$

for every $\mathcal{B}^{\prime}=[B^{\prime}|\alpha^{\prime}]$ where
$(\alpha^{\prime},B^{\prime})\in\mathcal{M}_{t}$, which defines the separation
hyperplane.

  * •

$\|\widetilde{\mathcal{B}}^{\top}e_{i}\|_{2}\leq 2L_{B},\forall i\in[N]$. This
condition can also be verified for each $i\in[N]$ by straightforward
computation. When the condition is not met for some $i\in[N]$, we have that
$2L_{B}<\|\widetilde{\mathcal{B}}^{\top}e_{i}\|_{2}$, and there exists
$c=\frac{\widetilde{\mathcal{B}}^{\top}e_{i}}{\|\widetilde{\mathcal{B}}^{\top}e_{i}\|_{2}}$
such that

$c^{\top}\widetilde{\mathcal{B}}^{\top}e_{i}>2L_{B}\geq
c^{\top}\mathcal{B}^{\prime\top}e_{i}$

for every $\mathcal{B}^{\prime}=[B^{\prime}|\alpha^{\prime}]$ where
$(\alpha^{\prime},B^{\prime})\in\mathcal{M}_{t}$, which defines the separation
hyperplane.

  * •

$\widetilde{B}+\widetilde{B}^{\top}\preceq 0$. This condition is equivalent to
$\lambda_{\max}(\widetilde{B}+\widetilde{B}^{\top})\leq 0$ which can be
efficiently verified. If the condition is not satisfied, we can efficiently
find a vector $c\in\mathbb{R}^{N}$ such that

$\langle\widetilde{B}+\widetilde{B}^{\top},cc^{\top}\rangle>0\geq\langle
B^{\prime}+(B^{\prime})^{\top},cc^{\top}\rangle$

for every $(\alpha^{\prime},B^{\prime})\in\mathcal{M}_{t}$, which defines the
separation hyperplane.

Combining Lemma 4.6, and the separation oracle constructed above, we may
invoke Lemma 4.5 with $R=\kappa\sqrt{N}$ and $r=T^{-4}$, and conclude this
subsection with the following lemma.

###### Lemma 4.7

With probability at least $(1-\mathcal{O}\left(T^{-1}\right))$, for all
$t\leq\tau$, $\mathcal{M}_{t}$ is feasible, and we can find
$(\widecheck{\alpha}_{t},\widecheck{B}_{t})\in\mathcal{M}_{t}$ via the
Ellipsoid method using only $\mathrm{poly}(N,\log
T,\log\overline{d},\log\overline{p},\log L_{B})$ arithmetic operations on real
numbers.

###  4.2 Efficient Primal Update

We now show that, thanks to the new $\ell_{\infty}$-norm-based confidence
region, we may efficiently implement the primal update (Line 6) by solving
$\mathcal{O}(N)$ convex optimization problems. We focus on the optimization
problem for $p_{t}$ as the one for $s_{t}$ is already convex. Note that

$\displaystyle\max_{p\in[\underline{p},\overline{p}]^{N}}\left\\{\widecheck{f}_{t}(p)+2\Delta_{t}^{f}(p)\right\\}$
$\displaystyle=\max_{p\in[\underline{p},\overline{p}]^{N}}\left\\{\Braket{p-A^{\top}\mu_{t},\widecheck{D}_{t}(p)}+2\sqrt{N+1}\kappa(N\overline{p}+\|\mu_{t}\|_{1}\cdot\|A\|_{\infty})\|\Lambda_{t}^{-1/2}\widetilde{p}\|_{\infty}\right\\}$
$\displaystyle=\max_{p\in[\underline{p},\overline{p}]^{N}}\left\\{\Braket{p-A^{\top}\mu_{t},\widecheck{D}_{t}(p)}+2\sqrt{N+1}\kappa(N\overline{p}+\|\mu_{t}\|_{1}\cdot\|A\|_{\infty})\max\limits_{\lambda\in\\{\pm
e_{1},\dots,\pm
e_{N+1}\\}}\lambda^{\top}\Lambda_{t}^{-1/2}\widetilde{p}\right\\}$
$\displaystyle=\max\limits_{\lambda\in\\{\pm e_{1},\dots,\pm
e_{N+1}\\}}\max_{p\in[\underline{p},\overline{p}]^{N}}\left\\{\Braket{p-A^{\top}\mu_{t},\widecheck{D}_{t}(p)}+2\sqrt{N+1}\kappa(N\overline{p}+\|\mu_{t}\|_{1}\cdot\|A\|_{\infty})\lambda^{\top}\Lambda_{t}^{-1/2}\widetilde{p}\right\\},$

where $e_{i}$ ($i\in\\{1,2,\dots,N+1\\})$ is the $i$-th canonical basis vector
in $\mathbb{R}^{N+1}$. For any $\lambda\in\\{\pm e_{1},\dots,\pm e_{N+1}\\}$,
define the convex program (which is convex due to the negative semi-
definiteness of $\widecheck{B}$ guaranteed in Line 4)

$P_{t}^{(\lambda)}:=\argmax_{p\in[\underline{p},\overline{p}]^{N}}\left\\{\Braket{p-A^{\top}\mu_{t},\widecheck{D}_{t}(p)}+2\sqrt{N+1}\kappa(N\overline{p}+\|\mu_{t}\|_{1}\cdot\|A\|_{\infty})\lambda^{\top}\Lambda_{t}^{-1/2}\widetilde{p}\right\\}.$

It is easy to verify that
$\argmax_{p\in[\underline{p},\overline{p}]^{N}}\left\\{\widecheck{f}_{t}(p)+2\Delta_{t}^{f}(p)\right\\}\subseteq\cup_{\lambda\in\\{\pm
e_{1},\dots,\pm e_{N+1}\\}}P_{t}^{(\lambda)}$. Therefore, to compute the
primal update for $p_{t}$, we only need to first solve $2(N+1)$ convex
programs to identify $p_{t}^{(\lambda)}\in P_{t}^{(\lambda)}$ for every
$\lambda\in\\{\pm e_{1},\dots,\pm e_{N+1}\\}$, and then select

$p_{t}\in\argmax\limits_{p\in\\{p_{t}^{(\lambda)}:\lambda\in\\{\pm
e_{1},\dots,\pm
e_{N+1}\\}\\}}\left\\{\Braket{p-A^{\top}\mu_{t},\widecheck{D}_{t}(p)}+2\sqrt{N+1}\kappa(N\overline{p}+\|\mu_{t}\|_{1}\cdot\|A\|_{\infty})\|\Lambda_{t}^{-1/2}\widetilde{p}\|_{\infty}\right\\}.$
(27)

##  5 Mirror Descent Solver $\varsigma^{D}$ and its Closed-form Dual Update

In this section, we design the mirror descent solver $\varsigma^{D}$ to
satisfy Definition 3.1. Given the dual space $\mathcal{D}$, for any _reference
function_ $h$ that is $\sigma$-strongly convex with respect to $\|\cdot\|_{1}$
over $\mathcal{D}$, the online mirror descent (OMD) algorithm operates in the
following way to update the dual variable:

$\displaystyle\mu_{t+1}\in\argmin_{\mu\in\mathcal{D}}\left\\{\langle\mu,\widecheck{g}_{t}\rangle+\frac{1}{\eta}D_{h}(\mu,\mu_{t})\right\\},$
(28)

where $D_{h}(x,y)=h(x)-h(y)-\nabla h(y)^{\top}(x-y)$ is the Bregman
divergence. It is well-known (see, e.g., Hazan et al. (2016)) that if
$\left\|\widecheck{g}_{t}\right\|_{\infty}\leq G$ for all $t$, then if we
start with any given $\mu_{1}\in\mathcal{D}$, the $\\{\mu_{t}\\}$ sequence
produced by Eq. (28) guarantees that for any stationary benchmark
$\mu\in\mathcal{D}$,

$\sum_{t=1}^{T}\left\langle\mu_{t},\widecheck{g}_{t}\right\rangle\leq\sum_{t=1}^{T}\left\langle\mu,\widecheck{g}_{t}\right\rangle+\frac{\sup_{\mu\in\mathcal{D}}D_{h}\left(\mu,\mu_{1}\right)}{\eta}+\frac{\eta
G^{2}}{2\sigma}T,$

which matches the requirement of Definition 3.1.

The popular choices of the reference functions are the negative entropy
function $h(x)=\sum_{i=1}^{n}x_{i}\ln x_{i}$ (so that
$D_{h}(x,y)=\sum_{i=1}^{n}x_{i}\ln(x_{i}/y_{i})$, and the OMD algorithm
becomes the exponentiated gradient algorithm) and the Euclidean norm
$h(x)=\frac{1}{2}\|x\|_{2}^{2}$ (so that $D_{h}(x,y)=\frac{1}{2}\|x-y\|_{2}$
and the OMD algorithm becomes the projected gradient descent algorithm).
However, based on the different shapes of the dual space $\mathcal{D}$, one
has to carefully choose $h$ to guarantee its strong convexity and proper
definition (e.g., the negative entropy function is not properly defined when
any of the coordinate becomes negative). Due to this reason, Balseiro et al.
(2020) have to design the reference function on a case-by-case basis for
various fairness regularizers $\phi$ which shape their dual space
$\mathcal{D}$. When designing $h$, Balseiro et al. (2020) also aim to simplify
the update rule (Eq. (28)) with the hope of a closed-form update, so as to
reduce the computational cost. However, they are only able to achieve this
goal for selected fairness regularizers.

In our work, thanks to the simplicity of newly designed dual space
$\mathcal{D}=\\{\mu\in\mathbb{R}^{M}\mid\|\mu\|_{1}\leq C\\}$ (Eq. (10)), we
are able to use a uniform mirror descent solver $\varsigma^{D}$ that enjoys
the closed-form update for all fairness regularizers. Our $\varsigma^{D}$ is
similar to the OMD algorithm with the negative entropy function. The only
issue, however, is that the negative entropy function does not apply to
negative coordinates covered by our dual space $\mathcal{D}$. To this end, we
employ the special variant of the algorithm that separately deals with the
positive weights and negative weights in $\mu_{t}$. The algorithm was proposed
by Kivinen and Warmuth (1997) and called $\mathrm{EG}^{\pm}$ (Exponentiated
Gradient Algorithm with Positive and Negative Weights).

The $\mathrm{EG}^{\pm}$ algorithms is formally described in Algorithm 2. Note
that instead of a single vector $\mu_{t}$, the algorithm keeps two vectors
$\mu^{+}_{t+1}$ and $\mu^{-}_{t+1}$, and the update of the two vectors are in
simple closed forms. While both vectors are in $\mathbb{R}_{+}^{M}$, they
respectively represent (the absolute values of) the positive and negative
weights in $\mu_{t}$ (see Eq. (30)). Due to this technical reason, to use
$\mathrm{EG}^{\pm}$ as our mirror descent solver, we need to slightly modify
the description of our main Algorithm 1. First, we initialize the two vectors
as

$\displaystyle\mu^{+}_{1}=\mu^{-}_{1}=(C/M,\dots,C/M),$ (29)

which replaces the initialization (Line 1) of Algorithm 1. We also replace the
dual update (Eq. (9)) of Algorithm 1 by

$\displaystyle(\mu^{+}_{t+1},\mu^{-}_{t+1})=\mathrm{EG}^{\pm}(\mu^{+}_{t},\mu^{-}_{t},\widecheck{g}_{t};\mathcal{D},\eta),\qquad\qquad\mu_{t+1}=\mu^{+}_{t+1}-\mu^{-}_{t+1}.$
(30)

Algorithm 2
$\mathrm{EG}^{\pm}(\mu^{+}_{t},\mu^{-}_{t},\widecheck{g}_{t};\mathcal{D},\eta)$

1:Compute the $\mu^{+}_{t+1}$ and $\mu^{-}_{t+1}$ vectors as follows:

2:for $i=1,2,\dots,M$ do  $\displaystyle[\mu_{t+1}^{+}]_{i}$
$\displaystyle=\frac{C[\mu_{t}^{+}]_{i}\exp(-\eta
C[\widecheck{g}_{t}]_{i})}{\sum_{i=1}^{M}\left([\mu_{t}^{+}]_{i}\exp(-\eta
C[\widecheck{g}_{t}]_{i})+[\mu_{t}^{-}]_{i}\exp(\eta
C[\widecheck{g}_{t}]_{i})\right)},$ $\displaystyle[\mu_{t+1}^{-}]_{i}$
$\displaystyle=\frac{C[\mu_{t}^{-}]_{i}\exp(\eta
C[\widecheck{g}_{t}]_{i})}{\sum_{i=1}^{M}\left([\mu_{t}^{+}]_{i}\exp(-\eta
C[\widecheck{g}_{t}]_{i})+[\mu_{t}^{-}]_{i}\exp(\eta
C[\widecheck{g}_{t}]_{i})\right)}.$

3:end for

4:return $(\mu^{+}_{t+1},\mu^{-}_{t+1})$.

It remains to choose $G$ as the upper bound of
$\|\widecheck{g}_{t}\|_{\infty}$. To this end, we set

$G:=2\max\\{\overline{p},1\\}(N+1)L_{B}\|A\|_{\infty}+\overline{\gamma}.$

Since for all $i\in[N]$ we have
$\|\widecheck{B}_{t}^{\top}e_{i}\|_{1}\leq(N+1)\|\widecheck{B}_{t}^{\top}e_{i}\|_{2}$
and $\|\widecheck{B}_{t}^{\top}e_{i}\|_{2}\leq 2L_{B}$, which is guaranteed in
Line 4, it is easy to obtain
$\|\widecheck{\mathcal{B}}_{t}\|_{\infty}=\max_{i}\|\widecheck{B}_{t}^{\top}e_{i}\|_{1}\leq
2(N+1)L_{B}$. And thus we could have the following upper bound of
$\|\widecheck{D}_{t}(p_{t})\|_{\infty}$

$\displaystyle\|\widecheck{D}_{t}(p_{t})\|_{\infty}=\|\widecheck{\mathcal{B}}_{t}\widetilde{p}_{t}\|_{\infty}\leq\|\widecheck{\mathcal{B}}_{t}\|_{\infty}\max\\{\overline{p},1\\}\leq
2(N+1)L_{B}\max\\{\overline{p},1\\}.$ (31)

Therefore, we may upper bound $\|\widecheck{g}_{t}\|_{\infty}$ by $G$:

$\displaystyle\|\widecheck{g}_{t}\|_{\infty}=\|A\widecheck{D}_{t}(p_{t})-s_{t}\|_{\infty}\leq\|A\|_{\infty}\|\widecheck{D}_{t}(p_{t})\|_{\infty}+\overline{\gamma}\leq
2\max\\{\overline{p},1\\}(N+1)L_{B}\|A\|_{\infty}+\overline{\gamma}=G.$ (32)

By directly applying Theorem 2 in Hoeven et al. (2018), we have the following
lemma showing that $\mathrm{EG}^{\pm}$ satisfies our requirement of the mirror
descent solver.

###### Lemma 5.1

By adopting $\mathrm{EG}^{\pm}$ as our mirror descent solver $\varsigma^{D}$,
Definition 3.1 is satisfied with

$\displaystyle C_{1}=\ln(2M)\qquad\qquad\text{and}\qquad\qquad
C_{2}=C^{2}G^{2}/2.$ (33)

##  6 Regret Analysis

With the main technical tools ready in hand, we now prove the following main
theorem which upper bounds the regret of our Algorithm 1.

###### Theorem 6.1

When combining Algorithm 1 with our $\mathrm{EG}^{\pm}$ mirror descent solver
(Algorithm 2), we may upper bound the regret of the algorithm by

$\displaystyle\mathcal{R}(T)$
$\displaystyle\leq\left(\|A\|_{\infty}\overline{d}/\underline{\gamma}+\mathcal{O}(1)\right)[r(p^{*})+\phi(AD(p^{*}))]+\mathcal{O}(\|A\|_{\infty}\overline{d}\sqrt{T\log(MT)})$
$\displaystyle\qquad+2\sqrt{C_{1}C_{2}T}+\mathcal{O}\left(\sqrt{N+1}\kappa\max\\{\overline{p},1\\}(N\overline{p}+\max\\{C\|A\|_{\infty},1\\})\right)\times\sqrt{NT\log(N+1+\overline{p}^{2}T)},$

where we may choose values for $C_{1}$ and $C_{2}$ according to Eq. (33) and
only universal constants are hidden in the $\mathcal{O}(\cdot)$ notations.

###### Remark 6.2

Recall that $C=L+((\overline{r}+\overline{\phi})/\underline{\gamma})$,
$\overline{r}=N\overline{p}\overline{d}$, and $\kappa$ is defined in Eq. (21).
Assuming the problem parameters
$\overline{d},\overline{p},\overline{\phi},L,L_{B},\|A\|_{\infty}\leq\mathcal{O}(1)$
and $\underline{\gamma}\geq\Omega(1)$, we have that
$C_{1}\leq\mathcal{\widetilde{O}}(1)$, $C,C_{2}\leq\mathcal{O}(N)$,
$\kappa\leq\mathcal{\widetilde{O}}(N)$, and
$\mathcal{R}(T)\leq\mathcal{\widetilde{O}}(N^{5/2}\sqrt{T})$.

The rest of this section is devoted to the proof of Theorem 6.1. Recall that
$\tau=\max\\{t:\min_{i\in[M]}C_{t,i}>0,t\leq T\\}$ is the stopping time till
when the inventory levels of all resources remain positive. For convenience,
for $t\leq\tau$, we define

$\displaystyle g_{t}:=-AD(p_{t})+s_{t}.$ (34)

For $t>\tau$, we set all relevant quantities to zeros:777We will treat
$D(p_{t})$ as a symbol rather than a function of $p_{t}$ for $t>\tau$.

$g_{t}=\widehat{g}_{t}=s_{t}=0,\qquad p_{t}=0,\qquad
D(p_{t})=d_{t}=0,\qquad\qquad\forall t>\tau.$

By Eq. (5), we have that

$\displaystyle\mathcal{R}(T)$ $\displaystyle\leq
T[r(p^{*})+\phi(AD(p^{*}))]-\mathbb{E}\left[\sum_{t=1}^{T}r(p_{t})+T\phi\left(\frac{1}{T}\sum_{t=1}^{T}Ad_{t}\right)\right].$
(35)

The proof of our main theorem follows the general framework of the primal-dual
analysis of online optimization problems (e.g., (Beck and Teboulle 2003, Hazan
et al. 2016, Balseiro et al. 2022, 2020)), and will be detailed in 5 steps.
The main differences from (Balseiro et al. 2020) is that in Step II, we need
to deal with the estimation error in the dual expression that relates to the
fairness regularizer (note the $\widecheck{g}_{t}$ term in
$\sum_{t=1}^{\tau}\left\langle\mu_{t},\widecheck{g}_{t}\right\rangle+\sum_{t=1}^{\tau}\phi(s_{t})-T\phi\left(\frac{1}{T}\sum_{t=1}^{T}AD(p_{t})\right)$).
We bound this part in Steps III and IV. This error can be upper bounded by
estimation error of $\widecheck{g}_{t}$ multiplied by the $\ell_{1}$-norm of
the dual variables. Our definition of the dual space
$\mathcal{D}=\left\\{\mu\in\mathbb{R}^{M}\mid\|\mu\|_{1}\leq C\right\\}$ again
kicks in to help upper bound the error.

###  6.1 Step I: Replacing $d_{t}$ with $D(p_{t})$ and Introducing
$\mathcal{\widetilde{R}}$

The first step is to replace the real demand $d_{t}$ on the Right-Hand-Side of
Eq. (35) with the expected demand $D(p_{t})$ so that the resulting expression
$\mathcal{\widetilde{R}}$ is easier to deal with. By applying the Azuma-
Hoeffding inequality and a union bound, we have the following lemma.

###### Lemma 6.3

With probability at least $(1-1/T)$, it holds that

$\forall
i\in[M],\qquad\left|\sum_{t=1}^{T}[Ad_{t}]_{i}-\sum_{t=1}^{T}[AD(p_{t})]_{i}\right|\leq\mathcal{O}(\|A\|_{\infty}\overline{d}\sqrt{T\log(MT)}).$
(36)

Lemma 6.3 implies that

$\displaystyle\left\|\sum_{t=1}^{T}Ad_{t}-\sum_{t=1}^{T}AD(p_{t})\right\|_{\infty}\leq\mathcal{O}(\|A\|_{\infty}\overline{d}\sqrt{T\log(MT)}).$
(37)

Together with the Lipschtz continuity of $\phi(\cdot)$, Eq. (37) implies that

$\displaystyle\left|\phi\left(\frac{1}{T}\sum_{t=1}^{T}Ad_{t}\right)-\phi\left(\frac{1}{T}\sum_{t=1}^{T}AD(p_{t})\right)\right|$
$\displaystyle\leq\frac{L}{T}\left\|\sum_{t=1}^{T}Ad_{t}-\sum_{t=1}^{T}AD(p_{t})\right\|_{\infty}\leq\mathcal{O}\left(L\|A\|_{\infty}\overline{d}\sqrt{\frac{\log(MT)}{T}}\right).$
(38)

Now we define the random variable

$\displaystyle\mathcal{\widetilde{R}}:=T[r(p^{*})+\phi(AD(p^{*}))]-\left[\sum_{t=1}^{\tau}r(p_{t})+T\phi\left(\frac{1}{T}\sum_{t=1}^{T}AD(p_{t})\right)\right].$
(39)

Eq. (38) (which holds with probability at least $(1-1/T)$) implies that

$\mathcal{R}(T)\leq\mathbb{E}[\mathcal{\widetilde{R}}]+\mathcal{O}(L\|A\|_{\infty}\overline{d}\sqrt{T\log(MT)}),$
(40)

and we may turn to upper bound $\mathbb{E}[\mathcal{\widetilde{R}}]$ instead.
In the following steps, we will upper bound the value of
$\mathcal{\widetilde{R}}$ conditioned on that the desired events of Lemma 6.3
and Lemma 4.1 hold. Note that this scenario happens with probability at least
$(1-\mathcal{O}(T^{-1}))$, and $\widetilde{\mathcal{R}}$ is at most
$T[r(p^{*})+\phi(AD(p^{*}))]$ in the rare opposite case.

###  6.2 Step II: Bounding the Fluid Optimum by the UCB of the Dual

The goal of the second step is, given the desired event of Corollary 4.2, to
establish for each $t\leq\tau$ that

$\displaystyle r(p^{*})+\phi\left(AD(p^{*})\right)\leq
r(p_{t})+\phi\left(s_{t}\right)+\left\langle\mu_{t},-A\widehat{D}_{t}(p_{t})+s_{t}\right\rangle+2(\Delta_{t}^{r}\left(p_{t}\right)+\Delta_{t}^{f}\left(p_{t}\right)),$
(41)

where $p^{*}$ is the optimal solution of the fluid model (Eq. (11)), and
recall the definitions of the primal variables $p_{t}$ and $s_{t}$ in Eq. (8).
The Right-Hand-Side of Eq. (41) can be viewed as the Upper-Confidence-Bound of
the dual function $\mathfrak{q}(\mu_{t})$.

To prove Eq. (41), we first introduce
$p^{*}_{t}:=\argmax_{p\in[\underline{p},\overline{p}]^{N}}\left\\{r(p)-\langle\mu_{t},AD(p)\rangle\right\\}$
which can be viewed as the desired choice for $p_{t}$ (without the estimation
errors of $r(\cdot)$ and $D(\cdot)$). In the following claim we upper bound
the fluid optimum by the exact dual function.

###### Claim 1

$r(p^{*})+\phi\left(AD(p^{*})\right)\leq
r(p_{t}^{*})+\phi(s_{t})+\langle\mu_{t},-AD(p_{t}^{*})+s_{t}\rangle$ .

Claim 1 is essentially a restatement of the weak duality and its proof is
deferred to the supplementary materials. Comparing Claim 1 and our goal (Eq.
(41)), we only need to upper bound the estimation errors. In particular, it
suffices to have that

$\displaystyle|r\left(p_{t}\right)-\widecheck{r}_{t}\left(p_{t}\right)|\leq
2\Delta_{t}^{r}\left(p_{t}\right)\qquad\text{and}\qquad
r(p_{t}^{*})+\left\langle\mu_{t},-AD(p_{t}^{*})\right\rangle\leq\widecheck{r}_{t}\left(p_{t}\right)+\left\langle\mu_{t},-A\widecheck{D}_{t}(p_{t})\right\rangle+2\Delta_{t}^{f}(p_{t}),$

where the first inequality is exactly guaranteed by the first item of
Corollary 4.2, for the second inequality, we have that

$r\left(p_{t}^{*}\right)-\left\langle\mu_{t},AD(p_{t}^{*})\right\rangle=f_{t}\left(p_{t}^{*}\right)\leq\overline{f}_{t}\left(p_{t}^{*}\right)\leq\overline{f}_{t}\left(p_{t}\right)=\widehat{r}_{t}\left(p_{t}\right)+\left\langle\mu_{t},-A\widehat{D}_{t}(p_{t})\right\rangle+2\Delta_{t}^{f}(p_{t}),$

where the first inequality is by the third item of of Corollary 4.2 and the
second inequality is due to our Upper-Confidence-Bound-style primal update
(Eq. (8)).

Now we have established Eq. (41). Together with the definition of
$\mathcal{\widetilde{R}}$ (Eq. (39)) and that
$\widecheck{g}_{t}=-A\widecheck{D}_{t}(p_{t})+s_{t}$ (Line 8 of Algorithm 1),
we obtain that

$\displaystyle\mathcal{\widetilde{R}}$
$\displaystyle\leq(T-\tau)[r(p^{*})+\phi(AD(p^{*}))]+\sum_{t=1}^{\tau}2(\Delta_{t}^{r}(p_{t})+\Delta_{t}^{f}(p_{t}))$
$\displaystyle\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad+\sum_{t=1}^{\tau}\left\langle\mu_{t},\widecheck{g}_{t}\right\rangle+\sum_{t=1}^{\tau}\phi(s_{t})-T\phi\left(\frac{1}{T}\sum_{t=1}^{T}AD(p_{t})\right).$
(42)

Observe that in Eq. (42) we have
$\sum_{t=1}^{\tau}\phi(s_{t})-T\phi\left(\frac{1}{T}\sum_{t=1}^{T}AD(p_{t})\right)$
and $\sum_{t=1}^{\tau}\left\langle\mu_{t},\widecheck{g}_{t}\right\rangle$. In
the next two steps, we will bound them separately.

###  6.3 Step III: Upper Bounding
$\sum_{t=1}^{\tau}\phi(s_{t})-T\phi\left(\frac{1}{T}\sum_{t=1}^{T}AD(p_{t})\right)$

In this step we upper bound the term
$\sum_{t=1}^{\tau}\phi(s_{t})-T\phi\left(\frac{1}{T}\sum_{t=1}^{T}AD(p_{t})\right)$
in Eq. (42) by the dot products between a carefully selected dual variable
$\overline{\mu}$ and $\\{g_{t}\\}$ (Eq. (34)). It is also important to
guarantee that $\overline{\mu}$ stays in the range of our novel dual space
$\mathcal{D}$, which is used by our later analysis. Formally, we prove the
following lemma.

###### Lemma 6.4

Let

$\displaystyle\overline{s}=\frac{1}{T}\sum_{t=1}^{T}AD(p_{t})\qquad\text{and}\qquad\overline{\mu}=\argmax_{\mu\in\mathbb{R}^{M}}\\{-(-\phi)^{*}(\mu)+\langle\mu,\overline{s}\rangle\\}.$
(43)

It holds that

$\displaystyle\sum_{t=1}^{T}\phi\left(s_{t}\right)-T\phi\left(\frac{1}{T}\sum_{t=1}^{T}AD(p_{t})\right)\leq-\sum_{t=1}^{T}\left\langle\overline{\mu},g_{t}\right\rangle=-\sum_{t=1}^{\tau}\left\langle\overline{\mu},g_{t}\right\rangle.$
(44)

Moreover, we have that $\overline{\mu}\in\mathcal{D}$.

Noting that when $t>\tau$ we have $s_{t}=0$ and thus $\phi(s_{t})\geq 0$ (by
Assumption 2.1). Together with Eq. (42) and Lemma 6.4 we further upper bound
$\mathcal{\widetilde{R}}$ by

$\displaystyle\mathcal{\widetilde{R}}$
$\displaystyle\leq(T-\tau)[r(p^{*})+\phi(AD(p^{*}))]+\sum_{t=1}^{\tau}2(\Delta_{t}^{r}(p_{t})+\Delta_{t}^{f}(p_{t}))+\sum_{t=1}^{\tau}\left\langle\mu_{t},\widecheck{g}_{t}\right\rangle-\sum_{t=1}^{\tau}\left\langle\overline{\mu},g_{t}\right\rangle.$
(45)

###  6.4 Step IV: Upper Bounding
$\sum_{t=1}^{\tau}\left\langle\mu_{t},\widecheck{g}_{t}\right\rangle$

In this step, we upper bound the term
$\sum_{t=1}^{\tau}\left\langle\mu_{t},\widecheck{g}_{t}\right\rangle$ in Eq.
(45) (as well as Eq. (42)) by combining the properties of the mirror descent
solver and our Upper-Confidence-Bound-type estimator. Intuitively, we would
like to replace $\widecheck{g}_{t}$ by $g_{t}$ so that the term could be
compared with the other term
$\sum_{t=1}^{\tau}\left\langle\overline{\mu},g_{t}\right\rangle$ in Eq. (45).
Formally, we will establish Eq. (48).

For any $\mu\in\mathcal{D}$, by applying the definition of the mirror descent
solver in Definition 3.1, we have that

$\displaystyle\sum_{t=1}^{\tau}\left\langle\mu_{t},\widecheck{g}_{t}\right\rangle$
$\displaystyle\leq\sum_{t=1}^{\tau}\left\langle\mu,\widecheck{g}_{t}\right\rangle+\frac{C_{1}}{\eta}+C_{2}\eta
T$
$\displaystyle\leq\sum_{t=1}^{\tau}\left\langle\mu,g_{t}\right\rangle+\sum_{t=1}^{\tau}\left|\Braket{\mu,A\widecheck{D}_{t}(p_{t})-AD(p_{t})}\right|+\frac{C_{1}}{\eta}+C_{2}\eta
T,$ (46)

where $C_{1}$ and $C_{2}$ are the constant parameters in Definition 3.1. By
Hölder’s Inequality, (for any $\mu\in\mathcal{D}$) we have that

$\displaystyle\left|\Braket{\mu,A\widecheck{D}_{t}(p_{t})-AD(p_{t})}\right|\leq\|\mu\|_{1}\cdot\|A\widecheck{D}_{t}(p_{t})-AD(p_{t})\|_{\infty}\leq
2C\|A\|_{\infty}\Delta_{t}^{D}\left(p_{t}\right).$ (47)

Note that here we crucially rely on our definition of the dual space
$\mathcal{D}=\left\\{\mu\in\mathbb{R}^{M}\mid\|\mu\|_{1}\leq C\right\\}$.
Combining Eq. (46) and Eq. (47), for any $\mu\in\mathcal{D}$, we establish
that

$\displaystyle\sum_{t=1}^{\tau}\left\langle\mu_{t},\widecheck{g}_{t}\right\rangle$
$\displaystyle\leq\sum_{t=1}^{\tau}\left\langle\mu,g_{t}\right\rangle+\frac{C_{1}}{\eta}+C_{2}\eta
T+\sum_{t=1}^{\tau}2C\|A\|_{\infty}\Delta_{t}^{D}\left(p_{t}\right),$ (48)

Recall the definition of $\overline{\mu}$ in Eq. (43). Let
$\mu=\overline{\mu}+\delta$ where $\delta\in\mathbb{R}^{M}_{+}$ satisfying
$\overline{\mu}+\delta\in\mathcal{D}$ will be determined later. Plugging our
choice of $\mu$ into Eq. (48), we have that

$\displaystyle\sum_{t=1}^{\tau}\left\langle\mu_{t},\widecheck{g}_{t}\right\rangle$
$\displaystyle\leq\sum_{t=1}^{\tau}\left\langle\overline{\mu},g_{t}\right\rangle+\sum_{t=1}^{\tau}\left\langle\delta,g_{t}\right\rangle+\frac{C_{1}}{\eta}+C_{2}\eta
T+\sum_{t=1}^{\tau}2C\|A\|_{\infty}\Delta_{t}^{D}\left(p_{t}\right).$ (49)

Recalling
$\Delta_{t}(p):=\Delta_{t}^{r}(p)+\max\\{C\|A\|_{\infty},1\\}\Delta_{t}^{D}(p)$
and combining Eq. (45) and Eq. (49), we obtain that

$\displaystyle\mathcal{\widetilde{R}}$
$\displaystyle\leq(T-\tau)[r(p^{*})+\phi(AD(p^{*}))]+\sum_{t=1}^{\tau}\left\langle\delta,g_{t}\right\rangle+\frac{C_{1}}{\eta}+C_{2}\eta
T+\sum_{t=1}^{\tau}4\Delta_{t}(p_{t}).$ (50)

###  6.5 Step V: Choosing Parameters and Putting Things Together

We finally choose the proper parameters to upper bound
$\mathcal{\widetilde{R}}$ and conclude the proof. For the choice of $\delta$,
we discuss the following two cases.

#### Case 1: $\tau=T$.

If none of the resources depletes before time horizon $T$, i.e., $\tau=T$, we
set $\delta=0$. Now, Eq. (50) implies that

$\displaystyle\mathcal{\widetilde{R}}\leq\frac{C_{1}}{\eta}+C_{2}\eta
T+\sum_{t=1}^{\tau}4\Delta_{t}(p_{t}).$

#### Case 2: $\tau<T$.

If $\tau<T$, then there exists a resource $i\in[M]$ such that

$\sum_{t=1}^{\tau}[Ad_{t}]_{i}+\|A\|_{\infty}\overline{d}\geq T\gamma_{i}.$
(51)

We now set $\delta=\left([r(p^{*})+\phi(AD(p^{*}))]/\gamma_{i}\right)e_{i}$
where $e_{i}$ is the $i$-th unit vector, it is easy to verify that
$\mu=\overline{\mu}+\delta\in\mathcal{D}$. Thus, combining Eq. (36) and Eq.
(51), we have that

$\displaystyle\sum_{t=1}^{\tau}\left\langle\delta,g_{t}\right\rangle$
$\displaystyle\leq\left([r(p^{*})+\phi(AD(p^{*}))]/\gamma_{i}\right)\sum_{t=1}^{\tau}([s_{t}]_{i}-[AD(p_{t})]_{i})$
$\displaystyle\leq\left([r(p^{*})+\phi(AD(p^{*}))]/\gamma_{i}\right)\sum_{t=1}^{\tau}(\gamma_{i}-[Ad_{t}]_{i})+\mathcal{O}(\|A\|_{\infty}\overline{d}\sqrt{T\log(MT)})$
$\displaystyle\leq\left([r(p^{*})+\phi(AD(p^{*}))]/\gamma_{i}\right)\left((\tau-T)\gamma_{i}+\|A\|_{\infty}\overline{d}\right)+\mathcal{O}(\|A\|_{\infty}\overline{d}\sqrt{T\log(MT)}).$
(52)

Plugging Eq. (52) back into Eq. (50), we obtain that

$\displaystyle\mathcal{\widetilde{R}}$
$\displaystyle\leq\left(\|A\|_{\infty}\overline{d}/\underline{\gamma}\right)[r(p^{*})+\phi(AD(p^{*}))]+\mathcal{O}(\|A\|_{\infty}\overline{d}\sqrt{T\log(MT)})+\frac{C_{1}}{\eta}+C_{2}\eta
T+\sum_{t=1}^{\tau}4\Delta_{t}(p_{t}).$

Combining the above two cases and setting $\eta=\sqrt{\frac{C_{1}}{C_{2}T}}$,
together with Lemma 4.3, we get that

$\displaystyle{\widetilde{\mathcal{R}}}$
$\displaystyle\leq\left(\|A\|_{\infty}\overline{d}/\underline{\gamma}\right)[r(p^{*})+\phi(AD(p^{*}))]+\mathcal{O}(\|A\|_{\infty}\overline{d}\sqrt{T\log(MT)})$
$\displaystyle\qquad+2\sqrt{C_{1}C_{2}T}+\mathcal{O}\left(\sqrt{N+1}\kappa\max\\{\overline{p},1\\}(N\overline{p}+\max\\{C\|A\|_{\infty},1\\})\right)\times\sqrt{NT\log(N+1+\overline{p}^{2}T)}.$

Together with Eq. (40) and the discussion about the rare case when either of
the desired events of Corollary 4.2 and Lemma 6.3 fails, we conclude that

$\displaystyle\mathcal{R}(T)$
$\displaystyle\leq\left(\|A\|_{\infty}\overline{d}/\underline{\gamma}+\mathcal{O}(1)\right)[r(p^{*})+\phi(AD(p^{*}))]+\mathcal{O}(\|A\|_{\infty}\overline{d}\sqrt{T\log(MT)})$
$\displaystyle+2\sqrt{C_{1}C_{2}T}+\mathcal{O}\left(\sqrt{N+1}\kappa\max\\{\overline{p},1\\}(N\overline{p}+\max\\{C\|A\|_{\infty},1\\})\right)\times\sqrt{NT\log(N+1+\overline{p}^{2}T)}.\Halmos$

##  7 Numerical Experiments

In this section, we present the numerical experiments on the synthetic data
sets to illustrate the effectiveness of our algorithm. For consistency, we use
the NRM example presented in (Besbes and Zeevi 2012, Ferreira et al. 2018). In
this example, the retailer sells two products ($N=2$) using three resources
($M=3$), and the resource consumption matrix is defined as

$U=\begin{bmatrix}1&1\\\ 3&1\\\ 0&5\end{bmatrix}.$

The underlying linear demand function is defined as

$D(p)=\begin{bmatrix}8\\\ 9\end{bmatrix}+\begin{bmatrix}-1.5&0\\\
0&-3\end{bmatrix}p.$

In contrast to (Besbes and Zeevi 2012, Ferreira et al. 2018) which use a
discrete price set in their experiments, we use the continuous price set to
test the effectiveness of our algorithm for handling large price sets. We
assume that the price range for each product is $[1,5]$.

In addition, we choose the weighted min-max fairness regularizer

$\phi(s):=\lambda\min_{i}(w_{i}s_{i})$

with $w_{i}=1$ for all $i$. And we test two initial inventory levels
($\gamma=(15,12,30)$ and $\gamma=(10,8,20)$) and four fairness regularization
level ($\lambda\in\\{0,0.5,1.0,1.5\\}$). For brevity, we present the numerical
results of $\gamma=(15,12,30)$ in this section and leave the numerical results
of initial inventory level $\gamma=(10,8,20)$ to Section 13 in the
supplementary materials.

Implementation Details. We implement Algorithm 1 with $C=5$,
$\eta=0.01/\sqrt{T}$ and time horizon
$T\in\\{100,500,1000,2000,3000,4000,6000,8000,10000\\}$. We generate the
demand noise from the truncated Gaussian distribution

$\mathrm{clip}(\mathcal{N}(0,1),1),\text{~{}~{}~{}where~{}}\mathrm{clip}(x,1)=\left\\{\begin{array}[]{rr}-1&x<-1;\\\
x&|x|\leq 1;\\\ 1&x>1\end{array}\right\\}.$

We set the coefficient of $\|\Lambda_{t}^{-1/2}\widetilde{p}\|_{\infty}$ in
Eq. (27) as $20\sqrt{\ln{T}}$. Although the regression regularization
parameter in Eq. (6) was set as $N+1$ to obtain better dependency on $N$ of
the theoretical regret bound, we fix this parameter to be $0.001$ in our
experiments for the better empirical performance. We conduct $10$ trials
independently for each case, and plot the average result of these trials in
Figure 2 and Figure 2. We also use the shaded region around each curve to
indicate the $95\%$ confidence interval across the $10$ trials.

Figure 1: The performance of Algorithm 1 with $\gamma=(15,12,30)$ and
$\lambda\in\\{0,0.5,1.0,1.5\\}$. Here the $x$-axis of the left figure is the
square root of the total time periods $T$ and the $y$-axis is the cumulative
regret defined in Eq. (5). The $x$-axis of the right figure is the total time
periods $T$ and the $y$-axis is the relative regret defined in Eq. (53).

Figure 2: The max-min fairness
$\min_{i}\left(\frac{1}{T}\sum_{t=1}^{T}[Ad_{t}]_{i}\right)$ and the average
reward $\frac{1}{T}\sum_{t=1}^{T}r(p_{t})$ at regularization levels
$\lambda\in\\{0,0.5,1.0,1.5\\}$ under the initial inventory level
$\gamma=(15,12,30)$.

Results. In the left of Figure 2 is the plot of the regret of Algorithm 1 with
$\gamma=(15,12,30)$ and $\lambda\in\\{0,0.5,1.0,1.5\\}$ versus the square root
of the total time periods $T$. This figure clearly demonstrates the regret of
our algorithm grows at rate $\mathcal{\widetilde{O}}(\sqrt{T})$ for all
regularization levels $\lambda\in\\{0,0.5,1.0,1.5\\}$, which is consistent
with the theoretical guarantee of Theorem 6.1. In the right of Figure 2 we
plot the relative regret of Algorithm 1 versus the total time periods $T$,
where the relative regret is defined as

$\frac{T[r(p^{*})+\phi(AD(p^{*}))]-\mathbb{E}\left[\sum_{t=1}^{T}r(p_{t})+T\phi\left(\frac{1}{T}\sum_{t=1}^{T}Ad_{t}\right)\right]}{T[r(p^{*})+\phi(AD(p^{*}))]}.$
(53)

Note that the narrow $95\%$ confidence intervals indicate the stability and
robustness of our algorithm.

We further empirically study the impact of the fairness regularization level
$\lambda$ to the utilization of the resources. In the left of Figure 2 is the
plot of the max-min fairness versus the total time periods $T$ with
$\gamma=(15,12,30)$ and $\lambda\in\\{0,0.5,1.0,1.5\\}$, where the max-min
fairness is defines as the minimum element of the average resource consumption
vector $\min_{i}\left(\frac{1}{T}\sum_{t=1}^{T}[Ad_{t}]_{i}\right)$. In the
right of Figure 2 we plot the average reward versus the total time periods
$T$, where the average reward is defines as
$\frac{1}{T}\sum_{t=1}^{T}r(p_{t})$. These figures show the max-min fairness
increases and the average reward decreases as $\lambda$ grows, indicating the
natural trade-off between fairness and the average reward. We also find that
the max-min fairness could be enhanced greatly with a small sacrifice of the
average reward reduction. In addition, the variance of max-min fairness is
large when there is no fairness regularizer ($\lambda=0$), and the variance
becomes very small after introducing the fairness regularizer. This
interesting phenomenon shows that the fairness regularizer could not only
enhance the max-min fairness, but also provide good control of its variance.

##  8 Conclusion

This paper studies the price-based network revenue management with both
fairness concern and demand learning, which is motivated by the practical
needs of industries such as online retailing and airline applications. To
tackle the challenges of this task, we make several innovative technical
contributions, which have the potential to be applied to other operations
management problems. We propose a primal-dual-type online policy with Upper-
Confidence-Bound (UCB) learning method to simultaneously learn the unknown
demand function and optimize the composite objective concerning both the NRM
revenue and the fairness metric. Both theoretical analysis and numerical
results show the effectiveness and the ability to balance the trade-off
between revenue and fairness of the developed policy.

For future directions, one can consider adapting the framework in this paper
to other revenue management applications with both fairness concern and demand
learning. One could also study the demand learning of non-parametric demand
functions and consider adapting our framework to other global ancillary
objectives beyond fair consumption across resources.

## References

  * Abbasi-Yadkori et al. (2011) Abbasi-Yadkori Y, Pál D, Szepesvári C (2011) Improved algorithms for linear stochastic bandits. _Advances in Neural Information Processing Systems_ 24:2312–2320.
  * Agarwal et al. (2018) Agarwal A, Beygelzimer A, Dudík M, Langford J, Wallach H (2018) A reductions approach to fair classification. _International Conference on Machine Learning_ , 60–69.
  * Agrawal and Devanur (2016) Agrawal S, Devanur N (2016) Linear contextual bandits with knapsacks. _Advances in Neural Information Processing Systems_ 29:3458–3467.
  * Agrawal and Devanur (2019) Agrawal S, Devanur NR (2019) Bandits with global convex constraints and objective. _Operations Research_ 67(5):1486–1502.
  * Azar et al. (2010) Azar Y, Buchbinder N, Jain K (2010) How to allocate goods in an online market? _European Symposium on Algorithms_ , 51–62.
  * Badanidiyuru et al. (2013) Badanidiyuru A, Kleinberg R, Slivkins A (2013) Bandits with knapsacks. _2013 IEEE 54th Annual Symposium on Foundations of Computer Science_ , 207–216.
  * Baek and Farias (2021) Baek J, Farias V (2021) Fair exploration via axiomatic bargaining. _Advances in Neural Information Processing Systems_ 34:22034–22045.
  * Balseiro et al. (2020) Balseiro S, Lu H, Mirrokni V (2020) Regularized online allocation problems: Fairness and beyond. _arXiv preprint arXiv:2007.00514_ .
  * Balseiro et al. (2022) Balseiro SR, Lu H, Mirrokni V (2022) The best of many worlds: Dual mirror descent for online allocation problems. _Operations Research_ Forthcoming.
  * Bansal and Sviridenko (2006) Bansal N, Sviridenko M (2006) The santa claus problem. _Proceedings of the 38th annual ACM symposium on Theory of computing_ , 31–40.
  * Bateni et al. (2022) Bateni M, Chen Y, Ciocan DF, Mirrokni V (2022) Fair resource allocation in a volatile marketplace. _Operations Research_ 70(1):288–308.
  * Beck and Teboulle (2003) Beck A, Teboulle M (2003) Mirror descent and nonlinear projected subgradient methods for convex optimization. _Operations Research Letters_ 31(3):167–175.
  * Bertsimas et al. (2011) Bertsimas D, Farias VF, Trichakis N (2011) The price of fairness. _Operations research_ 59(1):17–31.
  * Besbes and Zeevi (2009) Besbes O, Zeevi A (2009) Dynamic pricing without knowing the demand function: Risk bounds and near-optimal algorithms. _Operations Research_ 57(6):1407–1420.
  * Besbes and Zeevi (2012) Besbes O, Zeevi A (2012) Blind network revenue management. _Operations research_ 60(6):1537–1550.
  * Bonald et al. (2006) Bonald T, Massoulié L, Proutiere A, Virtamo J (2006) A queueing analysis of max-min fairness, proportional fairness and balanced fairness. _Queueing systems_ 53(1):65–84.
  * Boyd et al. (2004) Boyd S, Boyd SP, Vandenberghe L (2004) _Convex optimization_ (Cambridge university press).
  * Bu et al. (2022) Bu J, Simchi-Levi D, Xu Y (2022) Online pricing with offline data: Phase transition and inverse square law. _Management Science_ Forthcoming.
  * Cai et al. (2021) Cai W, Gaebler J, Garg N, Goel S (2021) Fair allocation through selective information acquisition. _AAAI/ACM Conference on Artificial Intelligence, Ethics, and Society_ , 22–28.
  * Cesa-Bianchi and Lugosi (2006) Cesa-Bianchi N, Lugosi G (2006) _Prediction, learning, and games_ (Cambridge university press).
  * Chen et al. (2021a) Chen G, Li X, Ye Y (2021a) Fairer LP-based online allocation via analytic center. _arXiv preprint arXiv:2110.14621_ .
  * Chen et al. (2014) Chen Q, Jasin S, Duenyas I (2014) Adaptive parametric and nonparametric multi-product pricing via self-adjusting controls. _Ross School of Business Paper_ (1258).
  * Chen et al. (2019) Chen Q, Jasin S, Duenyas I (2019) Nonparametric self-adjusting control for joint learning and optimization of multiproduct pricing with finite resource capacity. _Mathematics of Operations Research_ 44(2):601–631.
  * Chen et al. (2021b) Chen X, Zhang X, Zhou Y (2021b) Fairness-aware online price discrimination with nonparametric demand models. _arXiv preprint arXiv:2111.08221_ .
  * Chen and Shi (2019) Chen Y, Shi C (2019) Network revenue management with online inverse batch gradient descent method. _Available at SSRN 3331939_ .
  * Chen and Wang (2018) Chen Y, Wang H (2018) Why are fairness concerns so important? lessons from a shared last-mile transportation system. _Available at SSRN 3168324_ .
  * Cohen et al. (2022) Cohen MC, Elmachtoub AN, Lei X (2022) Price discrimination with fairness constraints. _Management Science_ Forthcoming.
  * Cohen et al. (2021) Cohen MC, Miao S, Wang Y (2021) Dynamic pricing with fairness constraints. _Available at SSRN 3930622_ .
  * Corbett-Davies and Goel (2018) Corbett-Davies S, Goel S (2018) The measure and mismeasure of fairness: A critical review of fair machine learning. _arXiv preprint arXiv:1808.00023_ .
  * Dani et al. (2008) Dani V, Hayes TP, Kakade SM (2008) Stochastic linear optimization under bandit feedback. _Conference on Learning Theory_ 355–366.
  * Den Boer (2014) Den Boer AV (2014) Dynamic pricing with multiple products and partially specified demand distribution. _Mathematics of operations research_ 39(3):863–888.
  * Den Boer (2015) Den Boer AV (2015) Dynamic pricing and learning: historical origins, current research, and new directions. _Surveys in operations research and management science_ 20(1):1–18.
  * Den Boer and Zwart (2014) Den Boer AV, Zwart B (2014) Simultaneously learning and optimizing using controlled variance pricing. _Management science_ 60(3):770–783.
  * Donahue and Kleinberg (2020) Donahue K, Kleinberg J (2020) Fairness and utilization in allocating resources with uncertain demand. _Proceedings of the 2020 Conference on Fairness, Accountability, and Transparency_ , 658–668.
  * Dwork et al. (2012) Dwork C, Hardt M, Pitassi T, Reingold O, Zemel R (2012) Fairness through awareness. _Proceedings of the 3rd Innovations in Theoretical Computer Science Conference_ , 214–226.
  * Elzayn et al. (2019) Elzayn H, Jabbari S, Jung C, Kearns M, Neel S, Roth A, Schutzman Z (2019) Fair algorithms for learning in allocation problems. _Proceedings of the Conference on Fairness, Accountability, and Transparency_ , 170–179.
  * Ferreira et al. (2018) Ferreira KJ, Simchi-Levi D, Wang H (2018) Online network revenue management using thompson sampling. _Operations research_ 66(6):1586–1602.
  * Gallego and Van Ryzin (1994) Gallego G, Van Ryzin G (1994) Optimal dynamic pricing of inventories with stochastic demand over finite horizons. _Management science_ 40(8):999–1020.
  * Gallego and Van Ryzin (1997) Gallego G, Van Ryzin G (1997) A multiproduct dynamic pricing problem and its applications to network yield management. _Operations Research_ 45(1):24–41.
  * Grötschel et al. (2012) Grötschel M, Lovász L, Schrijver A (2012) _Geometric algorithms and combinatorial optimization_ , volume 2 (Springer Science & Business Media).
  * Gupta and Kamble (2021) Gupta S, Kamble V (2021) Individual fairness in hindsight. _Journal of Machine Learning Research_ 22(144):1–35.
  * Hazan et al. (2016) Hazan E, et al. (2016) Introduction to online convex optimization. _Foundations and Trends in Optimization_ 2(3-4):157–325.
  * Hoeven et al. (2018) Hoeven D, Erven T, Kotłowski W (2018) The many faces of exponential weights in online learning. _Conference On Learning Theory_ , 2067–2092.
  * Hutchinson and Mitchell (2019) Hutchinson B, Mitchell M (2019) 50 years of test (un)fairness: Lessons for machine learning. _Proceedings of the conference on fairness, accountability, and transparency_ , 49–58.
  * Jabbari et al. (2017) Jabbari S, Joseph M, Kearns M, Morgenstern J, Roth A (2017) Fairness in reinforcement learning. _International conference on machine learning_ , 1617–1626.
  * Jang et al. (2022) Jang T, Shi P, Wang X (2022) Group-aware threshold adaptation for fair classification. _Proceedings of the AAAI Conference on Artificial Intelligence_ 36(6):6988–6995.
  * Jasin (2014) Jasin S (2014) Reoptimization and self-adjusting price control for network revenue management. _Operations Research_ 62(5):1168–1178.
  * Joseph et al. (2016) Joseph M, Kearns M, Morgenstern JH, Roth A (2016) Fairness in learning: Classic and contextual bandits.
  * Kallus et al. (2022) Kallus N, Mao X, Zhou A (2022) Assessing algorithmic fairness with unobserved protected class using data combination. _Management Science_ 68(3):1959–1981.
  * Kallus and Zhou (2021) Kallus N, Zhou A (2021) Fairness, welfare, and equity in personalized pricing. _Proceedings of the 2021 ACM Conference on Fairness, Accountability, and Transparency_ , 296–314.
  * Kandasamy et al. (2020) Kandasamy K, Sela GE, Gonzalez JE, Jordan MI, Stoica I (2020) Online learning demands in max-min fairness. _arXiv preprint arXiv:2012.08648v1_ .
  * Keskin and Zeevi (2014) Keskin NB, Zeevi A (2014) Dynamic pricing with an unknown demand model: Asymptotically optimal semi-myopic policies. _Operations research_ 62(5):1142–1167.
  * Keskin and Zeevi (2017) Keskin NB, Zeevi A (2017) Chasing demand: Learning and earning in a changing environment. _Mathematics of Operations Research_ 42(2):277–307.
  * Kivinen and Warmuth (1997) Kivinen J, Warmuth MK (1997) Exponentiated gradient versus gradient descent for linear predictors. _information and computation_ 132(1):1–63.
  * Klein et al. (2020) Klein R, Koch S, Steinhardt C, Strauss AK (2020) A review of revenue management: Recent generalizations and advances in industry applications. _European journal of operational research_ 284(2):397–412.
  * Li and Jain (2016) Li KJ, Jain S (2016) Behavior-based pricing: An analysis of the impact of peer-induced fairness. _Management Science_ 62(9):2705–2721.
  * Liu et al. (2017) Liu Y, Radanovic G, Dimitrakakis C, Mandal D, Parkes DC (2017) Calibrated fairness in bandits. _arXiv preprint arXiv:1707.01875_ .
  * Ma et al. (2020) Ma W, Xu P, Xu Y (2020) Group-level fairness maximization in online bipartite matching. _arXiv preprint arXiv:2011.13908_ .
  * Maglaras and Meissner (2006) Maglaras C, Meissner J (2006) Dynamic pricing strategies for multiproduct revenue management problems. _Manufacturing & Service Operations Management_ 8(2):136–148.
  * Mehrabi et al. (2021) Mehrabi N, Morstatter F, Saxena N, Lerman K, Galstyan A (2021) A survey on bias and fairness in machine learning. _ACM Computing Surveys (CSUR)_ 54(6):1–35.
  * Miao and Wang (2021) Miao S, Wang Y (2021) Network revenue management with nonparametric demand learning: $\sqrt{T}$-regret and polynomial dimension dependency. _Available at SSRN 3948140_ .
  * Miao et al. (2021) Miao S, Wang Y, Zhang J (2021) A general framework for resource constrained revenue management with demand learning and large action space. _Available at SSRN 3841273_ .
  * Nash Jr (1950) Nash Jr JF (1950) The bargaining problem. _Econometrica: Journal of the econometric society_ 155–162.
  * Rusmevichientong and Tsitsiklis (2010) Rusmevichientong P, Tsitsiklis JN (2010) Linearly parameterized bandits. _Mathematics of Operations Research_ 35(2):395–411.
  * Talluri et al. (2004) Talluri KT, Van Ryzin G, Van Ryzin G (2004) _The theory and practice of revenue management_ (Springer).
  * Vlasiou et al. (2014) Vlasiou M, Zhang J, Zwart B (2014) Insensitivity of proportional fairness in critically loaded bandwidth sharing networks. _arXiv preprint arXiv:1411.4841_ .
  * Wang and Wang (2022) Wang Y, Wang H (2022) Constant regret resolving heuristics for price-based revenue management. _Operations Research_ Forthcoming.
  * Wang et al. (2014) Wang Z, Deng S, Ye Y (2014) Close the gaps: A learning-while-doing algorithm for single-product revenue management problems. _Operations Research_ 62(2):318–331.
  * Zhang et al. (2022) Zhang Z, Shi P, Ward AR (2022) Routing for fairness and efficiency in a queueing model with reentry and continuous customer classes. _Proceedings of the American Control Conference (ACC)_.

Supplementary materials

##  9 Some useful technical lemmas

######  Lemma 9.1 (Azuma-Hoeffding Inequality)

Let
$\left(\left\\{\left(D_{k},\mathcal{F}_{k}\right)\right\\}_{k=1}^{\infty}\right)$
be a martingale difference sequence for which there are constants
$\left\\{\left(a_{k},b_{k}\right)\right\\}_{k=1}^{n}$ such that
$D_{k}\in\left[a_{k},b_{k}\right]$ almost surely for all $k=1,\ldots,n$. Then,
for all $t\geq 0$,

$\mathbb{P}\left[\left|\sum_{k=1}^{n}D_{k}\right|\geq t\right]\leq
2\mathrm{exp}\left(-\frac{2t^{2}}{\sum_{k=1}^{n}\left(b_{k}-a_{k}\right)^{2}}\right).$

Recall that $\mathcal{B}=[B|\alpha]\in\mathbb{R}^{N\times(N+1)}$
$\widehat{\mathcal{B}}=[\widehat{B}|\widehat{\alpha}]\in\mathbb{R}^{N\times(N+1)}$,
and $\widetilde{p}:=(p,1)$. Thus we have
$d_{t}^{\top}e_{i}=(\mathcal{B}^{\top}e_{i})^{\top}\widetilde{p}_{t}+\varepsilon_{i}$.
Noting $\left\|\mathcal{B}^{\top}e_{i}\right\|_{2}\leq L_{B}$,
$\varepsilon_{i}\leq\overline{d}$ and
$\|\widetilde{p}_{t}\|_{2}\leq\overline{p}\sqrt{N+1}$ and applying the Theorem
2 in Abbasi-Yadkori et al. (2011), we have the following confidence ellipsoid
lemma.

###### Lemma 9.2

Recall that
$\Lambda_{t}=(N+1)\cdot\mathbf{I}_{N+1}+\sum_{s<t}\widetilde{p}_{s}\widetilde{p}_{s}^{\top}$,
for any $\delta>0$, with probability at least $1-\delta$, for all $t$ we have

$\mathbb{P}\left[\|(\mathcal{B}-\widehat{\mathcal{B}}_{t})^{\top}e_{i}\|_{\Lambda_{t}}\leq\overline{d}\sqrt{(N+1)\ln\left(\frac{1+t\overline{p}^{2}}{\delta}\right)}+\sqrt{N+1}L_{B}\right]\geq
1-\delta.$ (54)

##  10 Proofs Omitted in Section 2

###  10.1 Proof of Proposition 2.1

###### Proof 10.1

Proof of Proposition 2.1. By the constraint of Eq. (1) , it is easy to obtain
$\mathbb{E}\left[\sum_{t=1}^{T}Ad_{t}\right]\leq T\gamma$. Therefore,

$\displaystyle J_{\mathrm{opt}}$
$\displaystyle\leq\left\\{\begin{array}[]{cl}\max\limits_{\pi}&\
\mathbb{E}\left[\sum_{t=1}^{T}r(p_{t})+T\phi\left(\frac{1}{T}\sum_{t=1}^{T}Ad_{t}\right)\right]\\\
\text{s.t.}&\ \mathbb{E}\left[\sum_{t=1}^{T}AD(p_{t})\right]\leq
T\gamma\end{array}\right\\}.$

With the concavity of $r(p_{t})$ by Jenson’s inequality we obtain

$\sum_{t=1}^{T}r(p_{t})\leq Tr\left(\frac{1}{T}\sum_{t=1}^{T}p_{t}\right).$

Therefore, we have

$\displaystyle\left\\{\begin{array}[]{cl}\max\limits_{\pi}&\
\mathbb{E}\left[\sum_{t=1}^{T}r(p_{t})+T\phi\left(\frac{1}{T}\sum_{t=1}^{T}Ad_{t}\right)\right]\\\
\text{s.t.}&\ \mathbb{E}\left[\sum_{t=1}^{T}AD(p_{t})\right]\leq
T\gamma\end{array}\right\\}$
$\displaystyle\leq\left\\{\begin{array}[]{cl}\max\limits_{\pi}&\
\mathbb{E}\left[Tr\left(\frac{1}{T}\sum_{t=1}^{T}p_{t}\right)+T\phi\left(\frac{1}{T}\sum_{t=1}^{T}Ad_{t}\right)\right]\\\
\text{s.t.}&\ \mathbb{E}\left[\sum_{t=1}^{T}AD(p_{t})\right]\leq
T\gamma\end{array}\right\\}.$

With the concavity of $r(\cdot)$ and $\phi(\cdot)$, using Jenson’s inequality
again, we have

$\displaystyle\left\\{\begin{array}[]{cl}\max\limits_{\pi}&\
\mathbb{E}\left[Tr\left(\frac{1}{T}\sum_{t=1}^{T}p_{t}\right)+T\phi\left(\frac{1}{T}\sum_{t=1}^{T}Ad_{t}\right)\right]\\\
\text{s.t.}&\ \mathbb{E}\left[\sum_{t=1}^{T}AD(p_{t})\right]\leq
T\gamma\end{array}\right\\}$
$\displaystyle\leq\left\\{\begin{array}[]{cl}\max\limits_{\pi}&\
Tr\left(\mathbb{E}\left[\frac{1}{T}\sum_{t=1}^{T}p_{t}\right]\right)+T\phi\left(\mathbb{E}\left[\frac{1}{T}\sum_{t=1}^{T}AD(p_{t})\right]\right)\\\
\text{s.t.}&\ \mathbb{E}\left[\sum_{t=1}^{T}AD(p_{t})\right]\leq
T\gamma\end{array}\right\\}$ $\displaystyle\leq J_{D},$

where the last inequality is due to Eq. (4). Combining the above inequalities,
we complete the proof.

###  10.2 Assumptions Validation of the Fairness Regularizers

We will prove the fairness regularizers proposed in Section 2.1 satisfy
Assumption 2.1 (we only validate Assumption 1.1 and Assumption 1.3, since
Assumption 1.2 can be easily validated).

Example 1: Weighted Max-min Fairness Regularizer:
$\phi(s):=\lambda\min_{i}(w_{i}s_{i})$.

We first show $\phi(\cdot)$ is $L$-Lipschitz continuous with respect to the
$\|\cdot\|_{\infty}$-norm in the following way,

$\displaystyle\phi(s)-\phi(t)$
$\displaystyle=\lambda(\min_{i}(w_{i}s_{i})-\min_{i}(w_{i}t_{i}))$
$\displaystyle\leq\lambda\max_{i}(|w_{i}s_{i}-w_{i}t_{i}|)$
$\displaystyle\leq(\lambda\max_{i}w_{i})\|s-t\|_{\infty}.$

Next we will show the convatity of $\phi(\cdot)$. For any $s,t$ and
$\alpha\in[0,1]$, we have

$\displaystyle\phi(\alpha s+(1-\alpha)t)$
$\displaystyle=\lambda(\min_{i}(\alpha w_{i}s_{i}+(1-\alpha)w_{i}t_{i})$
$\displaystyle\geq\lambda(\alpha\min_{i}(w_{i}s_{i})+(1-\alpha)\min_{i}(w_{i}t_{i}))$
$\displaystyle\geq\alpha\phi(s)+(1-\alpha)\phi(t).$

Example 2: Group Max-min Fairness Regularizer:
$\phi(s):=\lambda\min_{i}((U\widetilde{s})_{i})$, where
$\widetilde{s}=(w_{1}s_{1},\cdots,w_{m}s_{m})^{\top}$.

We first show $\phi(\cdot)$ is $L$-Lipschitz continuous with respect to the
$\|\cdot\|_{\infty}$-norm in the following way,

$\displaystyle\phi(s)-\phi(t)$
$\displaystyle=\lambda(\min_{i}((U\widetilde{s})_{i})-\min_{i}((U\widetilde{t})_{i}))$
$\displaystyle\leq\lambda\|U(\widetilde{s}-\widetilde{t})\|_{\infty}$
$\displaystyle\leq\lambda\|U\|_{\infty}\|\widetilde{s}-\widetilde{t}\|_{\infty}$
$\displaystyle\leq(\lambda\|U\|_{\infty}\max_{i}w_{i})\|s-t\|_{\infty}.$

Next we will show the convatity of $\phi(\cdot)$. For any $s,t$ and
$\alpha\in[0,1]$, we have

$\displaystyle\phi(\alpha s+(1-\alpha)t)$
$\displaystyle=\lambda(\min_{i}(\alpha(U\widetilde{s})_{i}+(1-\alpha)(U\widetilde{t})_{i})$
$\displaystyle\geq\lambda(\alpha\min_{i}((U\widetilde{s})_{i})+(1-\alpha)\min_{i}((U\widetilde{t})_{i}))$
$\displaystyle\geq\alpha\phi(s)+(1-\alpha)\phi(t).$

Example 3: Range Fairness
Regularizer:$\phi(s):=\lambda(\min_{i}(w_{i}s_{i})-\max_{i}(w_{i}s_{i})+\max_{i}(w_{i}\gamma_{i}))$.
Example 4: Load Balancing
Regularizer:$\phi(s):=\lambda(\min_{i}((\gamma_{i}-s_{i})/\gamma_{i})$.

We have shown $\min_{i}(w_{i}s_{i})$ is $L$-Lipschitz continuous with respect
to the $\|\cdot\|_{\infty}$-norm and concave. By this fact, it is easy to note
that Example 3 and Example 4 are also satisfy Assumption 2.1.

##  11 Proofs Omitted in Section 3

###  11.1 Proof of Lemma 4.1

###### Proof 11.1

Proof of Lemma 4.1. Let $\delta$ in Lemma 9.2 be $1/(NT)$, and thus with
probability $1-1/T$ for any $i\in[N]$ and $t\leq\tau$ it holds that

$\displaystyle\|(\mathcal{B}-\widehat{\mathcal{B}}_{t})^{\top}e_{i}\|^{2}_{\Lambda_{t}}$
$\displaystyle=\|\Lambda_{t}^{1/2}((\mathcal{B}-\widehat{\mathcal{B}}_{t})^{\top}e_{i})\|^{2}_{2}$
$\displaystyle\leq
2\overline{d}^{2}(N+1)\ln\left(NT(1+\overline{p}^{2}T)\right)+2(N+1)L_{B}^{2},$
(55)

where the inequality is due to $(a+b)^{2}\leq 2a^{2}+2b^{2}$.

By Eq. (55) and Cauchy-Schwarz inequality, we have

$\displaystyle\|(\widehat{\mathcal{B}}_{t}-\mathcal{B})\widetilde{p}\|_{\infty}$
$\displaystyle\leq\max_{i\in[N]}|((\mathcal{B}-\widehat{\mathcal{B}}_{t})^{\top}e_{i})^{\top}\widetilde{p}|$
$\displaystyle\leq\max_{i\in[N]}|((\mathcal{B}-\widehat{\mathcal{B}}_{t})^{\top}e_{i})^{\top}\Lambda_{t}^{1/2}\Lambda_{t}^{-1/2}\widetilde{p}|$
$\displaystyle\leq\max_{i\in[N]}\|\Lambda_{t}^{1/2}((\mathcal{B}-\widehat{\mathcal{B}}_{t})^{\top}e_{i})\|_{2}\|\Lambda_{t}^{-1/2}\widetilde{p}\|_{2}$
$\displaystyle\leq\sqrt{2\overline{d}^{2}(N+1)\ln\left(NT(1+\overline{p}^{2}T)\right)+2(N+1)L_{B}^{2}}\sqrt{\widetilde{p}^{\top}\Lambda_{t}^{-1}\widetilde{p}}.$
(56)

Noting that
$\|(\widehat{\mathcal{B}}_{t}-\mathcal{B})\widetilde{p}\|_{2}\leq\sqrt{N}\|(\widehat{\mathcal{B}}_{t}-\mathcal{B})\widetilde{p}\|_{\infty}$,
by Eq. (56) we have

$\displaystyle\|(\widehat{\mathcal{B}}_{t}-\mathcal{B})\widetilde{p}\|_{2}$
$\displaystyle\leq\sqrt{N}\|(\widehat{\mathcal{B}}_{t}-\mathcal{B})\widetilde{p}\|_{\infty}$
$\displaystyle\leq\sqrt{2\overline{d}^{2}N(N+1)\ln\left(NT(1+\overline{p}^{2}T)\right)+2N(N+1)L_{B}^{2}}\sqrt{\widetilde{p}^{\top}\Lambda_{t}^{-1}\widetilde{p}}.$
(57)

Proof of $\left|\widehat{r}_{t}(p)-r(p)\right|\leq\Delta_{t}^{r}(p)$.

By Eq. (57), we have

$\displaystyle\left|\langle
p,\widehat{\mathcal{B}}_{t}\widetilde{p}\rangle-\Braket{p,\mathcal{B}\widetilde{p}}\right|$
$\displaystyle\leq\|p\|_{2}\|(\widehat{\mathcal{B}}_{t}-\mathcal{B})\widetilde{p}\|_{2}$
$\displaystyle\leq\sqrt{N}\overline{p}\sqrt{2\overline{d}^{2}N(N+1)\ln\left(NT(1+\overline{p}^{2}T)\right)+2N(N+1)L_{B}^{2}}\sqrt{\widetilde{p}^{\top}\Lambda_{t}^{-1}\widetilde{p}},$
(58)

where the first inequality is due to Cauchy-Schwarz inequality.

Since for any vector $x\in\mathbb{R}^{d}$ it holds that

$\|x\|_{2}\leq\sqrt{d}\|x\|_{\infty}\leq\sqrt{d}\|x\|_{2}.$

Therefore, we have

$\displaystyle\sqrt{\widetilde{p}^{\top}\Lambda_{t}^{-1}\widetilde{p}}\leq\sqrt{N+1}\|\Lambda_{t}^{-1/2}\widetilde{p}_{t}\|_{\infty}\leq\sqrt{N+1}\sqrt{\widetilde{p}^{\top}\Lambda_{t}^{-1}\widetilde{p}}.$
(59)

Combining Eq. (58) and Eq. (59), we have

$\displaystyle\left|\widehat{r}_{t}(p)-r(p)\right|$
$\displaystyle=\left|\langle
p,\widehat{\mathcal{B}}_{t}\widetilde{p}\rangle-\Braket{p,\mathcal{B}\widetilde{p}}\right|$
$\displaystyle\leq\sqrt{N}\overline{p}\sqrt{2\overline{d}^{2}N(N+1)\ln\left(NT(1+\overline{p}^{2}T)\right)+2N(N+1)L_{B}^{2}}\sqrt{\widetilde{p}^{\top}\Lambda_{t}^{-1}\widetilde{p}}$
$\displaystyle\leq
N(N+1)\overline{p}\sqrt{2\overline{d}^{2}\ln\left(NT(1+\overline{p}^{2}T)\right)+2L_{B}^{2}}\|\Lambda_{t}^{-1/2}\widetilde{p}\|_{\infty}$
$\displaystyle\leq\Delta_{t}^{r}(p).$ (60)

Proof of $\|\widehat{D}_{t}(p)-D(p)\|_{\infty}\leq\Delta_{t}^{D}(p)$.

Combining Eq. (56) and Eq. (59), it is easy to obtain that

$\displaystyle\|\widehat{D}_{t}(p)-D(p)\|_{\infty}$
$\displaystyle=\|(\widehat{\mathcal{B}}_{t}-\mathcal{B})\widetilde{p}\|_{\infty}$
$\displaystyle\leq\sqrt{2\overline{d}^{2}(N+1)\ln\left(NT(1+\overline{p}^{2}T)\right)+2(N+1)L_{B}^{2}}\sqrt{\widetilde{p}^{\top}\Lambda_{t}^{-1}\widetilde{p}}$
$\displaystyle\leq(N+1)\sqrt{2\overline{d}^{2}\ln\left(NT(1+\overline{p}^{2}T)\right)+2L_{B}^{2}}\|\Lambda_{t}^{-1/2}\widetilde{p}\|_{\infty}$
$\displaystyle\leq\Delta_{t}^{D}(p).$ (61)

Proof of $|\widehat{f}_{t}(p)-f_{t}(p)|\leq\Delta_{t}^{f}(p)$.

By Eq. (61), with probability $1-1/T$ we have

$\displaystyle\left|\left\langle\mu_{t},A\widehat{D}_{t}(p)-AD(p)\right\rangle\right|$
$\displaystyle\leq\|\mu_{t}\|_{1}\cdot\|A(\widehat{D}_{t}(p)-D(p))\|_{\infty}$
$\displaystyle\leq\|\mu_{t}\|_{1}\cdot\|A\|_{\infty}\Delta_{t}^{D}(p).$ (62)

Since $f_{t}(p)=r(p)-\langle\mu_{t},AD(p)\rangle$,
$\widehat{f}_{t}(p)=\widehat{r}_{t}(p)-\left\langle\mu_{t},A\widehat{D}_{t}(p)\right\rangle$
and
$\Delta_{t}^{f}(p)=\Delta_{t}^{r}(p)+\|\mu_{t}\|_{1}\cdot\|A\|_{\infty}\Delta_{t}^{D}(p)$.
Combining Eq. (60) and Eq. (62), we have

$\displaystyle|\widehat{f}_{t}(p)-f_{t}(p)|$
$\displaystyle\leq\left|\widehat{r}_{t}(p)-r_{t}(p)\right|+\left|\left\langle\mu_{t},A\widehat{D}_{t}(p)-AD(p)\right\rangle\right|$
$\displaystyle\leq\Delta_{t}^{r}(p)+\|\mu_{t}\|_{1}\cdot\|A\|_{\infty}\Delta_{t}^{D}(p)$
$\displaystyle=\Delta_{t}^{f}(p).$

Therefore, we complete the proof of Lemma 4.1.

###  11.2 Proof of Corollary 4.2

###### Proof 11.2

Proof of Corollary 4.2. The proof will be conditioned on when we find a
feasible $(\widecheck{\alpha}_{t},\widecheck{B}_{t})\in\mathcal{M}_{t}$ for
all $t\leq\tau$ (which happens with probability
$(1-\mathcal{O}\left(T^{-1}\right))$ by Lemma 4.7) and the desired event of
Lemma 4.1.

For each $t\leq\tau$ and $p\in[\underline{p},\overline{p}]$, we first upper
bound $\|\widecheck{D}_{t}(p)-D(p)\|_{\infty}$. Note that

$\displaystyle\|\widecheck{D}_{t}(p)-D(p)\|_{\infty}\leq\|\widecheck{D}_{t}(p)-\widehat{D}(p)\|_{\infty}+\|\widehat{D}_{t}(p)-D(p)\|_{\infty}\leq\|\widecheck{D}_{t}(p)-\widehat{D}(p)\|_{\infty}+\Delta_{t}^{D}(p).$

Therefore, we only need to show that
$\|\widecheck{D}_{t}(p)-\widehat{D}(p)\|_{\infty}\leq\Delta_{t}^{D}(p)$ to
prove that $\|\widecheck{D}_{t}(p)-D(p)\|_{\infty}\leq 2\Delta_{t}^{D}(p)$.
For every $i\in[N]$, let
$\widecheck{\mathcal{B}}_{t}=[\widecheck{B}_{t}|\widecheck{\alpha}_{t}]$, and
we verify that

$\displaystyle|e_{i}^{\top}(\widecheck{D}_{t}(p)-\widehat{D}(p))|$
$\displaystyle=|e_{i}^{\top}(\widecheck{\mathcal{B}}_{t}-\widehat{\mathcal{B}}_{t})\widetilde{p}|=|e_{i}^{\top}(\widecheck{\mathcal{B}}_{t}-\widehat{\mathcal{B}}_{t})\Lambda_{t}^{1/2}\Lambda_{t}^{-1/2}\widetilde{p}|$
$\displaystyle\leq\|\Lambda_{t}^{1/2}(\widecheck{\mathcal{B}}_{t}-\widehat{\mathcal{B}}_{t})^{\top}e_{i}\|\cdot\|\Lambda_{t}^{-1/2}\widetilde{p}\|\leq\kappa\|\Lambda_{t}^{-1/2}\widetilde{p}\|\leq\sqrt{N+1}\kappa\|\Lambda_{t}^{-1/2}\widetilde{p}\|_{\infty}=\Delta_{t}^{D}(p).$

Here, the first inequality is due to Cauchy-Schwarz, the second inequality is
due to that $(\widecheck{\alpha}_{t},\widecheck{B}_{t})\in\mathcal{M}_{t}$.

We now upper bound $\left|\widecheck{r}_{t}(p)-r(p)\right|$ as follows.

$\displaystyle\left|\widecheck{r}_{t}(p)-r(p)\right|\leq\left|\widecheck{r}_{t}(p)-\widehat{r}(p)\right|+\left|\widehat{r}_{t}(p)-r(p)\right|\leq
N\overline{p}\|\widecheck{D}_{t}(p)-\widehat{D}(p)\|_{\infty}+\left|\widehat{r}_{t}(p)-r(p)\right|\leq\Delta_{t}^{r}(p)+\Delta_{t}^{r}(p),$

where in the inequality, we upper bound
$\|\widecheck{D}_{t}(p)-\widehat{D}(p)\|_{\infty}$ by $\Delta_{t}^{D}(p)$ due
to the paragraph above.

We finally upper bound $|\widecheck{f}_{t}(p)-f_{t}(p)|$. Note that

$\displaystyle|\widecheck{f}_{t}(p)-f_{t}(p)|$
$\displaystyle\leq|\widecheck{f}_{t}(p)-\widehat{f}_{t}(p)|+|\widehat{f}_{t}(p)-f_{t}(p)|$
$\displaystyle\leq\left|\widecheck{r}_{t}(p)-\widehat{r}(p)\right|+\|\mu_{t}\|_{1}\cdot\|A\|_{\infty}\|\widecheck{D}_{t}(p)-\widehat{D}(p)\|_{\infty}+|\widehat{f}_{t}(p)-f_{t}(p)|$
$\displaystyle\leq\Delta_{t}^{r}(p)+\|\mu_{t}\|_{1}\cdot\|A\|_{\infty}\Delta_{t}^{D}(p)+\Delta_{t}^{f}(p)=2\Delta_{t}^{f}(p),$

where the second inequality is by the definitions of $\widehat{f}_{t}$ and
$\widecheck{f}_{t}$, and the third inequality uses the upper bounds for
$\left|\widecheck{r}_{t}(p)-\widehat{r}(p)\right|$ and
$\|\widecheck{D}_{t}(p)-\widehat{D}(p)\|_{\infty}$ derived in the previous
parts of this proof.

###  11.3 Proof of Lemma 4.3

###### Proof 11.3

Proof of Lemma 4.3. Since
$\Lambda_{t}=(N+1)\cdot\mathbf{I}_{N+1}+\sum_{s<t}\widetilde{p}_{s}\widetilde{p}_{s}^{\top}$,
for every $t\geq 1$,
$\widetilde{p}_{t}^{\top}\Lambda_{t}^{-1}\widetilde{p}_{t}\leq\widetilde{p}_{t}^{\top}\widetilde{p}_{t}/(N+1)\leq\overline{p}^{2}$.
By this fact, we have

$\displaystyle\sqrt{\widetilde{p}_{t}^{\top}\Lambda_{t}^{-1}\widetilde{p}_{t}}$
$\displaystyle=\min\\{\overline{p},\sqrt{\widetilde{p}_{t}^{\top}\Lambda_{t}^{-1}\widetilde{p}_{t}}\\}$
$\displaystyle\leq\max\\{\overline{p},1\\}\min\\{1,\sqrt{\widetilde{p}_{t}^{\top}\Lambda_{t}^{-1}\widetilde{p}_{t}}\\}.$
(63)

Note
$\|\Lambda_{t}^{-1/2}\widetilde{p}_{t}\|_{\infty}\leq\sqrt{\widetilde{p}_{t}^{\top}\Lambda_{t}^{-1}\widetilde{p}_{t}}$
and recall the definition of $\Delta_{t}^{r}(p)$ and $\Delta_{t}^{D}(p)$ we
have

$\displaystyle\Delta_{t}^{r}(p)\leq
2N(N+1)\overline{p}\sqrt{2\overline{d}^{2}\ln\left(NT(1+\overline{p}^{2}T)\right)+2L_{B}^{2}}\sqrt{\widetilde{p}_{t}^{\top}\Lambda_{t}^{-1}\widetilde{p}_{t}},$
(64) $\displaystyle\Delta_{t}^{D}(p)\leq
2(N+1)\sqrt{2\overline{d}^{2}\ln\left(NT(1+\overline{p}^{2}T)\right)+2L_{B}^{2}}\sqrt{\widetilde{p}_{t}^{\top}\Lambda_{t}^{-1}\widetilde{p}_{t}}.$
(65)

Recalling the definition
$\kappa=2\sqrt{2\overline{d}^{2}(N+1)\ln\left(NT(1+\overline{p}^{2}T)\right)+2(N+1)L_{B}^{2}}$
and
$\Delta_{t}(p):=\Delta_{t}^{r}(p)+\max\\{C\|A\|_{\infty},1\\}\Delta_{t}^{D}(p)$,
by Eqs. (63, 64, 65), we obtain

$\displaystyle\Delta_{t}(p)$
$\displaystyle\leq\sqrt{N+1}\kappa(N\overline{p}+\max\\{C\|A\|_{\infty},1\\})\sqrt{\widetilde{p}_{t}^{\top}\Lambda_{t}^{-1}\widetilde{p}_{t}}$
$\displaystyle\leq\sqrt{N+1}\kappa\max\\{\overline{p},1\\}(N\overline{p}+\max\\{C\|A\|_{\infty},1\\})\min\left\\{1,\sqrt{\widetilde{p}_{t}^{\top}\Lambda_{t}^{-1}\widetilde{p}_{t}}\right\\}.$
(66)

Since
$\Lambda_{t}=\Lambda_{t-1}+\widetilde{p}_{t}\widetilde{p}_{t}^{\top}=\Lambda_{t-1}^{1/2}(\mathbf{I}_{N+1}+\Lambda_{t-1}^{-1/2}\widetilde{p}_{t}\widetilde{p}_{t}^{\top}\Lambda_{t-1}^{-1/2})\Lambda_{t-1}^{1/2}$,
we have

$\displaystyle\mathrm{det}(\Lambda_{t})$
$\displaystyle=\mathrm{det}(\Lambda_{t-1})(1+\widetilde{p}_{t}^{\top}\Lambda_{t-1}^{-1}\widetilde{p}_{t})$
$\displaystyle\geq\mathrm{det}(\Lambda_{t-1})\exp\left(\frac{1}{2}\min\\{1,\widetilde{p}_{t}^{\top}\Lambda_{t-1}^{-1}\widetilde{p}_{t}\\}\right),$
(67)

where the first equility is due to
$\mathrm{det}(\mathbf{I}+xx^{\top})=1+\|x\|_{2}^{2}$ and the last inequality
is due to $\exp(x/2)\leq 1+x$ when $x\in[0,1]$.

Therefore , with Eq. (67) we have

$\displaystyle\sum_{t=1}^{\tau}\min\left\\{1,\sqrt{\widetilde{p}_{t}^{\top}\Lambda_{t}^{-1}\widetilde{p}_{t}}\right\\}$
$\displaystyle\leq\sqrt{\tau}\sqrt{\sum_{t=1}^{\tau}\min\\{1,\widetilde{p}_{t}^{\top}\Lambda_{t}^{-1}\widetilde{p}_{t}\\}}$
$\displaystyle\leq\sqrt{T}\sqrt{2\ln\mathrm{det}(\Lambda_{\tau})-2\ln\mathrm{det}(\Lambda_{0})}$
$\displaystyle\leq\sqrt{T}\sqrt{2\ln\left(\frac{\mathrm{trace}(\Lambda_{\tau})}{N+1}\right)^{N+1}}$
$\displaystyle\leq\sqrt{T}\mathcal{O}(\sqrt{N\log(N+1+\overline{p}^{2}T)},$
(68)

where the first inequality is due to Cauchy-Schwarz inequality, the third
inequality is due to the AM-GM inequality, and the last inequality is due to
$\mathrm{trace}(\Lambda_{t})=\mathrm{trace}((N+1)\cdot\mathbf{I}_{N+1})+\mathrm{trace}(\sum_{s<t}\widetilde{p}_{s}\widetilde{p}_{s}^{\top})\leq(N+1)(N+1+T\overline{p}^{2})$.

Combining Eq. (66) and Eq. (68), we have

$\displaystyle\sum_{t=1}^{\tau}\Delta_{t}\left(p_{t}\right)$
$\displaystyle\leq\mathcal{O}\left(\sqrt{N+1}\kappa\max\\{\overline{p},1\\}(N\overline{p}+\max\\{C\|A\|_{\infty},1\\})\right)\times\sqrt{NT\log(N+1+\overline{p}^{2}T)},$

where we complete the proof.

###  11.4 Proof of Lemma 4.6

###### Lemma 11.4

With probability at least $(1-\mathcal{O}\left(T^{-1}\right))$, for all
$t\leq\tau$, we have $(\alpha,B-T^{-2}\cdot\mathbf{I}_{N})\in\mathcal{M}_{t}$,
where $(\alpha,B)$ is the underlying true parameter and
$\mathcal{M}_{t}=\\{(\widetilde{\alpha},\widetilde{B}):\|(\widetilde{\mathcal{B}}-\widehat{\mathcal{B}}_{t})^{\top}e_{i}\|_{\Lambda_{t}}\leq\kappa,\forall
i\in[N]\text{~{}and~{}}\widetilde{B}+\widetilde{B}^{\top}\preceq 0\\}$.

###### Proof 11.5

Proof of Lemma 11.4. Note that by the triangle inequality, for all $t\leq\tau$
and $i\in[N]$ we have

$\displaystyle\|([B-T^{-2}\cdot\mathbf{I}_{N}|\alpha]-\widehat{\mathcal{B}}_{t})^{\top}e_{i}\|_{\Lambda_{t}}$
$\displaystyle\leq\|(\mathcal{B}-\widehat{\mathcal{B}}_{t})^{\top}e_{i}\|_{\Lambda_{t}}+\|[T^{-2}\cdot\mathbf{I}_{N}|0]^{\top}e_{i}\|_{\Lambda_{t}}.$
(69)

For
$\|([B-T^{-2}\cdot\mathbf{I}_{N}|\alpha]-\widehat{\mathcal{B}}_{t})^{\top}e_{i}\|_{\Lambda_{t}}$,
by Eq. (55), with probability $1-1/T$ for any $i\in[N]$ and $t\leq\tau$ it
holds that

$\displaystyle\|(\mathcal{B}-\widehat{\mathcal{B}}_{t})^{\top}e_{i}\|_{\Lambda_{t}}\leq\sqrt{2\overline{d}^{2}(N+1)\ln\left(NT(1+\overline{p}^{2}T)\right)+2(N+1)L_{B}^{2}},$
(70)

Let $\mathrm{diag}(\Lambda_{t})_{i}$ be the $i$-th element of the diagonal of
$\Lambda_{t}$. For
$\|[T^{-2}\cdot\mathbf{I}_{N}|0]^{\top}e_{i}\|_{\Lambda_{t}}$, we have

$\displaystyle\|[T^{-2}\cdot\mathbf{I}_{N}|0]^{\top}e_{i}\|_{\Lambda_{t}}^{2}$
$\displaystyle\leq\mathrm{diag}(\Lambda_{t})_{i}\cdot T^{-4}$
$\displaystyle\leq(N+1+\overline{p}^{2}T)/T^{4},$ (71)

where the last inequality is due to
$\mathrm{diag}(\Lambda_{t})_{i}=N+1+\mathrm{diag}(\sum_{s<t}\widetilde{p}_{s}\widetilde{p}_{s}^{\top})_{i}\leq
N+1+\overline{p}^{2}T$.

Invoking Eq. (70) and Eq. (71) into Eq. (69), we have

$\displaystyle\|([B-T^{-2}\cdot\mathbf{I}_{N}|\alpha]-\widehat{\mathcal{B}}_{t})^{\top}e_{i}\|_{\Lambda_{t}}$
$\displaystyle\leq\sqrt{2\overline{d}^{2}(N+1)\ln\left(NT(1+\overline{p}^{2}T)\right)+2(N+1)L_{B}^{2}}+\sqrt{(N+1+\overline{p}^{2}T)/T^{4}}$
(72) $\displaystyle\leq
2\sqrt{2\overline{d}^{2}(N+1)\ln\left(NT(1+\overline{p}^{2}T)\right)+2(N+1)L_{B}^{2}}=\kappa.$

By assumption $\|\mathcal{B}^{\top}e_{i}\|_{2}\leq L_{B}$ and $L_{B}\geq 1$,
we have

$\displaystyle\|[B-T^{-2}\cdot\mathbf{I}_{N}|\alpha]^{\top}e_{i}\|_{2}$
$\displaystyle\leq\|\mathcal{B}^{\top}e_{i}\|_{2}+\|[T^{-2}\cdot\mathbf{I}_{N}|0]^{\top}e_{i}\|_{2}$
$\displaystyle\leq L_{B}+1/T^{2}$ (73) $\displaystyle\leq 2L_{B}.$

And it is easy to note that
$(B-T^{-2}\cdot\mathbf{I}_{N})+(B-T^{-2}\cdot\mathbf{I}_{N})^{\top}\preceq 0$
with the assumption $B+B^{\top}\preceq 0$. Therefore, we complete the proof of
this lemma.

###### Lemma 11.6

When the desired event in Lemma 11.4 happens ,
$[B-T^{-2}\cdot\mathbf{I}_{N}|\alpha]+X\in\mathcal{M}_{t}$ for any
$X\in\\{X\in\mathbb{R}^{N\times(N+1)}|\|X\|_{F}\leq 1/T^{4}\\}$.

###### Proof 11.7

Proof of Lemma 11.6

Note that by the triangle inequality, for all $t\leq\tau$ and $i\in[N]$ we
have

$\displaystyle\|([B-T^{-2}\cdot\mathbf{I}_{N}|\alpha]+X-\widehat{\mathcal{B}}_{t})^{\top}e_{i}\|_{\Lambda_{t}}$
$\displaystyle\leq\|([B-T^{-2}\cdot\mathbf{I}_{N}|\alpha]-\widehat{\mathcal{B}}_{t})^{\top}e_{i}\|_{\Lambda_{t}}+\|X^{\top}e_{i}\|_{\Lambda_{t}}.$
(74)

When the desired event in Lemma 11.4 happens, by Eq. (72), for any $i\in[N]$
and $t\leq\tau$ it holds that

$\displaystyle\|([B-T^{-2}\cdot\mathbf{I}_{N}|\alpha]-\widehat{\mathcal{B}}_{t})^{\top}e_{i}\|_{\Lambda_{t}}\leq\sqrt{2\overline{d}^{2}(N+1)\ln\left(NT(1+\overline{p}^{2}T)\right)+2(N+1)L_{B}^{2}}+\sqrt{(N+1+\overline{p}^{2}T)/T^{4}}.$
(75)

And for any $X\in\\{X\in\mathbb{R}^{N\times(N+1)}|\|X\|_{F}\leq 1/T^{4}\\}$,