* Galichon (2018) Galichon, Alfred. 2018.  Optimal transport methods in economics.  Princeton University Press.
  * Gallego and Topaloglu (2014) Gallego, Guillermo, Huseyin Topaloglu. 2014.  Constrained assortment optimization for the nested logit model.  Management Science 60(10) 2583–2601.
  * Gallego et al. (2019) Gallego, Guillermo, Huseyin Topaloglu, et al. 2019.  Revenue management and pricing analytics, vol. 209.  Springer.
  * Gallego and Van Ryzin (1994) Gallego, Guillermo, Garrett Van Ryzin. 1994.  Optimal dynamic pricing of inventories with stochastic demand over finite horizons.  Management science 40(8) 999–1020.
  * Garivier and Moulines (2008) Garivier, Aurélien, Eric Moulines. 2008.  On upper-confidence bound policies for non-stationary bandit problems.  arXiv preprint arXiv:0805.3415 .
  * Gibbs and Su (2002) Gibbs, Alison L, Francis Edward Su. 2002.  On choosing and bounding probability metrics.  International statistical review 70(3) 419–435.
  * Golrezaei et al. (2014) Golrezaei, Negin, Hamid Nazerzadeh, Paat Rusmevichientong. 2014.  Real-time optimization of personalized assortments.  Management Science 60(6) 1532–1551.
  * Gupta and Molinaro (2014) Gupta, Anupam, Marco Molinaro. 2014.  How experts can solve lps online.  European Symposium on Algorithms. Springer, 517–529.
  * Hall and Willett (2013) Hall, Eric, Rebecca Willett. 2013.  Dynamical models and tracking regret in online convex programming.  International Conference on Machine Learning. PMLR, 579–587.
  * Hazan (2016) Hazan, Elad. 2016.  Introduction to online convex optimization.  Foundations and Trends in Optimization 2(3-4) 157–325.
  * Immorlica et al. (2019) Immorlica, Nicole, Karthik Abinav Sankararaman, Robert Schapire, Aleksandrs Slivkins. 2019.  Adversarial bandits with knapsacks.  2019 IEEE 60th Annual Symposium on Foundations of Computer Science (FOCS). IEEE, 202–219.
  * Jadbabaie et al. (2015) Jadbabaie, Ali, Alexander Rakhlin, Shahin Shahrampour, Karthik Sridharan. 2015.  Online optimization: Competing with dynamic comparators.  Artificial Intelligence and Statistics. PMLR, 398–406.
  * Jagabathula (2014) Jagabathula, Srikanth. 2014.  Assortment optimization under general choice.  Available at SSRN 2512831 .
  * Jasin (2015) Jasin, Stefanus. 2015.  Performance of an lp-based control for revenue management with unknown demand parameters.  Operations Research 63(4) 909–915.
  * Jasin and Kumar (2012) Jasin, Stefanus, Sunil Kumar. 2012.  A re-solving heuristic with bounded revenue loss for network revenue management with customer choice.  Mathematics of Operations Research 37(2) 313–345.
  * Jasin and Kumar (2013) Jasin, Stefanus, Sunil Kumar. 2013.  Analysis of deterministic lp-based booking limit and bid price controls for revenue management.  Operations Research 61(6) 1312–1320.
  * Jenatton et al. (2016) Jenatton, Rodolphe, Jim Huang, Cédric Archambeau. 2016.  Adaptive algorithms for online convex optimization with long-term constraints.  International Conference on Machine Learning. PMLR, 402–411.
  * Jiang et al. (2019) Jiang, Jiashuo, Shixin Wang, Jiawei Zhang. 2019.  Achieving high individual service-levels without safety stock? optimal rationing policy of pooled resources.  Optimal Rationing Policy of Pooled Resources (May 2, 2019). .
  * Jiang and Zhang (2020) Jiang, Jiashuo, Jiawei Zhang. 2020.  Online resource allocation with stochastic resource consumption.  arXiv preprint arXiv:2012.07933 .
  * Kunnumkal and Talluri (2016) Kunnumkal, Sumit, Kalyan Talluri. 2016.  On a piecewise-linear approximation for network revenue management.  Mathematics of Operations Research 41(1) 72–91.
  * Lattimore and Szepesvári (2020) Lattimore, Tor, Csaba Szepesvári. 2020.  Bandit algorithms.  Cambridge University Press.
  * Lecarpentier and Rachelson (2019) Lecarpentier, Erwan, Emmanuel Rachelson. 2019.  Non-stationary markov decision processes, a worst-case approach using model-based reinforcement learning.  Advances in Neural Information Processing Systems. 7216–7225.
  * Li et al. (2015) Li, Guang, Paat Rusmevichientong, Huseyin Topaloglu. 2015.  The d-level nested logit model: Assortment and price optimization problems.  Operations Research 63(2) 325–342.
  * Li et al. (2020) Li, Xiaocheng, Chunlin Sun, Yinyu Ye. 2020.  Simple and fast algorithm for binary integer and online linear programming.  arXiv preprint arXiv:2003.02513 .
  * Lu et al. (2020) Lu, Haihao, Santiago Balseiro, Vahab Mirrokni. 2020.  Dual mirror descent for online allocation problems.  arXiv preprint arXiv:2002.10421 .
  * Ma et al. (2020) Ma, Yuhang, Paat Rusmevichientong, Mika Sumida, Huseyin Topaloglu. 2020.  An approximation algorithm for network revenue management under nonstationary arrivals.  Operations Research 68(3) 834–855.
  * Mangasarian and Shiau (1987) Mangasarian, Olvi L, T-H Shiau. 1987.  Lipschitz continuity of solutions of linear inequalities, programs and complementarity problems.  SIAM Journal on Control and Optimization 25(3) 583–595.
  * Mehta et al. (2005) Mehta, Aranyak, Amin Saberi, Umesh Vazirani, Vijay Vazirani. 2005.  Adwords and generalized on-line matching.  46th Annual IEEE Symposium on Foundations of Computer Science (FOCS’05). IEEE, 264–273.
  * Miao et al. (2021) Miao, Sentao, Yining Wang, Jiawei Zhang. 2021.  A general framework for resource constrained revenue management with demand learning and large action space.  Available at SSRN 3841273 .
  * Molinaro and Ravi (2013) Molinaro, Marco, Ramamoorthi Ravi. 2013.  The geometry of online packing linear programs.  Mathematics of Operations Research 39(1) 46–59.
  * Neely and Yu (2017) Neely, Michael J, Hao Yu. 2017.  Online convex optimization with time-varying constraints.  arXiv preprint arXiv:1702.04783 .
  * Rangi et al. (2018) Rangi, Anshuka, Massimo Franceschetti, Long Tran-Thanh. 2018.  Unifying the stochastic and the adversarial bandits with knapsack.  arXiv preprint arXiv:1811.12253 .
  * Rawlings (2000) Rawlings, James B. 2000.  Tutorial overview of model predictive control.  IEEE control systems magazine 20(3) 38–52.
  * Reiman and Wang (2008) Reiman, Martin I, Qiong Wang. 2008.  An asymptotically optimal policy for a quantity-based network revenue management problem.  Mathematics of Operations Research 33(2) 257–282.
  * Rusmevichientong et al. (2010) Rusmevichientong, Paat, Zuo-Jun Max Shen, David B Shmoys. 2010.  Dynamic assortment optimization with a multinomial logit choice model and capacity constraint.  Operations research 58(6) 1666–1680.
  * Russac et al. (2019) Russac, Yoan, Claire Vernade, Olivier Cappé. 2019.  Weighted linear bandits for non-stationary environments.  Advances in Neural Information Processing Systems. 12040–12049.
  * Sun et al. (2020) Sun, Rui, Xinshang Wang, Zijie Zhou. 2020.  Near-optimal primal-dual algorithms for quantity-based network revenue management.  arXiv preprint arXiv:2011.06327 .
  * Talluri and Van Ryzin (1998) Talluri, Kalyan, Garrett Van Ryzin. 1998.  An analysis of bid-price controls for network revenue management.  Management science 44(11-part-1) 1577–1593.
  * Talluri and Van Ryzin (2004) Talluri, Kalyan, Garrett Van Ryzin. 2004.  Revenue management under a general discrete choice model of consumer behavior.  Management Science 50(1) 15–33.
  * Talluri and Van Ryzin (2006) Talluri, Kalyan T, Garrett J Van Ryzin. 2006.  The theory and practice of revenue management, vol. 68.  Springer Science & Business Media.
  * Vanderbei et al. (2015) Vanderbei, Robert J, et al. 2015.  Linear programming.  Springer.
  * Vera and Banerjee (2020) Vera, Alberto, Siddhartha Banerjee. 2020.  The bayesian prophet: A low-regret framework for online decision making.  Management Science .
  * Vera et al. (2019) Vera, Alberto, Siddhartha Banerjee, Itai Gurvich. 2019.  Online allocation and pricing: Constant regret via bellman inequalities.  arXiv preprint arXiv:1906.06361 .
  * Villani (2008) Villani, Cédric. 2008.  Optimal transport: old and new, vol. 338.  Springer Science & Business Media.
  * Wagener et al. (2019) Wagener, Nolan, Ching-An Cheng, Jacob Sacks, Byron Boots. 2019.  An online learning approach to model predictive control.  arXiv preprint arXiv:1902.08967 .
  * Yi et al. (2021) Yi, Xinlei, Xiuxian Li, Tao Yang, Lihua Xie, Tianyou Chai, Karl Johansson. 2021\.  Regret and cumulative constraint violation analysis for online convex optimization with long term constraints.  International Conference on Machine Learning. PMLR, 11998–12008.
  * Yuan and Lamperski (2018) Yuan, Jianjun, Andrew Lamperski. 2018.  Online convex optimization for cumulative constraints.  Advances in Neural Information Processing Systems. 6137–6146.
  * Zhang and Adelman (2009) Zhang, Dan, Daniel Adelman. 2009.  An approximate dynamic programming approach to network revenue management with customer choice.  Transportation Science 43(3) 381–394.

Proofs of Lemmas, Propositions and Theorems

##  8 Proofs of Section 3

###  A1 Proof of Lemma 1

###### Proof.

Proof: Given the realized parameters
$\mathcal{H}=(\bm{\theta}_{1},\bm{\theta}_{2},\dots,\bm{\theta}_{T})$, we can
denote the offline optimum of (PCP) as a function of $\mathcal{H}$, namely,
$\\{\bm{x}^{*}_{t}(\mathcal{H})\\}_{t=1}^{T}$. Let

$\tilde{\bm{x}}_{t}(\bm{\theta})=\mathbb{E}\left[\bm{x}^{*}_{t}(\mathcal{H})|\bm{\theta}_{t}=\bm{\theta}\right]$

where the conditional expectation is taken with respect to $\mathcal{P}_{j}$
for $j\neq t$. We show that $\tilde{\bm{x}}_{t}(\bm{\theta})$ is a feasible
solution to (4). Specifically, note that for each $i=1,...,m$,

$\displaystyle c_{i}$
$\displaystyle\geq\mathbb{E}\left[\sum_{t=1}^{T}g_{i}(\bm{x}^{*}_{t}(\mathcal{H});\bm{\theta}_{t})\right]=\sum_{t=1}^{T}\mathbb{E}_{\bm{\theta}_{t}\sim\mathcal{P}_{t}}\left[\mathbb{E}[g_{i}(\bm{x}^{*}_{t}(\mathcal{H});\bm{\theta}_{t})|\bm{\theta}_{t}=\bm{\theta}]\right]$
$\displaystyle\geq\sum_{t=1}^{T}\int_{\bm{\theta}\in\Theta}g_{i}(\tilde{\bm{x}}_{t}(\bm{\theta});\bm{\theta})d\mathcal{P}_{t}(\bm{\theta})=\sum_{t=1}^{T}\mathcal{P}_{t}g_{i}(\bm{x}_{t};\bm{\theta})$

where the first inequality comes from the feasibility of the optimal solution
$\bm{x}_{t}^{*}(\mathcal{H})$ and the second inequality follows from that the
function $g_{i}(\cdot;\bm{\theta}_{t})$ is a convex function for each $i$ and
$\bm{\theta}_{t}\in\Theta$. Thus, $\\{\tilde{\bm{x}}_{t}(\bm{\theta})\\}$ is a
feasible solution to (4). Similarly, we can analyze the objective function

$\displaystyle\mathbb{E}[R^{*}_{T}]$
$\displaystyle=\mathbb{E}\left[\sum_{t=1}^{T}f(\bm{x}^{*}_{t}(\mathcal{H});\bm{\theta}_{t})\right]=\sum_{t=1}^{T}\mathbb{E}_{\bm{\theta}_{t}\sim\mathcal{P}_{t}}\left[\mathbb{E}[f(\bm{x}^{*}_{t}(\mathcal{H});\bm{\theta}_{t})|\bm{\theta}_{t}=\bm{\theta}]\right]$
$\displaystyle\leq\sum_{t=1}^{T}\int_{\bm{\theta}\in\Theta}f(\tilde{\bm{x}}_{t}(\bm{\theta});\bm{\theta})d\mathcal{P}_{t}(\bm{\theta})\leq
R^{\text{UB}}_{T}$

where the first inequality follows from that the function
$f(\cdot;\bm{\theta})$ is a concave function for any $\bm{\theta}\in\Theta$
and the last inequality comes from the optimality of $R^{\text{UB}}_{T}$. Thus
we complete the proof. ∎

###  A2 Proof of Proposition 1

###### Proof.

Proof: We first prove that $\bm{p}^{*}$ is an optimal solution for $L_{t}$.
Note that for each $t$, $L_{t}(\bm{p})$ is a convex function over $\bm{p}$ and

$\nabla L_{t}(\bm{p}^{*})=\bm{\gamma}_{t}+\mathcal{P}_{t}\nabla
h(\bm{p}^{*};\bm{\theta}_{t})=\bm{\gamma}_{t}-\mathcal{P}_{t}\bm{g}(\bm{x}^{*}(\bm{\theta}_{t});\bm{\theta}_{t})$

where
$\bm{x}^{*}(\bm{\theta})=\text{argmax}_{\bm{x}\in\mathcal{X}}\\{f(\bm{x};\bm{\theta})-(\bm{p}^{*})^{T}\cdot\bm{g}(\bm{x};\bm{\theta})\\}$.
With the definition of $\bm{\gamma}_{t}$ in (6), it follows immediately that

$\nabla L_{t}(\bm{p}^{*})=0$

which implies that $\bm{p}^{*}$ is a minimizer of the function $L(\cdot)$ for
each $t$. We then prove that $L(\bm{p}^{*})=\sum_{t=1}^{T}L_{t}(\bm{p}^{*})$.
Define the set of binding constraints
$\mathcal{I}_{B}=\\{i:p_{i}^{*}>0,i=1,...,m\\}$. From the convexity of the
function $L(\bm{p})$ over $\bm{p}$, for each $i\in\mathcal{I}_{B}$, it holds
that

$0=\nabla_{i}L(\bm{p}^{*})=c_{i}-\sum_{t=1}^{T}\mathcal{P}_{t}\bm{g}(\bm{x}^{*}(\bm{\theta}_{t});\bm{\theta}_{t})=c_{i}-\sum_{t=1}^{T}\gamma_{t,i}$

Thus, we have that

$\bm{c}^{\top}\cdot\bm{p}^{*}=\sum_{t=1}^{T}\bm{\gamma}_{t}^{\top}\cdot\bm{p}^{*}$

It follows immediately that $L(\bm{p}^{*})=\sum_{t=1}^{T}L_{t}(\bm{p}^{*})$. ∎

###  A3 Discussions on the function $h$

The definition of the function $h(\bm{p};\bm{\theta})$, described as follows
for completeness, plays a critical role in deriving our results,

