No-Regret Learning for Stackelberg Equilibrium Computation in Newsvendor Pricing Games

Our study integrates established economic theory with online learning theory within a practical game theoretic framework. Specifically, we employ a linear contextual bandit algorithm within a Stackelberg game to address a well-defined economic scenario. The primary technical challenge lies in optimizing for both contextual and Stackelberg regret, particularly when facing stochastic environmental parameters, as well as uncertainty in agent strategies. Incorporating economic theory into online learning theory is inherently challenging due to the unique characteristics of reward functions and best response functions, as expounded in Section 2.4.3. In some cases, closed-form solutions are unattainable, requiring innovative approaches for optimization and bounding functions, as expounded in Section 3.5, in order to derive theoretical worst-case bounds on regret.

To summarize, we provide technical contributions in the following areas:

1. 1.

   We prove the existence of a unique Stackelberg equilibrium under perfect information for a general sum game within a Newsvendor pricing game (described in Section 2.4).

2. 2.

   An online learning algorithm for the Newsvendor pricing game, leveraging stochastic linear contextual bandits, is outlined, which is integrated with established economic theory.

3. 3.

   The convergence properties of an online learning algorithm to approximate Stackelberg equilibrium, as well theoretical guarantees for bounds on finite-time regret, are provided.

4. 4.

   We demonstrate our theoretical results via economic simulations, to show that our learning algorithm outperforms baseline algorithms in terms of finite-time cumulative regret.

In a repeated Stackelberg game, the leader takes actions $\mathbf{a}\in\mathcal{A}$, and the follower takes actions $\mathbf{b}\in\mathcal{B}$ in reaction to the leader. The joint action is represented as $(\mathbf{a}^{t},\mathbf{b}^{t})$ for each time step $t$ from $1$ to $T$. The joint utility (reward) functions for the leader and follower are denoted as $\mathcal{G}_{A}(\mathbf{a}^{t},\mathbf{b}^{t})$ and $\mathcal{G}_{B}(\mathbf{a}^{t},\mathbf{b}^{t})$, respectively. From an economic standpoint, the application of pure strategies aligns with the prevalent strategic behaviours observed in many firms, emphasizing practicality and realism [PS80] [Tir88].

Strategy Definition: Let $\pi_{A}$ and $\pi_{B}$ denote the pure strategies of both agents represented as standard maps,

The strategy of the leader at time $t$ is denoted by $\pi_{A}(t)$, which maps from the filtration $\mathcal{F}_{t}$ to the set of possible actions $\mathcal{A}$. Where the filtration $\mathcal{F}_{t}$ consists of all possible $\sigma$-algebras of observations up until time $t$, i.e., $\mathcal{F}_{t}\equiv\{(\mathbf{a}^{1},\mathbf{b}^{1}),\ldots,(\mathbf{a}^{t},\mathbf{b}^{t})\}$. To clarify, $t$ belongs to the set of integers $\mathbb{Z}$ such that $1\leq t\leq T$, where $T$ is a fixed finite-time endpoint. The action taken by the leader at time $t$, denoted as $\mathbf{a}^{t}\in\mathcal{A}$, is determined by the leader’s strategy $\pi_{A}(t)$, which depends on the observed actions up to time $t$. Therefore, $\pi_{A}$ is a morphism from the set of filtrations to the set of actions in discrete time, $\pi_{A}:\{\mathcal{F}_{1},\ldots,\mathcal{F}_{T}\}\mapsto\{\mathbf{a}^{1},\ldots,\mathbf{a}^{T}\}$. On the other hand, the strategy of the follower is formulated as a response to the leader’s action; therefore, it is a morphism, $\pi_{B}:\{\mathbf{a}^{1},\dots,\mathbf{a}^{T}\}\mapsto\{\pi_{B}(\mathbf{a}^{1}),\dots,\pi_{B}(\mathbf{a}^{T})\}$.

