Santiago R Balseiro

Omar Besbes

Dana Pizarro
email: dana.pizarro@uoh.cl

Survey of Dynamic Resource Constrained Reward Collection Problems: Unified Model and Analysis *

Keywords: dynamic optimization, resource allocation, certainty equivalent, model predictive control, online matching, dynamic pricing, dynamic bidding, network revenue management, multi-secretary

Dynamic resource allocation problems arise under a variety of settings and have been studied across disciplines such as Operations Research and Computer Science. The present paper introduces a unifying model for a very large class of dynamic optimization problems, that we call dynamic resource constrained reward collection (DRC 2 ). We show that this class encompasses a variety of disparate and classical dynamic optimization problems such as dynamic pricing with capacity constraints, dynamic bidding with budgets, network revenue management, online matching, or order fulfillment, to name a few. Furthermore, we establish that the class of DRC 2 problems, while highly general, is amenable to analysis. In particular, we characterize the performance of the fluid certainty equivalent control heuristic for this class. Notably, this very general result recovers as corollaries some existing specialized results, generalizes other existing results by weakening the assumptions required, but also yields new results in specialized settings for which no such characterization was available. As such, the DRC 2 class isolates some common features of a broad class of problems, and offers a new object of analysis.

Introduction

Dynamic optimization problems with resource constraints arise across a variety of disparate applications. For example, retailers dynamically price products with inventory constraints, airlines and hotels engage in dynamic allocation of limited seats or rooms, advertisers bid in real-time to fulfill campaigns with limited budget. Due to the importance and centrality of these problems, various classes of dynamic optimization problems have received significant attention in industry but also across academic communities in Operations Research, Computer Science, and Economics.

A significant focus of the literature has been on the development of efficient algorithms to optimize performance subject to capacity constraints.

While the literature on these problems is rich and extensive,1 studies have focused on specific applications, or classes of applications. As such, arguments are specialized for specific settings and do not directly apply to other settings, typically requiring to re-develop, from scratch, analyses and proofs when faced with a new type of dynamic optimization problem with resource constraints.

While, from a practical perspective, problems such as those mentioned above can appear very different, these problems do admit some common mathematical structure. In the present work, we survey the literature, elucidate such common structure, and demonstrate that the latter can be captured by a general model we propose. In turn, we derive important theoretical implications of such commonalities.

A unified model. Our first main contribution is the introduction and definition of a general class of problems: dynamic resource constrained reward collection (DRC "squared" or for short DRC 2 ) problems, including problems with finite and continuum of actions and contexts. Notably, we show that this class admits as special cases a variety of problems studied separately in the literature. Broadly speaking, a DRC 2 problem is defined as follows. A decision maker endowed with some resources faces a finite (discrete) time horizon. At each period, the decision maker is presented with a stochastic opportunity (independent of other periods), and must select an action; the action leads to some stochastic resource consumption and reward collection. The goal of the decision maker is to select a sequence of actions to maximize her total expected rewards subject to the resource constraints. We assume that the decision maker knows the distribution of the various stochastic components, and, as such, this problem can be formulated as a discrete and finite-time dynamic program, with the state given by the vector of resources available.