$h(\bm{p};\bm{\theta})=\max_{\bm{x}\in\mathcal{X}}\left\\{f(\bm{x};\bm{\theta})-\sum_{i=1}^{n}p_{i}\cdot
g_{i}(\bm{x};\bm{\theta})\right\\}.$ (22)

Throughout the paper, we assume that the optimization problem in (22) can be
solved efficiently so as to obtain both its optimal solution and optimal
objective value. Here, we justify this assumption with a discussion of the
computational aspect of solving (22). Note that when the function $h$ is
defined in the setting with random reward and consumption given in Section 6.4
where $f,\bm{g}$ are random functions, $f,\bm{g}$ can be simply replaced by
their expectations $\hat{f},\hat{\bm{g}}$ in the definition of $h$ in (22). In
the following discussion, we use the notations of $f,\bm{g}$ and
$\hat{f},\hat{\bm{g}}$ exchangeably for simplicity.

When (PCP) refers to the online linear programming problem or price-based
network revenue management (NRM) problem as described in Section 2.2, the
optimization problem in (22) is reduced to a simple convex optimization
problem and it can indeed be solved in polynomial time by existing methods. We
now consider (22) when (PCP) represents the choice-based NRM problem.

In the choice-based NRM problem, there are $n$ products and each product $i$
is associated with a revenue $r_{i}$. The definitions of $\bm{x}_{t}$ and the
functions $f,\bm{g}$ are described in Section 2.2. Given the assortment $s$,
the customer with the type ${\theta}_{t}$ chooses one product $i$ to purchase
with a probability $\eta_{i}(s;{\theta}_{t})$, where $\bm{\eta}$ is specified
by the choice model of the customer and is assumed to be known to the decision
maker. Here, the function $f$ refers to the expected revenue of the assortment
$\bm{x}_{t}$ and the function $g_{i}$ refers to the probability that a product
$i$ is purchased:

$f(\bm{x}_{t};{\theta}_{t})=\sum_{s\in\mathcal{S}}\sum_{j=1}^{n}x_{t,s}\cdot
r_{j}\cdot\eta_{j}(s;{\theta}_{t})\text{~{}~{}and~{}~{}}g_{i}(\bm{x}_{t};{\theta}_{t})=\sum_{s\in\mathcal{S}}x_{t,s}\cdot\eta_{i}(s;{\theta}_{t})~{}~{}~{}\forall
i$

Then, the optimization problem in (22) could be rewritten in the following
equivalent formulation:

$\max_{s\in\mathcal{S}\subset\\{0,1\\}^{n}}\sum_{i=1}^{n}(r_{i}-p_{i})\cdot\eta_{i}(s;{\theta}_{t})$
(23)

With the following choice models to specify the function $\eta_{i}$’s, the
optimization problem in (23) could all be solved efficiently.
Multinomial logit model (NML): Talluri and Van Ryzin (2004) show that without
further constraints, it is optimal to sort the products according to a
decreasing order $r_{i}-p_{i}$ and find an optimal revenue-order assortment
among $\\{1\\},\\{1,2,\\},\dots,\\{1,2\dots,n\\}$. Rusmevichientong et al.
(2010) further propose a simple polynomial-time algorithm to compute the
optimal assortment where there is a capacity constraint. Davis et al. (2013)
consider the assortment problem with totally unimodular constraints and show
that the constrained problem could be solved as an equivalent linear program.
Nested logit model: Li et al. (2015) consider the assortment optimization
problem under a $d$-level nested logit model and propose an algorithm to
compute the optimal assortment in polynomial time. Gallego and Topaloglu
(2014) consider the setting with cardinality constraint and show that the
optimal assortment can be obtained efficiently by solving a linear program.
Gallego and Topaloglu (2014) further consider the setting with a capacity
constraint and propose an algorithm with constant competitiveness and good
empirical performance.
Markov chain based models: Blanchet et al. (2016) propose the Markov chain
based model and develop polynomial-time solution algorithms. Feldman and
Topaloglu (2017) propose a linear programming approach to obtain the optimal
assortment under this model.
General choice model: There are also papers considering the assortment problem
without exploiting the specific structures of the choice model. Jagabathula
(2014) studies a local search heuristic and shows its great empirical
performance. Also, Berbeglia and Joret (2020) analyze the performance of the
revenue-order assortment heuristic under the general discrete choice model,
which can be applied to solve (23) approximately.

###  A4 Proof of Lemma 2

###### Proof.

Proof: Note that the following two properties are satisfied by the update rule
(7):

  * (i).

If $\|\bm{p}_{t}\|_{\infty}\leq q$, then we must have
$\|\bm{p}_{t+1}\|_{\infty}\leq q+1$ by noting that for each $i$, the $i$-th
component of $\bm{p}_{t}$, denoted as $p_{t,i}$, is nonnegative and
$g_{i}(\cdot,\bm{\theta}_{t})$ is normalized within $[0,1]$.

  * (ii).

If there exists $i$ such that $p_{t,i}>q$, then we must have
$p_{t+1,i}<p_{t,i}$. Specifically, when $p_{t,i}>q$, we must have that
$g_{i}(\tilde{\bm{x}}_{t};\bm{\theta}_{t})=0$, otherwise we would have that

$f(\tilde{\bm{x}}_{t};\bm{\theta}_{t})-\bm{p}_{t}^{\top}\cdot\bm{g}(\tilde{\bm{x}}_{t};\bm{\theta}_{t})\leq
f(\tilde{\bm{x}}_{t};\bm{\theta}_{t})-p_{t,i}\cdot
g_{i}(\tilde{\bm{x}}_{t};\bm{\theta}_{t})<0$

which contradicts the definition of $\tilde{\bm{x}}_{t}$ in Algorithm 1 since
we could always select $\bm{x}_{t}=\bm{0}$ to obtain a zero objective value as
per Assumption 1. Then from (7), it holds that $p_{t+1,i}<p_{t,i}$.

Starting from $\bm{p}_{1}=\bm{0}$ and iteratively applying the above two
property to control the increase of $\bm{p}_{t}$ from $t=1$ to $T$, we obtain
that for the first time that one component of $\bm{p}_{t}$ exceeds the
threshold $q$, it is upper bounded by $q+1$ and this component will continue
to decrease until it falls below the threshold $q$. Thus, we have
$\|\bm{p}_{t}\|_{\infty}\leq q+1$ with probability $1$ for each $t$. ∎

###  A5 Proof of Theorem 1

###### Proof.

Proof: In IGD($\bm{\gamma}$), the true action $\bm{x}_{t}$ taken by the
decision maker differs from the virtual action $\tilde{\bm{x}}_{t}$ if and
only if $\bm{c}_{t}$ cannot fully satisfy
$\bm{g}(\tilde{\bm{x}}_{t};\bm{\theta}_{t})$. Thus, we have that

$f(\tilde{\bm{x}}_{t};\bm{\theta}_{t})-f(\bm{x}_{t};\bm{\theta}_{t})\leq
f(\tilde{\bm{x}}_{t};\bm{\theta}_{t})\cdot\mathbb{I}\left\\{\exists
i:c_{t,i}<g_{i}(\tilde{\bm{x}}_{t};\bm{\theta}_{t})\right\\}$

where $c_{t,i}$ denotes the $i$-th component of $\bm{c}_{t}$ and
$\mathbb{I}\left\\{\cdot\right\\}$ denotes the indicator function. Moreover,
we know

$\mathbb{I}\left\\{\exists
i:c_{t,i}<g_{i}(\tilde{\bm{x}}_{t};\bm{\theta}_{t})\right\\}\leq\sum_{i=1}^{m}\mathbb{I}\left\\{\sum_{j=1}^{t}g_{i}(\tilde{\bm{x}}_{j};\bm{\theta}_{j})>c_{i}\right\\}.$

Recall that the maximum reward generated by consuming per unit of budget of
each constraint is upper bounded by $q$. We have

$f(\tilde{\bm{x}}_{t};\bm{\theta}_{t})\cdot\mathbb{I}\left\\{\exists
i:c_{t,i}<g_{i}(\tilde{\bm{x}}_{t};\bm{\theta}_{t})\right\\}\leq
q\sum_{i=1}^{m}g_{i}(\tilde{\bm{x}}_{t};\bm{\theta})\cdot\mathbb{I}\left\\{\sum_{j=1}^{t}g_{i}(\tilde{\bm{x}}_{j};\bm{\theta}_{j})>c_{i}\right\\}$

From the fact that $\bm{g}(\cdot;\bm{\theta}_{t})\in[0,1]^{m}$,

$\displaystyle\sum_{t=1}^{T}f(\tilde{\bm{x}}_{t};\bm{\theta}_{t})-\sum_{t=1}^{T}f(\bm{x}_{t};\bm{\theta}_{t})$
$\displaystyle\leq
q\cdot\sum_{i=1}^{m}\sum_{t=1}^{T}g_{i}(\tilde{\bm{x}}_{t};\bm{\theta}_{t})\cdot\mathbb{I}\left\\{\sum_{j=1}^{t}g_{i}(\tilde{\bm{x}}_{j};\bm{\theta}_{j})>c_{i}\right\\}$
$\displaystyle\leq
q\cdot\sum_{i=1}^{m}\left[\sum_{t=1}^{T}g_{i}(\tilde{\bm{x}}_{t};\bm{\theta}_{t})-(c_{i}-1)\right]^{+}$

which related the total collected reward by the true action
$\\{\bm{x}_{t}\\}_{t=1}^{T}$ and the virtual action
$\\{\tilde{\bm{x}}_{t}\\}_{t=1}^{T}$. Further from Proposition 1, we have that

$\displaystyle\text{Reg}_{T}(\pi)\leq\min_{\bm{p}\geq
0}\sum_{t=1}^{T}L_{t}(\bm{p})-\mathbb{E}\left[\sum_{t=1}^{T}f(\bm{x}_{t};\bm{\theta}_{t})\right]$
$\displaystyle\leq\underbrace{\sum_{t=1}^{T}\min_{\bm{p}\geq
0}L_{t}(\bm{p})-\mathbb{E}\left[\sum_{t=1}^{T}f(\tilde{\bm{x}}_{t};\bm{\theta}_{t})\right]}_{\text{I}}$
$\displaystyle+\underbrace{q\cdot\mathbb{E}\left[\sum_{i=1}^{m}\left[\sum_{t=1}^{T}g_{i}(\tilde{\bm{x}}_{t};\bm{\theta}_{t})-(c_{i}-1)\right]^{+}\right]}_{\text{II}}$

We then bound the term I and term II separately to derive our regret bound.
Bound I: Note that for each $t$, the distribution of $\bm{p}_{t}$ is
independent from the distribution of $\bm{\theta}_{\tau}$ for any $\tau\leq
t$, then we have that

$\min_{\bm{p}\geq\bm{0}}L_{t}(\bm{p})\leq\mathbb{E}_{\bm{p}_{t}}\left[L_{t}(\bm{p}_{t})\right]=\mathbb{E}_{\bm{p}_{t}}\left[\bm{\gamma}_{t}^{\top}\bm{p}_{t}+\mathcal{P}_{t}h(\bm{p}_{t};\bm{\theta}_{t})\right]$

where the expectation is taken with respect to the randomness of the dual
price $\bm{p}_{t}.$ Thus, we have

$\text{I}\leq\sum_{t=1}^{T}\mathbb{E}_{\bm{p}_{t}}\left[\bm{\gamma}_{t}^{\top}\bm{p}_{t}+\mathcal{P}_{t}\left\\{h(\bm{p}_{t};\bm{\theta}_{t})-f(\tilde{\bm{x}}_{t};\bm{\theta}_{t})\right\\}\right]$

From the definition of $\tilde{\bm{x}}_{t}$, we get that
$h(\bm{p}_{t};\bm{\theta}_{t})-f(\tilde{\bm{x}}_{t};\bm{\theta}_{t})=-\bm{p}_{t}^{\top}\cdot\bm{g}(\tilde{\bm{x}}_{t};\bm{\theta}_{t})$,
which implies that

$\text{I}\leq\sum_{t=1}^{T}\mathbb{E}_{\bm{p}_{t}}\left[\bm{p}_{t}^{\top}\cdot\left(\bm{\gamma}_{t}-\mathcal{P}_{t}\bm{g}(\tilde{\bm{x}}_{t};\bm{\theta}_{t})\right)\right]$

Note that from the update rule (7), we have that

$\|\bm{p}_{t+1}\|_{2}^{2}\leq\|\bm{p}_{t}\|_{2}^{2}+\frac{1}{T}\cdot\|\bm{g}(\tilde{\bm{x}}_{t};\bm{\theta}_{t})-\bm{\gamma}_{t}\|_{2}^{2}-\frac{2}{\sqrt{T}}\cdot\bm{p}_{t}^{\top}\cdot\left(\bm{\gamma}_{t}-\bm{g}(\tilde{\bm{x}}_{t};\bm{\theta}_{t})\right)$

which implies that

$\mathbb{E}_{\bm{p}_{t}}\left[\bm{p}_{t}^{\top}\cdot\left(\bm{\gamma}_{t}-\mathcal{P}_{t}\bm{g}(\tilde{\bm{x}}_{t};\bm{\theta}_{t})\right)\right]\leq\frac{\sqrt{T}}{2}\cdot\left(\mathbb{E}[\|\bm{p}_{t}\|_{2}^{2}]-\mathbb{E}[\|\bm{p}_{t+1}\|_{2}^{2}]\right)+\frac{m}{2\sqrt{T}}$

Thus, it holds that

$\text{I}\leq\frac{m\sqrt{T}}{2}$ (24)

Bound II: Note that from the update rule (7), we have that

$\sqrt{T}\cdot\bm{p}_{t+1}\geq\sqrt{T}\cdot\bm{p}_{t}+\bm{g}(\tilde{\bm{x}}_{t};\bm{\theta}_{t})-\bm{\gamma}_{t}$

which implies that

$\sum_{t=1}^{T}\bm{g}(\tilde{\bm{x}}_{t};\bm{\theta}_{t})-\bm{c}\leq\sum_{t=1}^{T}\bm{g}(\tilde{\bm{x}}_{t};\bm{\theta}_{t})-\sum_{t=1}^{T}\bm{\gamma}_{t}\leq\sqrt{T}\cdot\bm{p}_{T+1}$

Thus, it holds that

$\text{II}=q\cdot\mathbb{E}\left[\sum_{i=1}^{m}\left[\sum_{t=1}^{T}g_{i}(\tilde{\bm{x}}_{t};\bm{\theta}_{t})-(c_{i}-1)\right]^{+}\right]\leq
mq(q+1)\cdot\sqrt{T}+qm$ (25)

We obtain the $O(\sqrt{T})$ regret bound immediately by combining (24) and
(25). ∎

###  A6 Proof of Proposition 2

###### Proof.

Proof: We construct the following distribution $\mathcal{P}$ over the
parameter $\theta$. Suppose that there is a single resource. Denote the
support set of $\mathcal{P}$ as
$\\{\theta^{(0)},\theta^{(1)},\theta^{(2)},\dots,\theta^{(j)},\dots\\}$ and
for each $j=1,2,\dots$, we have that

$\mathcal{P}(\theta=\theta^{(j)})=\frac{1}{2}\cdot\frac{1}{2^{j}}\text{~{}~{}and~{}~{}}\mathcal{P}(\theta=\theta^{(0)})=\frac{1}{2}$

Moreover, we have the following condition over the support set
$\\{\theta^{(1)},\theta^{(2)},\dots,\theta^{(j)},\dots\\}$ of $\mathcal{P}$.
Denote sequences of constants $\\{a_{j}\\}$, $\\{b_{j}\\}$, where

$a_{j}=1+\frac{2j+1}{2j(j+1)},~{}b_{j}=1+1/(j+1)$

for $j=1,2,....$ Clearly, we have $1\leq\dots\leq a_{j+1}<b_{j}<a_{j}\dots\leq
2$. The reward function satisfies