Best Response Function: To be specific, $\mathcal{G}_{B}(\mathbf{a}^{t},\mathbf{b}^{t})$ is expressed as a parametric function with exogenous sub-Gaussian noise (the exact parametric form for $\mathcal{G}_{B}(\mathbf{a}^{t},\mathbf{b}^{t})$ is provided in Eq. (2.14)). Conversely, for the leader, $\mathcal{G}_{A}(\mathbf{a}^{t},\mathbf{b}^{t})$ is a deterministic function solely driven by the direct action of the leader $\mathbf{a}^{t}$ followed by the reaction of the follower $\mathbf{b}^{t}$. At each discrete time interval, the best response of the follower, $\mathfrak{B}(\mathbf{a}^{t})$, is defined as follows:

Eq. (2.2) makes the assumption that there exists a unique best response to $\mathbf{a}^{t}$. We demonstrate the uniqueness of $\mathfrak{B}(\mathbf{a}^{t})$ later in Theorem 1. $\mathfrak{B}(\mathbf{a})$ is the best response function of $\mathbf{b}$ to $\mathbf{a}$, as defined in Equation (2.2) under perfect information. Given $\mathfrak{B}(\mathbf{a})$ is unique, the objective for the leader is to maximize her reward based on the expectation of the follower’s best response. In a Stackelberg game, the leader takes actions, from time $\{\mathbf{a}^{1},\dots,\mathbf{a}^{T}\}$, and receives rewards $\{\mathcal{G}_{A}(\mathbf{a}^{1},\pi_{B}(\mathbf{a}^{1})),\dots,\mathcal{G}_{A}(\mathbf{a}^{T},\pi_{B}(\mathbf{a}^{T}))\}$, as the follower is always reacting to the leader with his perfect or approximate best response, he receives rewards $\{\mathcal{G}_{B}(\mathbf{a}^{1},\pi_{B}(\mathbf{a}^{1})),\dots,\mathcal{G}_{B}(\mathbf{a}^{T},\pi_{B}(\mathbf{a}^{T}))\}$. We shall use the notation $(\pi_{A},\pi_{B})$ to represent the joint strategy of both players.

Contextual Regret (Follower): In the bandit setting with no state transitions, the leader’s strategy $\pi_{A}$ represents a sequence consisting of actions, or contexts, $\mathbf{a}^{t}$, $\forall t\in\{1,\dots,T\}$ for the follower. The contextual regret is defined as,

Contextual regret, defined as $R_{B}^{T}(\cdot)$ in Eq. (2.3), is the difference between cumulative follower rewards from the best-responding follower and any other strategy adhered to by the follower in response to a series of actions form the leader, $\{\mathbf{a}^{1},\dots,\mathbf{a}^{T}\}$. Given context $\mathbf{a}^{t}$ and environmental parameters $\theta$, the follower attempts to maximize his rewards via some no-regret learner (we choose an optimistic stochastic linear contextual bandit algorithm as outlined in Section 3). $\mathbbm{E}_{\theta}[\mathcal{G}_{B}(\cdot)]$ indicates that expectation over uncertainty is with respect to the stochastic demand environment, governed by parameter $\theta$.

Stackelberg Regret (Leader): The Stackelberg regret, defined as $R_{A}^{T}(\cdot)$ for the leader, is the difference in cumulative rewards when players optimize their strategies in hindsight, versus via any joint strategy $(\pi_{A},\pi_{B})$. Stackelberg regret, also known as the external regret [Hag+22] [Zha+23] is defined from the leader’s perspective in Eq. (2.4) as the cumulative difference in leader’s rewards between the maximization of $\mathcal{G}_{A}(\cdot)$ under a best responding follower, versus any other joint strategy adhered to by both agents. This definition assumes that the rational leader must commit to a strategy $\pi_{A}$ at the beginning of the game, which she believes is optimal on expectation. The leader maximizes their reward taking into account their anticipated uncertainty of the follower’s response $\mathbf{b}^{t}$. When computing the expectation of $\mathcal{G}_{A}(\cdot)$, the randomness of $\mathcal{G}_{A}(\cdot)$ is fully strategic, that is, it arises from the follower’s action according to the strategy $\mathbf{b}^{t}\sim\pi_{B}$. Our algorithm seeks to minimize the Stackelberg regret, constituting a no-regret learner from the leader’s perspective.