The DRC 2 class of problems generalizes and brings under the same umbrella a host of classical problems studied separately. Figure 1 provides a conceptual illustration of the class. In particular, we show in §3 how the proposed class of DRC 2 problems encompass the following classical problems: Network dynamic pricing problems (see, e.g., [START_REF] Gallego | A multiproduct dynamic pricing problem and its applications to network yield management[END_REF], Multi-secretary problems (see, e.g., [START_REF] Kleinberg | A multiple-choice secretary algorithm with applications to online auctions[END_REF], Dynamic bidding in repeated auctions with budgets (see, e.g., [START_REF] Santiago R Balseiro | Repeated auctions with budgets in ad exchanges: Approximations and design[END_REF], Network revenue management problems (see, e.g., [START_REF] Kalyan | The theory and practice of revenue management[END_REF], Choice-based revenue management problems (see, e.g., [START_REF] Talluri | Revenue management under a general discrete choice model of consumer behavior[END_REF], Order fulfillment problems (see, e.g., [START_REF] Acimovic | The fulfillment-optimization problem[END_REF], and Online matching problems (see, e.g., [START_REF] Aggarwal | Online vertex-weighted bipartite matching and single-bid budgeted allocations[END_REF]. For each of these problems, we explain how they map to a DRC 2 problem. A unified analysis of "fluid" certainty-equivalent control. Although from a theoretical perspective, DRC 2 problems can be formulated through a dynamic program, one natural question is whether the DRC 2 formulation lends itself to analysis, beyond a generic analysis of a general dynamic program, that can be applied to all special cases, or whether problems should be specialized first to be able to derive properties of interest. We indeed demonstrate that the general DRC 2 formulation can lead to unified analysis through the study of a central heuristic in the stochastic dynamic optimization literature. Our second layer of contribution is in the analysis domain. In particular, we characterize the performance of a classical "fluid" certainty-equivalent control for the general DRC 2 class of problems.

Stochastic

In more detail, solving even a special case of a DRC 2 problem to optimality is typically impossible due to the curse of dimensionality; indeed, the state space grows exponentially with the number of resources. This has brought forward the need for heuristics for such problems, and many such heuristics have been developed for subsets of the problems above. A notable heuristic for dynamic optimization problems is the so-called certainty-equivalent heuristic, which involves solving a deterministic problem in each period by using proxies for random quantities, implementing the prescribed decisions for that period, and repeating the process over time. Such certainty-equivalent heuristics have been shown to be near-optimal under some conditions in various special cases of DRC 2 problems. A notable example of a certainty-equivalent heuristic is the so-called "fluid" one, in which the random quantities are replaced by their expectations. We will refer to this heuristic 3

Electronic copy available at: https://ssrn.com/abstract=3963265

as CE. Such policies are sometimes also referred to as "re-solving" or "model predictive control" in the various related streams of literature. To analyze the performance of the heuristic, we measure the loss between the optimal performance and that of the CE heuristic, and characterize the dependence of this loss on the "scale" of the system.

More specifically, we establish a hierarchy of sufficient conditions for the CE heuristic to lead to a "small" performance loss. The first layer of sufficient conditions identifies fundamental properties of the primal fluid problem that drive the CE performance and are stated in terms of the local strong-smoothness of the latter as a function of the resource vector. This condition highlights upfront a dichotomy between whether the primal problem is locally linear in the resource vector (i.e., weakly locally smooth) or locally quadratic (i.e., strictly locally smooth). Under weak localsmoothness the CE heuristic leads to losses that do not grow with T (where T is the length of the horizon), while under strict local-smoothness the CE heuristic leads at most logarithmic losses in T .

The second layer of sufficient conditions explores the drivers of the local strong-smoothness of the fluid problem in terms of the primitives of a DRC 2 problem. In doing so, we highlight how the local strong-smoothness condition naturally emerges in a variety of settings. A central object for this set of sufficient conditions is the dual Lagrangian problem, and we elucidate how properties of the latter together with the nature of the problem (finite vs. continuum of actions, finite vs. continuum of contexts) impact the type of local smoothness of the primal fluid problem.

In particular, the analysis leads to a dichotomy between two fundamental cases: that when the set of contexts and actions are finite (and the fluid problem is a finite linear program), and that when one of these is a continuum. When the set of contexts and actions are finite, the primal fluid problem is locally linear under some conditions and, in turn, we show that one can guarantee a reward loss that does not grow with T (where T is the length of the horizon). When either the set of contexts or the actions is a continuum, the primal problem is an infinite-dimensional program.

In this case, we provide a variety of conditions that lead to its local strong-smoothness and, in turn, we can guarantee at most logarithmic losses in T for the CE heuristic. Our analysis also leads to some control over the constants that drive the losses.

In essence, the analysis establishes that the class of DRC 2 problems, under said sufficient conditions, is "easy" in that the CE heuristic is extremely effective. Intuitively, the CE heuristic enables the decision maker to implement good decisions through the proxy problem while controlling very closely the path of the resource constraints.

In general, the primal problem solved in each step of the CE heuristic needs to optimize over randomized controls. When the set of actions is a continuum, the resulting problems are over infinite-dimensional probability measures and, thus, challenging to solve. We provide simple conditions on the primitives under which the optimal controls are deterministic and strong duality holds

In each period t, an opportunity arises and each opportunity is characterized by a context θ ∈ Θ, where Θ is the set of contexts. The context includes auxiliary information available to the decision maker that allows to customize decisions. For example, it can capture a user's preferences, demographic or historical information about a consumer, information about an order of products that needs to be fulfilled, etc. Contexts are drawn independently from a distribution p ∈ ∆(Θ),

where we use ∆(•) to represent the set of all probability distributions over a set. Upon observing an opportunity, the decision maker takes an action a ∈ A, where A is the set of feasible actions.

Upon taking an action a, the decision maker collects a reward that depends on the context θ, the action a, and an idiosyncratic shock . Shocks lie in a space E and are drawn independently from a distribution f ∈ ∆(E). Shocks are revealed to the decision maker after an action is taken and are meant to capture exogenous factors that are idiosyncratic to the opportunity. We denote by r : Θ × A × E → R, the reward function, where r(θ, a, ) denotes the reward when the context is θ, the action is a, and the shock is . Taking an action consumes resources and we assume that the amount of resources consumed depends on the context θ and the value of the shock . We denote by y : Θ × A × E → R L , the vector-valued resource consumption function. In particular y l (θ, a, )

represents the consumption of resource l if context θ arrived, the decision maker chose an action a, and the shock was .

To ensure that the problem is feasible, we assume there is a null action a 0 in A that consumes no resources and generates no reward. That is, for every context θ and idiosyncratic shock , we have r(θ, a 0 , ) = 0 and y l (θ, a 0 , ) = 0 for every resource l.

We denote the history up to time t -1 as H t-1 = {θ s , a s , s } t-1 s=1 . We let Π denote the set of all non-anticipating policies, i.e., the set of policies such that the action at time t, a t , depends on the observed context of the opportunity in time t and the history up to (and including) time t -1.

That is, for a policy π, a t = a π t (θ t , H t-1 ).2 The decision maker's objective is to choose a policy π ∈ Π that maximizes her expected rewards earned during the horizon. Taking into account that the consumption's constraints must hold almost surely, the stochastic optimization formulation of the decision maker may be written as follows:

J * (C, T ) = sup π∈Π E T t=1 r(θ t , a π t , t ) s.t T t=1 y l (θ t , a π t , t ) ≤ C l , ∀l ∈ [L] (a.s.) , (P)
where [L] denotes the set {1, . . . , L}.

Note that in general, this is a dynamic program with potentially a high number of dimensions and the curse of dimensionality precludes solving this problem to optimality. Given this, various heuristics can be considered and their performance can be assessed through the resulting optimality gap

J * (C, T ) -J π (C, T ),
where J π (C, T ) represents the expected reward obtained by the decision maker if policy π is implemented. We refer to the expression above as the reward loss of the heuristic given by π.

Discussion of the modeling assumptions

To simplify notation, we make the probability distribution of independent of the action and the context. In some applications, it might be convenient to allow for some dependence. Dependencies may be captured in our framework by modifying reward and consumption functions. We present the details of this reduction in Appendix A.1.

In this paper, we assume that the decision maker knows all parameters and the probability distributions of all uncertainties. There exists another line of work studying problems when these quantities are unknown, and can be either stochastic or adversarial. When the context distribution is unknown but the shocks are either deterministic or from a known distribution, the problem is called the online allocation problem (see, e.g., [START_REF] Mahdian | Online optimization with uncertain information[END_REF][START_REF] Vahab S Mirrokni | Simultaneous approximations for adversarial and stochastic online budgeted allocation[END_REF][START_REF] Agrawal | A dynamic near-optimal algorithm for online linear programming[END_REF][START_REF] Ma | Algorithms for online matching, assortment, and pricing with tight weight-dependent competitive ratios[END_REF][START_REF] Li | Online linear programming: Dual convergence, new algorithms, and regret bounds[END_REF][START_REF] Balseiro | The best of many worlds: Dual mirror descent for online allocation problems[END_REF]. When the shock distribution is unknown and there is a single context, the problem is called the multi-armed bandit with knapsack [START_REF] Badanidiyuru | Bandits with knapsacks[END_REF] and it includes important subclasses such as dynamic pricing with unknown demand [START_REF] Besbes | Dynamic pricing without knowing the demand function: Risk bounds and near-optimal algorithms[END_REF]]. In the case when both the context and shock distributions are unknown, the problem is called the contextual multi-armed bandit with knapsack [START_REF] Badanidiyuru | Resourceful contextual bandits[END_REF].

In the following section, we survey part of the literature and review a set of problems that are particular cases of the proposed DRC 2 class of problems. For each problem, we show it can be modeled as a DRC 2 problem.

3 Mapping Notable Problem Classes to a DRC 2 Problem

As it was mentioned above, many dynamic resource allocation problems can be modeled as a DRC 2 problem. In this section, we present some notable subclasses of problems and provide an explicit mapping to a DRC 2 problem. In Table 1, we present a high level overview of how various notable classes map to a DRC 2 problem, together with the subsections in which this mapping is established.

Network Dynamic Pricing

In the Network Dynamic Pricing problem, a firm sells products to a sequence of customers over a finite horizon (see, e.g., [START_REF] Gallego | A multiproduct dynamic pricing problem and its applications to network yield management[END_REF]). On the demand side, each buyer belongs to a class, captured by the context, characterized by their valuation for the products, which influences her demand. On the firm side, at the beginning of each period, he observes the class of the customer who arrived and posts prices to maximize his expected revenue taking into account that each product consumes a subset of resources, whose inventories are finite and without replenishment.

The interest in dynamic pricing problems has grown during the last few decades. The design of near-optimal pricing policies that are easy to implement has been studied under several model variants and heuristic polices are widely used in practice by firms. For example, [START_REF] Kunnumkal | A stochastic approximation algorithm for making pricing decisions in network revenue management problems[END_REF] and [START_REF] Erdelyi | Using decomposition methods to solve pricing problems in network revenue management[END_REF] consider a dynamic programming formulation.

Both papers consider an airline network in which prices affect the probability of the arrival request.

In the former, the authors propose a stochastic approximation algorithm for choosing prices dynamically and prove its convergence. In the latter, they develop two methods for making pricing decisions based on a decomposition of the original dynamic program. We refer the reader to the review papers and textbook of [START_REF] Bitran | An overview of pricing models for revenue management[END_REF], [START_REF] Kalyan | The theory and practice of revenue management[END_REF], [START_REF] Gallego | Revenue management and pricing analytics[END_REF].

Mapping to a DRC 2 problem. In this setting, there is a set of N different products to sell during a finite, discrete horizon. The context θ ∈ Θ represents a customer class or consumer segment, which will influence their demand. The set of actions A = R N + consists of the set of all feasible price vectors to post for the products.

For each customer class θ, the idiosyncratic shock captures heterogeneity in customer values.

Then, given θ, posted prices a ∈ A = R N + and a realization of the shock , we denote by D(θ, a, ) ∈ R N + the induced vector of demand. The reward function captures the revenue of the firm and is given by r(θ, a, ) = a D(θ, a, ), and the consumption function is y(θ, a, ) = Q θ D(θ, a, ). In the latter expression, Q θ ∈ R L×N is a matrix where Q n lθ represents the units of resource l needed to serve a customer in class θ with a single unit of product n.

Dynamic Bidding in Repeated Auctions

Consider the problem faced by a bidder participating in a sequence of repeated auctions to buy opportunities. The bidder has a budget constraint that limits his total expenditure over the horizon and aims to maximize his cumulative utility. This model is mainly motivated by internet advertising markets in which advertisers buy opportunities to display advertisements-an event referred to as an impression-via repeated auctions subject to budget constraints.

For instance, [START_REF] Abhishek | Optimal bidding in multi-item multislot sponsored search auctions[END_REF] study this problem, where the goal is to compute optimal bids for multiple keywords in an advertiser's portfolio. Motivated by ad exchanges, [START_REF] Santiago R Balseiro | Repeated auctions with budgets in ad exchanges: Approximations and design[END_REF] introduce a fluid mean-field equilibrium notion to study the strategic outcome of advertisers competing in repeated second-price auctions. [START_REF] Fernandez-Tapia | Optimal real-time bidding strategies[END_REF] also study the problem of bidding in repeated auctions but they consider that the arrival of requests is a Poisson process and characterize the optimal bidding strategy via its Hamilton-Jacobi-Bellman equation.

Mapping to a DRC 2 problem. In this setting, the decision maker is an advertiser. The advertiser is present in the market for T periods and one impression is auctioned per period. Upon the arrival of an impression at time t, the advertiser observes a real-valued valuation (the context)

θ t ∈ Θ ⊆ [0, Θ max ]
for the impression, which is distributed according to p ∈ ∆(Θ), and chooses an action a t ∈ A = [0, Θ max ] representing his bid in the auction. We denote by C the budget of the advertiser. The shock captures all exogenous uncertainty in the auction, such as the bids of the competitors and any potential randomization of the auction. For simplicity, we assume that is independent of the buyer's valuation θ but our model can be easily be modified to account for correlation using the reduction in Appendix A.1. The auction is characterized by an allocation rule q : A×E → [0, 1] together with a payment rule m : A×E → R; the former determines the probability that the impression is allocated to the advertiser and the latter his expected payment as a function of his bid and the exogenous shock. In Appendix D.2, we explicitly state the allocation and payment rules when the advertisers bid in first and second-price auctions, which are two auctions commonly used in practice and studied in the literature. The reward earned by the advertiser and his budget consumption, given a, and θ can be expressed as r(θ, a, ) = θq(a, ) -m(a, ) and y(θ, a, ) = m(a, ), respectively.

Network Revenue Management

Another notable special case of the DRC 2 class is a classical problem in the Revenue Management literature: the Network Revenue Management (NRM) problem. It was originally proposed in D'Sylva [1982], [START_REF] Glover | The passenger-mix problem in the scheduled airlines[END_REF] and [START_REF] Kw | Optimum seat allocation for multi-leg flights with multiple fare types[END_REF] and analyzed in the seminal paper [START_REF] Talluri | An analysis of bid-price controls for network revenue management[END_REF]. Since then, it has been extensively studied in the literature and has also been the basis for various industry solutions. The books of [START_REF] Kalyan | The theory and practice of revenue management[END_REF] and [START_REF] Gallego | Revenue management and pricing analytics[END_REF] provide extensive reviews.

In the NRM problem, the decision maker is a firm who is trying to dynamically allocate a limited amount of resources over a finite horizon. Resources are sold to heterogeneous consumers who arrive sequentially over time and belong to different classes depending on their consumption of resources and the fixed fare they pay. The distribution of contexts is stationary. Upon a customer's arrival, the firm has to decide whether to accept or reject the customer's request. If the customer is accepted and there is enough remaining inventory to satisfy its request, she consumes the resources requested and pays the corresponding fare. Otherwise, no revenue is collected and no resource is used. The decision maker's objective is to maximize the expected revenue earned during the selling horizon.

It is worth mentioning that some other problems, such as versions of dynamic knapsack problems (see, e.g., [START_REF] Papastavrou | The dynamic and stochastic knapsack problem with deadlines[END_REF][START_REF] Kleywegt | The dynamic and stochastic knapsack problem[END_REF][START_REF] Arlotto | Logarithmic regret in the dynamic and stochastic knapsack problem[END_REF] and versions of the multisecretary problem (see, e.g., [START_REF] Samuel Karlin | Stochastic models and optimal policy for selling an asset[END_REF][START_REF] Sakaguchi | A class of best-choice problems with full information[END_REF][START_REF] Arlotto | Uniformly bounded regret in the multisecretary problem[END_REF], can be seen as particular cases of the NRM problem and therefore they also belong to the DRC 2 class.

Mapping to a DRC 2 problem. In a NRM problem, a customer class can be captured by the context θ ∈ Θ and is characterized by their usage of resources and a fixed price they pay for the service. We let r θ denote the fare associated with class θ. The decision maker's feasible actions has two values, A = {0, 1}, where we represent the action "accept" by 1 and "reject" by 0. In this problem the set of idiosyncratic shocks is empty; both reward and resource consumption are 10 Electronic copy available at: https://ssrn.com/abstract=3963265 deterministic given the class. The reward if the customer belongs to class θ and the decision maker chooses an action a is r(θ, a) = r θ a. If we denote by Q θ = (Q lθ ) l ∈ R L the consumption vector, where Q lθ is the amount of resource l required to serve a customer of class θ, the consumption given that the decision maker chooses an action a and the customer class is θ is given by y(θ, a) = Q θ a.

Choice-Based Network Revenue Management

This problem bears many similarities to the network revenue management problem. In this setting, a firm is trying to dynamically allocate a limited amount of products which are sold to heterogeneous consumers who arrive sequentially and belong to different classes characterized by their product preferences. The key difference with the NRM class is that, upon a customer's arrival, the firm makes an offer in the form of a set of options and depending on the offer and on the customer's preferences, the consumer selects a single product to buy. This class of problems appears in the literature under different names depending on whether each product in the offer is a combination of one or more resources or whether there is a oneto-one mapping between products and resources. The first variant is the so-called choice-based problem whereas the second stream corresponds to a dynamic assortment optimization problem under capacity constraints.

In the first stream, the single-leg case was introduced by [START_REF] Talluri | Revenue management under a general discrete choice model of consumer behavior[END_REF] who provided an analysis of the optimal control policy under a general discrete choice model of demand.

In a network setting, [START_REF] Gallego | Managing flexible products on a network[END_REF] was the first to study a choice-based NRM problem. They consider flexible products in a continuous time horizon and with arrivals following independent Poisson processes. A flexible product consists of a set of alternative products serving a customer class. That is, if a flexible product F is offered by the decision maker and accepted by the consumer, then the decision maker assigns him one of the products in F . [START_REF] Liu | On the choice-based linear programming model for network revenue management[END_REF] considered a choice-based network RM problem in which each consumer belongs to a market segment (customer class) characterized by a set of products (different for each segment) in which the consumer is interested and the decision maker has to decide a set of products to offer in each selling period. [START_REF] José | A column generation algorithm for choice-based network revenue management[END_REF] consider the same problems as [START_REF] Liu | On the choice-based linear programming model for network revenue management[END_REF] but they allow customer classes to overlap. [START_REF] Jasin | A re-solving heuristic with bounded revenue loss for network revenue management with customer choice[END_REF] considers a model with customer choice that is slightly more general that the choice-based NRM as it allows for more general reward functions and resource consumption distributions. Still, their model fits in the DRC 2 class with appropriately defined reward and resource consumption functions.

In the second stream, [START_REF] Bernstein | Dynamic assortment customization with limited inventories[END_REF] consider a dynamic assortment problem in continuous time. In the problem they consider, all products have the same price and for each customer class they compute the probability that a customer belonging to that class chooses a product from the offer according to a Multinomial Logit model. [START_REF] Golrezaei | Real-time optimization of personalized assortments[END_REF] also formulate a related 11 Electronic copy available at: https://ssrn.com/abstract=3963265 dynamic assortment optimization problem. Their formulation is different in that it focuses on arbitrary, possibly adversarial, sequences of customer arrivals.

Mapping to a DRC 2 problem. In this setting, we consider a set of N products, each of them consisting of a set of resources. Product n is priced at f n . Contexts represent customer classes.

Given a customer class θ and a product n, we denote by A n lθ the amount of resource l needed to serve product n to customer θ. The action set is given by A ⊆ 2 {1,...,N } , where an action a ∈ A represents a set of products to be offered to a consumer.

For each action a and customer class θ, we define the shock random vector θa ∈ E a = ∈ {0, 1} N :

n∈[N ]
n ≤ 1, n = 0 for n ∈ a , where its nth component n θa is 1 if and only if the customer selects product n from the offer a. Then, θa ∼ Multinomial(1, g θa ) where g n θa is the probability of the consumer choosing product n given that his class is θ and the action taken is a.

Here g n θa = 0 if n ∈ a, i.e., if the product does not belong to the offer set. Given the consumer class θ, the action a, and the shock realization θa , the reward function is given by r(θ, a, ) = n∈[N ] f n n and the consumption function by y(θ, a,

) = n∈[N ] Q n θ n .
Note that, conditional on the shock , the resource consumption does not depend on the action.

However, the action affects the distribution of . In Appendix A.1, we show how one may apply suitable transformations to the reward and consumption functions to obtain an equivalent problem in which the random shock is independent of the class and the action.

Online Matching

Another closely related class of problems is that of online matching. This problem is related to the NRM class, but now, instead of making accept/reject decisions and each opportunity consuming a subset of resources, each opportunity can be assigned to any one resource and the decision maker needs to decide the resource to which to assign the opportunity.

The bipartite online matching problem was introduced by Karp et al. [1990] where they consider the case with arrivals in arbitrary order and with the goal of maximizing the total number of matches. Their results were extended by [START_REF] Aggarwal | Online vertex-weighted bipartite matching and single-bid budgeted allocations[END_REF] to more general settings. It was also recently studied by Vera and Banerjee [2021]. Some special cases of the online matching problem were considered by [START_REF] Feldman | Online stochastic matching: Beating 1-1/e[END_REF], [START_REF] Vahideh H Manshadi | Online stochastic matching: Online actions based on offline statistics[END_REF] and [START_REF] Nikhil R Devanur | Randomized primal-dual analysis of ranking for online bipartite matching[END_REF].

Mapping to a DRC 2 problem. We have a bipartite graph with resources on one side and contexts on the other side. An opportunity with context θ arrives with probability p θ and the decision maker needs to decide which resource to assign it to. Calling L to the set of resources, each context θ has a reward vector f θ ∈ R L + and a resource consumption

Q θ ∈ R L + .
The action set is A = L ∪ {0}, where the action 0 represents rejecting the request, i.e., the decision maker needs to decide the resource to which to assign the opportunity. Given an arrival with context θ and an action a, the reward is given by r(θ, a) = f θa 1 {a =0} and the consumption of resource l ∈ L is given by y l (θ, a) = Q a θ 1 {a=l} . We assume that the bipartite graph is complete. Incomplete graphs can be modelled by setting f θj = -∞ if assigning context θ to resource j is not feasible.

Order Fulfillment

In this section we detail a class of problems faced by a retailer who needs to fulfill the orders they receive from different facilities. Specifically, in this problem orders arrive sequentially and a decision maker has to construct a fulfillment policy to decide from which facility each of the items in the arriving order should be fulfilled.

Many different variants of this DRC 2 problem have been studied in the literature (see, e.g., [START_REF] Acimovic | Making better fulfillment decisions on the fly in an online retail environment[END_REF][START_REF] Jasin | An lp-based correlated rounding scheme for multi-item ecommerce order fulfillment[END_REF][START_REF] John M Andrews | Primal-dual algorithms for order fulfillment at urban outfitters, inc[END_REF]. For example, papers have considered different objectives to optimize, whether the model requires a demand forecast or not, multi or single-item approaches, among others. We refer the reader [START_REF] Acimovic | The fulfillment-optimization problem[END_REF] for a recent overview of order fulfillment problems.

On the other hand, some works in the existing literature consider additional constraints related, for instance, to the set of feasible facilities (or resources) from which is it possible to serve an order. [START_REF] Asadpour | Online resource allocation with limited flexibility[END_REF] consider an online allocation problem with equal numbers of types of resources and types of requests with the restriction that a request of type i can be served only by resources of type i and type i + 1. If both resources have zero inventory left, then the sale is lost. Their goal is to provide an upper bound on the difference between the performance with and without the above described restriction on fulfillment.

It is worth mentioning that some works consider the order fulfillment problem jointly with the pricing problem (see, e.g., [START_REF] Harsha | Dynamic pricing of omnichannel inventories: Honorable mention-2017 m&som practice-based research competition[END_REF], Lei et al. 2018a) or jointly with both pricing and display problems (see, e.g., Lei et al. 2018b).

Mapping to a DRC 2 problem. We consider the setting where there are L different items that could be served from N different facilities. Each facility n is endowed with an inventory C n ∈ R L + , with C nl representing the initial capacity of item l in facility n, and we consider that facility N is fictitious with infinite initial capacity of all items.

Arrival θ occurs with probability p θ and corresponds to an order of products that needs to be fulfilled belonging to Θ = 2 {1,...,L} . We assume one order includes at most one unit of each item.

Then, l ∈ θ if and only if item l is included in the order θ.

The decision maker has to construct a fulfillment policy to decide from which facility n ∈ [N ] each of the items in θ should be fulfilled in order to maximize his expected revenue. That is, the action set is given by A = {1, . . . , N } L , where given l ∈ [L], a l = n means that item l is served 13 Electronic copy available at: https://ssrn.com/abstract=3963265 from facility n. Furthermore, serving item l from facility n has an associated reward denoted by

f ln .
Given that the order is θ and the decision maker chooses action a, the consumption of item l in the facility n is y ln (θ, a) = 1 {a l =n} , and the reward is given by r(θ, a) = l∈θ,n∈[N ] f ln 1 {a l =n} .

Performance Analysis of Certainty Equivalent Heuristic

As mentioned in §2, an optimal solution of the stochastic formulation of a DRC 2 problem is not easy to compute. A common and central heuristic in the theory of dynamic decision-making under uncertainty is based on the certainty equivalent principle: replace quantities by their expected values and take the best actions given the current history. Specifically, at each point of time t, we solve an optimization problem obtained by using the history up to t -1 and replacing the random quantities in problem (P) by their expectations.

That is, if we denote by Φ the set of all context-dependent probability distributions φ : Θ → ∆(A), and by ρ ∈ R L + a non-negative parameter representing the vector of available inventory divided by the number of remaining periods, at time t we solve the following parametric programming problem for ρ = ρ t , which we refer to as the fluid problem:

J(ρ) = sup φ∈Φ E θ∼p,a∼φ(θ), ∼f [r(θ, a, ))] s.t E θ∼p,a∼φ(θ), ∼f [y l (θ, a, )] ≤ ρ l , ∀l ∈ [L]. (P FLUID )
While we refer to (P FLUID ) as the fluid problem as it uses deterministic quantities as inputs (random quantities are replaced by their expected values), we remark that the controls are, in general, randomized. Because the distributions of contexts and shocks are independent and identically distributed (i.i.d.) and we allow for randomized actions, we can restrict attention without loss to static controls in the fluid problem. For each context θ ∈ Θ, the decision variable φ(θ) gives a probability distribution over actions a ∈ A conditional on the arrival belonging to context θ.

In what follows, we assume that problem (P FLUID ) admits an optimal solution. We denote by φ * ρ an optimal solution when the parameter is ρ. We will provide sufficient conditions for existence of an optimal solution in §5. When an optimal solution does not exist or it is computationally intractable, the analysis we develop can also be applied when an approximately optimal solution is computable. In particular, we can control the loss stemming from using an approximately optimal solution. In Appendix A.2, we provide a detailed analysis on the additional cumulative losses one incurs.

The Certainty Equivalence Principle leads to a natural heuristic for the decision maker: at each point in time t, choose actions according to a solution φ * ρt to (P FLUID ) with ρ t = c t /(Tt + 1) and c t the capacity remaining at beginning of time t. We call this heuristic the Certainty Equivalent Heuristic (CE) and denote the corresponding policy by π CE . The heuristic is formally presented in Algorithm 1. The CE heuristic adjusts the parameter ρ dynamically according to the amount of resources remaining to avoid running out of resources too early or avoid being overly constrained if resource consumption ends up being lower than expected.

The certainty equivalent heuristic has been extensively studied in the literature for specific applications. We return to these in §6. Our aim is to characterize its performance for the broader class of DRC 2 problems. Thus, as the family of DRC 2 problems encompasses a large number of applications that have been studied in the literature separately, by analyzing the performance of the CE heuristic, we shall recover some already known results and, in the process, obtain new results for other applications, while highlighting very general sufficient conditions to ensure "good" performance of the CE heuristic.

Algorithm 1 Certainty Equivalent Heuristic (CE) Initialize c 1 ← C for t = 1, . . . , T do ρ t ← c t /(T -t + 1) φ * ρt ← an optimal solution of Problem (P FLUID ) with ρ = ρ t observe the context θ t draw an action a t from the distributionφ * ρt (θ t ) if y(θ t , a t , ) ≤ c t ∀ ∈ E, then choose the action a t observe the shock t c t+1 ← c t -y(θ t , a t , t ) else choose the null action a 0 c t+1 ← c t end end
For simplicity, we focus on a certainty equivalent control that adjusts decisions based on resolving every period. We conjecture that the results developed in the present paper continue to hold when one re-solves less frequently. The latter has indeed been established for various special cases of DRC 2 problems (see, e.g., [START_REF] Jasin | A re-solving heuristic with bounded revenue loss for network revenue management with customer choice[END_REF].

Before proceeding to the analysis of the performance of the CE heuristic, we show that the fluid problem (P FLUID ) gives an upper bound on the optimal value of the stochastic problem (P), a result that we will use to obtain the bound for the reward loss of the CE heuristic in the next section.

Although versions of this result have been proven many times for some special cases and under stronger assumptions (see, e.g., [START_REF] Gallego | A multiproduct dynamic pricing problem and its applications to network yield management[END_REF], here we present a generic result in the context of the set of DRC 2 problems. We prove the result in the primal space, where the key observation is that the fluid problem allows for randomized policies. Therefore, for every dynamic policy, we can construct a feasible policy for the fluid problem that attains the same objective, by taking time averages and expectations over histories. The proof can be found in Appendix B.1.

Proposition 1. The optimal value of the stochastic problem (P) is upper bounded by T times the value of the fluid problem (P FLUID ) for ρ = C/T . That is,

J * (C, T ) ≤ T J(C/T ).

Bound on the cumulative reward loss of the CE heuristic

In this section we study the performance of the CE heuristic for the general class of DRC 2 problems.

To this end, we first introduce some definitions and conditions on the primitives.

We will assume that the reward and consumption functions are bounded. This assumption is well motivated in practice as opportunities typically consumer a small number of resources relative to the total initial capacities. For a vector x ∈ R n , we denote by x

= n i=1 x 2 i 1/2 its 2 -norm and denoted by x ∞ = max i |x i | its ∞ -norm.
Assumption 1. The following hold:

1. There exists r∞ ∈ R ++ such that r(θ, a, )≤ r∞ for all θ ∈ Θ, a ∈ A, and ∈ E.

2. There exist ȳ2 , ȳ∞ ∈ R ++ such that y(θ, a, ) ≤ ȳ2 and y(θ, a, ) ∞ ≤ ȳ∞ for all θ ∈ Θ, a ∈ A, and ∈ E.

Recall that ρ 1 is the vector of initial inventory divided by the number of periods to consider.

Given φ *

ρ 1 , an optimal solution of (P FLUID ) for ρ = ρ 1 , we partition the resources [L] into the set of resources C for which the corresponding resource constraint of problem (P FLUID ) is binding at ρ = ρ 1 and U the set of resources for which the constraint does not bind. That is,

C := l ∈ [L] : E θ∼p,a∼φ * ρ 1 (θ), ∼f [y(θ, a, )] = ρ l and U := l ∈ [L] : E θ∼p,a∼φ * ρ 1 (θ), ∼f [y(θ, a, )] < ρ l .
Note that C and U are complement sets, i.e., C ∪ U = [L]. Given a vector v, we will denote by v| C and v| U the restriction of v to the components of the set C and U, respectively.

We will assume that, in the "neighborhood" of ρ 1 , the optimal objective value of the fluid problem J(ρ) is locally smooth as well as that the consumption constraints corresponding to the 16

Electronic copy available at: https://ssrn.com/abstract=3963265

set C stay binding. We require the assumption to hold in the set of

N (ρ 1 , δ, C) = ρ ∈ R L + : ρ| C -ρ 1 | C ≤ δ and ρ| U -ρ 1 | U ≥ -δ1 , (1)
which are the vectors that are δ close to ρ 1 for the binding resources and at least -δ larger for those resources that are not binding. Intuitively, resources which are not binding can increase without changing the optimal solution so these are only restricted from below. When all resources are binding, i.e., C = [L], we write N (ρ 1 , δ) to represent the set of all points at distance at most δ

from ρ 1 . Assumption 2. There exist δ, K ∈ R ++ with δ < min l∈[L] ρ 1,l such that for every ρ ∈ N (ρ 1 , δ, C)
it holds that:

1. The function J(ρ) satisfies J(ρ) ≥ J(ρ 1 ) + ∇ J(ρ 1 )(ρ -ρ 1 ) -K 2 ρ| C -ρ 1 | C 2 .
2. There exists an optimal solution φ *

ρ satisfying E θ∼p,a∼φ * ρ (θ), ∼f [y(θ, a, )| C ] = ρ| C .
We will refer to the inequality given in Assumption 2.1 as J(ρ) admitting a K-lower downward quadratic (K-LDQ) envelope in N (ρ 1 , δ, C). See Figure 4 (a) for an example of a function admitting a K-LDQ envelope and its envelope. This condition is a weaker and local notion of the K-strongly smooth condition for concave functions, which requires the inequality in Assumption 2.1 to hold for every pair of parameters ρ, ρ . When all resources are binding, a sufficient condition for J(ρ)

to admit a K-LDQ envelope is that its gradient is locally K-Lipschitz continuous at ρ 1 for all

ρ ∈ N (ρ 1 , δ), that is, ∇ J(ρ 1 ) -∇ J(ρ) ≤ K ρ 1 -ρ .
See Lemma 3.4 in Bubeck [2014] for a proof of the previous fact.

The second part of Assumption 2 requires that all resources that are binding at ρ 1 remain binding at optimal solutions in a neighborhood of ρ 1 . Because the lower quadratic envelope in the first part is independent of the unconstrained resources, we are also implicitly precluding unconstrained resources from becoming constrained and impacting performance.

We are now ready to state our performance bound of the CE heuristic under Assumptions 1 and 2.

Specifically, in Theorem 1, we bound the reward loss of the heuristic given by CE as a function of the parameters in Assumptions 1 and 2.

Theorem 1. Let J CE (C, T ) be the expected performance of Algorithm 1. Then, under Assumptions 1 and 2, the reward loss satisfies

J * (C, T ) -J CE (C, T ) ≤ ȳ2 2 K log T + 2ȳ ∞ ρ 1 -δ + 14ȳ 2 ∞ δ 2 J(ρ 1 ),
where ρ 1 is the smallest component of the vector ρ 1 .

We note that the result above applies across all DRC 2 problems, and only requires Assumptions 1 and 2. Consider a regime in which C and T are scaled proportionally, i.e., C = ρ 1 T for some ρ 1 ∈ R L ++ . Theorem 1 implies that, in such a regime, the CE heuristic is asymptotically optimal in the sense that J CE (C, T )/J * (C, T ) → 1 as T → ∞ because the reward collected by the CE heuristic grows as T → ∞. Furthermore, the optimality gap is of order O(log T ) if K > 0 and of order O(1) if K = 0. In other words, we see a clear distinction among DRC 2 problems driven by the value of K in Assumption 2.

At a more detailed level, the dependency on the number of resources L enters our bound indirectly via the constants ȳ2 , ȳ∞ , and K. Interestingly, when resource consumption is uniformly bounded, i.e., ȳ∞ < ∞, the dependency on the number of resources is mostly driven by ȳ2

2 . While in the worst case we could have ȳ2 2 = Ω(L), in many settings of interest, one will have ȳ2 2 = O(1) and we obtain bounds that are independent of the number of resources. This could happen, for example, if every opportunity consumes only a finite subset of resources. Our dependence in the number of resources is better than some existing, specialized results on the literature (e.g., those in Jasin and Kumar 2012) because we use concentration inequalities for multi-dimensional martingales instead of a union bound to control the stopping time associated to the first time a resources is close to being depleted, which would naturally lead to a linear dependence on L. Finally, as it is common in the operations research literature, the bound provided in Theorem 1 is instance dependent, i.e., it depends on the parameters of the particular problem at hand. (This is in contrast to, e.g., bounds in the multi-armed bandit [START_REF] Bubeck | Regret analysis of stochastic and nonstochastic multiarmed bandit problems[END_REF] or online convex optimization [START_REF] Hazan | Introduction to online convex optimization[END_REF] literatures which are worst-case over a large class of instances and depend on few key parameters such as the size of the action space and the length of the horizon.)

The proof of the theorem can be found in Appendix B.2. The proof leverages ideas pioneered by [START_REF] Jasin | A re-solving heuristic with bounded revenue loss for network revenue management with customer choice[END_REF] and lifts them to more general settings than the one considered in their paper. In particular, we analyze the performance of the CE heuristic up to the stopping time τ , where τ is the first time that a resource is close to depletion or the ratio of capacity to time remaining ρ t leaves the ball N (ρ 1 , δ, C) defined in Assumption 2. Using that the fluid problem gives an upper bound on the optimal value of the stochastic problem, that is, J * (C, T ) ≤ T J(C/T ) (see Proposition 1), we can bound the reward loss as follows

J * (C, T ) -J CE (C, T ) ≤ T J(ρ 1 ) -J CE (C, T ) (2) ≤ E τ t=1 J(ρ 1 ) - τ t=1 r(θ t , a π CE t , t ) + E T t=τ +1 J(ρ 1 ) ,
where a π CE t denotes the action taken by the CE heuristic and the second inequality follows because 18

Electronic copy available at: https://ssrn.com/abstract=3963265 r(θ t , a π CE t , t ) ≥ 0 since the null action a 0 is feasible. The second term of the right-hand side can be written as E[T -τ ] • J(C/T ), which is of order O(1), as we establish in Lemma B-3. This follows because, under the CE heuristic, the ratio ρ t behaves like a martingale for the binding resources (and a submartingale for the ones that are not binding) by Assumption 2.2 and, as a result, the heuristic never runs out of resources nor ρ t leaves the set N (ρ 1 , δ, C) too early. The first term is shown to be of order O(log T ). To see this, note that up to time τ actions are not constrained by resources and the expected reward at period t satisfies E r(θ t , a π CE t , t ) | ρ t = J(ρ t ) because the CE heuristic takes actions according to φ * ρt . Therefore, using Assumption 2.1 together with the fact that ∂ J ∂ρ l (ρ 1 ) = 0 for every resource l ∈ U that is not binding, we can upper bound the first term by

E τ t=1 l∈C ∂ J ∂ρ l (ρ 1 )(ρ 1,l -ρ t,l ) + (K/2)E τ t=1 ρ 1 | C -ρ t | C 2 .
The first term is zero because, for the binding resources, ρ t behaves like a martingale, while the second term can be bounded using the fact that martingale differences are orthogonal. Putting everything together, we then conclude with the bound in the Theorem.

We highlight here again that, although the general idea behind the proof of Theorem 1 is not novel, our contribution is to generalize this result to the class of DRC 2 problems and identify crisp sufficient conditions that allow us to obtain a performance guarantees on the CE heuristic for every problem in this class without the need of exploiting specific structural features of each particular application. As we will see later, this allows us to obtain in some cases weaker conditions or sharper bounds, but also to obtain new results altogether. More specifically, we see that it is not only possible to define a unified model for a very large class of dynamic optimization problems as we established in §3, but it is also possible to identify general sufficient conditions that allow for a unified analysis of the CE heuristic and its performance.

Assumption 2 provides sufficient conditions to obtain good performance guarantees for the CE heuristic that involve, in a neighborhood of the "initial inventory per period," local smoothness of the optimal objective value of the fluid problem, as well as the fact that the consumption constraints stay binding if they were binding for the initial problem. These conditions, while simple to state, may not be easy to check in many applications. In §5 we provide a "tree" of sufficient conditions leading to assumptions on the primitives of the model, which are simple to check, that imply Assumption 2 and, therefore, also the bound in Theorem 1. Our conditions yield, in many cases, closed-form expressions for the values of δ and K based on the primitives of the problem. In particular, we highlight the drivers for positive values of K, delineating when one should expect to obtain logarithmic versus constant reward loss. Next, in §6 we revisit the applications presented in §3 using the results from §5. For each problem, we provide problem-specific sufficient conditions for our assumptions to hold, and we derive the implications of Theorem 1. As we will see, our results allow to recover some existing results in the literature as special cases, sometimes under weaker assumptions, and also uncover new results for other classes of problems studied in the literature.

Drivers of CE Heuristic Performance: Dual Problem and General Sufficient Conditions

An important component to understand the drivers of the CE heuristic is to link the primitives of a DRC 2 problem to the performance that is achieved. In this section, we address this goal by giving conditions on the primitives of a DRC 2 problem that are sufficient for Assumption 2 to be satisfied. These conditions provide a unifying framework to understand how the structural features of different problems across the DRC 2 class impact the performance of the CE heuristic, rather than requiring a problem-specific analysis for each application.

We introduce a dual of Problem (P FLUID ) in which we dualize the consumption constraints.

To this end, let µ ∈ R L + be the vector of Lagrange multipliers associated with the consumption constraints of Problem (P FLUID ). Let r : Θ × A → R + denote the expected reward function, i.e., r(θ, a) = E r(θ, a, ) . In the same way, for each l ∈ [L], let ȳ : Θ × A → R L + denote the expected resource consumption function, i.e., ȳ(θ, a) = E y(θ, a, ) . Then, the Lagrangian function is given by

L(φ, µ) = E θ∼p,a∼φ(θ) r(θ, a) + µ ρ -E θ∼p,a∼φ(θ) ȳ(θ, a) = E θ∼p,a∼φ(θ) r(θ, a) -µ ȳ(θ, a) + µ ρ.
Define, for each θ ∈ Θ, the function g θ : R L → R, which captures the optimal opportunity-cost adjusted reward given a context, and is given by

g θ (µ) = sup a∈A r(θ, a) -µ ȳ(θ, a) .
(3)

We will refer to g θ (µ) as the context-dependent adjusted reward function. We denote the set of maximizers associated with the function g θ (µ) by

A * θ (µ) = arg max a∈A r(θ, a) -µ ȳ(θ, a) , (4)
and let the adjusted reward function to be g

(µ) = E θ∼p [g θ (µ)]. The Lagrange dual function, for 20
Electronic copy available at: https://ssrn.com/abstract=3963265 fixed ρ ≥ 0, is given by

Ψ ρ (µ) = sup φ∈∆(A) L(φ, µ) = µ ρ + E θ∼p sup a∈A r(θ, a) -µ ȳ(θ, a) = µ ρ + E θ∼p [g θ (µ)] = µ ρ + g(µ) ,
where the second equality follows because the problem is separable over contexts. The dual problem of Problem (P FLUID ) is then given by inf

µ∈R L + Ψ ρ (µ) . (5)
In Figure 2, we provide an overview of the results in this Section, which highlight how a variety of assumptions naturally lead to Assumption 2. The arrows and associated results establish the sufficiency of the conditions from one block to another block. At a high level, we present two sets of conditions under which Assumption 2 holds and characterize the corresponding parameters. A first set of conditions is when the fluid problem (P FLUID ) is a linear program, which corresponds the case of finite actions and contexts ( §5.1); in this case, Assumption 2 holds with K = 0. A second set of conditions is on the dual of (P FLUID ) ( §5.2). These conditions apply to a variety of settings and the analysis links the values of K and δ to the primitives of the problem. In particular, we illustrate these conditions in two notable subfamilies of cases: a continuum of actions, and binary actions with a continuum of contexts.

When the fluid problem is a finite dimensional linear program

Suppose that the set of actions A is finite and the set of contexts Θ is finite. We will derive sufficient conditions for Assumption 2 to hold with K = 0. Examples of problems with finite set of contexts and actions are: network revenue management problems with finite customer classes, multi-secretary problems with finite types, choice-based revenue management problems, order fulfillment problems with discrete locations, online matching problems, among others.

Note that Problem (P FLUID ), in this special case, can be written as a finite-dimensional linear programming problem as follows

J(ρ) = max φ θ ∈∆(A) θ∈Θ p θ r θ φ θ s.t θ∈Θ p θ ȳθ φ θ ≤ ρ , (6)
where rθ = (r(θ, a)) a∈A ∈ R |A| + is the vector of expected rewards for the different actions and ȳθ = (ȳ(θ, a)) a∈A ∈ R L×|A| + is the matrix of expected resource consumption. Furthermore, the feasible set is non empty and compact, and therefore there exists an optimal solution.

22

Electronic copy available at: https://ssrn.com/abstract=3963265

The following is a common assumption in the literature associated with special cases of DRC 2 problems that guarantees that the CE policy has bounded reward loss (see, e.g., [START_REF] Jasin | Reoptimization and self-adjusting price control for network revenue management[END_REF]Kumar 2012, Wu et al. 2015).

SC 1. The primal problem (6) has a non-degenerate optimal solution for ρ = ρ 1 , denoted by φ * ρ 1 .

Considering the standard form of Problem (6) (see Appendix A.3 for details and the proof of Lemma 1 for an explicit matricial representation), let B ∈ R (L+|Θ|)×(L+|Θ|) be the corresponding optimal basis matrix and denote by B -1 ρ 1 the submatrix of B -1 associated to the resource constraints. In the following lemma, we show that Assumption 2 holds under Assumption SC 1 and characterize the associated values of K and δ.

Lemma 1. Suppose that Assumption SC 1 holds. Then Assumption 2 holds with K = 0 and δ = min(φ * min , x * min )/ B -1 ρ 1 , where φ * min = min θ∈Θ,a∈A {φ * θ (a) :

φ * θ (a) > 0}, x * min = min l∈[L] {x * l : x * l > 0} and x * l = ρ l -θ∈Θ p θ ȳlθ φ * θ is the slack of the l-th resource constraint.
The proof is provided in Appendix C.1. A direct implication of Lemma 1 is that the reward loss if the action and context spaces are finite is on the order of O(1).

Corollary 1. Suppose that the sets of actions and contexts are finite and that Assumptions 1 and SC 1 hold. Then, the reward loss of the certainty equivalent heuristic is bounded by a constant for DRC 2 problems.

Note that the bound on the reward loss is proportional to δ -2 and hence deteriorates when δ is small, which can occur if unconstrained resources are close to binding or if the fluid solution prescribes some actions to be taken with low probability.

Although the sufficient condition SC 1 is given on the primal problem (6), it is also possible to state sufficient conditions on the partial dual problem (5) to guarantee that Assumption 2 holds.

In this case, (5) can be thought of as a "partial" dual problem in which we dualize the resource constraints but not the simplex constraint a∈A φ θ (a) ≤ 1. Then, it follows that the duality gap is zero and J(ρ

) = inf µ∈R L + Ψ ρ (µ).
It is well known that a sufficient condition to have a non-degenerate (and unique) solution of a linear problem is uniqueness and non-degeneracy of the dual problem (see, e.g., [START_REF] Bertsimas | Introduction to linear optimization[END_REF], and therefore in what follows we state sufficient conditions to guarantee the latter.

More specifically, the condition SC 2 implies that the dual problem of (6) for ρ = ρ 1 has a unique solution, whereas from SC 2 and SC 3 we obtain that such optimal solution is not degenerate, concluding that under conditions SC 2 and SC 3, the problem (6) has a unique and non-degenerate optimal solution for ρ = ρ 1 , which is stated in Lemma 2.

SC 2. The dual problem (5) has a unique solution, µ 1 , for ρ = ρ 1 .

SC 3. The set of maximizers defined in (4) satisfies θ∈Θ |A * θ (µ 1 )| = L + |Θ|.

In the following lemma, we formalize that under Assumptions SC 2 and SC 3 there exists a unique and non-degenerate optimal solution of (6) for ρ = ρ 1 . The proof is provided in Appendix C.2.

Lemma 2. Under Assumptions SC 2 and SC 3, Assumption SC 1 holds.

Geometric interpretation. We now provide a geometric interpretation for Assumption SC 2 as well as for the deterministic and dual functions for the case of finite actions and finite contexts.

First, note that problem ( 6) is an LP and therefore the deterministic function J(ρ) is a concave piece-wise linear function (see Bertsimas and Tsitsiklis 1997 for more details). Moreover, due to the nature of the problem, it will be non-decreasing. In Figure 3 (a), the function J(ρ) is plotted for a problem with one resource and two contexts. Every optimal dual variable µ for Ψ ρ (µ) gives a super-gradient to J(ρ). Therefore, the slope of each straight-line segment is equal to the Lagrange multiplier associated to the consumption constraint, and the corresponding interval gives the values of the right-hand side range for the consumption constraint ρ for which the same dual variable is optimal.

In Figure 3 (b) and (c), we plot the dual function Ψ ρ (µ) as a function of µ for two different possible values of the parameter ρ. In Figure 3 (b), we take ρ = ρ 1 1 , a value where J(ρ) has a kink. In this case, the dual problem admits an infinite number of solutions (flat blue segment in the figure) and every dual solution is a super-gradient of J(ρ 1 ). In Figure 3 (c), we plot the dual function at ρ = ρ 2 1 , a value belonging to an interval where J(ρ) is smooth. There, the set of super-gradients is a singleton and, as a result, the dual optimal solution is unique (red dot in the figure). Thus, Assumptions SC 2 and SC 3 are equivalently asking that the parameters ρ 1 lies in the interior of an interval where the deterministic function J(ρ) is smooth.

Beyond finite dimensional linear programs as fluid problems

When either the set of actions or the set of contexts is a continuum, Problem (P FLUID ) is not necessarily a finite dimensional linear program. Next, we explore these cases and the drivers of the parameters K and δ associated with Assumption 2, and in turn why these problems often lead to logarithmic reward loss. (As we will see, natural conditions on the primitives lead to Assumption 2 holding with K > 0.)

In particular, we first provide sufficient conditions to ensure that strong duality holds for the fluid problem and that the fluid problem admits an optimal deterministic solution. Then, we give a closed-form expression for the values of K > 0 and δ for which Assumption 2 holds. Finally, we illustrate our conditions on two prototypical examples: finite contexts with a continuum of actions and a continuum of contexts with binary actions. ρ J(ρ)

ρ 1 1 ρ 2 1 (a) Function J(ρ) µ Ψ ρ 1 1 (µ) (b) Dual function at ρ 1 1 . Multiple optimal dual solutions. µ Ψ ρ 2 1 (µ) (c) Dual function at ρ 2 1 .
Unique optimal dual solution.

Strong duality and deterministic controls

We next present conditions on the function g θ defined in (3) that are sufficient to ensure that the fluid problem has zero duality gap for every positive parameter ρ and that the fluid problem admits an optimal deterministic solution. Our sufficient conditions require that the functions g θ are differentiable and an optimal action exists for every context and dual variable. SC 4. Almost surely over θ ∈ Θ we have that, for every µ ≥ 0, function g θ (µ) is differentiable in µ and the set of maximizers A * θ (µ) is non-empty.

Proposition 2. Under Assumptions 1 and SC 4, strong duality for (P FLUID ) holds, i.e., J(ρ) = inf µ∈R L + Ψ ρ (µ) for all ρ > 0. Furthermore, J(ρ) admits a deterministic optimal solution for all ρ.

A proof is provided in Appendix C.3. We first prove that the dual problem admits an optimal solution using the extreme value theorem. This follows because the dual objective is continous and, without loss, we can restrict dual variables to a compact set. We then prove that strong duality holds by first principles by constructing a primal-dual pair that satisfies complementary slackness and Lagrangian optimality. The result follows because the primal solution is, by construction, deterministic.

Proposition 2 implies that, under assumption SC 4, randomization in (P FLUID ) is not needed.

As a result, we can write J(ρ) as the following non-linear program:

J(ρ) = max a∈A |Θ| E θ∼p, ∼f [r(θ, a θ , )] s.t E θ∼p, ∼f [y l (θ, a θ , )] ≤ ρ l , ∀l ∈ [L] ,
where a ∈ A |Θ| is to be interpreted as a function that maps a context θ to an action a θ . We remark here that in the literature, the fluid problem is sometimes formulated directly over deterministic 25

Electronic copy available at: https://ssrn.com/abstract=3963265 actions as stated above. The analyses of the induced certainty equivalent policies typically require concavity of the objective and convexity of the constraints (with respect to actions or appropriate transformations of actions); see, e.g., [START_REF] Gallego | A multiproduct dynamic pricing problem and its applications to network yield management[END_REF], [START_REF] Maglaras | Dynamic pricing strategies for multiproduct revenue management problems[END_REF],

Jasin [2014]. Remarkably, Proposition 2 allows to recover the optimality of deterministic actions even when the problem is non-convex and allows to obtain strong guarantees on the performance of certainty equivalent controls in more generality.

The resulting non-linear program might be non-convex and, in general, challenging to solve.

A straightforward corollary of Proposition 2 is that instead of solving the primal problem, it is possible to construct deterministic controls for the CE heuristic by solving the dual problem at each step. In many cases the dual problem can be efficiently solved (e.g., using first-order methods)

because it is always guaranteed to be convex and finite dimensional. For all ρ > 0, we show in the same result that the dual problem admits an optimal solution µ * ∈ arg min µ∈R L + Ψ ρ (µ). A primal control can be constructed by solving, for each context θ ∈ Θ, for an action a * θ ∈ A * θ (µ * ) = arg max a∈A r(θ, a) -µ * ȳ(θ, a) . In other words, optimal actions maximize rewards minus the opportunity cost of consuming resources, where resources are priced according to the optimal dual variable µ * . We notice here that in some cases, such as the problem of dynamic bidding in repeated auctions ( §3.2, §6.2), once dual variables are available, an optimal action can be computed in closed form.

The assumptions presented above are stated in terms of g θ (µ), which are derived objects, and, in general, might not be easy to verify. We now present sufficient conditions on the primitives of the problem for Assumptions SC 4 to hold. SC 5. Almost surely over θ ∈ Θ, the expected reward function r(θ, a) is upper-semicontinuous in a and the expected resource consumption function ȳ(θ, a) is continuous in a. SC 6. Almost surely over θ ∈ Θ, the set of optimal actions A * θ (µ) is non-empty and the set of optimal resource consumptions {ȳ(θ, a * ) : a * ∈ A * θ (µ)} is a singleton for every µ.

Proposition 3. If the set of actions A is compact and conditions SC 5 and SC 6 hold, then condition SC 4 is fulfilled.

The proof of Proposition 3 follows directly from Corollary 4 of [START_REF] Milgrom | Envelope theorems for arbitrary choice sets[END_REF]. When the set of actions is finite, the continuity conditions SC 5 trivially hold, and we only require that the set of optimal resource consumptions is a singleton. For the latter condition to hold, one needs that the set of contexts is uncountable. It follows from Proposition 3 that if A is compact and SC 5 and SC 6 hold, then there is an optimal deterministic solution to the fluid problem (P FLUID ).

Dual-based sufficient conditions for Assumption 2

In addition to condition SC 4, we need to make another regularity assumption over the function g, stated below, to ensure Assumption 2 holds for these particular cases of DRC 2 .

SC 7. There exist positive real numbers κ and ν, with ν < µ = min l∈C µ 1 l , such that for all

µ ∈ N (µ 1 , ν) ∩ R L + , g(µ) satisfies g(µ) ≥ g(µ 1 ) + ∇g(µ 1 ) (µ -µ 1 ) + κ 2 µ -µ 1 2 . ( 7
)
In what follows we will refer to property (7) as g admitting a κ-lower upward quadratic (κ-LUQ)

envelope in N (µ 1 , ν). See Figure 4 (b) for an example of a function admitting a κ-LUQ and its envelope. 3 The next assumption provides a sufficient condition to guarantee that the resources that are not binding at the initial resource vector ρ 1 remain not binding if we locally perturb resource availability. The condition is stated in terms of the derivative of the dual function, but can be understood as requiring that resources that are not binding have sufficient "slack."

SC 8. For each µ ∈ N (µ 1 , ν) ∩ R L + and ρ j ≥ ρ j,1 -νκ/2, it holds that ∂g ∂µ j (µ) + ρ j > 0 for resources j ∈ U, where U = {j ∈ [L] : µ 1 j = 0} is the set of resources with zero initial dual variables.

Lemma 3. Suppose that Assumptions SC 4, SC 7, and SC 8 hold. Then Assumption 2 holds with K = 1/κ and δ = (νκ)/2.

A proof is provided in Appendix C.4. To prove the result we need to show that the two conditions of Assumption 2 hold for ρ ∈ N (ρ 1 , δ, C), i.e., J(ρ) admits a lower downward quadratic envelope and that all resources that are binding at ρ 1 remain binding at an optimal solutions in a neighborhood of ρ 1 . Some intuition can be gleaned in light of well-known duality results between strong convexity and strong smoothness (see, e.g., [START_REF] Kakade | On the duality of strong convexity and strong smoothness: Learning applications and matrix regularization[END_REF]. The proof of Lemma 3, however, is more delicate because our quadratic envelope condition is local. We prove the result by extending the envelope condition to hold globally over the dual domain and then optimizing over its convex envelope. For the second condition, we show that for every ρ ∈ N (ρ 1 , δ, C) the dual optimal solutions are strictly positive for resources C that are binding at the initial resource vector and zero for the other resources that are not binding. The condition would then follow from complementary slackness.

We obtain the following result as a corollary.

Corollary 2. Suppose that Assumptions 1, SC 4, SC 7, and SC 8 hold. Then, the reward loss of the certainty equivalent heuristic is of logarithmic order in T .

ρ Recall that in the case of a finite set of contexts and actions (cf. §5.1), in contrast, it was not necessary to assume that the dual function admits a κ-LUQ envelope (condition SC 7). As we can see in Figure 3 (b), a lower upward quadratic envelope is obtained for free when the optimal dual solution is unique and the context and action sets are finite because the dual problem is piece-wise linear.

J(ρ) ρ 1 (

Example 1: Continuum of actions

As a first example of the theory, we consider settings in which the set of actions A is a continuum (contexts can be either finite or not). Examples of applications with continuous actions include, for example, network dynamic pricing problems with finite segments and a continuum of prices, and dynamic bidding in repeated auctions with budgets. To simplify the exposition we assume that all resources are binding at the initial resource vector by imposing that µ 1 > 0 and give sufficient conditions on the primitives for SC 7 to hold. In this case, we shall prove that g θ (µ) admits a lower upward quadratic envelope for each context θ and then simply take expectations over the contexts to establish that SC 7 holds. We do so by imposing envelope conditions on the reward and consumption functions.

For each θ ∈ Θ, let us denote by a 1 θ a feasible action that maximizes r(θ, a) -(µ 1 ) ȳ(θ, a). We will assume the following extra conditions in order to bound the reward loss. These conditions need only hold almost surely over the distributions of contexts. SC 9. The feasible action a 1 θ is interior. That is, there exists a positive number ϕ such that N (a 1 θ , ϕ) ⊆ A almost surely over θ in Θ.

SC 10. The expected reward function r(θ, •) admits a κ r -LDQ envelope in N (a 1 θ , ϕ). That is, almost surely over θ ∈ Θ, r(θ, a) ≥ r(θ,

a 1 θ ) + ∇r(θ, a 1 θ ) (a -a 1 θ ) - κ r 2 a -a 1 θ 2 ∀a ∈ N (a 1 θ , ϕ).
SC 11. There exists a positive vector κ y such that almost surely over θ ∈ Θ and a ∈ N (a 1 θ , ϕ) the consumption function ȳ(θ, •) satisfies

ȳ(θ, a) ≤ ȳ(θ, a 1 θ ) + ∇ȳ(θ, a 1 θ )(a -a 1 θ ) + κ y 2 a -a 1 θ 2 , ( 8
)
where ∇ȳ(θ, •) represents the Jacobian matrix.

We will refer to property (8) as the consumption function ȳ(θ, •) admitting a κ y -upper upward quadratic (κ y -UUQ) envelope in N (a 1 θ , ϕ). 4 Analogously to the relation made with the lower downward quadratic envelope notion, a sufficient condition for Assumption SC 11 to hold is that the gradient ∇ȳ j (θ, •) is locally Lipschitz continuous for every resource j ∈ [L].

Given a real-valued matrix A, we denote by A = σ max (A), where σ max (M ) represents the largest singular value of matrix M . Recall that given a real-valued matrix A, its singular values are the square roots of the eigenvalues of matrix A A. We are now ready to provide sufficient conditions for Assumption SC 7 to hold.

Lemma 4. Suppose that Assumptions SC 5-SC 11 hold. Then, if A is compact, SC 7 holds with ν = κϕ/σ and κ = κ r + (ν + µ 1 ) κ y where σ = inf θ∈Θ σ θ , with σ θ the minimum singular value of ∇ȳ(θ, a 1 θ ).

A proof is provided in Appendix C.5. We obtain the following result as a corollary.

Corollary 3. Suppose that there is a continuum set of actions. Furthermore, suppose that Assumption 1 and Assumptions SC 5-SC 11 hold. If the set of feasible actions A is compact and µ 1 > 0, the reward loss of the certainty equivalent heuristic is of logarithmic order in T .

Example 2: A continuum of contexts with binary actions

We now consider problems with a continuum of contexts and binary actions. These problems naturally emerge in a variety of applications, dating back to the early network revenue management formulation of [START_REF] Talluri | An analysis of bid-price controls for network revenue management[END_REF] in which the context is the fare offer of a customer, to the special case of multi-secretary problems and knapsack problems in which the context is the ability of the applicant and the type of items, respectively (see, e.g., Lueker 1998 and Bray 2022

for formulations with a continuum of contexts). To simplify the exposition, we restrict attention to the case of binary actions-similar results can be derived when multiple actions are available to the decision maker. Additionally, we assume that all resources are binding at the initial resource vector by imposing that µ 1 > 0.

We denote the set of actions by A = {0, 1}, i.e., the decision maker can either accept (a = 1)

or reject (a = 0) each opportunity. We assume that the null action is a = 0 and to simplify the notation we denote by r(θ) = r(θ, 1) and ȳ(θ) = ȳ(θ, 1) the expected reward and resource consumption of accepting an opportunity, respectively. (The reward and resource consumption of rejecting are zero.) Resource consumption is non-negative, i.e., ȳ(θ) ≥ 0. Moreover, we have that g θ (µ) = max r(θ) -µ ȳ(θ), 0 . We assume that the distributions of contexts is such that only one action is optimal with probability one.

SC 12. For every µ ≥ 0, we have that P θ∼p r(θ) = µ ȳ(θ) = 0.

In the case of a continuum of contexts with binary actions, condition SC 5 trivially holds.

Moreover, under SC 12 we have that the set of maximizers A * θ (µ) is unique almost surely over the contexts θ and SC 6 holds. Therefore, by Proposition 3, we readily obtain that condition SC 4 is fulfilled. Thus, strong duality holds and the fluid problem admits an optimal deterministic control.

The functions g θ (µ) are piecewise linear and, thus, do not admit lower upward quadratic envelopes as in the case of a continuum of actions. When there is a continuum of contexts, however, we can establish that the expected function g(µ) = E θ∼p [g θ (µ)] admits a lower upward quadratic envelope because the convolution over contexts smoothes out kinks.

Our next assumption imposes that the density of rewards is bounded from below or, equivalently, its distribution is strictly increasing, which is required for contexts to act as mollifiers.

SC 13. There exists a positive real number p such that for every measurable set R ⊂ [0, r∞ ] and consumption vector 0 ≤ y ≤ ȳ∞ , we have that

P θ∼p {r(θ) ∈ R | ȳ(θ) = y} ≥ p • |R|.
Our final assumption imposes that there is enough variation in resource consumption. This condition is trivially satisfied when we have one resource. When we have multiple resources, it guarantees that the dual function is strongly convex by preventing it from being constant along fixed directions.

30

Electronic copy available at: https://ssrn.com/abstract=3963265 SC 14. There exists some positive reals ν > µ 1 and λ such that the minimum eigenvalue of the positive definite matrix E θ∼p ȳ(θ)ȳ(θ) 1 y(θ) µ 1 + ν y(θ) ≤ r∞ ∈ R L×L is at least λ.

We are now ready to provide sufficient conditions for Assumption SC 7 to hold.

Lemma 5. Suppose that Assumptions SC 12-SC 14 hold. Then, SC 7 holds with κ = pλ and ν.

A proof is provided in Appendix C.6. We obtain the following result as a corollary.

Corollary 4. Suppose that there are two actions and the set of contexts is a continuum. Furthermore, suppose that Assumptions SC 12-SC 14 hold. If µ 1 > 0, the reward loss of the certainty equivalent heuristic is of logarithmic order in T .

CE Heuristic Performance: Corollaries Across Subclasses of Problems

In this section we revisit the applications discussed in §3. Using the results from §5, we discuss sufficient conditions for Assumption 2 together with the resulting performance characterization of the CE heuristic; the detailed sufficient conditions are presented in Appendix D. We then comment on the specific connections to the existing literature in the study of the CE heuristic.

Network Dynamic Pricing

This class of problems was presented in §3.1. As highlighted there, this is a central class of problems widely studied. For simplicity we assume for now that contexts are finite-similar results can be provided when there is a continuum of contexts.

When the set of prices is a continuum, in Appendix D.1, we present sufficient conditions on the primitives that allow to leverage Lemma 3 to ensure that Assumption 2 holds with values of K > 0, δ and ν. Therefore, we can use Corollary 2 to deduce that the revenue loss of the certainty equivalent heuristic is of order O(log T ) for the network dynamic pricing problem with a continuum set of feasible prices. Another implication of our result is that the optimal pricing policy associated with the deterministic proxy is deterministic and the decision maker does not need to randomize over posted prices.

Finally, note that, if we consider a finite set of feasible prices, the fluid problem reduces to a finite linear program and the sufficient conditions from Section 5.1 guarantee constant revenue loss for the CE heuristic. Conversely, if we have finite prices but a continuum contexts, then it is possible to guarantee O(log T ) reward loss in a variety of cases by invoking results similar to those in Section 5.2.4.

Connection with earlier analysis of the CE heuristic. The CE heuristic for this problem was previously analyzed in [START_REF] Maglaras | Dynamic pricing strategies for multiproduct revenue management problems[END_REF] and [START_REF] Jasin | Reoptimization and self-adjusting price control for network revenue management[END_REF]. The former established that a CE heuristic for the pricing problem will always yield an asymptotic weak decrease in the revenue loss compared to a static control. [START_REF] Jasin | Reoptimization and self-adjusting price control for network revenue management[END_REF] considers a single customer class and presents a certainty equivalent heuristic akin to the CE one. Our general result recovers the bound in Jasin [2014] on the logarithmic revenue loss but our sufficient conditions are weaker than his. It is worth mentioning that this problem is typically analyzed in the demand space in the literature, i.e., for each class θ, the decision variables are the expected demands λ = D(θ, a) instead of the prices a (see, e.g., Jasin 2014). In many cases, this leads to a more tractable problem because constraints become linear and, under additional conditions, the objective becomes concave. However, further assumptions are needed for this reformulation of the problem to go through. For example, it is typically assumed that the reward function is concave in the demand space and the demand function is invertible. Our result yields similar performance guarantees for the CE heuristic and only requires local smoothness properties of the revenue function, which typically leads to weaker assumptions. This is an important departure from previous work, even when specializing the analysis. We see here, how by lifting the formulation to a DRC 2 problem, we are not only able to recover existing results through a generalized argument, but also to weaken the assumptions needed for such results to hold.

Dynamic Bidding in Repeated Auctions

This class of problems was presented in §3.2. In Appendix D.2, we characterize an optimal bidding strategy in terms of an optimal bidding function for the static auction without budget constraints.

Moreover, we study the particular cases of second-price and first-price auctions, providing sufficient conditions on the primitives of the problem for conditions SC 4 and SC 7 to be satisfied, leading to a revenue loss of logarithmic order in T for these problems.

Connection with earlier analysis of the CE heuristic. While the problem of bidding in repeated auctions with budgets has been studied in the past (see, e.g., [START_REF] Abhishek | Optimal bidding in multi-item multislot sponsored search auctions[END_REF]Hosanagar 2013, Balseiro et al. 2015), to the best of our knowledge, this is the first result that characterizes the reward loss of a certainty equivalent heuristic with resolving for the advertiser's decision problem.

We note here that this problem is an important illustration of the value of the unified DRC 2 model we propose and the associated highly general sufficient conditions for the logarithmic loss of the CE heuristic. Even more, we note that our analysis does not require convexity assumptions to hold.

Network Revenue Management

This class of problems was presented in §3.3. Note that here, in contrast to the two problems exposed before, the set of actions is finite (binary). In the case of finite contexts, we present, in Appendix D.3, a closed-form expression for the value of δ based on the primitives of the problem (notice that here K = 0). When there is a continuum of contexts5 , one may use the analysis in §5.2.4 and the associated sufficient conditions to observe that the CE heuristic will guarantee logarithmic reward loss under a variety of settings.

Connection with earlier analysis of the CE heuristic. The question of approximating optimal performance through simple policies has also received significant attention around the network revenue management problem. [START_REF] Jasin | A re-solving heuristic with bounded revenue loss for network revenue management with customer choice[END_REF] consider a more general version of the NRM problem than ours with finite contexts (they consider a NRM problem with customer choice), and provide a constant revenue loss guarantee for the CE heuristic under the nondegeneracy assumption. In that sense, we recover their result for the setting where there is no customer choice.

Bray [2022] studies a NRM problem with a continuum of contexts and obtains logarithmic reward loss under some regularity conditions and assumptions that imply SC 4 and SC 7, namely the local strong convexity and smoothness of the adjusted reward function. The set of sufficient conditions in Bray [2022] are stated in terms of the Hessian matrix of the adjusted reward function, whereas the set of conditions in Section 5.2.4 are directly stated in terms of problem primitives.

He considers a policy similar to the CE heuristic that in each period burns a certain amount of the resources that are not binding to prevent their inventory levels from drifting and make the sequence of remaining inventory follow a martingale. Lueker [1998] derives a logarithmic reward loss bound for online knapsack problems under conditions related to the ones we present. When specialized to the case of the multi-secretary problem his Condition 1 implies our Assumption 1; the first part of his Condition 2 implies that µ 1 > 0 and the second part implies a local version of SC 13; and his Condition 3 implies SC 12. [START_REF] Wu | Algorithms with logarithmic or sublinear regret for constrained contextual bandits[END_REF] study a variant with one resource in which the decision maker can take one of many actions (not just accept/reject) and show that the CE heuristic attains constant revenue loss under non-degeneracy while O( √ T ) revenue loss under degeneracy. [START_REF] Bumpensanti | A re-solving heuristic with uniformly bounded loss for network revenue management[END_REF] assume that arrivals follow a Poisson process and show that the CE heuristic could have a Θ( √ T ) revenue loss when the fluid problem at ρ = C/T is degenerate, which highlights the necessity of the non-degeneracy assumption for the loss considered here (we further comment on alternative losses in §7).

2015, Andrews et al. 2019), to the best of our knowledge, our result is the first that provides guarantees for the CE heuristic.

Concluding Remarks

In this paper, we show that several classical dynamic optimization problems, which are usually studied separately in the literature, possess structural similarities that allow them to be studied under a common framework. More explicitly, we introduce a large class of problems, that we called DRC 2 , which encompasses many notable problems that have been studied individually in the literature.

In addition to presenting this novel, unified model, we exploit the common features of problems in the DRC 2 class to study the performance of a fluid certainty equivalent control heuristic. More specifically, we establish some sufficient conditions to obtain good performance guarantees (see §4- §5), which depend on whether the set of contexts or actions are finite or a continuum. We provide general conditions under which the CE heuristic guarantees constant or logarithmic reward loss.

This leads us to recover a variety of existing results for some of the classical problems in DRC 2 , sometimes under weaker conditions, but also to obtain new ones for others (see §6). [START_REF] Wang | Constant regret re-solving heuristics for price-based revenue management[END_REF] to evaluate the performance of the CE heuristic in a dynamic pricing problem. We also refer the reader Vera et al. [2021] for a novel framework that allows using various information augmented benchmarks, enabling to obtain constant reward loss across a broad family of problems.

A second important and related avenue is to study alternative heuristics at the DRC 2 level and weaken the assumptions required for strong performance. For instance, for the dynamic pricing problem [START_REF] Jasin | Reoptimization and self-adjusting price control for network revenue management[END_REF] shows it is possible to attain revenue losses of similar order using a heuristic that solves a single optimization problem at the beginning of the selling horizon and then adjusts controls linearly. There has also been an important stream of recent papers that consider the

35

Electronic copy available at: https://ssrn.com/abstract=3963265

hindsight optimum benchmark while also relaxing the non-degeneracy assumption in the NRM problem. Reiman and [START_REF] Martin | An asymptotically optimal policy for a quantity-based network revenue management problem[END_REF] propose a heuristic that resolves the deterministic problem once at a judiciously chosen time that obtains a revenue loss of order o( √ T ). In a related setting, [START_REF] Bumpensanti | A re-solving heuristic with uniformly bounded loss for network revenue management[END_REF] propose a heuristic that has a O(1) revenue loss. The idea is to resolve the deterministic problem only a few selected times, using the approach of Reiman and Wang

[2008] recursively, while applying thresholds to the controls. Vera and Banerjee [2021] propose a meta-algorithm based on statistical predictions of the hindsight benchmark that leads to a constant upper bound on the revenue loss for NRM and online matching problems. Thus, an interesting question is whether existing arguments and analyses for these particular problems and heuristics can be lifted to derive similar results for the broader class of DRC 2 problems that accommodates, e.g., a continuum of actions.

Performance bounds in the literature are typically instance dependent which makes it hard to directly compare different algorithms. For example, some algorithms might have better dependence on the length of the horizons but worse dependence on other important parameters such as the size of the action space or the number of resources. A third important direction is to investigate the impact of different parameters, either numerically or analytically, on the performance of the algorithms proposed in the literature.

A fourth direction pertains to further expanding the class of DRC 2 problems for which a unified analysis is possible. One direction could be to include additional flexibility in inventory evolution and decisions. For instance, [START_REF] Vera | Dynamic resource allocation: The geometry and robustness of constant regret[END_REF], in the context of a NRM problem, consider possible replenishment of resources and/or the possibility of delays in serving requests, and proves a constant reward loss of a policy that involves re-solving the fluid problem at each time period.

Finally, another promising direction would be to relax informational assumptions and understand if algorithms that jointly learn and optimize can be analyzed in a unified manner in the DRC 2 class.

A Additional material

A.1 Idiosyncratic shock

The goal of this section is to show that we can assume, without loss of generality, that the probability distribution of the idiosyncratic shock is independent of the action and the context. To this end, we assume that for each context θ and each action a, we have a random shock θa lying in a space E θa and drawn from a distribution f θa . We denote by r(θ, a, θa ) and y(θ, a, θa ) the reward and consumption functions, respectively. It is enough to show that there exists a random variable with probability distribution f , independent of θ and a, and functions r and ȳ such that r(θ, a, ) has the same distribution as r(θ, a, θa ) and ȳ(θ, a, ) has the same distribution as y(θ, a, θa ). We first introduce the following technical lemma.

Lemma A-1. Let X be a random variable with distribution F . If G : (0, 1) → R is defined as the

generalized inverse of F , that is G(y) = inf{x : F (x) ≥ y}, and Y ∼ U (0, 1), then Z = G(Y ) has distribution F .
Proof. We have to show that Z ∼ F. Let x be such that F (x) ∈ (0, 1) and let y ∈ (0, 1). Note that y ≤ F (x) if and only if G(y) ≤ x, where one of the directions holds because F is right continuous and the other by definition of the generalized inverse of F . Then,

P(Z ≤ x) = P(G(Y ) ≤ x) = P(Y ≤ F (x)) = F (x),
where the first equality follows from the definition of Z, the second holds because of the observation above, and the last equality holds because Y ∼ U (0, 1).

Applying Lemma A-1 with X = θa and Y = uniformly distributed in (0, 1), it follows that G θa ( ) ∼ f θa , where G θa is the generalized inverse of f θa . Therefore, defining r(θ, a, ) := r(θ, a, G θa ( )) and ȳ(θ, a, ) := y(θ, a, G θa ( )), we obtain that has a probability distribution independent of θ and a, and r(θ, a, ) and ȳ(θ, a, ) has the same distributions as r(θ, a, θa ) and y(θ, a, θa ), respectively.

Above, we assumed that the idiosyncratic shock is univariate. If we assume that for each context θ and action a the random shock θa = ( 1 θa , . . . , D θa ) is a D-dimensional random vector with joint distribution f θa and marginals f i θa , we can generate it by sampling sequentially from the conditional distributions. More specifically, we first generate the random variable X 1 with distribution function f 1 θa by using the procedure described for the univariate case. Then, we consider the conditional distribution of 2 θa given that X 1 = x 1 , denoted by f 2 θa ( • |x 1 ) and we generate the random variable X 2 with distribution f 2 θa ( • |x 1 ). Then, we consider the conditional distribution of 3 θa given that

App-2

Electronic copy available at: https://ssrn.com/abstract=3963265

X 1 = x 1 and X 2 = x 2 , denoted by f 3 θa ( • |x 1 , x 2
), and we generate the random variable X 3 with distribution f 3 θa ( • |x 1 , x 2 ), and so on and so forth. For more details on the algorithm to generate random vectors using conditional distributions we refer the reader to [START_REF] Johnson | Multivariate Statistical Simulation[END_REF].

A.2 Approximate solution of Problem P FLUID One of the goals of this paper is to study the performance of the certainty equivalent heuristic described in Section 4 for the class of DRC 2 problems. This heuristic uses, at each time period, an optimal solution of a fluid problem. However, for some applications the fluid problem could be computationally intractable and then it is important to develop guarantees when only an approximately optimal solution is available. We develop such guarantees in this section.

To this end, consider Algorithm 1 with φ * ρt a feasible solution of Problem P FLUID with ρ = ρ t satisfying the second statement of Assumption 2 and such that θ∈Θ p θ A E (r(θ, a, ))dφ * ρt ≥ J(ρ t ) -α t , that is, an α t -approximate solution of Problem P FLUID for ρ = ρ t . Then, if we denote by J CE (C, T ) the expected performance of Algorithm 1 and a CE t the action taken by the CE heuristic at time t, we have that

J CE (C, T ) = E T t=1 r(θ t , a CE t , t ) ≥ E τ t=1 r(θ t , a CE t , t ) = E τ t=1 θ∈Θ p θ A E (r(θ, a, ))dφ * ρt ≥ E τ t=1 J(ρ t ) - T t=1 α t ,
where τ is the first time that a resource is close to depletion or ρ t leaves the ball defined in Assumption 2. The first inequality follows from dropping the performance after the stopping time τ , the second equality follows from the optional stopping theorem, and the last inequality because our controls are approximately optimal.

Therefore, it holds that J * (C, T ) -J CE (C, T ) ≤ J * (C, T ) -E τ t=1 J(ρ t ) + T t=1 α t , and applying the same arguments as in proof of Theorem 1 we obtain the same guarantee plus the sum of the approximation errors. Thus, it is enough that T t=1 α T = O(1) or equivalently take 1/T -approximate solutions of Problem P FLUID in Algorithm 1 to have the same guarantee as in Theorem 1.

A.3 Finite set of actions

Problem 6 is a linear program. In particular, introducing the set of slack variables {x 1 . . . x L }, the standard form is given by App-3

Electronic copy available at: https://ssrn.com/abstract=3963265

J(ρ) = max Θ θ=1 p θ rθ φ θ s.t θ∈Θ p θ ȳlθ φ θ + x l = ρ l ∀l ∈ [L] a∈A φ θ (a) = 1 ∀θ ∈ Θ φ θ (a) ≥ 0 ∀θ ∈ Θ, ∀a ∈ A x l ≥ 0 ∀l ∈ [L]. (A-1)
B Proofs of Section 4

B.1 Proof of Proposition 1

Proof of Proposition 1. We divide the proof into three steps. First, we consider a dynamic feasible policy for the stochastic problem (P) and we use it to define a static randomized policy. Then, we prove that this static policy is a feasible solution of the fluid problem for ρ = C/T and that the value attained by this feasible solution is the same as the value of the stochastic problem, divided by T . Finally, we obtain the desired result by applying the argument to the optimal solution of (P) and noting that (P FLUID ) is a maximization problem.

Step 1. Let π ∈ Π be a feasible policy for the stochastic problem (P) and a π t (θ t , H t-1 ) the resulting actions, where H t-1 is the history up to (and including) time t -1. Let us define φ : Θ → ∆(A) by

φ θ (A) = 1 T T t=1 E t-1 1 {a π t (θ,H t-1 )∈A}
, where E t-1 (X) denotes the expectation of X with respect to the history up to time t -1.

Let us see that φ is well defined:

1. Non negativity. It follows directly from the definition that for every θ ∈ Θ and A ∈ A,

φ θ (A) ≥ 0. 2. Measure of A. Notice that φ θ (A) = 1 T T t=1 E t-1 1 {a π t (θ,H t-1 )∈A} = 1 T T t=1 E t-1 (1) = 1.
3. σ-additivity. Let {A i : i ∈ I} be a countable, pairwise disjoint collection of elements of A, then App-4

Electronic copy available at: https://ssrn.com/abstract=3963265

φ θ i∈I A i = 1 T T t=1 E t-1 1 {a π t (θ,H t-1 )∈∪ i A i } = 1 T T t=1 P t-1 (a π t (θ, H t-1 ) ∈ ∪ i A i ) = 1 T T t=1 P t-1 i {a π t (θ, H t-1 ) ∈ A i } = 1 T T t=1 i∈I P t-1 (a π t (θ, H t-1 ) ∈ A i ) = i∈I φ θ (A i ),
where the third equality holds because the elements are pairwise disjoint and the fourth equality because P t-1 is a probability measure.

Step 2. In this step, we will check that the probability distribution φ defined in Step 1 is a feasible solution of Problem P FLUID for ρ = C/T and that J π (C, T ) = T J φ (C/T ), where J φ (C/T ) represents the value of the fluid problem for the feasible solution φ.

1. Feasibility. Given the probability distribution φ we need to prove that

θ∈Θ p θ A E (y l (θ, a, )) dφ θ (a) ≤ C l /T, ∀l ∈ [L].
Due to the fact that π is a feasible policy for problem (P), it holds, almost surely, that

T t=1 y l (θ t , a π t , t ) ≤ C l , ∀l ∈ [L].
Then, the inequality above also must hold in expectation, that is:

T t=1 E θt∼p,a π t ∼P t-1 , t∼f (y l (θ t , a π t , t )) ≤ C l , ∀l ∈ [L].
Note that for each l ∈ [L], we have that

T t=1 E θt∼p,a π t ∼P t-1 , t∼f (y l (θ t , a π t , t )) = T t=1 θt∈Θ p θt A E t (y l (θ t , a, t )) dP t-1 (a π t (θ t , H t-1 ) ∈ a) = θ∈Θ p θ A E (y l (θ, a, )) d T t=1 P t-1 (a π t (θ t , H t-1 ) ∈ a) = T θ∈Θ p θ A E (y l (θ, a, )) dφ θ (a), App-5
where the first equality follows from definition of expectation, the second equality holds because the distributions of contexts and shocks are independent and identically distributed and the last equality follows from the definition of φ.

Putting all together, we obtain that

T θ∈Θ p θ A E (y l (θ, a, )) dφ θ (a) ≤ C l , ∀l ∈ [L],
which is the desired inequality.

2. Equality. Notice that

J π (C, T ) = T t=1 E θt∼p,a π t ∼P t-1 , t∼f (r(θ t , a π t , t )) .
And using the same arguments as before, we obtain

J π (C, T ) = T θ∈Θ p θ A E (r(θ, a, )) dφ θ (a),
which is exactly T J φ (C/T ).

Step 3. Fix δ > 0 and let π be an δ-approximately optimal solution of Problem P, i.e., J π (C, T ) ≥ J * (C, T ) -δ. Applying Step 1 to π we define a feasible solution to the fluid problem φ. Therefore, we conclude that

J * (C, T ) ≤ J π (C, T ) + δ = T J φ (C/T ) + δ ≤ T J(C/T ) + δ,
where the first equality follows from Step 2 because J π (C, T ) = T J φ (C/T ), and the second inequality because, by Step 2 again, φ is a feasible solution of Problem P FLUID for ρ = C/T . The result is obtained because δ was arbitrary.

B.2 Proof of Theorem 1

The goal of this section is to prove Theorem 1, which is our main result regarding the performance of the heuristic CE for the set of DRC 2 problems. To do that, we assume that Assumption 1 and Assumption 2 hold and we first introduce some processes and random variables, as well as technical results, that will be useful to obtain the desire result.

In what follows we will denote by y t the resource consumption at time t if the decision maker follows the policy π CE . That is, y t = y(θ t , a π CE t , t ). Let us consider the process {M t } t≥1 up to

App-6

Electronic copy available at: https://ssrn.com/abstract=3963265 time T consisting in, at each time period, the accumulated difference between the resource vector consumption and its expectation, divided the remaining horizon. More specifically, for each t ∈ [T ],

M t = t s=1 E (y s |ρ s ) -y s T -s .
Let us define the stopping time τ. To this end, we need to introduce two random variables. On one hand, we define τ δ to be the first time t such that M t has 2 -norm greater than or equal to δ, where δ is defined in Assumption 2. That is,

τ δ = min t∈[T ] {t : M t ≥ δ} .
If M t is at most δ for all t ∈ [T ], we set τ δ = ∞. On the other hand, we define τ -as the first time at which there exists a resource such that its consumption under the policy φ * ρt is close to over capacity. That is,

τ -= min t∈[T ] t : ∃ l ∈ [L] s.t. c t,l -y l (θ t , a φ * ρ t , t ) < ȳ∞ .
As above, if c t,l -y l (θ t , a φ * ρ t , t ) is greater or equal to ȳ∞ for all t ∈ [T ] and l ∈ [L], we set τ -= ∞. Then, we define the random variable τ as the minimum between τ δ and τ -, and the number of periods T , i.e., τ = min {τ δ , τ -, T } .

Because y(θ t , a φ * ρ t , t ) ≤ ȳ∞ by Assumption 1, we have that the actions of the policy up to time τ - are not constrained by resources and they are taken according to an optimal solution of the fluid problem. To see this, note that if t = τ -, then c t,l = c t-1,l -y l (θ t-1 , a φ * ρ t-1 , t-1 ) ≥ ȳ∞ and, thus, c t,l -y l (θ t , a φ * ρ t , t ) ≥ 0. Note that both τ δ and τ -are stopping times with respect to the filtration {F t } t≥1 , with F t = σ(θ 1 , . . . , θ t , a 1 , . . . , a t , 1 , . . . , t ), the history up to the end of period t, and thus we obtain that τ is also a stopping time with respect to the same filtration {F t } t≥1 . Furthermore, the process {M t } t≥1 is a martingale with respect to the filtration {F t } t≥1 . In fact, for each t, from Assumption 1.2 follows that E(y t |ρ t ) -y t ≤ ȳ∞ < ∞, and therefore E( M t ) < ∞ for all t. On the other hand, for each t, it holds that

M t+1 -M t = E(y t+1 |ρ t+1 ) -y t+1 T -t -1 App-7
Electronic copy available at: https://ssrn.com/abstract=3963265

and E (E(y t+1 |ρ t+1 ) -y t+1 |F t ) = 0, concluding that

E(M t+1 |F t ) = M t ∀t ≥ 1.
Since {M t } t≥1 is a martingale and τ an stopping time, it turns out that the stopped process {M t∧τ } t≥1 is also a martingale with respect to the filtration {F t } t≥1 .

We are now ready to present some properties for the process and the stopping time defined above, which will be needed to prove the bound for the reward loss.

Lemma B-1. Under Assumption 2, if t is at most τ δ , it holds that:

1. (ρ t+1 -ρ 1 )| C = M t | C and (ρ t+1 -ρ 1 )| U ≥ M t | U 2. (ρ t -ρ 1 )| C < δ and (ρ t -ρ 1 )| U ≥ -1δ.
Proof of Lemma B-1. We will proceed by induction on t, dividing the proof into two steps, the first corresponds to prove the base case and the other the induction step.

Step 1. Note that for t = 1, statement 2 of the lemma follows trivially and we are then under the hypothesis of Assumption 2, obtaining E(y

1 |ρ 1 )| C = ρ 1 | C and E(y 1 |ρ 1 )| U ≤ ρ 1 | U . Therefore, we can express M 1 | C and bound M 1 | U as follows: M 1 | C = (E(y 1 |ρ 1 ) -y 1 )| C T -1 = ρ 1 | C -y 1 | C T -1 , (B-1) M 1 | U = (E(y 1 |ρ 1 ) -y 1 )| U T -1 ≤ ρ 1 | U -y 1 | U T -1 (B-2)
From the definition of ρ 1 and ρ 2 , we have that y 1 = ρ 1 Tρ 2 (T -1) and replacing in (B-1) and (B-2) follows that

M 1 | C = (ρ 2 -ρ 1 )| C and M 1 | U ≤ (ρ 2 -ρ 1 )| U ,
obtaining the first statement of the lemma and completes the base case.

Step 2. Now, assume that Lemma B-1 holds for all s smaller or equal than a fixed t < τ δ and let us prove that both statements also hold for t + 1.

As in the base case, we will first prove statement 2 and we then use it to prove statement 1.

That is, let us show that (ρ t+1 -ρ 1 )| C < δ and (ρ t+1 -ρ 1 )| U ≥ -1δ. Applying the induction hypothesis to t, it holds that (ρ t+1 -ρ

1 )| C = M t | C and (ρ t+1 -ρ 1 )| U ≥ M t | U . On the other App-8
Electronic copy available at: https://ssrn.com/abstract=3963265 hand, t < τ δ and thus M t < δ, which implies that M t | C < δ and M t | U ≥ -1δ, and the second statement follows.

In the remainder of the proof, we show that (ρ t+2 -ρ

1 )| C = M t+1 | C and (ρ t+2 -ρ 1 )| U ≥ M t+1 | U .
Note that

ρ t+2 -ρ 1 = t+1 s=1 ρ s+1 -ρ s = t+1 s=1 (T -s + 1)ρ s -y s T -s -y s = t+1 s=1 ρ s -y s T -s ,
where the first equality is obtained by using a telescoping sum and the second holds because

ρ s+1 = c s+1 /(T -s), c s = ρ s (T -s + 1
) and c s+1 = c s -y s . By the induction hypothesis, together with the statement 2 we already proved for s = t + 1, it holds that (ρ s -ρ 1 )| C < δ for all s ≤ t + 1.

Therefore we can apply Assumption 2 to the expression above obtaining that

(ρ t+2 -ρ 1 )| C = t+1 s=1 (E(y s |ρ s ) -y s )| C T -s = M t+1 | C .
On the other hand, E(y s |ρ s )| U ≤ ρ s | U and using again the expression above we conclude that

(ρ t+2 -ρ 1 )| U ≥ t+1 s=1 (E(y s |ρ s ) -y s )| U T -s = M t+1 | U .
and the lemma follows.

Since {M t∧τ } t≥1 is a zero mean martingale with respect to the filtration {F t } t≥1 , a direct consequence of Lemma B-1 is that also the stopped process {ρ t∧τ | C } t≥1 is a martingale with respect to the same filtration.

The following lemma is a technical result we need to prove Lemma B-3, which, in turn, states that the expected number of remaining periods after the stopping time τ is bounded by a constant.

Specifically, the following result gives sufficient conditions on t to be a lower bound for the stopping time τ -.

Lemma B-2. Assume that Assumption 1 and 2 hold, and define

T -= T + 1 -2 ȳ∞ ρ 1 -δ , where ρ 1 is the smallest component of vector ρ 1 . If t ≤ T -and t < τ δ , then t < τ -.
Proof of Lemma B-2. Due to the definition of the stopping time τ -, we have to show that for all s ≤ t, the consumption is at most the available capacity (minus the maximum possible consumption), i.e., y(θ s , a φ * ρs , s ) ≤ c s -1ȳ ∞ . Take s ≤ t. By hypothesis, s < τ δ and by Lemma B-1 it holds that (ρ s -ρ

1 )| C < δ and (ρ s -ρ 1 )| U ≥ -1δ. In particular, |(ρ s -ρ 1 ) l | < δ ∀l ∈ C, obtaining ρ s > ρ 1 -1δ , (B-3) App-9
where 1 denotes the vector of ones of size L. On the other hand, note that

c s > (T -s + 1)(ρ 1 -1δ) ≥ 2ȳ ∞ ρ 1 -δ (ρ 1 -1δ) ≥ 2 • 1ȳ ∞ ≥ 1ȳ ∞ + y(θ s , a φ * ρs , s ),
where the strict inequality follows from the definition of ρ s , together with inequality (B-3); the second inequality holds because t ≤ T -and ρ 1 > δ; the third due to the definition of ρ 1 ; and the last because y(θ s , a φ * ρs , s ) ≤ 1ȳ ∞ from Assumption 1.2. We then conclude that τ -is greater than t and the proof is completed.

We next prove that the expected number of remaining periods after the stopping time τ is upper bounded by a constant that does not depend on T , which is a key result to obtain the main theorem.

Lemma B-3. If Assumptions 1 and 2 hold, then E(T -τ ) = O(1). More specifically,

E(T -τ ) < 2ȳ ∞ ρ 1 -δ + 14 ȳ2 ∞ δ 2 .
Proof of Lemma B-3. We will prove the result by bounding the expected value of τ , which is equivalent to the expression ∞ t=1 P(τ ≥ t) because τ is a non-negative random variable. From the definition of τ , the probability of τ being greater than T is zero, and then,

E(τ ) = T t=1 P(τ δ ∧ τ -≥ t) ≥ T --1 t=1 P(τ δ ∧ τ -≥ t) (B-4)
where the last inequality follows just splitting the horizon and because probabilities are nonnegative.

On the other hand,

T --1 t=1 P(τ δ ∧ τ -≥ t) = T --1 t=1 P min s∈[T ] {s : M s ≥ δ} ≥ t = T --1 t=1 P ( M s < δ ∀s ∈ [t]) = T --1 - T --1 t=1 P max s∈[t] M s ≥ δ ,
where the first equality is obtained by Lemma B-2 (since t < T -, τ δ ∧ τ -= τ δ ) and the last one because

P( M s < δ ∀s ∈ [t]) = 1 -P(max s∈[t] M s ≥ δ).

App-10

Electronic copy available at: https://ssrn.com/abstract=3963265

Then, using the equality above in (B-4) it holds that

E(τ ) ≥ T --1 - T --1 t=1 P max s∈[t]
M s ≥ δ .

In the remainder of the proof we will upper bound T --1 t=1 P max s∈[t] M s ≥ δ , and we proceed by applying Theorem 3.5 in [START_REF] Pinelis | Optimum bounds for the distributions of martingales in banach spaces[END_REF]. To this end, note first that (R L , • ) is a separable Banach space, and since x+y + x-y ≤ 2 x 2 +2 y 2 holds for all x, y ∈ R + , it is (2, 1)-smooth.

Define, for each t, the martingale {M t∧s } s≥1 . From the definition of M s it follows that

M s -M s-1 = E(y s |ρ s ) -y s T -s ,
and therefore

t s=1 E(y s |ρ s ) -y s T -s 2 ∞ ≤ (2ȳ ∞ ) 2 T -t ,
where the inequality follows from Assumption 1.2, and using that t

s=1 1/(T -s) 2 ≤ t 0 1/(T -s) 2 < 1/(T -t).
Then, we are under the hypothesis of the theorem mentioned above, and applying it together with the inequality P max s∈[t] M s ≥ δ ≤ 1, we obtain

P max s∈[t] M s ≥ δ ≤ 1 ∧ 2 exp - δ 2 (T -t) 8ȳ 2 ∞ .
Summing over t and using the bound obtained above, we have

T --1 t=1 P max s∈[t] M s ≥ δ ≤ T t=1 2 exp - δ 2 (T -t) 8ȳ 2 ∞ ∧ 1 ≤ T 0 2 exp - δ 2 (T -t) 8ȳ 2 ∞ ∧ 1 dt ≤ 8ȳ 2 ∞ δ 2 (log 2 + 1) ,
where the second inequality follows from bounding the summation by the integral and the last inequality from Lemma E-1.

App-11

Electronic copy available at: https://ssrn.com/abstract=3963265

Putting all together and using that 8(log 2 + 1) ≤ 14 we conclude

E(T -τ ) < T -T -+ 1 + 14 ȳ2 ∞ δ 2 = 2ȳ ∞ ρ 1 -δ + 14 ȳ2 ∞ δ 2 ,
and the desire result is obtained.

The next results shows that increasing the availability of a resource that is not binding should not change the optimal objective value of a the fluid problem.

Lemma B-4. Under Assumption 2, if the consumption constraint corresponding to the resource i is not binding for the problem (P FLUID ) with ρ = ρ 1 , that is i ∈ U, then ∇ J(ρ 1 ) i = 0.

Proof of Lemma B-4. We take i ∈ U and we prove that there exists ∆ ∈ R ++ such that J(ρ 1 ) = J(ρ 1 + e i κ) for all κ ∈ [-∆, ∆], where e i denotes the i-th canonical vector of R L . We divide the proof into two parts: In the first part, we prove that there exists ∆ ∈ R ++ such that J(•) is constant in [ρ 1 -e i ∆, ρ 1 ], whereas in the second part, we prove that increasing the i-th component of ρ 1 , the optimal solution of problem (P FLUID ) does not change and therefore the optimal value is constant.

Part 1. If we denote by φ * the optimal solution of (P FLUID ) with ρ = ρ 1 , by hypothesis we know that ȳi < (ρ 1 ) i , where ȳi = E θ∼p,a∼φ * , ∼f y i (θ, a, ) is the expected resource consumption under φ * .

Thus, φ * is also feasible of (P FLUID ) with ρ = ρ 1 -ξe i for all ξ ∈ [0, (ρ 1 ) i -ȳi ]. Moreover, the feasibility set of the latter problem is contained in the feasibility set of the former, and therefore φ * is an optimal solution of (P FLUID ) with ρ = ρ 1 -ξe i for all ξ ∈ [0, (ρ 1 ) i -ȳi ], obtaining that

J(ρ 1 ) = J(ρ 1 + e i ξ) for all ξ ∈ [ȳ i -(ρ 1 ) i , 0]. (B-5)
Part 2. On the other hand, suppose that there exists κ > 0 such that every optimal solution φ * κ of (P FLUID ) for ρ κ = ρ 1 + κe i satisfies (ȳ κ ) i > (ρ 1 ) i where (ȳ κ ) i = E θ∼p,a∼φ * κ , ∼f y i (θ, a, ) is the expected resource consumption under φ * κ . Fix such an optimal solution φ * κ . Then, we can take a number γ ∈ (0, 1] such that ρ = γ ȳ + (1 -γ)ρ κ ≤ ρ 1 because by hypothesis we know that ȳi < (ρ 1 ) i .

Note that φ = γφ

* + (1 -γ)φ * κ is feasible for (P FLUID ) with ρ = ρ 1 , since E θ∼p,a∼ φ, ∼f y(θ, a, ) = γE θ∼p,a∼φ * , ∼f y(θ, a, ) + (1 -γ)E θ∼p,a∼φ * κ , ∼f y(θ, a, ) = γ ȳ + (1 -γ)ȳ κ ≤ γ ȳ + (1 -γ)ρ κ = ρ ≤ ρ 1 ,

App-12

Electronic copy available at: https://ssrn.com/abstract=3963265 because ȳκ ≤ ρ κ since φ * κ is feasible for ρ κ . Moreover, E θ∼p,a∼ φ, ∼f r(θ, a, ) = γE θ∼p,a∼φ * , ∼f r(θ, a, ) + (1 -γ)E θ∼p,a∼φ * κ , ∼f r(θ, a, ) > γE θ∼p,a∼φ * , ∼f r(θ, a, ) + (1 -γ)E θ∼p,a∼ φ, ∼f r(θ, a, ), where the inequality follows because φ is feasible but not optimal for (P FLUID ) with ρ = ρ κ (i.e., φ cannot be optimal because it consumes less than ρ 1 resources). Because γ > 0, the latter expression implies that E θ∼p,a∼ φ, ∼f r(θ, a, ) > E θ∼p,a∼φ * , ∼f r(θ, a, ), which contradicts that φ * is optimal solution of (P FLUID ) with ρ = ρ 1 .

We therefore have that for every positive number κ, the optimal solution φ * κ satisfies (ȳ κ ) i < (ρ 1 ) i , and therefore must be also solution of (P FLUID ) with ρ = ρ 1 , obtaining that J(ρ 1 ) = J(ρ 1 + e i κ) for all κ > 0.

(B-6)

Taking ∆ = (ρ 1 ) i -ȳi , and using (B-5) and (B-6), we obtain the result.

We are now ready to prove Theorem 1 by combining the technical results already presented.

Proof of Theorem 1. We have to bound J * (C, T )-J CE (C, T ), which is upper bounded by T J(ρ 1 )-

J CE (C, T ) because J * (C, T ) ≤ T J(C/T
) by Proposition 1. Thus, it is enough to bound T J(ρ 1 ) -J CE (C, T ). By dividing the horizon from 1 to τ and from τ to T and dropping the performance of the CE policy after time τ , we obtain

T J(ρ 1 ) -J CE (C, T ) ≤ E τ t=1 J(ρ 1 ) - τ t=1 r(θ t , a CE t , t ) (A) + E T t=τ +1 J(ρ 1 ) (B)
, (B-7)

and we then have to bound (A) and (B), which will be done in Part 1 and Part 2, respectively.

Part 1. We bound (A) by dividing the proof into three steps. First, we show that the expected reward earned up to time τ considering the policy given by the CE heuristic equals the expected reward until time τ of the fluid problem for ρ = ρ t at time t. Let us prove that

E τ t=1 r(θ t , a CE t , t ) = E τ t=1 J(ρ t ) . (B-8) App-13
Electronic copy available at: https://ssrn.com/abstract=3963265

To this end, consider the sequence of zero mean, i.i.d. random variables {X t } t≥1 given by

X t = r(θ t , a CE t , t ) -E θ, r(θ t , a CE t , t )|ρ t .
Then, letting N s = s t=1 X t it holds that {N s } s≥1 is a martingale relative to the filtration {F t } t≥1 previously defined (see e.g. Ross et al. 1996 page 296). Therefore, due to τ being a stopping time with respect to the same filtration, we can apply the Martingale Stopping Theorem (Ross et al. 1996, Theorem 6.6.2), which in turns implies that E (N τ ) = E (N 1 ) = 0. On the other hand, by the definition of the fluid problem, we have that E θ, r(θ t , a CE , t )|ρ t = J(ρ t ) for all t ≤ τ . Then, (B-8) follows from combining these equations.

Second, using (B-8) and applying Assumption 2 (the hypothesis is fulfilled because t ≤ τ and then by Lemma B-1 we have (ρ t -ρ 1 )| C < δ) we obtain

(A) = E τ t=1 J(ρ 1 ) -J(ρ t ) ≤ E τ t=1
-∇ J(ρ 1 )(ρ t -ρ 1 )

(A 1 ) + E τ t=1 K 2 ρ t | C -ρ 1 | C 2 (A 2 )
.

From the linearity of the expectation, for the first term we obtain that

(A 1 ) = -∇ J(ρ 1 )E τ t=1 ρ t -ρ 1 = 0 ,
where we used that {ρ t∧τ | C } t≥1 is a martingale and that ∇ J(ρ 1 ) l = 0 for all l ∈ U by Lemma B-4, and thus the term (A 1 ) vanishes in the bound.

In the third and last step, we bound (A 2 ). Using Lemma B-1 have that

(A 2 ) = K 2 E τ t=2 M t-1 | C 2 ≤ K 2 E T t=2 M t-1 | C 2 = K 2 T t=2 E M t-1 | C 2 ,
where the inequality follows because t ≤ T and using that the summands are positive, and the last from the linearity of expectations. where the inequality follows because Var(X) = E[X 2 ] -E[X] 2 ≤ E[X 2 ] and the last inequality follows from Assumption 1.2.

Using expression (B-9), we finally obtain

(A 2 ) ≤ K 2 ȳ2 2 T t=2 t-1 s=1 1 (T -s) 2 = K 2 ȳ2 2 T -1 s=1 T t=s+1 1 (T -s) 2 = K 2 ȳ2 2 T -1 s=1 1 T -s ≤ K 2 ȳ2 2 (γ + log(T )) ,
where the second equation follows from exchanging the order of summations and the last inequality where the inequality follows from applying Lemma B-3.

Putting everything together. Using (B-10) together with (B-11) in (B-7) we get

J * (C, T ) -J CE (C, T ) ≤ ȳ2 2 K log T + 2ȳ ∞ ρ 1 -δ + 14ȳ 2 ∞ δ 2 J(C/T ),
and the result follows.

App-15

Electronic copy available at: https://ssrn.com/abstract=3963265

where the last equality follows because B is optimal basis of problem (A-1) and v = ρρ 1 .

We then have that J(•) is linear over N (ρ 1 , δ). Notice that if we increase the components of ρ corresponding to the unbinding constraints, then the optimal basis does not change (see Part 2 in the proof of Lemma B-4 ) and therefore the equalities above still holds, obtaining that J(•) is linear over N (ρ 1 , δ, C) and the first statement holds with K = 0.

We proved that taking ρ ∈ N (ρ 1 , δ, C) the optimal basis does not change and therefore the second statement follows directly because the constraints are binding for ρ 1 | C .

Therefore, we conclude that Assumption 2 holds for δ = min(φ * min ,x * min ) B -1 ρ 1

, and K = 0.

C.2 Proof of Lemma 2

Proof of Lemma 2. We want to prove that the problem (6) has a unique non-degenerate optimal solution for ρ = ρ 1 . To this end, we will prove that its dual problem has a unique non-degenerate optimal solution.

Note that if we denote by z θ ∈ R to the dual variable associated to the constraint a φ θ (a) = 1, the dual problem of (6) can be written as follows which has a unique solution µ 1 by Assumption SC 2, and therefore we obtain that the dual problem (C-1) has a unique solution for ρ = ρ 1 . It remains to show that such solution (µ 1 , z 1 ) is not degenerate. To show that, we will prove that there is at most L + |Θ| (number of variables) active constraints. Note that the number of constraints in problem (C-1) is L + |Θ| × |A|. However, by Assumption SC 3 we know that for each θ ∈ Θ, there exists a unique a * θ ∈ A such that z 1 θ = p θ (r θ (a * θ ) -µ ȳθ (a * θ )) and thus p θ µ 1 ȳθ (a) + z 1 θ > p θ rθ (a) ∀a ∈ A \ {a * θ }. We conclude that exactly |Θ| constraints from the first set are binding and therefore there are at most L + |Θ| active

App-17

Electronic copy available at: https://ssrn.com/abstract=3963265 constraints, obtaining the desired result.

C.3 Proof of Proposition 2

Proof of Proposition 2. We divide the proof into two steps. First, we prove that an optimal solution to the dual problem exists, namely µ * . Then, we define φ * properly and we apply Proposition 5.1.5

in [START_REF] Bertsekas | Nonlinear programming[END_REF] to prove that φ * is primal solution and µ * is in fact a Lagrangian multiplier and that therefore there is no duality gap, obtaining the desired result.

Step 1. Note that for each θ ∈ Θ, g θ is convex because it is defined as the supremum of a family of linear functions and therefore the dual problem is a convex problem. Then, the function g is convex because convex combinations of convex functions are convex.

To prove the existence of optimal dual solution µ * , we first prove Ψ ρ is continuous and then we argue that the domain of the dual problem can be restricted to a compact set, achieving the result applying the extreme value theorem. Continuity of the dual function follows because it is differentiable (as we argue in the step 2 below). On the other hand, we can prove that we can restrict the domain of the dual problem to the hypercube [0, μρ ] L , for μρ = r∞ /ρ, where ρ = min l∈[L] ρ l and r∞ is the positive real number provided by Assumption1.1. We have that μρ < ∞ because ρ > 0. Let us check that every µ ∈ [0, μρ ] L is suboptimal. Take µ ∈ [0, μρ ] L , and define L 1 = {l ∈ [L] : µ l > μρ } the components of µ greater than μρ . Then, we have

Ψ ρ (µ) ≥ ρ µ ≥ l∈L 1 ρ l μl = l∈L 1 r∞ ρ l ρ ≥ r∞ ≥ Ψ ρ (0),
where the first inequality holds because r(θ, a 0 ) = ȳ(θ, a 0 ) = 0, for all θ ∈ Θ and therefore g θ (µ) ≥ 0; the second follows from the non-negativity of vectors µ and ρ, the third inequality holds because L 1 contains at least one element and ρ l ≥ ρ, and the last one follows because Ψ ρ (0) = E θ∼p [max a∈A r(θ, a)] and r∞ ≥ r(θ, a) for all θ ∈ Θ, and a ∈ A. Then, we have Ψ ρ (0) ≤ Ψ ρ (µ) and together with the extreme value theorem we conclude that for each ρ > 0 there exist µ * optimal dual solution satisfying µ * ∈ [0, μρ ] L .

Step 2. Given ρ > 0, take µ * an optimal dual solution and, for each θ ∈ Θ, define φ * (θ) a distribution that assigns probability one to an action a * θ ∈ arg max a∈A r(θ, a) -µ * ȳ(θ, a) . Such actions are guaranteed to exist by Assumption SC 4. Let us now show that (φ * , µ * ) is an optimal solution-Lagrange multiplier pair. We will proceed by using Proposition 5.1.5 in [START_REF] Bertsekas | Nonlinear programming[END_REF].

That is, we need to check primal and dual feasibility, Lagrangian optimality and complementary slackness.

App-18

Electronic copy available at: https://ssrn.com/abstract=3963265 1. Primal and dual feasibility. Dual feasibility follows because µ * ≥ 0. For primal feasibility, note that the gradient of r(θ, a) -µ ȳ(θ, a) with respect to µ exists and is given by -ȳ(θ, a).

Because the value function g θ (µ) is differentiable and achieved for some action a * θ , we have from the envelope theorem applied to g θ (see, e.g., Theorem 1 in [START_REF] Milgrom | Envelope theorems for arbitrary choice sets[END_REF], that ∇g θ (µ) = -ȳ(θ, a * θ ). The last statement holds almost surely over θ ∈ Θ. Because g θ (µ) is convex, we obtain from Theorem 7.46 of [START_REF] Shapiro | Lectures on stochastic programming: modeling and theory[END_REF] that g(µ) = E θ∼p [g θ (µ)] is differentiable with gradient ∇g(µ) = -E θ∼p [ȳ(θ, a * θ )]. Therefore, Ψ ρ is differentiable and its gradient evaluated at µ * is given by

∇Ψ ρ (µ * ) = ρ -E θ∼p [ȳ(θ, a * θ )] . (C-2)
Because µ * is an optimal dual solution and the constraint set is convex, by Proposition 2.1.2

in [START_REF] Bertsekas | Nonlinear programming[END_REF], the first-order conditions are given by ∇Ψ ρ (µ * ) (µµ * ) ≥ 0, ∀µ ∈ R L + .

(C-3)

Letting µ l → ∞, we obtain that ∇Ψ ρ (µ * ) ≥ 0, which, in turn, implies that E θ∼p [ȳ(θ, a * θ )] ≤ ρ by (C-2). Primal feasibility follows.

2. Complementary slackness. If µ * l = 0, we trivially have (∇Ψ ρ (µ * )) l µ * l = 0 and complementary slackness follows. If µ * l > 0, we can take ν > 0 with µ * l + ν and µ * l -ν belonging to R + . Using (C-3), we obtain that (∇Ψ ρ (µ * )) l ν ≥ 0 and (∇Ψ ρ (µ * )) l ν ≤ 0. Thus, it holds that (∇Ψ ρ (µ * )) l = 0 and complementary slackness follows. Therefore, the four conditions hold and the proof is complete.

App-19

Electronic copy available at: https://ssrn.com/abstract=3963265

Figure 1 :

 1 Figure 1: Definition of a new large class of dynamic decision problems (DRC 2 ) that encompasses many known problem classes.

Figure 2 :

 2 Figure2: Sufficient conditions and their implications on the performance of the CE heuristic. Throughout, we assume that Assumption 1 holds.

Figure 3 :

 3 Figure 3: Function J and dual function Ψ ρ for two different parameters.

  a) Deterministic proxy function in blue. Its 0.9-LDQ envelope in red. dual function in blue. Its 0.3-LUQ envelope in red.

Figure 4 :

 4 Figure 4: Deterministic proxy J and its Lagrangian dual function, and their envelopes.

  The present work opens many avenues for future research. A first one involves the use of different benchmarks to analyze the performance of the CE heuristic or variations of it. While in this paper we use the fluid problem as a benchmark, some authors consider tighter benchmarks for particular problems in the DRC 2 class. One of them is known as hindsight optimum (see, e.g., Reiman and Wang 2008, Bumpensanti and Wang 2020, Vera and Banerjee 2021), which is the problem obtained when all uncertainties are revealed in advance. This benchmark is usually considered in situations without idiosyncratic shocks such as the network revenue management problem or the online matching problem as knowledge of the idiosyncratic shocks confers too much power to the decision maker. (Stronger bounds can be obtained in the presence of idiosyncratic shocks by only granting the decision maker advance knowledge of the contexts.) Another natural benchmark is the optimal value of the dynamic program, which was recently considered by Wang

  because T -1 s=1 (Ts) -1 = T -1 s=1 s -1 ≤ γ + log(T ), where γ is the Euler-Mascheroni constant. Putting all together we getE log T ) ≤ K ȳ2 2 log(T ) ,(B-10) because γ + log T ≤ log(T ) for T ≥ 2, and the proof of Part 1 is complete. Part 2. It only remains to bound the second term in (B-7). Note that E T t=τ +1 J(ρ 1 ) = E(T -τ ) J(C/T )

  p θ µ ȳθ (a) + z θ ≥ p θ rθ (a) ∀a ∈ A ∀θ ∈ Θ , µ ≥ 0 . (C-1) From the constraints, for each θ ∈ Θ, the dual variable z θ should satisfy z θ ≥ p θ (r θ (a)-µ ȳθ (a)) ∀a ∈ A , and therefore z θ ≥ p θ max a∈A {r θ (a)-µ ȳθ (a)}. Due to (C-1) being a minimization problem, we conclude that the optimal value for the dual variable z θ is given by z 1 θ = p θ max a∈A {r θ (a)-µ ȳθ (a)}. The dual problem is then equivalent to the following problem min a∈A {r θ (a) -µ ȳθ (a)} ,

3.E

  Lagrangian optimality. Note that arg max φ∈Φ L(φ, µ * ) = arg max φ∈Φ µ * ρ + E θ∼p,a∼φ(θ) r(θ, a) -µ * ȳ(θ, a) a∼φ θ r(θ, a) -µ * ȳ(θ, a) equality holds because we can separate the problem for each θ. But note that g θ (µ * ) is maximized at a * θ and thus we have Lagrangian optimality.

Table 1 :

 1

	Elements of the DRC 2 problem

Comparison of some special subclasses of DRC 2 problems. The idiosyncratic shocks are meant to qualitatively capture the underlying exogenous factors associated with each opportunity as opposed to the distribution of the actual random variable .

  Therefore, it is enough to bound E ||M t | C || 2 . Because martingale increments are orthogonal (see e.g. Gut 2013, Chapter 10 Lemma 4.1), we have that s) 2 E (E (y s |ρ s ) -y s )| C Furthermore, by definition of 2 -norm, it holds that E (E (y s |ρ s ) -y s )| C 2 = l∈C E (E (y s,l |ρ s ) -y s,l ) 2 = l∈C E (Var(y s,l |ρ s ))

				≤	E E(y 2 s,l |ρ s ) = E y s | C	2 ≤ ȳ2 2 ,
				l∈C
	E M t | C	2 = E	t s=1	(E (y s |ρ s ) -y s )| C T -s	2	=	t s=1	1 (T 2 .	(B-9)
						App-14

Electronic copy available at: https://ssrn.com/abstract=3963265

We discuss the literature in detail when we discuss our model and present our main results and associated corollaries.

To simplify notation we will write a π t to refer to the action taken at time t given the policy π

Electronic copy available at: https://ssrn.com/abstract=3963265

Admitting a κ-LUQ envelope is a weaker and local notion of the κ-strongly convex condition, which requires (7) to hold for every pair of dual variables µ, µ .

The κy-UUQ envelope condition is a weaker and local notion of the κy-strongly smooth condition for concave functions, which requires (8) to hold for every pair of actions a, a .

Interestingly, the early NRM formulation in[START_REF] Talluri | An analysis of bid-price controls for network revenue management[END_REF] considers a continuum of contexts.

Columbia University, Graduate School of Business. Email: srb2155@columbia.edu.

Columbia University, Graduate School of Business. Email: ob2105@columbia.edu.

Universidad de O'Higgins, Institute of Engineering Sciences. Email: dana.pizarro@uoh.cl.App-1Electronic copy available at: https://ssrn.com/abstract=3963265

The work of Dana Pizarro has benefited from the AI Interdisciplinary Institute ANITI, which is funded by the French "Investing for the Future -PIA3" program under the Grant agreement ANR-19-P3IA-0004.

Choice-Based Network Revenue Management

This class of problems was presented in §3.4. In this case, the set of actions is finite and we obtain a constant bound on the revenue loss of the CE heuristic. For completeness, we give a formulation for the fluid problem in Appendix D.4.

Connection with earlier analysis of the CE heuristic. Our formulation shows that a certainty equivalent heuristic admits strong performance guarantees under Assumption SC 1. This recovers a result from [START_REF] Jasin | A re-solving heuristic with bounded revenue loss for network revenue management with customer choice[END_REF] for a slightly different model with consumer choice.

Online Matching

Here we revisit the problem presented in §3.5. In Appendix D.5, we conduct a similar analysis to the one for the NRM problem with finite contexts. That is, we interpret the value of δ for this class of problems, and we obtain a constant bound for the revenue loss.

Connection with earlier analysis of the CE heuristic. Although the online matching problem has been extensively studied under different settings (see, e.g., [START_REF] Richard M Karp | An optimal algorithm for on-line bipartite matching[END_REF][START_REF] Aggarwal | Online vertex-weighted bipartite matching and single-bid budgeted allocations[END_REF], Vera and Banerjee 2021), to the best of our knowledge, our paper is the first to document the performance of the CE heuristic for the online matching problem. Our analysis yields good performance bounds under the so-called "small bid assumption," which requires that the maximum possible resource consumption in a time period is small relative to the total amount of initial resources. This requirement is implicitly imposed by part 2 of Assumption 1, where we assume that resource consumption is uniformly bounded. While the CE policy still can be implemented when the small bid assumption does not hold, our performance bounds are not meaningful in such settings. In light of the recent results by [START_REF] Bumpensanti | A re-solving heuristic with uniformly bounded loss for network revenue management[END_REF] and [START_REF] Arlotto | Uniformly bounded regret in the multisecretary problem[END_REF], we expect that similar bounds might hold even in the absence of the small bid assumption.

We refer the reader to [START_REF] Mehta | Online matching and ad allocation[END_REF] for an overview of online matching problems and the small bid assumption.

Order Fulfillment

The order fulfillment problem was presented in §3.6. In Appendix D.6, we describe the fluid problem for this case. Here, Assumption 2 holds with K = 0 and we recover a constant revenue loss bound for the order fulfillment problem when the primal problem is non-degenerate.

Connection with earlier analysis of the CE heuristic. While there are related studies analyzing the performance of heuristics (see, e.g., Acimovic

That is, ρ = ρ 1 + v for some v unitary vector and a positive real number smaller than δ.

In the standard form representation of the problem given in problem (A-1), the constraint |Θ|+L) is the matrix associated to the resource constraints and |Θ|+L) is the matrix associated to the constraints a∈A φ θ (a) = 1. The matrix Q 1 is obtained by horizontally stacking the matrices p θ ȳθ ∈ R L×|A| and the identity matrix I ∈ R L×L . The matrix Q 2 is obtained by horizontally stacking the matrices e 1 , e 2 , . . . , e |Θ| ∈ R |Θ|×|A| and the zero matrix 0 ∈ R |Θ|×L , where e θ ∈ R |Θ|×|A| is the matrix with all columns equal to the θ-th canonical vector of R |Θ| . Let ξ = (ρ 1 , 1) be the corresponding right hand side of problem (A-1) for ρ = ρ 1 and u = (v, 0), where 1 ∈ R |Θ| and 0 ∈ R |Θ| denote a vector of ones and zeros, with a proper size, respectively. In this notation, we can write the perturbed right-hand vector as ξ + u. Let B be the submatrix of Q corresponding to the columns associated to the basic variables at an optimal solution for ρ = ρ 1 , and B -1 ρ 1 the submatrix of B -1 associated to the resource constraints. We can write the optimal basic variable vector as φ B

x B = B -1 ξ. Note that in this case, B -1 u = B -1 ρ 1 v because the last |Θ| components of u are zero and thus

where the last equality hold because v is an unitary vector. Then, by

, B is an optimal basis for the standard problem with right hand side ξ + u and therefore the optimal basic variable vector, namely φ B

x B , can be computed as B -1 (ξ + u). Let us define c ∈ R |A|•|Θ|+L the objective function coefficient vector of problem (A-1). That is, the coefficient vector is obtained by vertically stacking the vectors p θ rθ ∈ R |A| and the zero vector 0 ∈ R L . Thus, calling c B to the coefficient vector associated to the basic variables, it holds that

We divide the proof into five parts: First, we extend the strong convexity lower bound of g in SC 7 to the entire domain. Then, we use a claim (that we prove in Part 4) to show the second statement of Assumption 2. In the third part of the proof, we show that given δ ∈ N (ρ 1 , δ, C), the optimal solution of ( 5) is contained in

In the last part, we use the preliminary results showed along the proof to prove the first statement of Assumption 2.

Part 1. We first extend the strong convexity lower bound of g θ to the entire domain. By SC 7, g admits a κ-LUQ envelope in

We next extend the lower bound to every feasible dual variable. Consider µ ≥ 0 with µ ∈ I ν .

Take α such that αµ + (1 -α)µ 1 = μ where μ ≥ 0 is in the boundary of the ball N (µ 1 , ν), i.e., μ ∈ N (µ 1 , ν). The latter is possible because µ ∈ I ν . Note that μµ 1 = α(µµ 1 ). Taking 2 -norm in both sides, we get that α = μµ 1 / µµ 1 . Moreover, α ∈ (0, 1) because ν > 0, μ ∈ ∂N (µ 1 , ν) and µ ∈ I ν . Because g is convex, we have

which can be reordered to give

where the second inequality follows by (C-4) with µ = μ and the second equality from μ -

Electronic copy available at: https://ssrn.com/abstract=3963265 μ lies at the boundary of the ball N (µ 1 , ν). Combining both cases we obtain that g(µ) ≥ g(µ 1 ) + ∇g(µ 1 ) (µµ 1 ) + κ (µµ 1 ) , (C-5)

where

Part 2. Let us now see the second statement. We will actually prove a stronger result. Let µ be any optimal solution of (5) for a fixed ρ, i.e., µ ∈ arg min µ∈R L

the Lagrange dual function. We shall show that µ i > 0 ∀i ∈ C and µ i = 0 ∀i ∈ U for every optimal solution when the resource vector ρ belongs to N (ρ 1 , δ, C). In the latter we denote by

the resources with positive initial dual variables. Note that by complementary slackness we know that for all j ∈ [L]

where µ is the optimal solution of (5). Therefore, the previous claim would imply for all j ∈ C and

where φ * is an optimal solution of the fluid problem when the resource vector is ρ, and thus the second statement of Assumption 2 would follow.

In the rest of this part, we use the bound obtained in the first part of the proof to bound the Lagrange dual function. We prove the claim in Part 4.

For all µ ≥ 0, we have from (C-5) that

where we used that Ψ ρ (µ 1 ) = ρ µ 1 + g(µ 1 ). Because µ 1 is an optimal dual solution and the constraint set is convex, by Proposition 2.1.2 in [START_REF] Bertsekas | Nonlinear programming[END_REF], the first order conditions are given by

App-21

Electronic copy available at: https://ssrn.com/abstract=3963265

and applying it for μ = µ and using that ∇Ψ ρ (µ 1 ) = ∇g(µ 1 ) + ρ 1 we obtain

Putting all together we conclude that

Part 3. We now prove that µ, the optimal solution of ( 5) for a fixed ρ ∈ N (ρ 1 , δ, C), belongs to the truncated ball

To this end, we show that min µ ∈I ν Ψ ρ (µ) > Ψ ρ 1 (µ 1 ). To do so, using (C-6), it is sufficient to prove that

Note that it is enough to consider ρ with (ρ 1 -ρ) (κν)/2. In fact, if we have ρ = ρ + ξ, where ρ ∈ N (ρ 1 , (κν)/2) and ξ ∈ R L + with ξ i = 0 for all i ∈ C and ξ > 0, we obtain

where we use that µ 1 i = 0 for all i ∈ U. Let us show now that given ρ such that (ρ 1 -ρ) < (κν)/2, it holds that (I) > 0. Take µ ∈ I ν .

We then have µµ 1 > ν and, in this case, (z) = ν z /2. Using Cauchy-Schwartz we obtain

where the third inequality follows because (ρ 1 -ρ) < (κν)/2. We conclude that µ belongs to I ν .

Part 4. In this part we prove the claim of Part 2, that is, that µ i > 0 ∀i ∈ C and µ i = 0 ∀i ∈ U for every optimal dual solution when the resource vector ρ belongs to N (ρ 1 , δ, C).

• Case U. We first handle the resources that are unconstrained at the initial optimal dual variable. We will prove that if ρ is suitably chosen, then the optimal solution of the dual problem satisfies µ i = 0 for all i ∈ U. Recall that the first order conditions are given by

where ∇Ψ ρ (µ) = ρ + ∇g(µ). By Part 3, we know that µ ∈ I ν and thus we are under the

App-22

Electronic copy available at: https://ssrn.com/abstract=3963265 hypothesis of Assumption SC 8, obtaining ρ j + ∂g ∂µ i (µ) > 0 for all i ∈ U. We then conclude that µ i = 0 for all i ∈ U. Otherwise, if there exists j ∈ U with µ j > 0, we can take μl = µ l 1 {l =j} ∈ R L + , contradicting (C-7).

• Case C. We now handle the resources that are constrained at the initial optimal dual variable.

Notice that since ν < µ = min i∈C µ 1 i and µ 1 | C > 0, it holds that for all μ ∈ I ν , μ| C is strictly positive. On the other hand, by Part 3 we know that the optimal dual solution µ belongs to I ν , concluding that µ| C > 0, and the claim is proved. The function : R L → R in (C-5) is, unfortunately, not convex. We restore convexity while preserving the lower bound by shrinking the radius of ball in half and shifting down the cone outside the ball. In particular, consider the function f * : R L → R given by

The function is easily shown to be convex and satisfies (z

is the largest convex function satisfying (z) ≥ f * (z).) Combining this with (C-5) we obtain that

Using this lower bound on g to bound Ψ ρ we have

,

where the second equality holds because for all constrained resources i ∈ C we have by the first-order conditions of the dual problem that ∂g ∂µ i (µ 1 ) + ρ 1,i = 0 and for all unconstrained resources i ∈ U we have µ i = µ 1 i = 0, and the last equality follows from performing the change of variables µµ 1 = z, defining the vector ρ ∈ R L + as ρ| C = (ρρ 1 )| C and ρ| U = 0, and because J(ρ 1 ) = ρ 1 µ 1 + g(µ 1 )

App-23

Electronic copy available at: https://ssrn.com/abstract=3963265

together with ∇ J(ρ 1 ) = µ 1 from the envelope theorem. Note that envelope theorem applies to J because both g and J-in a neighborhood of ρ 1 -are continuously differentiable (it follows from Assumption SC 4, and from the concavity of J and Theorem 25.5 in Rockafellar 1970, respectively).

In the remainder of the proof we lower bound the error term (E). We have that

where the first inequality follows from relaxing the constraints z ≥ -µ 1 and z| U =0 , the first equality from factoring κ > 0 and changing the direction of the optimization, and the last one by denoting

Putting it all together, we conclude that for ρ

The result follows.

C.5 Proof of Lemma 4

Proof of Lemma 4. We will show that under assumptions SC 5-SC 11, g(µ) admits a κ-LUQ enve-Therefore, if µ ∈ N (µ 1 , ν), we have that µµ 1 ≤ ν = κϕ/σ, in which case h(σz) = (σ 2 /2κ) z 2 , which yields

and the result follows by taking expectations over contexts and using that the assumptions hold almost surely over θ ∈ Θ together with the fact that g θ (µ) is uniformly bounded from below (by zero).

C.6 Proof of Lemma 5

Proof. By Danskin's theorem we have that the value function g θ (µ) is differentiable whenever the set of optimal actions is unique, which, in light of SC 12, happens almost surely over the contexts θ. Because g θ (µ) is convex, we obtain from Theorem 7.46 of [START_REF] Shapiro | Lectures on stochastic programming: modeling and theory[END_REF] that

because action a = 1 is optimal whenever r(θ) ≥ µ ȳ(θ). We prove SC 7 holds by showing that ∇g(µ) -∇g(µ 1 ) (µµ 1 ) ≥ κ µµ 1 2 , (C-10)

for every µ ≥ 0 with µµ 1 ≤ ν. To see that the latter condition implies the result, write (µ) = g(µ) -(κ/2)µ µ and note that condition (C-10) is equivalent to ∇ (µ) -∇ (µ 1 ) (µµ 1 ) ≥ 0.

Now consider the function

We obtain that

where the inequality follows from using (C-10) with µ = µ 1 + α(µµ 1 ). The claim follows.

Using our formula for the gradient, we obtain that

where

App-26

Electronic copy available at: https://ssrn.com/abstract=3963265

Let M (θ) = max ȳ(θ) µ 1 , ȳ(θ) µ and m(θ) = min ȳ(θ) µ 1 , ȳ(θ) µ . Then, we can write the term inside the expectation as

which follows simply by using that M (θ) = ȳ(θ) µ 1 and m(θ) = ȳ(θ) µ when ȳ(θ) µ 1 ≥ ȳ(θ) µ and viceversa. Because D(θ) ≥ 0, we obtain by restricting to the event M (θ) ≤ r∞ and taking expectations that

where the second equality follows from conditioning on ȳ(θ) and using that M (θ) and m(θ) are measurable with respect to ȳ(θ), the second inequality from using SC 13 together with the fact that [m(θ), M (θ)) ⊆ [0, r∞ ], the third equality because

and using the linearity of expectations, the third inequality because

from Cauchy-Schwartz and using that µµ 1 ≤ ν, and the last inequality from SC 14. The result follows with κ = pλ.

App-27

Electronic copy available at: https://ssrn.com/abstract=3963265 D Complement to Section 6: CE Heuristic Performance Across

Subclasses of Problems

In this section, we complement the exposition in §6 by providing the detailed sufficient conditions on the primitives in each problem class.

D.1 Network Dynamic Pricing

For simplicity we assume that contexts are finite-similar results can be provided when there is a continuum of contexts. In this problem, we will assume, as is commonly done in the literature, that there is a continuum of actions (we comment on the case of finite actions later). We map conditions SC 5-SC 11 to sufficient conditions for this particular problem. The following conditions together with µ 1 > 0 and compactness of the set of actions A are sufficient for Lemma 4 to hold.

• The expected demand function D(θ, a) is continuous in a.

• The expected resource consumption Q θ D(θ, a) at a maximizer of (a-Q θ µ) D(θ, a) is unique.

• For each θ ∈ Θ, the price vector maximizing (a -Q θ µ) D(θ, a), namely a 1 θ , is interior. That is, there exists a positive number ϕ such that N (a 1 θ , ϕ) ⊆ A for all θ in Θ.

• The expected revenue function r(θ, •) admits a κ r -LDQ envelope in N (a 1 θ , ϕ).

• There exists a positive vector κ y such that the expected demand function D(θ, •) admits a

In particular, under the conditions above, from Lemma 3, Assumption 2 holds with K = 1/κ and δ = (νκ)/2, where κ = κ r + (ν + µ 1 ) κ y , ν = κϕ/σ, and σ is a lower bound on the minimum singular value of Q θ ∇ D(θ, a 1 θ ). Therefore, we can use Corollary 2 to deduce that the revenue loss of the certainty equivalent heuristic is of order O(log T ) in this case. Another implication of our result is that the optimal App-28

Electronic copy available at: https://ssrn.com/abstract=3963265 pricing policy associated with the deterministic proxy is deterministic and the decision maker does not need to randomize over posted prices.

D.2 Dynamic Bidding in Repeated Auctions

To simplify some of the notation in what follows, given an action a, we introduce the interim allocation and interim payment variables defined as follows: q(a) = E ∼f [q(a, )], m(a) = E ∼f [m(a, )].

For simplicity, we assume that the set of values Θ is finite, but our results hold when the set of values is a continuum. For the particular setting described in §3.2, the fluid problem (P FLUID ) is equivalent to the following problem:

For each value θ ∈ Θ, let g θ (µ) = max a∈A {θ q(a) -(µ + 1) m(a)}. Assumption SC 4 requires that g θ (µ) is differentiable in µ and that g θ (µ) is achieved by an action. Under these conditions, Proposition 2 implies that strong duality holds and the Problem (D-12) admits a deterministic optimal solution. In this application, we can characterize an optimal bidding strategy in terms of an optimal bidding function for the static auction without budget constraints, which we denote by

That is, given an advertiser with valuation θ, the optimal bidding strategy for the static auction (ignoring budget constraints) satisfies β(θ) ∈ arg max a∈A {θ q(a) -m(a))} .

We have the following result.

Proposition D-1. Under Assumption SC 4, an optimal solution of (D-12) is to bid β(θ/(1 + µ * ))

when the value is θ, where µ * is the optimal solution of the dual problem of (D-12).

Proof. Recall that there exist µ * optimal dual solution satisfying µ * ∈ [0, μ] (see Step 1 in the proof of Proposition 2). Thus, it is enough to show that β θ 1+µ * , µ * is an optimal solution-Lagrange multiplier pair. We will proceed by using Proposition 5.1.5 in [START_REF] Bertsekas | Nonlinear programming[END_REF]. That is, we need to check primal and dual feasibility, Lagrangian optimality and complementary slackness.

1. Dual feasibility. It follows directly because we take µ * optimal dual solution.

2. Primal feasibility and complementary slackness. To check primal feasibility and complementary slackness we will apply Proposition 2.1.2 in [START_REF] Bertsekas | Nonlinear programming[END_REF], which gives us that, as µ *

App-29

Electronic copy available at: https://ssrn.com/abstract=3963265 is optimal dual solution, we have that

where the derivative of Ψ ρ is given by

If µ * = 0, Ψ ρ (0)µ ≥ 0 and therefore Ψ ρ (0) ≥ 0. Note that we also have Ψ ρ (µ * )µ * = 0, and then primal feasibility and complementary slackness follows by (D-13) because θ∈Θ p θ m β

is the expected payment under the optimal bidding strategy.

If µ * > 0, there exists ν > 0 such that µ * + ν and µ * -ν belongs to [0, μ]. Therefore both Ψ ρ (µ * )ν and Ψ ρ (µ * )(-ν) and non-negative, obtaining Ψ ρ (µ * ) = 0, and primal feasibility and complementary slackness hold.

3. Lagrangian optimality. Note that

where the second equality holds because we can separate the problem for each θ. But note that g θ (a, µ * ) is maximized at a = β(θ/(µ * + 1)) and thus we have Lagrangian optimality.

Therefore, the four conditions holds and the proof is completed.

If in addition Assumptions SC 7 and SC 8 hold, from Lemma 3 we obtain that Assumption 2 holds with K = 1/κ and δ = (νκ)/2. Below, we study the particular cases of second-price auction and first-price auction. Specifically, we provide sufficient conditions on the primitives of the problem for conditions SC 4 and SC 7 to be satisfied.

Second-price auctions. In a second-price auction, the bidder with the highest bid wins the auction and pays the second-highest bid. In this case, we reduce the definition of to a random variable capturing the maximum bid of the competitors and take E = R + . Again, we assume

App-30

Electronic copy available at: https://ssrn.com/abstract=3963265

is distributed according to f , with density function f . While the maximum competing bid is assumed to be independent of the values θ, our results can easily incorporate correlation (see Appendix A.1). Without loss, ties are broken in favor of the decision maker. The allocation and payment functions are given by q(a, ) = 1 {a≥ } and m(a, ) = 1 {a≥ } , respectively.

Suppose that the following conditions hold:

• The distribution of the maximum competing bid f is absolutely continuous and strictly increasing.

• The density f is locally ξ-Lipschitz continuous with respect to

In the next Lemma, we show that these conditions are sufficient to apply Proposition 3 and Lemma 4 and, in turn, Corollary 3 holds. This leads to a revenue loss of logarithmic order in T .

Lemma D-1. If f absolutely continuous and strictly increasing and f is locally ξ-Lipschitz continuous in N (a 1 θ , ϕ), then conditions SC 5-SC 11 hold.

Proof. Let us see that conditions SC 5-SC 11 hold.

• Condition SC 5: By hypothesis f is absolutely continuous and therefore both q and m are continuous.

• Condition SC 6: For each θ ∈ Θ, let us define the function

. Because θ > 0, then lim a 0 G θ (a) > 0 and β(θ) = 0. Because θ = Θ max , we also have lim a Θmax G θ (a) < 0.

Therefore, β(θ) ∈ arg max a G θ (a) is interior and β(θ) satisfies the first-order condition

Therefore, as the cumulative distribution function f is strictly increasing, the unique optimum is to bid truthfully, as it is known in the literature. We conclude that SC 6 holds because the optimal auction is interior almost surely.

• Condition SC 9: Due to the truthfulness property of the second price auction, from Proposition D-1, it follows that a 1 θ = θ/(1 + µ 1 ) which belongs to (0, Θ max ) due to the fact that the bid is positive, and thus condition SC 9 holds.

• Conditions SC 10 and SC 11: Note first that r(θ, a) = θf (a)-m(θ, a) and ȳ(θ, a) = m(a), because f is absolutely continuous. Then, it is enough to show the conditions hold for

App-31

Electronic copy available at: https://ssrn.com/abstract=3963265

In the case of finite customer classes (contexts), Problem (6) can be written as follows

Because the set of actions consists of A = {0, 1}, it is enough to consider decision variables φ θ (1) for all θ ∈ Θ because φ θ (0) = 1-φ θ (1). Removing the variable φ θ (0) from the fluid problem requires a slight change in the statement of Lemma 1. In the standard form representation of the problem, L+2|Θ|) where Q ∈ R (L+|Θ|)×|Θ| is the constraint matrix associated to the decision variables (φ θ (1)) θ∈Θ and the identity matrix

is associated to the slack variables of the resource constraints and the constraints φ θ (1) ≤ 1. The θ-th column of Q consists of the vector p θ Q θ e θ , where e θ ∈ R |Θ| is the canonical vector. Let B be the submatrix of Q corresponding to the columns associated to the basic variables at an optimal solution, and B -1 ρ 1 the submatrix of B -1 associated to the resource constraints. Then, under Assumption SC 1, Assumption 2 holds with K = 0 and δ = min{φ * min , x * min }/ B -1 ρ 1 , where

is the slack of the l-th resource constraint. In the definition of φ * min we now take into account how close the controls are to both zero and one. That is, φ * min = min θ∈Θ {φ * θ (1) :

, where x ∧ y denotes the minimum between x and y.

D.4 Choice-Based Network Revenue Management

In this case, the set of actions is finite and the fluid problem can be expressed as

We can define the vector of variables and the associated matrix involved in the constraints of problem (D-16) by setting each column to p θ n∈[N ] Q n θ g n θa . Then, under Assumption SC 1, we can apply Lemma 1 and Assumption 2 holds for K = 0 and δ defined as in the statement of the lemma.

Therefore, we obtain a constant bound on the revenue loss of the CE heuristic for the choice-based network revenue management problem.

App-34

Electronic copy available at: https://ssrn.com/abstract=3963265

D.5 Online Matching

First, note that the fluid problem is given by (D-17) where φ θ = (φ θ (1), . . . , φ θ (L)) and where for a vector x ∈ R L , diag(x) ∈ R L×L is a diagonal matrix with diagonal entry i given by x i .

Here, as in the network revenue management problem, we need a slight change in the statement of Lemma 1 because we removed the decision variable associated to the action a = 0. In the standard form representation of the problem, the constraint matrix is L|Θ|+L+|Θ|) where L|Θ|+L+|Θ|) is the matrix associated to the resource constraints and Q 2 ∈ R |Θ|×(L|Θ|+L+|Θ|) is the matrix associated to the constraints a∈[L] φ θ (a) ≤ 1. The matrix Q 1 is obtained by horizontally stacking the matrices diag(p θ Q θ ) ∈ R L×L , the identity matrix I ∈ R L×L , and the zero matrix L|Θ|+L+|Θ|) is obtained by horizontally stacking the matrices e 1 , e 2 , . . . , e |Θ| , 0 ∈ R |Θ|×L and the identity matrix I ∈ R |Θ| , where e θ ∈ R |Θ|×L is the matrix with all columns equal to the θ-th canonical vector of R |Θ| . Let B be the submatrix of Q corresponding to the columns associated to the basic variables at an optimal solution, and B -1 ρ 1 the submatrix of B -1 associated to the resource constraints. Then, if the problem (D-17) has a non-degenerate optimal solution for ρ = ρ 1 , Assumption 2 holds with K = 0 and δ

is the slack of the l-th resource constraint, and the constant bound for the revenue loss is obtained.

D.6 Order Fulfillment

In this case, the fluid problem can be expressed as follows J(ρ) = max As in the previous problems, we can write the constraints of problem (D-18) in matrix form and,

App-35

Electronic copy available at: https://ssrn.com/abstract=3963265

thus, obtain an expression for δ involved in the assumption. We do not give an explicit formula for δ here to avoid introducing more notation. Moreover, if problem (D-18) has a non-degenerate optimal solution for ρ = ρ 1 , Assumption 2 holds with K = 0 and we recover a constant revenue loss bound for the order fulfillment problem.

E Auxiliary Results

The following lemma is a technical result we need to prove Lemma B-3.

Lemma E-1. For every a > 1, b > 0 we have

Proof. We assume that a exp(-bT ) < 1. Otherwise, the integrand is always one and the bound Lemma E-2. Let x be a norm in the Euclidean space and let z * = max x ≤1 {z x} be its dual norm. Let f (x) = 1 2 x 2 if x ≤ ϕ and f (x) = ∞ otherwise. Then, its convex conjugate

App-36

Electronic copy available at: https://ssrn.com/abstract=3963265

Proof. Note that the convex conjugate can be more compactly written as min(ϕ, z * ) • z * -1 2 min(ϕ, z * ) 2 . We first show that the latter expression provides an upper bound and then show that the upper can be attained by choosing a suitable feasible solution.

For the upper bound, use Cauchy-Schwartz inequality to obtain that f * (z) ≤ max x ≥ 0 , where c, x, 0, 1 ∈ R n , ξ, u ∈ R m , A ∈ R m×n matrix of rank m and a real parameter. Define

x * min = min{x * i : x * i > 0}, where x * denotes a non-degenerate optimal solution of problem (E-1) for = 0, and denote by A B ∈ R m×m its associated basis matrix. If δ = x * min / A -1 B u , then A B remains optimal for problem (E-1) for all 0 ≤ ≤ δ.

App-37

Electronic copy available at: https://ssrn.com/abstract=3963265

Proof. By permuting its columns, matrix A can be written as A = (A B |A N ) , where A B ∈ R m×m is the submatrix containing the columns associated to the basic variables of x * and A N ∈ R m× (n-m) is the submatrix corresponding to the non-basic variables of x * . Furthermore, we can write x * = (x * B , 0), where x * B = A -1 B ξ ∈ R m is the subvector of basic variables and 0 ∈ R n-m . Note that non-degeneracy of x * implies that x * B > 0. Note that δ > 0 is well defined because {x * i : x * i > 0} is not empty due to the non-degeneracy condition on x * . Take ≤ δ. We will prove that A B is an optimal basis for (E-1), that is, x = (x B , 0) with x B = A -1 B (ξ + u) is an optimal solution for Problem (E-1). Changing the right-hand side of the equality constraints does not change the reduced cost vector and, therefore, it is enough to show that x B is non-negative.

To this end, take j ∈ {1, . . . , m} such that (A -1 B u) j < 0. Note that if does not exist such j, the desired inequality follows trivially because x * j = (A -1 B ξ) j > 0 since x * is non-degenerate. Otherwise, we have that

where the first equation follows from the definition of x B , the second because (x * B ) j is a basic variable, the first inequality from the definition of x * min together with |x j | ≤ x for every x j ∈ R m , the second inequality because ≤ δ, and the last from the definition of δ. The proof is completed.

App-38

Electronic copy available at: https://ssrn.com/abstract=3963265