$0\leq\min_{0<x\leq 1}\frac{f(x;\theta^{(0)})}{x}\leq\max_{0<x\leq
1}\frac{f(x;\theta^{(0)})}{x}\leq 1\text{~{}and~{}}b_{j}\leq\min_{0<x\leq
1}\frac{f(x;\theta^{(j)})}{x}\leq\max_{0<x\leq
1}\frac{f(x;\theta^{(j)})}{x}\leq a_{j},~{}~{}\forall j=1,2,\dots$

There is a single resource and the resource consumption function satisfies
$g(x;\theta)=x$ for each $\theta$. We are now ready to construct the example
and show the lower bound.

Suppose there is a single resource with an initial capacity $\frac{T}{2}$,
where $T$ is the total time periods. For a fixed $T$, there must exists an
integer $k$ such that

$\frac{1}{2\sqrt{T}}\leq\frac{1}{2^{k+2}}\leq\frac{1}{\sqrt{T}}$

Now, we assume without loss of generality that $T$ is set such that

$\frac{1}{2^{k+2}}=\frac{1}{\sqrt{T}}$

We now divide the support set
$\\{\theta^{(0)},\theta^{(1)},\theta^{(2)},\dots,\theta^{(j)},\dots\\}$ into
three subsets:

$A_{1}=\\{\theta^{(j)}:1\leq
j<k\\},~{}A_{2}=\\{\theta^{(k)}\\}\text{~{}and~{}}A_{3}=\\{\theta^{(0)},\theta^{(j)}:j\geq
k+1\\}.$

Clearly, at each time period $t$, we have that

$P(\theta_{t}\in A_{1})=\frac{1}{2}+\frac{1}{2^{k+1}},P(\theta_{t}\in
A_{2})=\frac{1}{2^{k+1}}\text{~{}and~{}}P(\theta_{t}\in
A_{3})=\frac{1}{2}-\frac{2}{2^{k+1}}.$

Denote $\varepsilon=\frac{1}{2^{k+2}}$. We call that we encounter a type $q$
request whenever the event $\\{\theta_{t}\in A_{q}\\}$ happens, where
$q=1,2,3$. We now denote $Z_{q}^{t}$ as the number type $q$ requests in the
first $t$ periods. We next introduce the event:

$\displaystyle\mathcal{H}_{1}=\left\\{\frac{1}{\epsilon}\leq
Z_{2}^{T}\leq\min\\{2Z_{2}^{T/2},\frac{2}{\epsilon}\\}\right\\}=\left\\{\frac{1}{2}\mathbb{E}[Z_{2}^{T}]\leq
Z_{2}^{T}\leq\min\\{2Z_{2}^{T/2},\mathbb{E}[Z_{2}^{T}]\\}\right\\}$
$\displaystyle\mathcal{H}_{2}=\left\\{Z_{1}^{T}\geq\frac{T}{2}+\frac{2}{\epsilon}\right\\}=\left\\{Z_{1}^{T}\geq\mathbb{E}[Z_{1}^{T}]+\frac{6}{\epsilon}\right\\}$
$\displaystyle\mathcal{H}_{3}=\left\\{Z_{1}^{T}\leq\frac{T}{2}-\frac{4}{\epsilon}\right\\}=\left\\{Z_{1}^{T}\leq\mathbb{E}[Z_{1}^{T}]\right\\}$

It is obvious that on event $\mathcal{H}_{2}$, particularly on the event
$\mathcal{H}_{2}\cap\mathcal{H}_{1}$, all the resources will be consumed by
type 1 requests by the offline optimum. That is, at each period $t$, the
offline optimum will set the decision variable $x_{t}$ non-zero only when the
event $\\{\theta_{t}\in A_{1}\\}$ happens. Similarly, on event
$\mathcal{H}_{1}\cap\mathcal{H}_{3}$, the offline optimum will set the
decision variable $x_{t}=1$ whenever the event $\\{\theta_{t}\in A_{1}\\}$ or
$\\{\theta_{t}\in A_{2}\\}$ happens. Following the same argument as Arlloto
and Gurvich (2019), we know that there exists a constant $\alpha_{1}>0$,
independent of $\epsilon$, such that

$P(\mathcal{H}_{1}\cap\mathcal{H}_{2})\geq\alpha_{1}\text{~{}~{}and~{}~{}}P(\mathcal{H}_{1}\cap\mathcal{H}_{3})\geq\alpha_{1}$

Next, we consider the difference between the offline optimum and the dynamic
programming policy. We denote $S^{T/2}_{2}$ as the amount of resource consumed
by type 2 request during the first $T/2$ periods, and we consider the event

$\mathcal{H}_{4}=\left\\{S^{T/2}_{2}\geq\frac{Z_{2}^{T}}{4}\right\\}$

Now, on the event $\mathcal{H}_{4}^{c}\cap\mathcal{H}_{1}\cap\mathcal{H}_{3}$,
the offline optimum will set $x_{t}=1$ for all type 1 and type 2 request. On
the other hand, the optimal online policy consumes at most $Z^{T}_{2}/4$
amount of resource using type 2 requests during the first $T/2$ periods. Note
that as induced by the event $\mathcal{H}_{1}$, at most $Z^{T}_{2}/2$ number
of type 2 request can arrive during the last $T/2$ periods. Thus, for the
optimal online policy, type 2 request can consume at most $\frac{3}{4}\cdot
Z^{T}_{2}$ amount of resource, while the offline optimum consume $Z^{T}_{2}$
amount of resource with type 2 request. Further note that the reward/size for
type 2 request is at least $b_{k}$ and the reward/size for type 3 request is
at most $a_{k+1}$. This will incur a regret at least

$\mathbb{E}[\text{Regret}]\geq\frac{b_{k}-a_{k+1}}{4}\cdot\mathbb{E}[Z^{T}_{2}\cdot
1\\{\mathcal{H}_{4}^{c}\cap\mathcal{H}_{1}\cap\mathcal{H}_{3}\\}]\geq\frac{b_{k}-a_{k+1}}{4\epsilon}\cdot
P(\mathcal{H}_{4}^{c}\cap\mathcal{H}_{1}\cap\mathcal{H}_{3})$

For each arrival sample path that falls in the set
$\mathcal{H}_{4}\cap\mathcal{H}_{1}\cap\mathcal{H}_{3}$, we can find another
sample path in $\mathcal{H}_{4}\cap\mathcal{H}_{1}\cap\mathcal{H}_{2}$ by
keeping the first $T/2$ arrivals unchanged, and for the last $T/2$ periods,
replacing at most $6/\epsilon$ type 3 requests with type 1 requests. We denote
this resulting set of sample path as $\mathcal{L}$. Note that for each period,
the arrival probability for type 1 request and type 3 request are both bounded
away from 0. We know that there exists a constant $\alpha_{2}>0$, independent
of $\epsilon$, such that

$P(\mathcal{L})\geq\alpha_{2}\cdot
P(\mathcal{H}_{4}\cap\mathcal{H}_{1}\cap\mathcal{H}_{3}).$

Moreover, for each sample path in the set $\mathcal{L}$, since it is on the
event $\mathcal{H}_{4}\cap\mathcal{H}_{1}\cap\mathcal{H}_{2}$, we know that
the offline optimum will consume all the resource with type 1 request, while
the optimal online policy consumes at least $\frac{Z_{2}^{T}}{4}$ amount of
resource with type 2 requests. Note that the reward/size for type 1 is at
least $b_{k-1}$, while the reward/size for type 2 is at most $a_{k}$. This
will incur a regret at least

$\mathbb{E}[\text{regret}]\geq\frac{b_{k-1}-a_{k}}{4}\cdot\mathbb{E}[Z^{T}_{2}\cdot
1\\{\mathcal{L}\\}]\geq\frac{b_{k-1}-a_{k}}{4\epsilon}\cdot
P(\mathcal{L})\geq\alpha_{2}\cdot\frac{b_{k-1}-a_{k}}{4\epsilon}\cdot
P(\mathcal{H}_{4}\cap\mathcal{H}_{1}\cap\mathcal{H}_{3}).$

Since

$P(\mathcal{H}_{1}\cap\mathcal{H}_{3})=P(\mathcal{H}_{4}^{c}\cap\mathcal{H}_{1}\cap\mathcal{H}_{3})+P(\mathcal{H}_{4}\cap\mathcal{H}_{1}\cap\mathcal{H}_{3})\geq\alpha_{1},$

we know that there exists a constant $\alpha_{3}>0$, independent of
$\epsilon$, such that

$\mathbb{E}[\text{regret}]\geq\frac{\alpha_{3}}{\epsilon}\cdot\min\\{b_{k-1}-a_{k},b_{k}-a_{k+1}\\}.$

Recall that $\epsilon=1/\sqrt{T}$ and

$\min\\{b_{k-1}-a_{k},b_{k}-a_{k+1}\\}=\frac{1}{(k+1)(k+2)}$

and that $\frac{1}{2^{k+2}}=\frac{1}{\sqrt{T}}$, i.e., $k+2=\frac{\log T}{2}$.
We have

$\mathbb{E}[\text{regret}]\geq\frac{\alpha_{3}}{4}\cdot\frac{\sqrt{T}}{(\log
T)^{2}}$

which completes our proof. ∎

##  9 Proofs of Section 4

###  B1 Proof of Theorem 2

###### Proof.

Proof: It follows directly from Proposition 2 that for any policy $\pi$, we
have $\text{Reg}_{T}(\pi)\geq\Omega(\sqrt{T})$. Thus, it is enough to consider
the $\Omega(W_{T})$ part in the lower bound. We consider the following
estimated problem, where the true coefficients in (PCP) are replaced by the
estimates:

$\displaystyle\max\ \ $ $\displaystyle x_{1}+...+x_{c}+x_{c+1}+...+x_{T}$ (26)
s.t. $\displaystyle x_{1}+...+x_{c}+x_{c+1}+...+x_{T}\leq c$ $\displaystyle
0\leq x_{t}\leq 1\ \text{ for }t=1,...,T.$

where $c=\frac{T}{2}$ and the prior estimate $\hat{\mathcal{P}}_{t}$ is simply
a one-point distribution for each $t$. Now we consider the following two
possible true problems, the distributions of which are all one-point
distributions and belong to the set $\Xi_{P}$ with variation budget $W_{T}$:

$\displaystyle\max\ \ $ $\displaystyle
x_{1}+...+x_{c}+\left(1+\frac{W_{T}}{T}\right)x_{c+1}+...+\left(1+\frac{W_{T}}{T}\right)x_{T}$
(27) s.t. $\displaystyle x_{1}+...+x_{c}+x_{c+1}+...+x_{T}\leq c$
$\displaystyle 0\leq x_{t}\leq 1\ \text{ for }t=1,...,T.$ $\displaystyle\max\
\ $ $\displaystyle
x_{1}+...+x_{c}+\left(1-\frac{W_{T}}{T}\right)x_{c+1}+...+\left(1-\frac{W_{T}}{T}\right)x_{T}$
(28) s.t. $\displaystyle x_{1}+...+x_{c}+x_{c+1}+...+x_{T}\leq c$
$\displaystyle 0\leq x_{t}\leq 1\ \text{ for }t=1,...,T.$

where $c=\frac{T}{2}$. Denote $x^{1}_{t}(\pi)$ as the decision of any policy
$\pi$ at period $t$ for scenario (27) and denote $x^{2}_{t}(\pi)$ as the
decision of policy $\pi$ at period $t$ for scenario (28). Further define
$T_{1}(\pi)$ (resp. $T_{2}(\pi)$) as the expected capacity consumption of
policy $\pi$ on scenario (27) (resp. scenario (28)) during the first
$\frac{T}{2}$ time periods:

$T_{1}(\pi)=\mathbb{E}\left[\sum_{t=1}^{\frac{T}{2}}x^{1}_{t}(\pi)\right]\text{~{}~{}~{}and~{}~{}~{}}T_{2}(\pi)=\mathbb{E}\left[\sum_{t=1}^{\frac{T}{2}}x^{2}_{t}(\pi)\right]$

Then, we have that

$R_{T}^{1}(\pi)=\frac{T+W_{T}}{2}-\frac{W_{T}}{T}\cdot
T_{1}(\pi)\text{~{}~{}~{}and~{}~{}~{}}R_{T}^{2}(\pi)=\frac{T-W_{T}}{2}+\frac{W_{T}}{T}\cdot
T_{2}(\pi)$

where $R_{T}^{1}(\pi)$ (resp. $R_{T}^{2}(\pi)$) denotes the expected reward
collected by policy $\pi$ on scenario (27) (resp. scenario (28)). Thus, the
regret of policy $\pi$ on scenario (27) and (28) are $\frac{W_{T}}{T}\cdot
T_{1}(\pi)$ and $W_{T}-\frac{W_{T}}{T}\cdot T_{2}(\pi)$ respectively. Further
note that since the implementation of policy $\pi$ at each time period should
be only dependent on the historical information and the coefficients in the
estimated problem (26), we must have $T_{1}(\pi)=T_{2}(\pi)$. Thus, we have
that

$\text{Reg}_{T}(\pi)\geq\max\left\\{\frac{W_{T}}{T}\cdot
T_{1}(\pi),W_{T}-\frac{W_{T}}{T}\cdot
T_{1}(\pi)\right\\}\geq\frac{W_{T}}{2}=\Omega(W_{T})$

which completes our proof. ∎

###  B2 Proof of Lemma 3

###### Proof.

Proof: Due to symmetry, it is sufficient to show that for every $\bm{p}$ such
that $\bm{p}\in\Omega_{\bar{p}}$,

$L_{\mathcal{Q}_{2}}(\bm{p})-L_{\mathcal{Q}_{1}}(\bm{p})\leq\max\\{1,\bar{p}\\}\cdot
W(\mathcal{Q}_{1},\mathcal{Q}_{2}).$

Denote $\mathcal{Q}^{*}_{1,2}$ as the optimal coupling of the distribution
$\mathcal{Q}_{1}$ and $\mathcal{Q}_{2}$, i.e., the optimal solution to (8),
and denote

$\bm{x}^{*}(\bm{\theta})=\text{argmax}_{\bm{x}\in\mathcal{X}}\left\\{f(\bm{x};\bm{\theta})-\sum_{i=1}^{m}p_{i}\cdot
g_{i}(\bm{x};\bm{\theta})\right\\}$

Then for each $\bm{\theta}_{1}\in\Theta$, we define

$\bm{\hat{x}}(\bm{\theta}_{1})=\int_{\bm{\theta}_{2}\in\Theta}\bm{x}^{*}(\bm{\theta}_{2})\frac{d\mathcal{Q}^{*}_{1,2}(\bm{\theta}_{1},\bm{\theta}_{2})}{d\mathcal{Q}_{1}(\bm{\theta}_{1})}$

where
$\frac{d\mathcal{Q}^{*}_{1,2}(\bm{\theta}_{1},\bm{\theta}_{2})}{d\mathcal{Q}_{1}(\bm{\theta}_{1})}$
is the Radon–Nikodym derivative of $\mathcal{Q}^{*}_{1,2}$ with respect
$\mathcal{Q}_{1}$ and it can be interpreted as the conditional distribution of
$\bm{\theta}_{2}$ given $\bm{\theta}_{1}.$ Note that from the definition of
$\mathcal{Q}^{*}_{1,2}$, we have that
$\int_{\bm{\theta}_{2}\in\Theta}\frac{d\mathcal{Q}^{*}_{1,2}(\bm{\theta}_{1},\bm{\theta}_{2})}{d\mathcal{Q}_{1}(\bm{\theta}_{1})}=1$.
Thus, $\bm{\hat{x}}(\bm{\theta}_{1})$ is actually a convex combination of
$\\{\bm{x}^{*}(\bm{\theta}_{2})\\}_{\forall\bm{\theta}_{2}\in\Theta}$.
Moreover, from the concavity of $f(\cdot;\bm{\theta}_{1})$ and the convexity
of $g_{i}(\cdot;\bm{\theta}_{1})$ for each $i$, we have that