For convenience of notation, moving forward, we will establish the equivalences for $\mathbbm{E}_{\pi_{B}}[\mathcal{G}_{A}(\cdot)]\equiv\mathbbm{E}[\mathcal{G}_{A}(\cdot)]$ and $\mathbbm{E}_{\theta}[\mathcal{G}_{B}(\cdot)]\equiv\mathbbm{E}[\mathcal{G}_{B}(\cdot)]$.

We classify game theoretic learning as consisting of two key aspects. The first is the learning of the opposing player’s strategy. In particular, the strategy of the follower can be optimal, in the case of an omniscient follower, or $\epsilon$-optimal [CLP19] [Bal+15] [Gan+23], in the case of an imperfect best response stemming from hindered information sharing or suboptimal follower policies. In this setting, the parameters of the reward function $\theta^{*}$ are known, and the players are learning an approximate or perfect equilibrium strategy. Notably, [Bal+15] demonstrated that there always exists an algorithm that will produce a worst case leader regret bound of $\mathcal{O}(\log{(T)})$. In another example, [CLP19] presents a method where polytopes constructed within the joint action space of the players can be adaptively partitioned to produce a learning algorithm achieving sublinear regret under perfect information, demonstrated in a spam classification setting.

The second aspect of online learning in SG’s pertains to the learning of the parameters of the joint reward function $\theta^{*}$ which corresponds to $\mathcal{G}_{B}(\cdot)$ and influences $\mathcal{G}_{A}(\cdot)$. In this environment, $\theta^{*}$ is unknown or only partially known, and must be learned over time in a bandit setting. Several approaches address this problem setting. For example, a worst case regret bound of $\mathcal{O}(\hat{\epsilon}T+\sqrt{N(\hat{\epsilon})T})$ was proven in [Zha+23], where the authors use a $\hat{\epsilon}$-covering method to achieve the bound on regret. Where $N(\hat{\epsilon})$ is the $\hat{\epsilon}$-covering over the joint action space. [Hag+22] produce a worst-case regret bound of $\mathcal{O}(\log(T)+T_{\gamma}\log^{2}{(T_{\gamma})})$ by leveraging batched binary search in a demand learning problem setting. Furthermore, they investigate the problem of a non-myopic follower, where the anticipation of future rewards ameliorated by a discount factor $\gamma$, induces the follower to suboptimally best respond. $T_{\gamma}=1/(1-\gamma)$ represents a parameter proportional to the delay in the revelation of the follower’s actions by a third party. Under this mechanism, the regret is proportional to both $T$ as well as $\gamma$, where for very small values of $\gamma$ (close to non-discounting), the $T_{\gamma}$ could potentially dominate the regret. [FKM04] provide a bound for a convex joint reward function using approximate gradient descent, where $P(T)$ represents a polynomial function with respect to $T$. Note that in the partial information setting, the bound on worst-case leader regret is typically superlinear.

The Stackelberg Equilibrium of this game is defined as any joint strategy which,

Where $\mathfrak{B}(\mathbf{a})$ is the best response of the follower, as defined in Eq. (2.2). Let $\Delta_{B}$ denote a probability simplex over possible strategies $\pi_{B}$, thus the expectation on $\mathbbm{E}_{\pi_{B}}[\cdot]$ is with respect to $\pi_{B}$. From the follower’s perspective, suppose he adopts an approximate best response strategy $\hat{\pi}_{B}\equiv\hat{\pi}_{B}(\mathbf{a})$. This implies that there exists some $\epsilon_{B}\geq 0$, such that,

This formalization allows for an $\epsilon$ deviation, potentially making the problem computationally tractable, particularly when optimization over certain functions lacks simple closed-form solutions or is computationally intensive (as we explore in detail in Section 2.4.3). It’s worth noting that the expectation for the leader reflects uncertainty about the follower’s strategy, while the expectation for the follower relates to the randomness of the environment. Acknowledging the presence of the error of best response function resulting from the possibility of the follower to act imperfectly, or strategically with purpose influence the leader’s strategy, we propose an $\epsilon$-approximate equilibrium with full support, [Rou10] [DGP09].