$f(\bm{\hat{x}}(\bm{\theta}_{1});\bm{\theta}_{1})\geq\int_{\bm{\theta}_{2}\in\Theta}f(\bm{x}^{*}(\bm{\theta}_{2});\bm{\theta}_{1})\cdot\frac{d\mathcal{Q}^{*}_{1,2}(\bm{\theta}_{1},\bm{\theta}_{2})}{d\mathcal{Q}_{1}(\bm{\theta}_{1})}$

and

$g_{i}(\bm{\hat{x}}(\bm{\theta}_{1});\bm{\theta}_{1})\leq\int_{\bm{\theta}_{2}\in\Theta}g_{i}(\bm{x}^{*}(\bm{\theta}_{2});\bm{\theta}_{1})\cdot\frac{d\mathcal{Q}^{*}_{1,2}(\bm{\theta}_{1},\bm{\theta}_{2})}{d\mathcal{Q}_{1}(\bm{\theta}_{1})}$

Thus, we have that

$\displaystyle L_{\mathcal{Q}_{1}}(\bm{p})$
$\displaystyle=\int_{\bm{\theta}_{1}\in\Theta}\max_{\bm{x}\in\mathcal{X}}\left\\{f(\bm{x};\bm{\theta}_{1})-\sum_{i=1}^{m}p_{i}\cdot
g_{i}(\bm{x};\bm{\theta}_{1})\right\\}d\mathcal{Q}_{1}(\bm{\theta}_{1})$
$\displaystyle\geq\int_{\bm{\theta}_{1}\in\Theta}\left\\{f(\bm{\hat{x}}(\bm{\theta}_{1});\bm{\theta}_{1})-\sum_{i=1}^{m}p_{i}\cdot
g_{i}(\bm{\hat{x}}(\bm{\theta}_{1});\bm{\theta}_{1})\right\\}d\mathcal{Q}_{1}(\bm{\theta}_{1})$
$\displaystyle\geq\int_{\bm{\theta}_{1}\in\Theta}\int_{\bm{\theta}_{2}\in\Theta}\left\\{f(\bm{x}^{*}(\bm{\theta}_{2});\bm{\theta}_{1})-\sum_{i=1}^{m}p_{i}\cdot
g_{i}(\bm{x}^{*}(\bm{\theta}_{2});\bm{\theta}_{1})\right\\}d\mathcal{Q}^{*}_{1,2}(\bm{\theta}_{1},\bm{\theta}_{2})$

Also, note that for any $\bm{\theta}_{1},\bm{\theta}_{2}\in\Theta$, it holds
that

$f(\bm{x}^{*}(\bm{\theta}_{2});\bm{\theta}_{1})-\sum_{i=1}^{m}p_{i}\cdot
g_{i}(\bm{x}^{*}(\bm{\theta}_{2});\bm{\theta}_{1})\geq
f(\bm{x}^{*}(\bm{\theta}_{2});\bm{\theta}_{2})-\sum_{i=1}^{m}p_{i}\cdot
g_{i}(\bm{x}^{*}(\bm{\theta}_{2});\bm{\theta}_{2})-\max\\{1,\bar{p}\\}\cdot(m+1)\rho(\bm{\theta}_{1},\bm{\theta}_{2})$

which follows the definition of $\rho(\bm{\theta}_{1},\bm{\theta}_{2})$ in
(2). Thus, we get that

$\displaystyle L_{\mathcal{Q}_{1}}(\bm{p})$
$\displaystyle\geq\int_{\bm{\theta}_{1}\in\Theta}\int_{\bm{\theta}_{2}\in\Theta}\left\\{f(\bm{x}^{*}(\bm{\theta}_{2});\bm{\theta}_{2})-\sum_{i=1}^{m}p_{i}\cdot
g_{i}(\bm{x}^{*}(\bm{\theta}_{2});\bm{\theta}_{2})\right\\}d\mathcal{Q}^{*}_{1,2}(\bm{\theta}_{1},\bm{\theta}_{2})$
$\displaystyle~{}~{}-\max\\{1,\bar{p}\\}\cdot(m+1)\int_{\bm{\theta}_{1}\in\Theta}\int_{\bm{\theta}_{2}\in\Theta}\rho(\bm{\theta}_{1},\bm{\theta}_{2})d\mathcal{Q}^{*}_{1,2}(\bm{\theta}_{1},\bm{\theta}_{2})$
$\displaystyle=\int_{\bm{\theta}_{2}\in\Theta}\left\\{f(\bm{x}^{*}(\bm{\theta}_{2});\bm{\theta}_{2})-\sum_{i=1}^{m}p_{i}\cdot
g_{i}(\bm{x}^{*}(\bm{\theta}_{2});\bm{\theta}_{2})\right\\}d\mathcal{Q}_{2}(\bm{\theta}_{2})-\max\\{1,\bar{p}\\}\cdot(m+1)\mathcal{W}(\mathcal{Q}_{1},\mathcal{Q}_{2})$
$\displaystyle=L_{\mathcal{Q}_{2}}(\bm{p})-\max\\{1,\bar{p}\\}\cdot(m+1)\mathcal{W}(\mathcal{Q}_{1},\mathcal{Q}_{2})$

where the first equality holds by noting that
$\int_{\bm{\theta}_{1}\in\Theta}d\mathcal{Q}^{*}_{1,2}(\bm{\theta}_{1},\bm{\theta}_{2})=d\mathcal{Q}_{2}(\bm{\theta}_{2})$.
∎

As a remark, we note that the proof of Lemma 3 will still go through even when
the concavity and convexity of $f(\cdot;\bm{\theta})$ and
$g_{i}(\cdot;\bm{\theta})$ do not hold. To see this, we use $F$ to denote a
distribution over the action set $\mathcal{X}$ and accordingly,

$\hat{f}(F;\bm{\theta})=\int_{\bm{x}\in\mathcal{X}}\hat{f}(\bm{x};\bm{\theta})dF(\bm{x})\text{~{}and~{}}\hat{g}_{i}(F;\bm{\theta})=\int_{\bm{x}\in\mathcal{X}}g_{i}(\bm{x};\bm{\theta})dF(\bm{x}).$

Then, we denote

$\hat{h}(\bm{p};\bm{\theta})\coloneqq\max_{F}\left\\{\hat{f}(F;\bm{\theta})-\bm{p}^{\top}\hat{\bm{g}}(F;\bm{\theta})\right\\},~{}~{}\hat{L}_{\mathcal{Q}}(\bm{p})=\mathcal{Q}\hat{h}(\bm{p};\bm{\theta})$

and

$\hat{\rho}(\bm{\theta},\bm{\theta}^{\prime})=\sup_{F}\|(\hat{f}(F;\bm{\theta}),\hat{\bm{g}}(F;\bm{\theta}))-(\hat{f}(F;\bm{\theta}^{\prime}),\hat{\bm{g}}(F;\bm{\theta}^{\prime}))\|_{\infty},~{}\hat{\mathcal{W}}(\mathcal{Q}_{1},\mathcal{Q}_{2})\coloneqq\inf_{\mathcal{Q}_{1,2}\in\mathcal{J}(\mathcal{Q}_{1},\mathcal{Q}_{2})}\int\hat{\rho}(\bm{\theta_{1}},\bm{\theta_{2}})d\mathcal{Q}_{1,2}(\bm{\theta_{1}},\bm{\theta_{2}}).$

Now that $\hat{f}(F;\bm{\theta})$ and $\hat{\bm{g}}(F;\bm{\theta})$ can be
regarded as linear functions of $(dF(\bm{x}),\forall\bm{x}\in\mathcal{X})$,
which fully characterizes the distribution $F$, we can apply the same
procedure as the proof of Lemma 3 to show that

$\sup_{\bm{p}\in\Omega_{\bar{p}}}\left|\hat{L}_{\mathcal{Q}_{1}}(\bm{p})-\hat{L}_{\mathcal{Q}_{2}}(\bm{p})\right|\leq\max\\{1,\bar{p}\\}\cdot(m+1)\hat{\mathcal{W}}(\mathcal{Q}_{1},\mathcal{Q}_{2}).$

On the other hand, note that

$\hat{h}(\bm{p};\bm{\theta})\coloneqq\max_{F}\left\\{\hat{f}(F;\bm{\theta})-\bm{p}^{\top}\hat{\bm{g}}(F;\bm{\theta})\right\\}=\max_{\bm{x}\in\mathcal{X}}\left\\{f(\bm{x};\bm{\theta})-\bm{p}^{\top}\bm{g}(\bm{x};\bm{\theta})\right\\}=h(\bm{p};\bm{\theta})$

and
$\hat{\rho}(\bm{\theta},\bm{\theta}^{\prime})=\rho(\bm{\theta},\bm{\theta}^{\prime})$.
We know that

$\left|\hat{L}_{\mathcal{Q}_{1}}(\bm{p})-\hat{L}_{\mathcal{Q}_{2}}(\bm{p})\right|=\left|L_{\mathcal{Q}_{1}}(\bm{p})-L_{\mathcal{Q}_{2}}(\bm{p})\right|\text{~{}and~{}}\hat{\mathcal{W}}(\mathcal{Q}_{1},\mathcal{Q}_{2})=\mathcal{W}(\mathcal{Q}_{1},\mathcal{Q}_{2}).$

Therefore, (12) can be proved to hold for general $f(\cdot;\bm{\theta})$ and
$g_{i}(\cdot;\bm{\theta})$ without any convexity or concavity structure.

###  B3 Proof of Lemma 4

###### Proof.

Proof: Note that the following two property is satisfied by the update rule
(11):

  * (i).

If $\|\bm{p}_{t}\|_{\infty}\leq q$, then we must have
$\|\bm{p}_{t+1}\|_{\infty}\leq q+1$ by noting that for each $i$, the $i$-th
component of $\bm{p}_{t}$, denoted as $p_{t,i}$, is nonnegative and
$g_{i}(\cdot,\bm{\theta}_{t})$ is normalized within $[0,1]$.

  * (ii).

If there exists $i$ such that $p_{t,i}>q$, then we must have
$p_{t+1,i}<p_{t,i}$. Specifically, when $p_{t,i}>q$, we must have that
$g_{i}(\tilde{\bm{x}}_{t};\bm{\theta}_{t})=0$, otherwise we would have that

$f(\tilde{\bm{x}}_{t};\bm{\theta}_{t})-\bm{p}_{t}^{\top}\cdot\bm{g}(\tilde{\bm{x}}_{t};\bm{\theta}_{t})\leq
f(\tilde{\bm{x}}_{t};\bm{\theta}_{t})-p_{t,i}\cdot
g_{i}(\tilde{\bm{x}}_{t};\bm{\theta}_{t})<0$

which contradicts the definition of $\tilde{\bm{x}}_{t}$ in
IGD($\hat{\bm{\gamma}}$) since we could always select
$\tilde{\bm{x}}_{t}=\bm{0}$ to obtain $0$ in the objective value. Then from
the non-negativity of $\hat{\bm{c}}_{t}$, it holds that $p_{t+1,i}<p_{t,i}$ in
(11).

Starting from $\bm{p}_{1}=0$ and iteratively applying the above two property
to control the increase of $\bm{p}_{t}$ from $t=1$ to $T$, we obtain that for
the first time that one component of $\bm{p}_{t}$ exceeds the threshold $q$,
it is upper bounded by $q+1$ and this component will continue to decrease
until it falls below the threshold $q$. Thus, it is obvious that we have
$\|\bm{p}_{t}\|_{\infty}\leq q+1$ with probability $1$ for each $t$. ∎

###  B4 Proof of Theorem 3

Similar to case of known distribution, we define the following function
$\hat{L}_{t}(\cdot)$, based on the prior estimate $\hat{\mathcal{P}}_{t}$.

$\hat{L}_{t}(\bm{p})\coloneqq\hat{\bm{\gamma}}_{t}^{\top}\bm{p}+\hat{\mathcal{P}}_{t}h(\bm{p};\bm{\theta}).$
(29)

Then we have the following relation between $\hat{L}(\cdot)$ and
$\hat{L}_{t}(\cdot).$ As its analysis is identical to Proposition 1, we omit
its proof for simplicity.

###### Lemma 5

For each $t=1,...,T$, it holds that

$\hat{\bm{p}}^{*}\in\text{argmin}_{\bm{p}\geq 0}\hat{L}_{t}(\bm{p})$ (30)

where $\hat{\bm{p}}^{*}$ is defined in (9) as the minimizer of the function
$\hat{L}(\cdot)$. Moreover, it holds that

$\hat{L}(\hat{\bm{p}}^{*})=\sum_{t=1}^{T}\hat{L}_{t}(\hat{\bm{p}}^{*}).$ (31)

Now we proof Theorem 3 and the idea of proof is similar to Theorem 1.

###### Proof.

Proof: From the proof of Theorem 1, we have

$\displaystyle\sum_{t=1}^{T}f(\tilde{\bm{x}}_{t};\bm{\theta}_{t})-\sum_{t=1}^{T}f(\bm{x}_{t};\bm{\theta}_{t})$
$\displaystyle\leq
q\cdot\sum_{i=1}^{m}\sum_{t=1}^{T}g_{i}(\tilde{\bm{x}}_{t};\bm{\theta}_{t})\cdot\mathbb{I}\left\\{\sum_{j=1}^{t}g_{i}(\tilde{\bm{x}}_{j};\bm{\theta}_{j})>c_{i}\right\\}$
$\displaystyle\leq
q\cdot\sum_{i=1}^{m}\left[\sum_{t=1}^{T}g_{i}(\tilde{\bm{x}}_{t};\bm{\theta}_{t})-(c_{i}-1)\right]^{+}$

which related the total collected reward by the true action
$\\{\bm{x}_{t}\\}_{t=1}^{T}$ and the virtual action
$\\{\tilde{\bm{x}}_{t}\\}_{t=1}^{T}$ of the algorithm
IGD($\hat{\bm{\gamma}}$). Further from Proposition 1, we have that

$\displaystyle\text{Reg}_{T}(\pi)\leq\min_{\bm{p}\geq
0}L(\bm{p})-\mathbb{E}\left[\sum_{t=1}^{T}f(\bm{x}_{t};\bm{\theta}_{t})\right]$
$\displaystyle\leq\underbrace{\min_{\bm{p}\geq
0}L(\bm{p})-\mathbb{E}\left[\sum_{t=1}^{T}f(\tilde{\bm{x}}_{t};\bm{\theta}_{t})\right]}_{\text{I}}$
$\displaystyle+\underbrace{q\cdot\mathbb{E}\left[\sum_{i=1}^{m}\left[\sum_{t=1}^{T}g_{i}(\tilde{\bm{x}}_{t};\bm{\theta}_{t})-(c_{i}-1)\right]^{+}\right]}_{\text{II}}$

We then bound the term I and term II separately to derive our regret bound.
Bound I: Note that $\|\hat{\bm{p}}^{*}\|_{\infty}\leq q$, it follows directly
from Lemma 3 and Lemma 5 that

$\min_{\bm{p}\geq\bm{0}}L(\bm{p})\leq
L(\hat{\bm{p}}^{*})\leq\hat{L}(\hat{\bm{p}}^{*})+\max\\{q,1\\}\cdot(m+1)\cdot
W_{T}=\sum_{t=1}^{T}\hat{L}_{t}(\hat{\bm{p}}^{*})+\max\\{q,1\\}\cdot(m+1)\cdot
W_{T}$

Note that from Lemma 4, we have that for each $t$,
$\|\bm{p}_{t}\|_{\infty}\leq(q+1)$ with probability $1$. Further note that for
each $t$, the distribution of $\bm{p}_{t}$ is independent from the
distribution of $\bm{\theta}_{t}$, then from Lemma 3 and Lemma 5, we have that