Upper-Bounding Approximation Function: Let $\mathcal{U}_{B}(\mathbf{a},\mathbf{b})$ represent a Lipschitz function, $\mathcal{U}_{B}:\mathbf{a}\times\mathbf{b}\to\mathbb{R}^{+}$ such that it is consistently greater than or equal to $\mathbbm{E}[\mathcal{G}_{B}(\mathbf{a},\mathbf{b})]$. The selection of this upper-bounding function is appropriate within our problem framework for two key reasons. Firstly, it leverages on established theory on economic pricing, allowing us to derive a rational best response for the follower (see Section 2.4.3). Secondly, its adoption aligns with our implementation of an optimistic bandit algorithm, ensuring an inherent tendency to overestimate reward potential in the face of uncertainty.

Therefore, we define the approximate follower best response as,

In accordance with Eq. (2.7), we note that the follower reward utilizing the approximate best response is less than that of the optimal best response as a consequence, where $\mathop{\mathbb{E}}[\mathcal{G}_{B}(a,\widetilde{\mathfrak{B}}(a))]\leq\mathop{\mathbb{E}}[\mathcal{G}_{B}(a,\mathfrak{B}(a))]$. Furthermore, in our problem definition, the follower approximates his best response with $\widetilde{\mathfrak{B}}(\mathbf{a})$ such that, across its domain of $\mathbb{E}[\mathcal{G}_{B}(\cdot)]$, the image of the approximating function, $\mathcal{U}(\cdot)$, is greater or equal than the image of $\mathop{\mathbb{E}}[\mathcal{G}_{B}(\cdot)$]. The motivation behind this is that, $\mathcal{U}(\cdot)$ can represent a simple parametric function with a known analytical solution, whereas $\mathop{\mathbb{E}}[\mathcal{G}_{B}(\cdot)]$ could represent an more elaborate function, with no known exact analytical solution. Therefore it is possible that, $\mathcal{U}(\cdot)$ and $\mathbb{E}[\mathcal{G}_{B}(\cdot)]$ may not necessarily belong to the same parametric family, nor adhere to the same functional form.

Approximate SE: As a consequence, we can therefore infer that there exists some additive $\epsilon_{B}\geq 0$ which upper-bounds this approximation error in the image of $\mathbb{E}[\mathcal{G}_{B}(\cdot)]$. We define an approximate $\epsilon$-Stackelberg equilibrium with $\epsilon_{B}$ approximation error the follower’s perspective as follows,

Effectively, $\epsilon_{B}$ defines an upper bound of the range on where $\mathop{\mathbb{E}}[\mathcal{G}_{B}(\mathbf{a},\mathfrak{B}(\mathbf{a}))]$ could lie, given the approximate best response under perfect information, defined as $\widetilde{\mathfrak{B}}(\mathbf{a})$. $\epsilon_{B}$ represents the worst case additive approximation error of $\mathbbm{E}[\mathcal{G}_{B}(\mathbf{a},\mathfrak{B}(\mathbf{a}))]$, where $\epsilon_{B}>0$.

The suboptimality of $\mathop{\mathbb{E}}[\mathcal{G}_{B}(\mathbf{a},\widetilde{\mathfrak{B}}(\mathbf{a}))]$ is attributed to the error in the approximation of the theoretically optimal response $\mathfrak{B}(\mathbf{a})$ with $\widetilde{\mathfrak{B}}(\mathbf{a})$, in response to the leader’s action $\mathbf{a}$ (the economic definitions of $\mathfrak{B}(\cdot)$, $\mathcal{U}_{B}(\cdot)$ and $\mathcal{G}_{B}(\cdot)$ are later illustrated in Section 2.4). In our learning scenario, the follower has access to $\mathcal{U}(\cdot)$, which shares the same parameters but differs from the functional form of $\mathbb{E}[\mathcal{G}_{B}(\cdot)]$. This allows us devise a learning algorithm which converges to $\epsilon_{B}$. Thus, any algorithm which learns an $\epsilon$-approximate Stackelberg equilibrium, is formally defined as an algorithm that converges to an equilibrium solution with $\epsilon_{B}$ approximation error, as defined in Eq. (2.10).

We model the two learning agents in a Newsvendor pricing game, involving a supplier $A$ and a retailer $B$. The leader, a supplier, is learning to dynamically price the product for the follower, a retailer, aiming to maximize her reward. To achieve this, the follower adheres to classical Newsvendor theory, which involves finding the optimal order quantity given a known demand distribution before the realization of the demand. We provide further economic details in Section 2.4.3.

Differing from the closely related work of [Ces+23], we do make some relaxations to the problem in their setting. Firstly, we assume no production cost for the item, which provides a non-consequential change to the economic theory. Secondly, we assume full observability of the realized demand of both the supplier and retailer. This is commonplace in settings where a disclosure of the realized sales must be disclosed to an upstream supplier, which could occur as a stipulation as a part of the supplier contract, and/or when the sales ecosystem is part of an integrated eCommerce platform.

Nevertheless, our problem setting further sophisticates the solution from [Ces+23] in multiple ways. Firstly, in addition to determining the optimal order amount (known as the Newsvendor problem), the follower must also dynamically determine the optimal retail price for the product in the face of demand uncertainty (known as the price-setting Newsvendor). Thereby, we introduce the problem of demand learning coupled with inventory risk. Secondly, in our problem setting, although the linear relation of price to demand $p\sim d_{\theta}(p)$ is assumed, the distribution of neither demand nor market price is explicitly given. Third, we apply the optimism under uncertainty linear bandit (OFUL) [APS11] to the Stackelberg game, whereas in [Ces+23] the Piyavsky-Schubert [Bou+20] algorithm is applied. Lastly, we provide Stackelberg regret guarantees on the cumulative regret, whereas [Ces+23] provides guarantees on the simple regret.

We propose an adaptation of the optimism-under-uncertainty (OFUL) algorithm from [APS11] (illustrated in Appendix B.1 for reference) to learn the parameters of demand from Eq. (2.11). The OFUL algorithm is a contextual linear bandit algorithm, also previously studied in [DHK08] and [RT10], which constructs a confidence ball $\mathcal{C}^{t}$ where the parameters of an estimated reward function fall within.

Given context $a$, we have two parameters to estimate $\theta_{0}$ and $\theta_{1}$, leading us to learning of the optimal riskless price optimization. From Eq. (3.1) we see that $||\theta^{*}_{t}-\theta_{t}||_{\bar{V}_{t}}$ grows logarithmically, matching the covariance of $\theta_{t}$, where $||\cdot||_{\bar{V}_{t}}$ is defined as the self-normalizing norm [PKL04]. Lemma 3.1 extends this relationship to a shrinking finite 2-norm bound, which we later use to derive bounds on regret.

Let $\mathcal{H}(\theta)\equiv\theta_{0}/\theta_{1}$. We introduce a learning algorithm where both the leader and the follower optimistically estimates $\mathcal{H}(\theta)$, while the follower learns $\mathcal{U}_{B}(p_{0},b_{0}|a)$. We denote by $\mathcal{C}^{t}$, the confidence set, wherein the true parameters lie with high probability $1-\delta$ (i.e. $\theta^{*}\in\mathcal{C}^{t}$). Our intuition, supported by Lemma 3.1, suggests that the size of $\mathcal{C}^{t}$ decreases linearly with the sample size $t$. Moreover, the linear structure of $\mathcal{U}_{B}(p_{0},b_{0}|a)$ enables Lemma 3.1 to remain valid during estimation of $\theta$ via linear contextual bandits. To highlight, the follower executes the optimistic linear contextual bandit, while the leader selects her actions maximizing over the follower’s optimistic best response.

Given leader action $a$, the optimal follower, $\mathcal{G}_{B}^{*}(\cdot)$ is unique from Theorem 2. Thus there there exists a unique solution where $\mathcal{G}_{A}^{*}(a)$ is maximized for any estimate of $\theta$. Although Theorem 2 illustrates the uniqueness of the SE under perfect information, there still exists uncertainty under imperfect information, when the parameters of demand are unknown. From the leader’s perspective, she is rewarded $\mathcal{G}_{A}(a,b)=ab$ depending on the reaction of the follower. The follower’s economic reaction is determined by $F_{\theta}^{-1}((p_{0}-a)/p_{0})$, which is affected by estimate $\theta$. We present empirical results of Algorithm 1 in Appendix E.