$\hat{L}_{t}(\hat{\bm{p}}^{*})=\min_{\bm{p}\geq\bm{0}}\hat{L}_{t}(\bm{p})\leq\mathbb{E}_{\bm{p}_{t}}\left[\hat{L}_{t}(\bm{p}_{t})\right]\leq\mathbb{E}_{\bm{p}_{t}}\left[\hat{\bm{\gamma}}_{t}^{\top}\bm{p}_{t}+\mathcal{P}_{t}h(\bm{p}_{t};\bm{\theta}_{t})\right]+(q+1)(m+1)\cdot
W(\mathcal{P}_{t},\hat{\mathcal{P}})$

where the expectation is taken with respect to the randomness of the dual
price $\bm{p}_{t}.$ Thus, we have

$\text{I}\leq\sum_{t=1}^{T}\mathbb{E}_{\bm{p}_{t}}\left[\hat{\bm{\gamma}}_{t}^{\top}\bm{p}_{t}+\mathcal{P}_{t}\left\\{h(\bm{p}_{t};\bm{\theta}_{t})-f(\tilde{\bm{x}}_{t};\bm{\theta}_{t})\right\\}\right]+2(q+1)(m+1)\cdot
W_{T}.$

From the definition of $\tilde{\bm{x}}_{t}$, we get that
$h(\bm{p}_{t};\bm{\theta}_{t})-f(\tilde{\bm{x}}_{t};\bm{\theta}_{t})=-\bm{p}_{t}^{\top}\cdot\bm{g}(\tilde{\bm{x}}_{t};\bm{\theta}_{t})$,
which implies that

$\text{I}\leq\sum_{t=1}^{T}\mathbb{E}_{\bm{p}_{t}}\left[\bm{p}_{t}^{\top}\cdot\left(\hat{\bm{\gamma}}_{t}-\mathcal{P}_{t}\bm{g}(\tilde{\bm{x}}_{t};\bm{\theta}_{t})\right)\right]+2(q+1)(m+1)\cdot
W_{T}$

Note that from the update rule (11), we have that

$\|\bm{p}_{t+1}\|_{2}^{2}\leq\|\bm{p}_{t}\|_{2}^{2}+\frac{1}{T}\cdot\|\bm{g}(\tilde{\bm{x}}_{t};\bm{\theta}_{t})-\hat{\bm{\gamma}}_{t}\|_{2}^{2}-\frac{2}{\sqrt{T}}\cdot\bm{p}_{t}^{\top}\cdot\left(\hat{\bm{\gamma}}_{t}-\bm{g}(\tilde{\bm{x}}_{t};\bm{\theta}_{t})\right)$

which implies that

$\mathbb{E}_{\bm{p}_{t}}\left[\bm{p}_{t}^{\top}\cdot\left(\hat{\bm{\gamma}}_{t}-\mathcal{P}_{t}\bm{g}(\tilde{\bm{x}}_{t};\bm{\theta}_{t})\right)\right]\leq\frac{\sqrt{T}}{2}\cdot\left(\mathbb{E}[\|\bm{p}_{t}\|_{2}^{2}]-\mathbb{E}[\|\bm{p}_{t+1}\|_{2}^{2}]\right)+\frac{m}{2\sqrt{T}}$

Thus, it holds that

$\text{I}\leq\frac{m\sqrt{T}}{2}+2(q+1)(m+1)\cdot W_{T}$ (32)

Bound II: Note that from the update rule (11), we have that

$\sqrt{T}\cdot\bm{p}_{t+1}\geq\sqrt{T}\cdot\bm{p}_{t}+\bm{g}(\tilde{\bm{x}}_{t};\bm{\theta}_{t})-\hat{\bm{\gamma}}_{t}$

which implies that

$\sum_{t=1}^{T}\bm{g}(\tilde{\bm{x}}_{t};\bm{\theta}_{t})-\bm{c}\leq\sum_{t=1}^{T}\bm{g}(\tilde{\bm{x}}_{t};\bm{\theta}_{t})-\sum_{t=1}^{T}\hat{\bm{\gamma}}_{t}\leq\sqrt{T}\cdot\bm{p}_{T+1}$

Thus, it holds that

$\text{II}=q\cdot\mathbb{E}\left[\sum_{i=1}^{m}\left[\sum_{t=1}^{T}g_{i}(\tilde{\bm{x}}_{t};\bm{\theta}_{t})-(c_{i}-1)\right]^{+}\right]\leq
mq(q+1)\cdot\sqrt{T}+qm$ (33)

We obtain the $O(\max\\{\sqrt{T},W_{T}\\})$ regret bound immediately by
combining (32) and (33). ∎

##  10 Proofs of Section 5

###  C1 Proof of Proposition 3

###### Proof.

Proof: We consider the implementation of any online policy $\pi$ on the two
scenarios (13) and (14) for $\kappa=1$, which is replicated as follows for
completeness:

$\displaystyle\max\ \ $ $\displaystyle x_{1}+...+x_{c}+2x_{c+1}+...+2x_{T}$
(34) s.t. $\displaystyle x_{1}+...+x_{c}+x_{c+1}+...+x_{T}\leq c$
$\displaystyle 0\leq x_{t}\leq 1\ \text{ for }t=1,...,T.$ $\displaystyle\max\
\ $ $\displaystyle x_{1}+...+x_{c}$ (35) s.t. $\displaystyle
x_{1}+...+x_{c}+x_{c+1}+...+x_{T}\leq c$ $\displaystyle 0\leq x_{t}\leq 1\
\text{ for }t=1,...,T.$

where $c=\frac{T}{2}$. Denote $x^{1}_{t}(\pi)$ as the decision of policy $\pi$
at period $t$ for scenario (34) and denote $x^{2}_{t}(\pi)$ as the decision of
policy $\pi$ at period $t$ for scenario (35). Further define $T_{1}(\pi)$
(resp. $T_{2}(\pi)$) as the expected capacity consumption of policy $\pi$ on
scenario (34) (resp. scenario (35)) during the first $\frac{T}{2}$ time
periods:

$T_{1}(\pi)=\mathbb{E}\left[\sum_{t=1}^{\frac{T}{2}}x^{1}_{t}(\pi)\right]\text{~{}~{}~{}and~{}~{}~{}}T_{2}(\pi)=\mathbb{E}\left[\sum_{t=1}^{\frac{T}{2}}x^{2}_{t}(\pi)\right]$

Then, we have that

$R_{T}^{1}(\pi)=T-T_{1}(\pi)\text{~{}~{}~{}and~{}~{}~{}}R_{T}^{2}(\pi)=T_{2}(\pi)$

where $R_{T}^{1}(\pi)$ (resp. $R_{T}^{2}(\pi)$) denotes the expected reward
collected by policy $\pi$ on scenario (34) (resp. scenario (35)). Thus, the
regret of policy $\pi$ on scenario (34) and (35) are $T_{1}(\pi)$ and
$T-T_{2}(\pi)$ respectively. Further note that since the implementation of
policy $\pi$ at each time period should be independent of the future
information, we must have $T_{1}(\pi)=T_{2}(\pi)$. Thus, we have that

$\text{Reg}_{T}(\pi)\geq\max\\{T_{1}(\pi),T-T_{1}(\pi)\\}\geq\frac{T}{2}=\Omega(T)$

which completes our proof. ∎

###  C2 Proof of Theorem 4

The proof of the theorem can be directly obtained from Theorem 2.

###  C3 Proof of Theorem 5

We first prove the following lemma, which implies that the dual variable
updated in (15) is always bounded. It derivation is essentially the same as
Lemma 2, so we omit its proof for simplicity.

###### Lemma 6

Under Assumption 1, for each $t=1,2,\dots,T$, the dual price vector satisfies
$\|\bm{p}_{t}\|_{\infty}\leq q+1$, where $\bm{p}_{t}$ is specified by (15) in
Algorithm 2 and the constant $q$ is defined in Assumption 1 (c).

Now we proceed to prove Theorem 5.

###### Proof.

Proof: From the proof of Theorem 1, we have

$\displaystyle\sum_{t=1}^{T}f(\tilde{\bm{x}}_{t};\bm{\theta}_{t})-\sum_{t=1}^{T}f(\bm{x}_{t};\bm{\theta}_{t})$
$\displaystyle\leq
q\cdot\sum_{i=1}^{m}\left[\sum_{t=1}^{T}g_{i}(\tilde{\bm{x}}_{t};\bm{\theta}_{t})-(c_{i}-1)\right]^{+}$

which relates the total collected reward by the true action
$\\{\bm{x}_{t}\\}_{t=1}^{T}$ and the virtual action
$\\{\tilde{\bm{x}}_{t}\\}_{t=1}^{T}$. Here $[\cdot]^{+}$ denotes the positive
part function. Furthermore, from Proposition 1 and the feasibility, we have
that

$\displaystyle\text{Reg}_{T}(\pi)\leq\min_{\bm{p}\geq\bm{0}}L(\bm{p})-\mathbb{E}\left[\sum_{t=1}^{T}f(\bm{x}_{t};\bm{\theta}_{t})\right]$
$\displaystyle\leq\underbrace{\min_{\bm{p}\geq\bm{0}}L(\bm{p})-\mathbb{E}\left[\sum_{t=1}^{T}f(\tilde{\bm{x}}_{t};\bm{\theta}_{t})\right]}_{\text{I}}$
$\displaystyle+\underbrace{q\cdot\mathbb{E}\left[\sum_{i=1}^{m}\left[\sum_{t=1}^{T}g_{i}(\tilde{\bm{x}}_{t};\bm{\theta}_{t})-(c_{i}-1)\right]^{+}\right]}_{\text{II}}$

Next, we bound the term I and term II separately to derive our regret bound.
Bound I: We first define the following function $\bar{L}(\cdot)$:

$\bar{L}(\bm{p})\coloneqq\frac{1}{T}\bm{p}^{\top}\bm{c}+\bar{\mathcal{P}}_{T}h(\bm{p};\bm{\theta})$

Note that $\hat{\mathcal{P}}_{T}=\frac{1}{T}\sum_{t=1}^{T}\mathcal{P}_{t}$, it
holds that $L(\bm{p})=T\cdot\bar{L}(\bm{p})$ for any $\bm{p}$. From Lemma 6,
we know that for each $t$, $\|\bm{p}_{t}\|_{\infty}\leq q+1$ with probability
$1$. In addition, for each $t$, the distribution of $\bm{p}_{t}$ is
independent from the distribution of $\bm{\theta}_{t}$, then from Lemma 3, we
have that

$\min_{\bm{p}\geq\bm{0}}\bar{L}(\bm{p})\leq\mathbb{E}_{\bm{p}_{t}}\left[\bar{L}(\bm{p}_{t})\right]\leq\mathbb{E}_{\bm{p}_{t}}\left[\frac{1}{T}\bm{p}_{t}^{\top}\bm{c}+\mathcal{P}_{t}h(\bm{p}_{t};\bm{\theta}_{t})\right]+(q+1)(m+1)\cdot\mathcal{W}(\mathcal{P}_{t},\bar{\mathcal{P}}_{T}),$
(36)

where the expectation is taken with respect to $\bm{p}_{t}$ in a random
realization of the algorithm. Thus, we have the first term

$\text{I}\leq\sum_{t=1}^{T}\mathbb{E}_{\bm{p}_{t}}\left[\frac{1}{T}\bm{c}^{\top}\bm{p}_{t}+\mathcal{P}_{t}\left\\{h(\bm{p}_{t};\bm{\theta}_{t})-f(\tilde{\bm{x}}_{t};\bm{\theta}_{t})\right\\}\right]+(q+1)(m+1)\cdot\mathcal{W}(\mathcal{P}_{t},\bar{\mathcal{P}}_{T})$

which comes from combining (36) with the relation
$L(\bm{p})=T\cdot\bar{L}(\bm{p})$. By the definition of $\tilde{\bm{x}}_{t}$,
$h(\bm{p}_{t};\bm{\theta}_{t})-f(\tilde{\bm{x}}_{t};\bm{\theta}_{t})=-\bm{p}_{t}^{\top}\cdot\bm{g}(\tilde{\bm{x}}_{t};\bm{\theta}_{t})$,
which implies that

$\text{I}\leq\sum_{t=1}^{T}\mathbb{E}_{\bm{p}_{t}}\left[\bm{p}_{t}^{\top}\cdot\left(\frac{\bm{c}}{T}-\mathcal{P}_{t}\bm{g}(\tilde{\bm{x}}_{t};\bm{\theta}_{t})\right)\right]+(q+1)(m+1)\cdot\mathcal{W}(\mathcal{P}_{t},\bar{\mathcal{P}}_{T})$
(37)

Note that from the update rule (15), we have that

$\|\bm{p}_{t+1}\|_{2}^{2}\leq\|\bm{p}_{t}\|_{2}^{2}+\frac{1}{T}\cdot\|\bm{g}(\tilde{\bm{x}}_{t};\bm{\theta}_{t})-\frac{\bm{c}}{T}\|_{2}^{2}-\frac{2}{\sqrt{T}}\cdot\bm{p}_{t}^{\top}\cdot\left(\frac{\bm{c}}{T}-\bm{g}(\tilde{\bm{x}}_{t};\bm{\theta}_{t})\right).$

By taking expectation with respect to both sides,

$\mathbb{E}_{\bm{p}_{t}}\left[\bm{p}_{t}^{\top}\cdot\left(\frac{\bm{c}}{T}-\mathcal{P}_{t}\bm{g}(\tilde{\bm{x}}_{t};\bm{\theta}_{t})\right)\right]\leq\frac{\sqrt{T}}{2}\cdot\left(\mathbb{E}[\|\bm{p}_{t}\|_{2}^{2}]-\mathbb{E}[\|\bm{p}_{t+1}\|_{2}^{2}]\right)+\frac{m}{2\sqrt{T}}$
(38)

Plugging (38) into (37), we obtain an upper bound on Term I,

$\text{I}\leq\frac{m\sqrt{T}}{2}+(q+1)(m+1)\cdot W_{T}$ (39)

Bound II: Note that from the update rule (15), we have

$\sqrt{T}\cdot\bm{p}_{t+1}\geq\sqrt{T}\cdot\bm{p}_{t}+\bm{g}(\tilde{\bm{x}}_{t};\bm{\theta}_{t})-\frac{\bm{c}}{T}$

Taking a summation with respect to both sides,

$\sum_{t=1}^{T}\bm{g}(\tilde{\bm{x}}_{t};\bm{\theta}_{t})-\bm{c}\leq\sqrt{T}\cdot\bm{p}_{T+1}$

Applying Lemma 6 for a bound on $\bm{p}_{T+1},$ we obtain the upper bound for
Term II,

$\text{II}=q\cdot\mathbb{E}\left[\sum_{i=1}^{m}\left[\sum_{t=1}^{T}g_{i}(\tilde{\bm{x}}_{t};\bm{\theta}_{t})-(c_{i}-1)\right]^{+}\right]\leq
mq(q+1)\cdot\sqrt{T}+qm$ (40)

We obtain the desired regret bound by combining (39) and (40). ∎

##  11 Proofs of Section 6

###  D1 Proof of Theorem 6

###### Proof.

Proof: Note that the regret can be denoted as

$\displaystyle\text{Reg}_{T}(\mathcal{H},\pi_{\text{Resolve}})$
$\displaystyle=\mathbb{E}_{\mathcal{H}\sim\mathcal{P}}[R^{*}_{1}(\mathbf{c}_{1},\mathcal{H}(1))]-\mathbb{E}_{\mathcal{H}\sim\mathcal{P}}[\sum_{t=1}^{T}r_{t}\cdot
x_{t}]$ (41)
$\displaystyle=\sum_{t=1}^{T}\underbrace{\mathbb{E}_{\mathcal{H}\sim\mathcal{P}}[R^{*}_{t}(\mathbf{c}_{t},\mathcal{H}(t))-R^{*}_{t+1}(\mathbf{c}_{t+1},\mathcal{H}(t+1))-r_{t}\cdot
x_{t}]}_{\text{I}_{t}}$

Now we denote $\\{x^{*}_{j}(\mathbf{c}_{t},\mathcal{H}(t))\\}$ as one optimal
solution to $R^{*}_{t}(\mathbf{c}_{t},\mathcal{H}(t))$. Clearly, we have the
following: if $\bm{\theta}_{t}$ is realized as $\bm{\theta}^{(j)}$, i.e.,
$\mathcal{H}_{j}(t)=\mathcal{H}_{j}(t+1)+1$ and
$\mathcal{H}_{j^{\prime}}(t)=\mathcal{H}_{j^{\prime}}(t+1)$ for other
$j^{\prime}$, it holds that

$\displaystyle
R^{*}_{t}(\mathbf{c}_{t},\mathcal{H}(t))=r_{j}+R^{*}_{t+1}(\mathbf{c}_{t}-\bm{a}_{j},\mathcal{H}(t+1)),$
$\displaystyle\text{if~{}}x^{*}_{j}(\mathbf{c}_{t},\mathcal{H}(t))\geq 1$ (42)
$\displaystyle
R^{*}_{t}(\mathbf{c}_{t},\mathcal{H}(t))=R^{*}_{t+1}(\mathbf{c}_{t},\mathcal{H}(t+1)),$
$\displaystyle\text{if~{}}\mathcal{H}_{j}(t)-x^{*}_{j}(\mathbf{c}_{t},\mathcal{H}(t))\geq
1$

We also denote the event
$\mathcal{A}_{t}=\\{x^{*}_{j}(\mathbf{c}_{t},\mathcal{H}(t))\geq 1\\}$ and the
event
$\mathcal{B}_{t}=\\{\mathcal{H}_{j}(t)-x^{*}_{j}(\mathbf{c}_{t},\mathcal{H}(t))\geq
1\\}$.

In the rest of the proof, we mainly analyze the term $\text{I}_{t}$ in (41).
We first focus on the case when $t\leq
T+1-\frac{4(\alpha\beta_{2}+\beta_{2})}{p_{\min}}\cdot
W_{T}-\frac{4}{p_{\min}}$, where $W_{T}$ is the deviation budget from the
estimates $\\{\hat{\mathcal{P}}_{t}\\}_{t=1}^{T}$ to the true distributions
$\\{\mathcal{P}_{t}\\}_{t=1}^{T}$, $p_{\min}$ is given in 2, and
$\alpha,\beta_{2}$ are parameters to be determined later.
Case I:
$\hat{x}_{j_{t}}(\mathbf{c}_{t})\geq\frac{1}{2}\cdot\mathbb{E}_{\mathcal{H}\sim\hat{\mathcal{P}}}[\mathcal{H}_{j_{t}}(t)]$.
Then we have $x_{t}=1$, and from (42), we have

$\displaystyle\text{I}_{t}=$
$\displaystyle\mathbb{E}_{\mathcal{H}\sim\mathcal{P}}[R^{*}_{t}(\mathbf{c}_{t},\mathcal{H}(t))-R^{*}_{t+1}(\mathbf{c}_{t+1},\mathcal{H}(t+1))-r_{t}\cdot
x_{t}]$ $\displaystyle=$
$\displaystyle\mathbb{E}\left[\mathbb{E}[r_{j_{t}}-r_{j_{t}}\cdot
x_{t}+R^{*}_{t+1}(\mathbf{c}_{t}-\bm{a}_{j_{t}},\mathcal{H}(t+1))-R^{*}_{t+1}(\mathbf{c}_{t}-\bm{a}_{j_{t}}\cdot
x_{t},\mathcal{H}(t+1))|\mathcal{A}_{t}]\right]$
$\displaystyle+\mathbb{E}\left[\mathbb{E}[-r_{j_{t}}\cdot
x_{t}+R^{*}_{t+1}(\mathbf{c}_{t},\mathcal{H}(t+1))-R^{*}_{t+1}(\mathbf{c}_{t}-\bm{a}_{j_{t}}\cdot
x_{t},\mathcal{H}(t+1))|\mathcal{A}^{c}_{t}]\right]$ $\displaystyle=$
$\displaystyle\mathbb{E}\left[\mathbb{E}[-r_{j_{t}}\cdot
x_{t}+R^{*}_{t+1}(\mathbf{c}_{t},\mathcal{H}(t+1))-R^{*}_{t+1}(\mathbf{c}_{t}-\bm{a}_{j_{t}}\cdot
x_{t},\mathcal{H}(t+1))|\mathcal{A}^{c}_{t}]\right]$ $\displaystyle\leq$
$\displaystyle P(\mathcal{A}^{c}_{t})$

where $\mathcal{A}^{c}_{t}$ denotes the complementary event of
$\mathcal{A}_{t}$. We now bound $P(\mathcal{A}^{c}_{t})$.

From Theorem 2.4 in (Mangasarian and Shiau, 1987), there exists a constant
$\alpha>0$, which depends only on
$\\{(r_{1},\bm{a}_{1}),\dots,(r_{n},\bm{a}_{n})\\}$, such that

$\|\bm{x}^{*}(\mathbf{c}_{t},\mathcal{H}(t))-\hat{\bm{x}}(\mathbf{c}_{t})\|_{\infty}\leq\alpha\cdot\|\mathcal{H}(t)-\mathbb{E}_{\mathcal{H}\sim\hat{\mathcal{P}}}[\mathcal{H}(t)]\|_{\infty}.$

Moreover, from Hoeffdings’ inequality, we know that

$P\left(\|\mathcal{H}(t)-\mathbb{E}_{\mathcal{H}\sim\hat{\mathcal{P}}}[\mathcal{H}(t)]\|_{\infty}\leq\frac{p_{\min}\cdot(T-t+1)}{4\alpha}\right)\geq
1-\exp(-\beta_{1}\cdot(T-t+1))$

for some constant $\beta_{1}>0$, and

$\|\mathbb{E}_{\mathcal{H}\sim\hat{\mathcal{P}}}[\mathcal{H}(t)]-\mathbb{E}_{\mathcal{H}\sim\mathcal{P}}[\mathcal{H}(t)]\|_{\infty}\leq\beta_{2}\cdot
W_{T}.$

Thus, we have that

$P\left(\|x^{*}(\mathbf{c}_{t},\mathcal{H}(t))-\hat{x}(\mathbf{c}_{t})\|_{\infty}\leq\frac{p_{\min}\cdot(T-t+1)}{4}+\alpha\beta_{2}\cdot
W_{T}\right)\geq 1-\exp(-\beta_{1}\cdot(T-t+1))$

Since we have

$\hat{x}_{j_{t}}(\mathbf{c}_{t})\geq\frac{1}{2}\cdot\mathbb{E}_{\mathcal{H}\sim\hat{\mathcal{P}}}[\mathcal{H}_{j_{t}}(t)]\geq\frac{1}{2}\cdot
p_{\min}\cdot(T-t+1)-\beta_{2}\cdot W_{T},$

we have that

$P\left(x^{*}_{j_{t}}(\mathbf{c}_{t},\mathcal{H}(t))\geq\frac{p_{\min}\cdot(T-t+1)}{4}-(\alpha\beta_{2}+\beta_{2})\cdot
W_{T}\geq 1\right)\geq 1-\exp(-\beta_{1}\cdot(T-t+1)).$

when $t\leq T+1-\frac{4(\alpha\beta_{2}+\beta_{2})}{p_{\min}}\cdot
W_{T}-\frac{4}{p_{\min}}$.

Thus, when $t\leq T+1-\frac{4(\alpha+1)}{p_{\min}}\cdot
W_{T}-\frac{4}{p_{\min}}$, we know that
$P(\mathcal{A}^{c}_{t})\leq\exp(-\beta_{1}\cdot(T-t+1))$.
Case II:
$\hat{x}_{j_{t}}(\mathbf{c}_{t})<\frac{1}{2}\cdot\mathbb{E}_{\mathcal{H}\sim\hat{\mathcal{P}}}[\mathcal{H}_{j_{t}}(t)]$.
Then we have $x_{t}=0$, and from (42), we have

$\displaystyle\text{I}_{t}=$
$\displaystyle\mathbb{E}[R^{*}_{t}(\mathbf{c}_{t},\mathcal{H}(t))-R^{*}_{t+1}(\mathbf{c}_{t+1},\mathcal{H}(t+1))-r_{t}\cdot
x_{t}]$ $\displaystyle=$
$\displaystyle\mathbb{E}\left[\mathbb{E}[-r_{j_{t}}\cdot
x_{t}+R^{*}_{t+1}(\mathbf{c}_{t},\mathcal{H}(t+1))-R^{*}_{t+1}(\mathbf{c}_{t}-\bm{a}_{j_{t}}\cdot
x_{t},\mathcal{H}(t+1))|\mathcal{B}_{t}]\right]$
$\displaystyle+\mathbb{E}\left[\mathbb{E}[r_{j_{t}}-r_{j_{t}}\cdot
x_{t}+R^{*}_{t+1}(\mathbf{c}_{t}-\bm{a}_{j_{t}},\mathcal{H}(t+1))-R^{*}_{t+1}(\mathbf{c}_{t}-\bm{a}_{j_{t}}\cdot
x_{t},\mathcal{H}(t+1))|\mathcal{B}_{t}^{c}]\right]$ $\displaystyle=$
$\displaystyle\mathbb{E}\left[\mathbb{E}[r_{j_{t}}+R^{*}_{t+1}(\mathbf{c}_{t}-\bm{a}_{j_{t}},\mathcal{H}(t+1))-R^{*}_{t+1}(\mathbf{c}_{t},\mathcal{H}(t+1))|\mathcal{B}_{t}^{c}]\right]$
$\displaystyle\leq$ $\displaystyle P(\mathcal{B}^{c}_{t})$

Following the same approach, we have that
$P(\mathcal{B}^{c}_{t})\leq\exp(-\beta_{1}\cdot(T-t+1))$ when $t\leq
T+1-\frac{4(\alpha\beta_{2}+\beta_{2})}{p_{\min}}\cdot
W_{T}-\frac{4}{p_{\min}}$.

Thus, on both cases, we conclude that

$\text{I}_{t}\leq\exp(-\beta_{1}\cdot(T-t+1))$

when $t\leq T+1-\frac{4(\alpha\beta_{2}+\beta_{2})}{p_{\min}}\cdot
W_{T}-\frac{4}{p_{\min}}$. Thus, from (41), we have that

$\displaystyle\text{Reg}_{T}(\mathcal{H},\pi_{\text{Resolve}})$
$\displaystyle\leq\sum_{t=1}^{T+1-\frac{4(\alpha\beta_{2}+\beta_{2})}{p_{\min}}\cdot
W_{T}-\frac{4}{p_{\min}}}\text{I}_{t}+\frac{4(\alpha\beta_{2}+\beta_{2})}{p_{\min}}\cdot
W_{T}+\frac{4}{p_{\min}}$
$\displaystyle\leq\sum_{t=1}^{T}\exp(-\beta_{1}\cdot(T-t+1))+\frac{4(\alpha\beta_{2}+\beta_{2})}{p_{\min}}\cdot
W_{T}+\frac{4}{p_{\min}}$ $\displaystyle=\max\\{O(1),O(W_{T})\\}$

which completes our proof. ∎

Remark: Note that Vera and Banerjee (2020); Banerjee and Freund (2020a, b)
utilize the condition of $p_{\min}$ in Assumption 2 to control the non-
stationarity of the distribution $\mathcal{P}_{t}$. To be specific, suppose
the support set $\Theta=\\{\bm{\theta}^{(1)},\dots,\bm{\theta}^{(n)}\\}$ and
for each $j=1,\dots,n$, we denote $H_{j}(t)$ as the number of times that
$\bm{\theta}_{\tau}$ is realized as $\bm{\theta}_{j}$ for $\tau=t,\dots,T$.
Denote by $\mathcal{H}(t)=(\mathcal{H}_{1}(t),\dots,\mathcal{H}_{n}(t))$. Then
this concentration condition of $p_{\min}$ in Vera and Banerjee (2020);
Banerjee and Freund (2020a, b) essentially requires that

$P\left(\|\mathcal{H}(t)-\mathbb{E}[\mathcal{H}(t)]\|\geq\frac{\mathbb{E}[\mathcal{H}_{j}(t)]}{2\kappa^{1}_{j}}\right)\leq\frac{c_{j}}{(T-t)^{2}},~{}~{}\forall
t\leq T-\kappa_{j}^{2},~{}~{}\forall j=1,\dots,n$ (43)

for some constants $\kappa^{1}_{j},\kappa^{2}_{j}$ and $c_{j}$.

We now show through the following example for which our WBNB is sublinear in
$T$ and the example can not covered by the above concentration condition. The
example can be constructed as follows. For $t=1,\dots,T-\sqrt{T}$, we have
$\mathcal{P}_{t}=\mathcal{P}_{1}$ and for $t=T-\sqrt{T}+1,\dots,T$, we have
$\mathcal{P}_{t}=\mathcal{P}_{2}$, where $\mathcal{P}_{1}$ and
$\mathcal{P}_{2}$ are two different distributions and it is satisfied that
$\mathcal{P}_{2}(\bm{\theta}=\bm{\theta}_{j}^{\prime})=0$ for a $j^{\prime}$.
Clearly, (43) is not satisfied for $j=j^{\prime}$, thus, the concentration
condition does not hold. However, it is direct to check that the WBNB can be
upper bounded by $O(\sqrt{T})$, which is sublinear in $T$.

###  D2 Analysis of the sub-optimality of static policies

####  D2.1 Proof of Proposition 4

###### Proof.

Proof: We first describe a problem instance. Consider a single resource with
initial capacity $c=3T/4$. The parameter $\bm{\theta}_{t}=(r_{t},1)$; the
functions $f(x_{t},\bm{\theta}_{t})=r_{t}\cdot x_{t}$ and
$g(x_{t},\bm{\theta}_{t})=x_{t}$, where $x_{t}\in[0,1]$ is the decision
variable at time period $t$. Suppose that the prior estimate
$\hat{\mathcal{P}}$ is given by