To characterize the best response of the follower, we must first establish a bound on the optimistic, yet uncertain, pricing behaviour $p_{a}$ of the follower given leader action $a$. From Theorem (1) there exists a direct relationship between $p^{t}$ and $b_{a}^{t}$. As the follower is learning parameters via OFUL, its certainty about the model parameters is bounded by $||\theta-\theta^{*}||_{2}\leq\mathcal{O}(\sqrt{\log(t)/t})$. For each given action $a$, and a confidence bound on the parameters $\theta^{*}$, denoted as $\mathcal{C}^{t}$, we can have an optimistic and pessimistic estimate of the best response, $b_{a}$, denoted as $(\bar{b}_{a},\underline{b}_{a})$ respectively. We define the pessimistic estimate of $b_{a}^{*}$ as,

The pessimistic best response $\underline{b}_{a}$ to $a$ occurs when the optimistic parameter estimate is equal to the maximum likelihood estimate itself, denoted as $\hat{\theta}$. Thus for realism, we set a lower bound of 0 for $b_{a}$. Additionally, we recognize that the riskless price estimate $p_{0}$ is always greater than or equal to $p^{*}$, represented as $a\leq p^{*}\leq p_{0}$ in Eq. (3.2). Later, in Lemma 3.3, we will demonstrate that when the algorithm converges to $p_{0}$, the learned parameters enable the follower to calculate $p^{*}$ and $b_{a}^{*}$ respectively.

The upper bound of the optimistic best response, $\bar{b}_{a}$ (Eq. (3.4)), can be determined by estimating the optimistic riskless price $\bar{p}_{0}$. Let $\mathbb{E}[\mathcal{G}_{B}(\theta|a)]$ denote the expected profit under parameter $\theta$, give $a$. Both the left and right terms of Eq. (3.3) are optimistic estimates of expected profit, $\mathbb{E}[\mathcal{G}_{B}(\theta|a)]$, using the riskless price $p_{0}$ as a surrogate for the optimal price. The follower’s pricing with $\bar{p}_{0}$, and ordering with $\bar{b}_{a}$, under an optimistic estimate of the demand parameters $\theta$ given data $\mathcal{D}^{t}$, can be summarized from Eq. (3.3) to Eq. (3.4). (The derivation from Eq. (3.3) to Eq. (3.4) is in Appendix C.2.)

Sketch of Proof: As illustrated in Fig. 3, we specify the optimization problem, where with probability $1-\delta$, the 2-norm error of the parameter estimates for $\theta$ lie within the confidence ball characterized by a radius less than $\kappa\sqrt{\log(t)/t}$. The general maximization problem is expressed in Eq. (3.5a) and (3.5b). The optimistic estimate of the $\theta$, denoted as $\mathcal{H}^{*}(\theta)$ (which we can denote in short as $\mathcal{H}^{*}$) lies in the extreme point between a ray $\mathcal{H}(\theta)$ and the boundary of $||\theta-\theta^{*}||_{2}\leq\kappa\sqrt{\log(t)}/\sqrt{t}$.

Leveraging Eq. (3.7), we can construct a bound on $\Delta_{\mathcal{H}}(t)$. Theorem 3 characterizes the shrinking nature of $\Delta_{\mathcal{H}}(t)$ with respect to $t$, as more samples are observed. Similar to Lemma 3.1, there also exists some $\kappa_{H}$, where $\kappa_{H}\sqrt{\log(t)/t}$ bounds $\Delta_{\mathcal{H}}(T)$ as expressed in Theorem 3. The establishment of this bound characterizes the pricing deviation of the follower pricing strategy, and is used to prove Theorem 4. To obtain a closed form solution to this optimization problem, we note the closed form expression of the Euclidean distance between a point in 2-space $(\theta_{0},\theta_{1})$ to a line described in Eq. (3.6). This distance measure is expressed in Eq. (3.7).

From Lemma 3.2 we can see that the cumulative optimistic pricing deviation of the follower is $\Delta_{\mathcal{H}}(T)\in\mathcal{O}(\sqrt{T\log(T)})$. This will have further ramifications when we compute the Stackelberg regret in Theorem 5. For interest to the reader, the current bound in Lemman 3.2 would naturally extend to non-linear settings such as exponential class General Linear Models (GLM’s) (we provide a description of this Appendix C.6).

In Algorithm 1 we propose that the follower prices the product at the optimistic riskless price $\bar{p}_{0}$, and not necessarily the optimistic optimal price $\bar{p}^{*}$. The profits derived from pricing with any of these suboptimal prices would result in suboptimal follower rewards (we characterize this regret later in Theorem 4).

For any approximately best responding follower, we can always expect a worst case error of $\epsilon_{B}$, defined in Eq. (2.10), for the follower at any discrete time interval. Thus, by intuition alone, we can presume the regret to be at least $\mathcal{O}(T)$. Nevertheless, it is worth noting that there exists these two distinct components to the regret, one caused specifically by the approximation of the best response, and one caused by the parameter uncertainty of the learning algorithm itself. The problem ultimately reduces to a contextual linear bandit problem.

Given our bounds on the optimistic pricing behaviour of the follower under context $a$ and uncertainty $\theta\in\mathcal{C}^{t}$, for any sequence of actions, $\{a^{1},...,a^{T}\}$, the expected regret of the follower is expressed in Eq. (2.3).

Sketch of Proof: As the follower implements the OFUL algorithm (see Appendix B.1) to estimate the demand parameters $\theta$, we propose $\mathcal{U}_{B}(p_{0}|a)$ as the theoretically maximum achievable expected reward. We quantify the variation in $\mathcal{U}_{B}(\bar{p}_{0}|a)$, represented by $\Delta_{\mathcal{U}}(t)$, across a finite number of samples $T$. Furthermore, we provide an upper bound on the instantaneous regret using the larger upper-bounding discrepancy $\mathcal{U}_{B}(\bar{p}_{0}|a)-\mathbb{E}[\mathcal{G}_{B}(p^{*}|a)]$. It is worth noting that although $\mathcal{U}_{B}(p|a)$ is a concave function, $\mathbb{E}[\mathcal{G}_{B}(p|a)]$ may not be. Under perfect information, the follower may incur an approximation error $\tilde{\epsilon}$ derived from this discrepancy, rendering it $\tilde{\epsilon}$-suboptimal in the worst case scenario. Nonetheless, this error is independent of $t$, and the learning error for $\theta$. Next, we establish a bound for the linear function estimation to compute optimal riskless pricing, for this we can apply the results of Theorem 3, and establish the bound of $\Delta_{\mathcal{U}}(t)\leq\theta_{1}\kappa_{H}^{2}\log(t)/t$. We then partition the learning time period into two phases: Case 2 denotes the period where $\mathbbm{E}[\mathcal{G}_{B}(p^{*}|a)]>\mathcal{U}_{B}(\bar{p}_{0}|a)$, occurring within the time interval $1\leq t\leq T^{\prime}$, and Case 1 denotes when $\mathbbm{E}[\mathcal{G}_{B}(p^{*}|a)]\leq\mathcal{U}_{B}(\bar{p}_{0}|a)$, occurring within the interval $T^{\prime}\leq t\leq T$ (assuming sufficiently large values of $T$). We note the differences in regret behaviour within these regimes and focus on the asymptotic regime as $T$ approaches $\infty$, where the cumulative regret is bounded between the worst-case approximation error for $\mathbbm{E}[\mathcal{G}_{B}(p^{*}|a)]$, denoted as $\epsilon_{B}$, and the logarithmic term $\Delta_{\mathcal{U}}(t)$ pertaining to linear stochastic bandit learning, presented as $\aleph_{B}+\epsilon_{B}T-\theta_{1}\kappa_{H}^{2}\log^{2}(T)$. (Complete details are provided in Appendix C.3.)