$r_{t}=\left\\{\begin{aligned} &1,&\text{w.p.}~{}\frac{3}{4}\\\
&\text{Unif}[0,1],&\text{w.p.}~{}\frac{1}{4}\end{aligned}\right.$

for each $t$. Here $\text{Unif}[0,1]$ denotes a uniform distribution over
$[0,1]$. Clearly, the deterministic upper bound under prior estimate
$\hat{\mathcal{P}}$ takes a value of $\frac{3T}{4}$. Furthermore, we denote
$\mathbb{E}[h_{t}^{\pi}(r)]$ as the expectation of the decision variable under
the static policy $\pi$ when the reward of period $t$ is realized as $r$.
Then, we make following claim.
Claim: There exists a $\hat{r}\in[1-\frac{2W_{T}}{T},1-\frac{W_{T}}{T}]$ such
that $\sum_{t=1}^{3T/4}\mathbb{E}[h_{t}^{\pi}(\hat{r})]\leq T/4$.
Otherwise, suppose that for each $r\in[1-\frac{2W_{T}}{T},1-\frac{W_{T}}{T}]$,
we have $\sum_{t=1}^{3T/4}\mathbb{E}[h_{t}^{\pi}(r)]\geq T/4$. Then, we
compute the expected reward gained by the policy $\pi$ from
$r\in[1-\frac{2W_{T}}{T},1-\frac{W_{T}}{T}]$ during the first $3T/4$ periods,
where the budget will never be violated. To be specific, note that the event
$r\in[1-\frac{2W_{T}}{T},1-\frac{W_{T}}{T}]$ happens with probability
$\frac{W_{T}}{4T}$ at each period $t$. Comparing with $R_{T}^{UB}$, this will
cause a gap of at least $\frac{W_{T}}{T}$ for $\pi$ to collect a reward
$r\in[1-\frac{2W_{T}}{T},1-\frac{W_{T}}{T}]$. Thus, the gap of
$R^{\text{UB}}_{T}$ and $\pi$ on $\hat{\mathcal{P}}$, caused from $\pi$
obtaining reward from $r\in[1-\frac{2W_{T}}{T},1-\frac{W_{T}}{T}]$ during the
first $3T/4$ periods is at least

$\frac{W_{T}}{T}\cdot\frac{W_{T}}{4T}\cdot\frac{T}{4}=C_{1}\cdot T^{1/2}$

which violates the regret upper bound. Thus, the claim is proved.

Denote by $\hat{r}$ the value described in the claim. Now we construct a true
distribution $\mathcal{P}=\\{\mathcal{P}_{1},\dots,\mathcal{P}_{T}\\}$ as
follows:

$r_{t}=\left\\{\begin{aligned} &\hat{r},&\text{w.p.}~{}\frac{3}{4}\\\
&\text{Unif}[0,1],&\text{w.p.}~{}\frac{1}{4}\end{aligned}\right.$

Clearly, the deviation budget is upper bounded by $W_{T}$. Then, we compute
the total expected reward that policy $\pi$ can collect on the true
distribution $\mathcal{P}$. The expected reward collected by policy $\pi$
during the first $3T/4$ periods is at most

$\frac{1}{4}\cdot\frac{1}{2}\cdot\frac{3T}{4}+\frac{3}{4}\cdot\frac{T}{4}\cdot\hat{r}\leq\frac{9T}{32}$

where the first term in the LHS denotes the upper bound of the expected reward
collected from $\text{Unif}[0,1]$, and the second term in the LHS denotes the
upper bound of the expected reward collect from $\hat{r}$, which follows from
the claim. Finally, without considering the budget violation and we let $\pi$
to collect every reward during the last $T/4$ periods. The policy $\pi$ can
collect reward at most

$\frac{T}{4}\cdot(\frac{1}{2}\cdot\frac{1}{4}+\frac{3}{4})=\frac{7T}{32}$

during the last $T/4$ periods. Thus, the policy $\pi$ can collect at most
$T/2$ reward on the true distribution $\mathcal{P}$ during the entire horizon.
However, the value of $\mathbb{E}_{\mathcal{P}}[R^{\text{UB}}_{T}]$ is at
least
$\frac{3T}{4}\cdot\hat{r}\geq\frac{3T}{4}\cdot(1-\frac{2W_{T}}{T})\geq\frac{9T}{16}$,
when $W_{T}\leq\frac{T}{8}$ which clearly holds since $W_{T}$ grows
sublinearly in $T$. Thus, the regret of policy $\pi$ on the true distribution
$\mathcal{P}$ is at least $\frac{T}{16}$. ∎

####  D2.2 Discussion on Bid Price Policy

The well-known bid price policy (Talluri and Van Ryzin (1998)) computes a dual
optimal solution (bid price) $\hat{\bm{p}}^{*}$ based on the prior estimates.
Specifically, the policy makes the decision $\bm{x}_{t}$ at each period $t$
based on the fixed $\hat{\bm{p}}^{*}$ throughout the procedure:

$\bm{x}_{t}\in\text{argmax}_{\bm{x}\in\mathcal{X}}f(\bm{x},\bm{\theta}_{t})-(\hat{\bm{p}}^{*})^{\top}\cdot\bm{g}(\bm{x},\bm{\theta}_{t}).$

When there is no deviation between the true distributions and prior estimates,
i.e., $\mathcal{P}_{t}=\hat{\mathcal{P}}_{t}$ for each $t$, Talluri and Van
Ryzin (1998) show that bid price policy is asymptotically optimal if each
period is repeated sufficiently many times and the capacity is scaled up
accordingly. The following example shows that the bid price policy may fail
drastically even when the deviations between the true distributions and prior
estimates are small. The example follows the same spirit as the lower bound
examples in our paper.

Consider the following linear program as the underlying problem (PCP) for the
online stochastic optimization problem:

$\displaystyle\max\ \ $ $\displaystyle
x_{1}+...+x_{2c}+\frac{1}{2}x_{2c+1}+...+\frac{1}{2}x_{T}$ (44) s.t.
$\displaystyle x_{1}+...+x_{2c}+x_{2c+1}+...+x_{T}\leq c$ $\displaystyle 0\leq
x_{t}\leq 1\ \text{ for }t=1,...,T.$

where $c=\frac{T}{3}$ and without loss of generality, we assume $c$ is an
integer. Suppose that the prior estimates for the coefficients in the
objective function is larger than the true coefficients by $2\epsilon$ for the
first $\frac{T}{3}$ time periods and by $\epsilon$ for the last $\frac{2T}{3}$
time periods. Then we obtain the following linear program based on the prior
estimates.

$\displaystyle\max\ \ $
$\displaystyle(1+2\epsilon)x_{1}+...+(1+2\epsilon)x_{c}+(1+\epsilon)x_{c+1}+...+(1+\epsilon)x_{2c}+(\frac{1}{2}+\epsilon)x_{2c+1}+...+(\frac{1}{2}+\epsilon)x_{T}$
s.t. $\displaystyle x_{1}+...+x_{2c}+x_{2c+1}+...+x_{T}\leq c$ (45)
$\displaystyle 0\leq x_{t}\leq 1\ \text{ for }t=1,...,T.$

Obviously, the optimal dual solution for (45) can take any value in
$(1+\epsilon,1+2\epsilon)$. When we apply such a bid price policy to the true
problem (44), the policy will set $x_{t}=0$ throughout the horizon as the
reward per time period under the true problem (44) is no greater than 1. Given
the optimal objective value is $\frac{T}{3}$, the bid price policy will incur
a regret of $\frac{T}{3}$.

As a remark, we note that the regret bound for our algorithm
IGD($\hat{\gamma}$) is upper bounded by $2\epsilon T+\sqrt{T}$ which can be
much smaller than $\frac{T}{3}$ for small $\epsilon.$

###  D3 Proof of Theorem 7

The proof follows the same argument as that of the previous upper bounds in
Theorem 3 and Theorem 5. We prove the details for completeness.

###### Proof.

Proof: From the proof of Theorem 1, we have

$\displaystyle\sum_{t=1}^{T}f(\tilde{\bm{x}}_{t};\bm{\theta}_{t})-\sum_{t=1}^{T}f(\bm{x}_{t};\bm{\theta}_{t})\leq
q\cdot\sum_{i=1}^{m}\left[\sum_{t=1}^{T}g_{i}(\tilde{\bm{x}}_{t};\bm{\theta}_{t})-(c_{i}-1)\right]^{+}$

which relates the total collected reward by the true action
$\\{\bm{x}_{t}\\}_{t=1}^{T}$ and the virtual action
$\\{\tilde{\bm{x}}_{t}\\}_{t=1}^{T}$. Here $[\cdot]^{+}$ denotes the positive
part function. Furthermore, from Proposition 1, we have that

$\displaystyle\text{Reg}_{T}(\pi)\leq\min_{\bm{p}\geq\bm{0}}L(\bm{p})-\mathbb{E}\left[\sum_{t=1}^{T}f(\bm{x}_{t};\bm{\theta}_{t})\right]$
$\displaystyle\leq\underbrace{\min_{\bm{p}\geq\bm{0}}L(\bm{p})-\mathbb{E}\left[\sum_{t=1}^{T}f(\tilde{\bm{x}}_{t};\bm{\theta}_{t})\right]}_{\text{I}}$
$\displaystyle+\underbrace{q\cdot\mathbb{E}\left[\sum_{i=1}^{m}\left[\sum_{t=1}^{T}g_{i}(\tilde{\bm{x}}_{t};\bm{\theta}_{t})-(c_{i}-1)\right]^{+}\right]}_{\text{II}}$

where the function $L(\cdot)$ is given in (17). Next, we bound the term I and
term II separately to derive our regret bound.
Bound I: We first define the following function $\bar{L}(\cdot)$:

$\bar{L}(\bm{p})\coloneqq\frac{1}{T}\bm{p}^{\top}\bm{c}+\bar{\mathcal{P}}_{T}h(\bm{p};\bm{\theta}).$

Note that $\hat{\mathcal{P}}_{T}=\frac{1}{T}\sum_{t=1}^{T}\mathcal{P}_{t}$, it
holds that $L(\bm{p})=T\cdot\bar{L}(\bm{p})$ for any $\bm{p}$. From Lemma 2,
we know that for each $t$, $\|\bm{p}_{t}\|_{\infty}\leq q+1$ with probability
$1$. In addition, for each $t$, the distribution of $\bm{p}_{t}$ is
independent from the distribution of $\bm{\theta}_{t}$, then from Lemma 3, we
have that

$\min_{\bm{p}\geq\bm{0}}\bar{L}(\bm{p})\leq\mathbb{E}_{\bm{p}_{t}}\left[\bar{L}(\bm{p}_{t})\right]\leq\mathbb{E}_{\bm{p}_{t}}\left[\frac{1}{T}\bm{p}_{t}^{\top}\bm{c}+\mathcal{P}_{t}h(\bm{p}_{t};\bm{\theta}_{t})\right]+(q+1)(m+1)\cdot\mathcal{W}(\mathcal{P}_{t},\bar{\mathcal{P}}_{T}),$
(46)

where the expectation is taken with respect to $\bm{p}_{t}$ in a random
realization of the algorithm. Thus, we have the first term

$\text{I}\leq\sum_{t=1}^{T}\mathbb{E}_{\bm{p}_{t}}\left[\frac{1}{T}\bm{c}^{\top}\bm{p}_{t}+\mathcal{P}_{t}\left\\{h(\bm{p}_{t};\bm{\theta}_{t})-\hat{f}(\tilde{\bm{x}}_{t};\bm{\theta}_{t})\right\\}\right]+(q+1)(m+1)\cdot\mathcal{W}(\mathcal{P}_{t},\bar{\mathcal{P}}_{T})$

which comes from first taking expectation over
$f(\tilde{\bm{x}}_{t};\bm{\theta}_{t})$ for given
$\tilde{\bm{x}}_{t},\bm{\theta}_{t}$, and then combining (46) with the
relation $L(\bm{p})=T\cdot\bar{L}(\bm{p})$. By the definition of
$\tilde{\bm{x}}_{t}$,
$h(\bm{p}_{t};\bm{\theta}_{t})-\hat{f}(\tilde{\bm{x}}_{t};\bm{\theta}_{t})=-\bm{p}_{t}^{\top}\cdot\hat{\bm{g}}(\tilde{\bm{x}}_{t};\bm{\theta}_{t})$,
which implies that

$\text{I}\leq\sum_{t=1}^{T}\mathbb{E}_{\bm{p}_{t}}\left[\bm{p}_{t}^{\top}\cdot\left(\frac{\bm{c}}{T}-\mathcal{P}_{t}\hat{\bm{g}}(\tilde{\bm{x}}_{t};\bm{\theta}_{t})\right)\right]+(q+1)(m+1)\cdot\mathcal{W}(\mathcal{P}_{t},\bar{\mathcal{P}}_{T})$
(47)

Note that from the update rule (15), we have that

$\|\bm{p}_{t+1}\|_{2}^{2}\leq\|\bm{p}_{t}\|_{2}^{2}+\frac{1}{T}\cdot\|\bm{g}(\tilde{\bm{x}}_{t};\bm{\theta}_{t})-\frac{\bm{c}}{T}\|_{2}^{2}-\frac{2}{\sqrt{T}}\cdot\bm{p}_{t}^{\top}\cdot\left(\frac{\bm{c}}{T}-\bm{g}(\tilde{\bm{x}}_{t};\bm{\theta}_{t})\right).$

By taking expectation with respect to both sides,

$\mathbb{E}_{\bm{p}_{t}}\left[\bm{p}_{t}^{\top}\cdot\left(\frac{\bm{c}}{T}-\mathcal{P}_{t}\hat{\bm{g}}(\tilde{\bm{x}}_{t};\bm{\theta}_{t})\right)\right]\leq\frac{\sqrt{T}}{2}\cdot\left(\mathbb{E}[\|\bm{p}_{t}\|_{2}^{2}]-\mathbb{E}[\|\bm{p}_{t+1}\|_{2}^{2}]\right)+\frac{m}{2\sqrt{T}}$
(48)

Plugging (48) into (47), we obtain an upper bound on Term I,

$\text{I}\leq\frac{m\sqrt{T}}{2}+(q+1)(m+1)\cdot W_{T}$ (49)

Bound II: Note that from the update rule (15), we have

$\sqrt{T}\cdot\bm{p}_{t+1}\geq\sqrt{T}\cdot\bm{p}_{t}+\bm{g}(\tilde{\bm{x}}_{t};\bm{\theta}_{t})-\frac{\bm{c}}{T}$

Taking a summation with respect to both sides,

$\sum_{t=1}^{T}\bm{g}(\tilde{\bm{x}}_{t};\bm{\theta}_{t})-\bm{c}\leq\sqrt{T}\cdot\bm{p}_{T+1}$

Applying Lemma 2 for a bound on $\bm{p}_{T+1},$ we obtain the upper bound for
Term II,

$\text{II}=q\cdot\mathbb{E}\left[\sum_{i=1}^{m}\left[\sum_{t=1}^{T}g_{i}(\tilde{\bm{x}}_{t};\bm{\theta}_{t})-(c_{i}-1)\right]^{+}\right]\leq
mq(q+1)\cdot\sqrt{T}+qm$ (50)

We obtain the desired regret bound by combining (49) and (50). ∎

###  D4 Proof of Theorem 8

The proof follows the same argument as that of the previous upper bounds in
Theorem 3 and Theorem 5. We prove the details for completeness.

We first prove the following lemma, which implies that the dual variable
updated in (21) is always bounded. The analysis is similar to that of Lemma 2.

###### Lemma 7

Under Assumption 1, for each $l=1,2,\dots,\lfloor T/K\rfloor$, the dual price
vector satisfies $\|\bm{p}_{l}\|_{\infty}\leq q+\alpha_{T,K}\cdot K$, where
$\bm{p}_{l}$ is specified by (21) in Algorithm 4 and the constant $q$ is
defined in Assumption 1 (c).

###### Proof.

Proof: Note that the following two properties are satisfied by the update rule
(21):

  * (i).

If $\|\bm{p}_{l}\|_{\infty}\leq q$, then we must have
$\|\bm{p}_{l+1}\|_{\infty}\leq q+\alpha_{T,K}\cdot K$ by noting that for each
$i$, the $i$-th component of $\bm{p}_{l}$, denoted as $p_{l,i}$, is
nonnegative and $g_{i}(\cdot,\bm{\theta}_{t})$ is normalized within $[0,1]$
for each $t=(l-1)K+1,\dots,lK$.

  * (ii).

If there exists $i$ such that $p_{l,i}>q$, then we must have
$p_{l+1,i}<p_{l,i}$. Specifically, when $p_{l,i}>q$, we must have that
$g_{i}(\tilde{\bm{x}}_{t};\bm{\theta}_{t})=0$ for each $t=(l-1)K+1,\dots,lK$,
otherwise, we would have that

$f(\tilde{\bm{x}}_{t};\bm{\theta}_{t})-\bm{p}_{l}^{\top}\cdot\bm{g}(\tilde{\bm{x}}_{t};\bm{\theta}_{t})\leq
f(\tilde{\bm{x}}_{t};\bm{\theta}_{t})-p_{l,i}\cdot
g_{i}(\tilde{\bm{x}}_{t};\bm{\theta}_{t})<0$

which contradicts the definition of $\tilde{\bm{x}}_{t}$ in Algorithm 4 since
we could always select $\bm{x}_{t}=\bm{0}$ to obtain a zero objective value as
per Assumption 1. Then from (21), it holds that $p_{l+1,i}<p_{l,i}$.

Starting from $\bm{p}_{1}=\bm{0}$ and iteratively applying the above two
property to control the increase of $\bm{p}_{l}$ from $l=1$ to $\lfloor
T/K\rfloor$, we obtain that for the first time that one component of
$\bm{p}_{l}$ exceeds the threshold $q$, it is upper bounded by
$q+\alpha_{T,K}\cdot K$ and this component will continue to decrease until it
falls below the threshold $q$. Thus, it is obvious that we have
$\|\bm{p}_{l}\|_{\infty}\leq q+\alpha_{T,K}\cdot K$ with probability $1$ for
each $l$. ∎

Now we proceed to prove Theorem 8.

###### Proof.

Proof: From the proof of Theorem 1, we have

$\displaystyle\text{Reg}_{T}(\pi)\leq\underbrace{\sum_{t=1}^{T}\min_{\bm{p}\geq
0}L_{t}(\bm{p})-\mathbb{E}\left[\sum_{t=1}^{T}f(\tilde{\bm{x}}_{t};\bm{\theta}_{t})\right]}_{\text{I}}+\underbrace{q\cdot\mathbb{E}\left[\sum_{i=1}^{m}\left[\sum_{t=1}^{T}g_{i}(\tilde{\bm{x}}_{t};\bm{\theta}_{t})-(c_{i}-1)\right]^{+}\right]}_{\text{II}}$

We then bound the term I and term II separately to derive our regret bound.
Bound I: Note that for each $t$, the distribution of $\bm{p}_{l}$ is
independent from the distribution of $\bm{\theta}_{t}$ for any
$t=(l-1)K+1,\dots,lK$, then we have that

$\min_{\bm{p}\geq\bm{0}}L_{t}(\bm{p})\leq\mathbb{E}_{\bm{p}_{l}}\left[L_{t}(\bm{p}_{l})\right]=\mathbb{E}_{\bm{p}_{l}}\left[\bm{\gamma}_{t}^{\top}\bm{p}_{l}+\mathcal{P}_{t}h(\bm{p}_{l};\bm{\theta}_{t})\right]$

where the expectation is taken with respect to the randomness of the dual
price $\bm{p}_{t}.$ Thus, we have

$\text{I}\leq\sum_{l=1}^{\lfloor T/K\rfloor}\sum_{t=(l-1)K+1}^{lK\wedge
T}\mathbb{E}_{\bm{p}_{l}}\left[\bm{\gamma}_{t}^{\top}\bm{p}_{l}+\mathcal{P}_{t}\left\\{h(\bm{p}_{l};\bm{\theta}_{t})-f(\tilde{\bm{x}}_{t};\bm{\theta}_{t})\right\\}\right]$

From the definition of $\tilde{\bm{x}}_{t}$, we get that
$h(\bm{p}_{t};\bm{\theta}_{t})-f(\tilde{\bm{x}}_{t};\bm{\theta}_{t})=-\bm{p}_{l}^{\top}\cdot\bm{g}(\tilde{\bm{x}}_{t};\bm{\theta}_{t})$
for $t=(l-1)K+1,\dots,lK$, which implies that

$\text{I}\leq\sum_{l=1}^{\lfloor T/K\rfloor}\sum_{t=(l-1)K+1}^{lK\wedge
T}\mathbb{E}_{\bm{p}_{l}}\left[\bm{p}_{l}^{\top}\cdot\left(\bm{\gamma}_{t}-\mathcal{P}_{t}\bm{g}(\tilde{\bm{x}}_{t};\bm{\theta}_{t})\right)\right]$

Note that from the update rule (21), we have that

$\|\bm{p}_{l+1}\|_{2}^{2}\leq\|\bm{p}_{l}\|_{2}^{2}+\alpha_{T,K}^{2}\cdot\|\sum_{t=(l-1)K+1}^{lK}\bm{g}(\tilde{\bm{x}}_{t};\bm{\theta}_{t})-\bm{\gamma}_{t}\|_{2}^{2}-2\alpha_{T,K}\cdot\sum_{t=(l-1)K+1}^{lK\wedge
T}\bm{p}_{t}^{\top}\cdot\left(\bm{\gamma}_{t}-\bm{g}(\tilde{\bm{x}}_{t};\bm{\theta}_{t})\right)$

which implies that

$\sum_{t=(l-1)K+1}^{lK\wedge
T}\mathbb{E}_{\bm{p}_{l}}\left[\bm{p}_{l}^{\top}\cdot\left(\bm{\gamma}_{t}-\mathcal{P}_{t}\bm{g}(\tilde{\bm{x}}_{t};\bm{\theta}_{t})\right)\right]\leq\frac{1}{2\alpha_{T,K}}\cdot\left(\mathbb{E}[\|\bm{p}_{l}\|_{2}^{2}]-\mathbb{E}[\|\bm{p}_{l+1}\|_{2}^{2}]\right)+\frac{mK^{2}\cdot\alpha_{T,K}}{2}$

Thus, it holds that

$\text{I}\leq\frac{mTK\cdot\alpha_{T,K}}{2}$ (51)

Bound II: Note that from the update rule (21), we have that

$\frac{1}{\alpha_{T,K}}\cdot\bm{p}_{l+1}\geq\frac{1}{\alpha_{T,K}}\cdot\bm{p}_{l}+\sum_{t=(l-1)K+1}^{lK}(\bm{g}(\tilde{\bm{x}}_{t};\bm{\theta}_{t})-\bm{\gamma}_{t})$

which implies that

$\sum_{t=1}^{T}\bm{g}(\tilde{\bm{x}}_{t};\bm{\theta}_{t})-\bm{c}\leq\sum_{l=1}^{\lfloor
T/K\rfloor}\sum_{t=(l-1)K+1}^{lK\wedge
T}(\bm{g}(\tilde{\bm{x}}_{t};\bm{\theta}_{t})-\bm{\gamma}_{t})\leq\frac{1}{\alpha_{T,K}}\cdot\bm{p}_{\lfloor
T/K\rfloor+1}$

Thus, it holds that

$\text{II}=q\cdot\mathbb{E}\left[\sum_{i=1}^{m}\left[\sum_{t=1}^{T}g_{i}(\tilde{\bm{x}}_{t};\bm{\theta}_{t})-(c_{i}-1)\right]^{+}\right]\leq
mq(q+\alpha_{T,K}\cdot K)\cdot\frac{1}{\alpha_{T,K}}+qm$ (52)

We obtain the $O(TK\alpha_{T,K}+\frac{1}{\alpha_{T,K}}+K)$ regret bound
immediately by combining (51) and (52). ∎

##  12 More Numerical Results for Experiment I

| $\alpha=1$ | $\alpha=1.5$ | $\alpha=2$ | $\alpha=2.5$ | $\alpha=3$
---|---|---|---|---|---
Upper Bound | $282.5433$ | $363.7044$ | $459.7807$ | $563.3545$ | $670.5960$
$\beta=0$ | IGDP |  $270.2411$ (96%) |  $349.1769$ (96%) |  $441.6677$ (96%) |  $543.3373$ (96%) |  $645.6582$ (96%)
UGD | $270.3621(96\%)$ |  $337.3192$ (93%) |  $403.7044$ (88%) |  $469.7643$ (83%) |  $535.0654$ (80%)
FBP |  $270.1211$ (96%) |  $347.4997$ (96%) |  $439.7016$ (96%) |  $539.9865$ (96%) |  $642.3940$ (96%)
O2O | 270.6872 (96%) | 351.2534 (96%) | 440.9020 (96%) | 545.2106 (96%) | 644.4059 (96%)
$\beta=0.5$ | IGDP |  $270.1595$ (96%) |  $347.9148$ (96%) |  $439.6166$ (96%) |  $539.8719$ (96%) |  $643.6777$ (96%)
UGD |  $270.3568$ (96%) |  $338.6916$ (93%) |  $405.7927$ (88%) |  $473.6640$ (84%) |  $540.0894$ (81%)
FBP |  $64.7526$ (23%) |  $174.2642$ (48%) |  $314.7806$ (68%) |  $446.7646$ (79%) |  $582.7744$ (87%)
O2O | 202.3966 (72%) | 289.6858 (80%) | 423.5247 (92%) | 536.0362 (95%) | 621.4144 (93%)
$\beta=1$ | IGDP |  $269.8058$(95%) |  $347.1246$ (95%) |  $437.6279$ (95%) |  $535.3521$ (95%) |  $638.8322$ (95%)
UGD |  $269.6893$ (95%) |  $339.1676$ (93%) |  $408.3862$ (89%) |  $477.2329$ (84%) |  $544.9401$ (81%)
FBP |  $4.8549$ (2%) |  $53.7881$ (15%) |  $188.3271$ (41%) |  $340.850$ (61%) |  $486.4006$ (73%)
O2O | 202.6792 (72%) | 202.9555 (56%) | 330.5638 (72%) | 480.2536 (85%) | 620.2584 (92%)
$\beta=2$ | IGDP |  $265.1512$ (94%) |  $343.7802$ (95%) |  $432.2275$ (94%) |  $527.4351$ (94%) |  $627.7440$ (94%)
UGD |  $265.4187$ (94%) |  $337.4751$ (93%) |  $410.3510$ (89%) |  $482.8652$ (86%) |  $554.0038$ (83%)
FBP |  $0.0171$ (0%) |  $1.6210$ (0.5%) |  $22.5201$ (5%) |  $104.5026$ (19%) |  $243.1575$ (36%)
O2O | 203.5851 (72%) | 206.4316 (57%) | 210.6264 (46%) | 361.1129 (64%) | 514.6730 (77%)
Table 3: Computation results for Experiment I under the uniform setting: The
results are reported based on $500$ simulation trials. For each entry b(c) of
the table, b denotes the expected reward collected by the algorithm and c
denotes the percentage of the expected reward of the algorithm over the upper
bound.

| $\alpha=1$ | $\alpha=1.5$ | $\alpha=2$ | $\alpha=2.5$ | $\alpha=3$
---|---|---|---|---|---
Upper Bound | 705.1450 | 803.5559 | 921.6550 | 1060.5567 | 1213.3552
$\beta=0$ | IGDP | 679.9687 (96%) | 771.9511 (96%) | 884.2661 (96%) | 1022.9439 (96%) | 1171.1208 (97%)
UGD | 681.1875 (97%) | 764.6037 (95%) | 840.5685 (91%) | 928.6610 (88%) | 1018.0635 (84%)
FBP | 674.968 (96%) | 768.0327 (96%) | 883.1946 (96%) | 1013.5706 (96%) | 1165.1827 (96%)
O2O | 676.3823 (96%) | 769.396 (96%) | 882.5831 (96%) | 1017.4399 (96%) | 1159.9922(96%)
$\beta=0.5$ | IGDP | 680.4068 (97%) | 773.4652 (96%) | 890.2161 (96%) | 1023.3161 (97%) | 1170.2227 (96%)
UGD | 680.931 (97%) | 765.1636 (95%) | 851.4681 (92%) | 934.5877 (88%) | 1028.4509 (85%)
FBP | 459.16 (65%) | 525.5739 (66%) | 619.198 (67%) | 751.7758 (71%) | 907.9537 (75%)
O2O | 656.6648 (93%) | 712.215 (89%) | 784.1766 (85%) | 873.1237(82%) | 996.943 (82%)
$\beta=1$ | IGDP | 680.5808 (97%) | 777.7524 (97%) | 888.5206 (96%) | 1024.4519 (97%) | 1175.2438 (97%)
UGD | 681.824 (97%) | 766.3631 (95%) | 851.6300 (92%) | 944.0707 (89%) | 1035.5280 (85%)
FBP | 254.2547 (36%) | 296.1898 (37%) | 375.3518 (41%) | 476.4165 (45%) | 610.2982 (50%)
O2O | 588.1039 (83%) | 744.5618 (93%) | 833.9981 (90%) | 916.2876 (86%) | 1009.1384 (83%)
$\beta=2$ | IGDP | 666.6237 (94%) | 764.0318 (95%) | 873.8978 (95%) | 1014.7539 (96%) | 1160.7693 (96%)
UGD | 667.4160 (95%) | 756.7188 (94%) | 851.0122 (92%) | 944.1322 (89%) | 1046.7647 (86%)
FBP | 51.9166 (7%) | 68.2078(8%) | 100.4066 (11%) | 148.1866 (14%) | 212.5127 (18%)
O2O | 466.4348 (66%) | 535.7102 (67%) | 728.6945 (79%) | 957.5749 (90%) | 1072.6659(88%)
Table 4: Computation results for Experiment I under the normal setting: The
results are reported based on $500$ simulation trials. For each entry b(c) of
the table, b denotes the expected reward collected by the algorithm and c
denotes the percentage of the expected reward of the algorithm over the upper
bound.

| $\alpha=1$ | $\alpha=1.5$ | $\alpha=2$ | $\alpha=2.5$ | $\alpha=3$
---|---|---|---|---|---
Upper Bound | 532.6379 | 630.1063 | 746.5027 | 871.63281 | 1010.7956
$\beta=0$ | IGDP | 513.2625 (96%) | 609.6643 (97%) | 717.3434 (96%) | 840.7550 (96%) | 973.4778 (96%)
UGD | 513.9690 (97%) | 592.9739 (94%) | 672.7648 (90%) | 758.0174 (87%) | 840.9000 (83%)
FBP | 511.9639 (96%) | 601.4187 (95%) | 714.4849 (96%) | 831.7872 (95%) | 964.0174 (95%)
O2O | 512.9872 (96%) | 603.5403 (96%) | 713.4253 (96%) | 834.2972 (96%) | 970.8423 (96%)
$\beta=0.5$ | IGDP | 517.2177 (97%) | 607.7310 (96%) | 714.3025 (96%) | 843.8988 (97%) | 975.2676 (97%)
UGD | 514.1228 (96%) | 596.0002 (95%) | 678.3624 (91%) | 762.7194 (87%) | 844.0139 (84%)
FBP | 372.5857 (70%) | 441.8714 (70%) | 542.3811 (73%) | 667.7373 (77%) | 821.8302 (82%)
O2O | 478.3224 (90%) | 600.7489 (95%) | 681.4778 (91%) | 774.0669 (89%) | 881.9813 (87%)
$\beta=1$ | IGDP | 517.8502 (97%) | 609.3739 (97%) | 717.3040 (96%) | 842.7028 (97%) | 977.9344 (97%)
UGD | 515.1376 (97%) | 598.2675 (95%) | 683.0459 (92%) | 769.4935 (88%) | 853.1061 (85%)
FBP | 253.2191 (47%) | 295.4627 (47%) | 372.9051 (50%) | 469.2851 (54%) | 613.1751 (61%)
O2O | 391.8374 (73%) | 509.6126 (81%) | 674.1803 (90%) | 813.8023 (93%) | 912.8408 (91%)
$\beta=2$ | IGDP | 507.9654 (95%) | 598.2148 (95%) | 713.2802 (96%) | 835.5463 (96%) | 963.8020 (95%)
UGD | 505.8237 (95%) | 591.2771 (94%) | 684.4290 (92%) | 770.5260 (88%) | 866.7157 (86%)
FBP | 78.3954 (15%) | 96.3983 (15%) | 136.5682 (18%) | 197.7166 (23%) | 281.8724 (28%)
O2O | 343.4216 (64%) | 358.0907 (57%) | 494.0880 (66%) | 686.6650 (79%) | 890.9912 (88%)
Table 5: Computation results for Experiment I under the mixed setting: The
results are reported based on $500$ simulation trials. For each entry b(c) of
the table, b denotes the expected reward collected by the algorithm and c
denotes the percentage of the expected reward of the algorithm over the upper
bound.