Extracted main text — title through conclusion, appendix excluded. This is what our citation measures are computed over, published so the extraction can be checked by eye.
78,366 characters · 12 sections · 51 citation commands
Adaptive maximization of social welfare
\onehalfspacing
Consider a policymaker who aims to maximize social welfare, defined as a weighted sum of utility across individuals. The policymaker can choose a policy parameter such as a sales tax rate, an unemployment benefit level, a health-insurance copay rate, etc. The policymaker does not directly observe the welfare resulting from their policy choices. They do, however, observe behavioral outcomes such as consumption of the taxed good, labor market participation, or health care expenditures. They can revise their policy choices over time in light of observed outcomes. How should such a policymaker act? This is the question that we study. To address this question, we bring together insights from welfare economics (in particular optimal taxation, ramsey1927contribution, Mirrlees1971, baily1978some, Saez2001, chetty09suff) with insights from machine learning (in particular online learning and multi-armed bandits, see slivkins2019introduction, lattimore2020bandit for recent reviews, and thompson1933likelihood,lai1985asymptotically for classic contributions).
In our baseline model, individuals arrive sequentially and make a single binary decision. In each period the policymaker chooses a tax rate that applies to this binary decision, and then observes the individual's response. They do not observe the individual's private utility. Social welfare is given by a weighted sum of private utility and public revenue. Later, we extend our model to nonlinear income taxation, where welfare weights vary as a function of individual earnings capacity, and sketch an extension to commodity taxation, where individual decisions involve a continuous consumption vector.
Our goal is to give guidance to the policymaker. We propose algorithms to maximize cumulative social welfare, and we provide (adversarial and stochastic) guarantees for the performance of these algorithms. In doing so, we also show that welfare maximization is a harder learning problem than reward maximization in the multi-armed bandit setting. Private utility in our baseline model is equal to consumer surplus, which is given by the integral of demand. In order to learn this integral, we need to learn demand for counterfactual, suboptimal tax rates. This drives the difficulty of the learning problem.
\paragraph{Why welfare, why adversarial guarantees?} Our algorithms are designed to maximize social welfare, which is not directly observable, rather than maximizing outcomes that are directly observable. The definition of social welfare as an aggregation of individual utilities is at the heart of welfare economics in general, and of optimal tax theory in particular. The distinction between utility and observable outcomes is important in practice. To illustrate, consider the example of a policymaker who chooses the level of unemployment benefits, where the observable outcome is employment. The policymaker could use an algorithm that adaptively maximizes employment. The problem with this approach is that employment might be maximized by making the unemployed as miserable as possible. This is not normatively appealing. Such an algorithm would minimize the utility of the unemployed, rather than maximizing social welfare. Similar examples can be given for many domains of public policy, including health, education, and criminal justice. In contrast to observable outcomes such as employment, welfare is improved by increasing the choice sets of those affected, not by reducing these choice sets.
Our theoretical analysis provides not only stochastic but also adversarial guarantees, which hold for arbitrary sequences of preference parameters. Adversarial guarantees for algorithms promise robustness against deviations from the assumption that heterogeneity is independently and identically distributed over time. Possible deviations from this assumption include autocorrelation, trends, heteroskedasticity, more general non-stationarity, and other concerns of time-series econometrics. In the employment example, such deviations might for instance be due to the business cycle. One might fear that adversarial robustness is achieved at the price of worsened performance for the i.i.d. setting, relative to less robust algorithms. That this is not the case follows from our theoretical characterizations.
\paragraph{Lower and upper bounds on regret} Our main theorems provide lower and upper bounds on cumulative regret. Cumulative regret is defined as the difference in welfare between the chosen sequence of policies and the best possible constant policy. We consider both stochastic and adversarial regret. A lower bound on stochastic regret satisfies that, for any algorithm, there exists some stationary distribution of preference parameters for which the algorithm has to suffer at least a certain amount of regret. An upper bound on adversarial regret has to hold for a given algorithm and any sequence of preference parameters.
For a given algorithm, stochastic regret, averaged over i.i.d. sequences of preference parameters, is always less or equal than adversarial regret, for the worst-case sequence. A lower bound on stochastic regret (for any algorithm) therefore implies a corresponding lower bound on adversarial regret, and an upper bound on adversarial regret (for a given algorithm) immediately implies an upper bound on stochastic regret. When an adversarial upper bound coincides with a stochastic lower bound, in terms of rates of regret, it follows that the proposed algorithm is rate efficient, for both stochastic and adversarial regret. It follows, furthermore, that the bounds are sharp.
\paragraph{A lower bound on stochastic regret} We first prove a stochastic (and thus also adversarial) lower bound on regret, for any possible algorithm in the welfare maximization problem. Our proof of this bound constructs a family of possible distributions for preferences. This family is such that there are two candidate policies which are potentially optimal. The difference in welfare between these two policies depends on the integral of demand over intermediate policy values. In order to learn which of the two candidate policies is optimal, we need to learn behavioral responses for intermediate policies, which are strictly suboptimal. Because of the need to probe these suboptimal policies sufficiently often, we obtain a lower bound on regret which grows at a rate of $T^{2/3}$, even if we restrict our attention to settings with finite, known support for preference parameters and policies. This rate is worse than the worst-case rate for bandits of $T^{1/2}$.
\paragraph{A matching upper bound on adversarial regret for modified Exp3} We next propose an algorithm for the adaptive maximization of social welfare. Our algorithm is a modification of the Exp3 algorithm auer2002nonstochastic. Exp3 is based on an unbiased estimate of cumulative welfare for each policy. The probability of choosing a given policy is proportional to the exponential of this estimate of cumulative welfare, times some rate parameter. Relative to Exp3, we require two modifications for our setting. First, we need to discretize the continuous policy space. Second, and more interestingly, we need additional exploration of counterfactual policies, including some policies that are clearly sub-optimal, in order to learn welfare for the policies which are contenders for the optimum. This need for additional exploration again arises because of the dependence of welfare on the integral of demand over counterfactual policy choices. For our modified Exp3 algorithm, we prove an adversarial (and thus also stochastic) upper bound on regret. We show that, for an appropriate choice of tuning parameters, worst case cumulative regret over all possible sequences of preference parameters grows at a rate of $T^{2/3}$, up to a logarithmic term. The algorithm thus achieves the best possible rate. Since the rates for our stochastic lower and adversarial upper bound coincide, up to a logarithmic term, we have a complete characterization of learning rates for the welfare maximization problem.
\paragraph{Improved stochastic bounds for concave social welfare} The proof of our lower bound on regret is based on the construction of a distribution of preferences which delivers a non-concave social welfare function. If we restrict attention to the stochastic setting, where preferences are i.i.d.\ over time, and if we assume that social welfare is concave, then we can improve upon this bound on regret. We prove a lower bound on stochastic regret, under the assumption of concavity, which grows at the rate of $T^{1/2}$. We then propose a dyadic search algorithm which achieves this rate, up to logarithmic terms. This dyadic search algorithm maintains an “active interval,” containing the optimal policy with high probability, which is narrowed down over time. Only policies within the active interval are sampled.
\paragraph{Extensions to non-linear income taxation and to commodity taxation} Our discussion up to this point focuses on a minimal, stylized case of an optimal tax problem, where individual actions are binary, and the policy imposes a tax on this binary action. Our arguments generalize, however, to more complicated and practically relevant settings. This includes optimal nonlinear income taxation, as in Mirrlees1971 and Saez2001, and commodity taxation for a bundle of goods, as in ramsey1927contribution. For nonlinear income taxation, different tax rates apply at different income levels, and welfare weights depend on individual earnings capacity. In Section (ref), we discuss an extension of our tempered Exp3 algorithm to nonlinear income taxation, and characterize its regret. For commodity taxation, different tax rates apply to different goods, and consumption decisions are continuous vectors. In Section (ref) we sketch an extension of our algorithm to commodity taxation, but leave its characterization for future research.
\paragraph{Roadmap} The rest of this paper proceeds as follows. We conclude this introduction with a discussion of some related work and relevant references. Section (ref) introduces our setup, formally defines the adversarial and stochastic settings, and compares our setup to related learning problems. Section (ref) provides lower and upper bounds on regret in the adversarial and stochastic settings. Section (ref) restricts attention to the stochastic setting with concave social welfare, and provides improved regret bounds for this setting. Section (ref) discusses an extension of our baseline model to non-linear income taxation. Section (ref) sketches another extension of our baseline model to commodity taxation. Section (ref) concludes, and discusses some possible applications of our algorithm, as well as an alternative Bayesian approach to adaptive welfare maximization. The proofs of Theorem (ref) and Theorem (ref) can be found in Appendix (ref). The proofs of our remaining theorems and proofs of technical lemmas are discussed in the Online Appendix.
To put our work in context, it is useful to contrast our framework with the standard approach in public finance and optimal tax theory, and with the frameworks considered in machine learning and the multi-armed bandit literature.
\paragraph{Optimal taxation} Optimal tax theory, and optimal policy theory more generally, is concerned with the maximization of social welfare, where social welfare is understood as a (weighted) sum of subjective utility across individuals ramsey1927contribution, Mirrlees1971, baily1978some, Saez2001, chetty09suff. A key tradeoff in such models is between, first, redistribution to those with higher welfare weights, and second, the efficiency cost of behavioral responses to tax increases. Such behavioral responses might reduce the tax base.
Optimal tax problems are defined by normative parameters (such as welfare weights for different individuals), as well as empirical parameters (such as the elasticity of the tax base with respect to tax rates). The typical approach in public finance uses historical or experimental variation to estimate the relevant empirical parameters (causal effects, elasticities). These estimated parameters are then plugged into formulas for optimal policy choice, which are derived from theoretical models. The implied optimal policies are finally implemented, without further experimental variation.
\paragraph{Multi-armed bandits} The standard approach of public finance, which separates elasticity estimation from policy choice, contrasts with the adaptive approach that characterizes decision-making in many branches of AI, including online learning, multi-armed bandits, and reinforcement learning. Multi-armed bandit algorithms, in particular, trade off exploration and exploitation over time RegretBandit2012, slivkins2019introduction, lattimore2020bandit. {Exploration} here refers to the acquisition of information for better future policy decisions, while {exploitation} refers to the use of currently available information for optimal policy decisions at the present moment. The goal of bandit algorithms is to maximize a stream of {rewards}, which requires an optimal balance between exploration and exploitation. Bandit algorithms for the stochastic setting are characterized by {optimism in the face of uncertainty}: Policies with uncertain payoff should be tried until their expected payoff is clearly suboptimal.
Bandit algorithms (and similarly, adaptive experimental designs for informing policy choice, as in russo2020simple, adaptive2019) are not directly applicable to social welfare maximization problems, such as those of optimal tax theory. The reason is that bandit algorithms maximize a stream of observed rewards. By contrast, social welfare as conceived in welfare economics is based on unobserved subjective utility.
\paragraph{Adversarial decision-making} Adversarial models for sequential decision-making find their roots in repeated game theory hannan1957approximation, while related settings were independently studied in information theory cover1966behavior and computer science vovk1990aggregating,littlestone1994weighted,cesa1997use. Regret minimization, also in a bandit setting, was investigated as a tool to prove convergence of uncoupled dynamics to equilibria in $N$-person games hart2000simple,hart2001general -- the exponential weighting scheme used by Exp3 is also known as \textsl{smooth fictitious play} in the game-theoretic literature fudenberg1995consistency. Recent works seldin2014one,zimmert2021tsallis show that simple variants of Exp3 simultaneously achieve essentially optimal regret bounds in adversarial, stochastic, and contaminated settings, without prior knowledge of the actual regime. This suggests that algorithms designed for adversarial environments can behave well in more benign settings, whereas the opposite is provably not true.
\paragraph{Bandit approaches for economic problems} Bandit-type approaches have been applied to a number of other economic and financial scenarios in the literature where rewards are observable. These include monopoly pricing kleinberg2003value (see also the survey den2015dynamic), second-price auctions cesa2015regret,weed2016online,cesa2017algorithmic, first-price auctions han2020optimal,han2020learning,achddou2021fast,cesa2023transparency---see also kolumbus2022auctions,feng2018learning,feng2021convergence, and combinatorial auctions daskalakis2022learning. Bandit-type approaches have also been applied to some settings where rewards are not directly observable, including bilateral trading cesa2021regret,cesa2023smooth,cesa2023bilateral, and the newsvendor problem lugosi2023hardness.
Bandit algorithms are widely used in online advertising and recommendation. Online learning methods are successfully used for tuning the bids made by autobidders (a service provided by advertising platforms) lucier2024autobidders. While these algorithms are analyzed in adversarial environments, the extent to which they are deployed in commercial products remains unclear.
At each time $i = 1,2, \ldots, T$, one individual arrives who is characterized by an unknown willingness to pay $v_i \in [0,1]$. This individual is exposed to a tax rate $x_i$, and makes a binary decision $y_i = \boldsymbol 1(x_i \leq v_i)$. The implied public revenue is $x_i \cdot y_i$. The implied private welfare is $\max(v_i - x_i, 0)$. We define social welfare as a weighted sum of public revenue and private welfare, with a weight $\lambda \in (0,1)$ for the latter. Social welfare for time period $i$ is therefore given by \be U_i(x_i) = \underbrace{x_i \cdot \boldsymbol 1(x_i \leq v_i)}_{Public revenue}\quad + \quad \lambda \cdot \underbrace{\max(v_i - x_i, 0)}_{Private welfare}. \ee After period $i$, we observe $y_i$ and the tax rate $ x_i$, but nothing else. In particular, we do not observe welfare $U_i(x_i)$.
We can rewrite social welfare $U_i(x)$ as follows. Denote $G_i(x) = \boldsymbol 1(v_i \geq x)$, so that $y_i = G_i(x_i)$. This is the individual demand function. Then private welfare can be written as $ \max(v_i - x, 0) = \int_{x}^1 G_i(x') \mathrm{d} x'. $ That is, private welfare is given by integrated demand.\footnote{This reflects the absence of income effects in our model, which implies that private utility, consumer surplus, compensating variation, and equivalent variation all coincide.} This representation of private welfare implies \be U_i(x) = \underbrace{x \cdot G_i(x)}_{Public revenue} + \quad \lambda \cdot \underbrace{\int_x^1 G_i(x') \mathrm{d} x'}_{Private welfare}. \ee We consider algorithms for the choice of $x_i$ which might depend on the observable history $(x_j, y_j)_{j=1}^{i-1}$, as well as possibly a randomization device.
\paragraph{Notation} For the adversarial setting, we will consider cumulative demand and welfare, denoted by blackboard bold letters, summing across $j=1, \ldots, i$. In particular, \bals \mathbb G_i(x) &= \sum_{j\leq i} G_i(x),& \mathbb U_i(x) &= \sum_{j\leq i} U_i(x),& \mathbb U_i &= \sum_{j\leq i} U_j(x_j). \eals $\mathbb G_i(x)$ and $\mathbb U_i(x)$ are cumulative demand and welfare for a counterfactual, fixed policy $x$. $\mathbb U_i$, without an argument, is the cumulative welfare for the policies $x_j$ actually chosen.
For the stochastic setting, we will analogously consider expected demand and expected welfare, denoted by boldface letters. The expectation is taken across some stationary distribution $\mu$ of $v_i$, where $v_i$ is statistically independent of $x_i$, and of $v_j$ for $j\neq i$. In particular, \bals {\boldsymbol G}(x) &= E[G_i(x)],& {\boldsymbol U}(x) &= E[U_i(x)]. \eals
\paragraph{The adversarial case} Following the literature, we consider regret for both the adversarial and the stochastic setting. In the adversarial setting, we allow for arbitrary sequences of willingness to pay, $\{v_i\}_{i=1}^T$. We compare the expected performance of any given algorithm for choosing $\{x_i\}_{i=1}^T$ to the performance of the best possible constant policy $x$. This comparison yields cumulative expected regret, which is given by \be \mathcal{R}_T(\{v_i\}_{i=1}^T) = \sup_{x} E\left [ \mathbb U_T(x)- \mathbb U_T \Big| \{v_i\}_{i=1}^T \right ]. \ee The expectation in this expression is taken over any possible randomness in the tax rates $x_i$ chosen by the algorithm; there is no other source of randomness.
\paragraph{The stochastic case} We also consider the stochastic setting. In this setting, we add structure by assuming that the $v_i$ are i.i.d.\ draws from some distribution $\mu$ on $[0,1]$, with implied demand function ${\boldsymbol G}(x) = P(v_i \geq x)$. This demand function is identified by the regression $$ {\boldsymbol G}(x) = E[y_i | x_i = x]. $$ The expectation in this expression is taken over the distribution of $v_i$, which is presumed to be statistically independent of the tax rate $x_i$. Expected welfare for this distribution of $v_i$ is given by $$ {\boldsymbol U}(x) = x \cdot {\boldsymbol G}(x) + \lambda \int_{x}^1 {\boldsymbol G}(x') \mathrm{d}x'. $$ Cumulative expected regret in the stochastic case equals \bal \mathcal{R}_T({\boldsymbol G}) &= \sup_{x} E\left [\mathbb U_T(x)-\mathbb U_T \right ] = T \cdot \sup_{x} {\boldsymbol U}(x)- E\left[\sum_{i\leq T}{\boldsymbol U}(x_i) \right ]. \eal The expectation in this expression is taken over both any possible randomness in the tax rates $x_i$, and the i.i.d.\ draws $v_i$.
Before proceeding with our analysis of regret, we take a step back, and compare our learning problem to two related problems that have received some attention in the literature. The first of these is the adaptive monopoly pricing problem; see for instance kleinberg2003value. This problem is equivalent to our setting when we set $\lambda = 0$, interpret $x$ as a price, and $U^{\mathrm{MP}}_i$ as monopolist profits (neglecting production costs): \bal U_i^{\mathrm{MP}}(x) &= x_i \cdot \boldsymbol 1(x_i \leq v_i) = \underbrace{x \cdot G_i(x).}_{Monopolist revenue} \eal As in our adaptive taxation setting, the feedback received at the end of period $i$ is $$y_i = G_i(x_i) = \boldsymbol 1(x_i \leq v_i).$$
Another related problem is price setting for bilateral trade, see for instance cesa2023bilateral. In this problem, welfare $U_i^{\mathrm{BT}}(x)$ is given by the sum of seller and buyer welfare. Trade happens if and only if both sides agree to transact at the proposed price. Buyer willingness to pay is given by $v^b_i$, while the seller is willing to trade at prices above $v^s_i$. \be
\ee Feedback in this case is a little richer: We observe both whether the buyer $b$ would have accepted the posted price, and whether the seller would have accepted this price, \[ y^b_i =G^b_i(x_i) = \boldsymbol 1(x_i \leq v^b_i) \qquad\textrm{and}\qquad y^s_i = G^s_i(x_i) = \boldsymbol 1(x_i \geq v^s_i). \]
\paragraph{Lipschitzness and information requirements} The difficulty of the learning problem in each of these models critically depends on (i) the Lipschitz properties of the welfare function, and (ii) the information required to evaluate welfare at a point.
We say that a generic welfare function $W:[0,1]\to\mathbb{R}$ is one-sided Lipschitz if $W(x + \varepsilon) \le W(x) + \varepsilon$ for all $0 \le x \le 1$ and all $0 \le \varepsilon \le 1 - x$. One-sided Lipschitzness allows us to bound the approximation error of a learning algorithm operating on a finite subset of the set of policies. One-sided Lipschitzness is an intrinsic property of both the monopoly pricing and the optimal taxation problem; it is not an assumption that is additionally imposed. To see this for monopoly pricing, note that, for $\epsilon \ge 0$, $U_i^{\mathrm{MP}}(x +\varepsilon) = (x +\varepsilon) \cdot \boldsymbol 1(x + \varepsilon \leq v_i) \le x \cdot \boldsymbol 1(x \leq v_i) +\varepsilon = U_i^{\mathrm{MP}}(x) +\varepsilon$. For social welfare, $U_i(x) = (x_i+\varepsilon) \cdot \boldsymbol 1(x_i+\varepsilon \leq v_i) + \lambda \cdot \max(v_i - x_i-\varepsilon, 0) \le x \cdot \boldsymbol 1(x \leq v_i)+\varepsilon + \lambda\cdot \max(v_i - x_i, 0) = U_i(x) +\varepsilon$.
We say that learning $W( \cdot )$ requires only pointwise information if $W( x )$ is a function of $G(x)$, and does not depend on $G( \cdot )$ otherwise. Pointwise information allows us to avoid exploring policies that are clearly suboptimal, when we aim to learn the optimal policy.
(ref) summarizes the Lipschitz properties and information requirements in each of the three models; the following justifies the claims made in (ref):
These properties suggest a ranking in terms of the difficulty of the corresponding learning problems, and in particular in terms of the rates of divergence of cumulative regret: The information requirements of optimal taxation are stronger than those of monopoly pricing, but its continuity properties are more favorable than those of bilateral trade. This intuition is correct, as shown by (ref). The rates for monopoly pricing and for bilateral trade are known (or can be easily adapted) from the literature. In this paper we prove corresponding rates for optimal taxation.
In comparing optimal taxation and monopoly pricing to conventional multi-armed bandits, it is worth emphasizing that there are two distinct reasons for the slower rate of convergence. First, the continuous support of $x$, as opposed to a finite number of arms, which is shared by optimal taxation and monopoly pricing. Second, the requirement of additional exploration of sub-optimal policies for the optimal tax problem. As shown in (ref), the continuous support alone is enough to slow down convergence, with no extra penalty for the additional exploration requirement, in terms of rates. If, however, we restrict our attention to a discrete set of feasible policies $x$, then monopoly pricing reduces to a multi-armed bandit problem, with a minimax regret rate of $T^{1/2}$. The optimal tax problem, by contrast, still has a rate of $T^{2/3}$, even if we restrict our attention to the case of finite known support for $v$ and $x$, as shown by the proof of Theorem (ref) below.
\paragraph{Hannan consistency} The cumulative regret of any non-adaptive algorithm necessarily grows at a rate of $T$. This includes, in particular, randomized experiments where the policy is chosen uniformly at random, from a fixed policy set, in every period. Algorithms for which adversarial regret (and thus also stochastic regret) grows at a rate less than $T$, so that per-period regret goes to $0$ as $T$ increases, are known as Hannan consistent. Non-adaptive algorithms are not Hannan consistent. Table (ref) implies that Hannan consistent algorithms exist in all settings considered, with the exception of Bilateral trade and continuous policy spaces.
We now turn to our main theoretical results, lower and upper bounds on stochastic and adversarial regret for the problem of social welfare maximization. We first prove a lower bound on stochastic regret, which applies to any algorithm, and which immediately implies a lower bound on adversarial regret. We then introduce the algorithm Tempered Exp3 for Social Welfare. We show that, for an appropriate choice of tuning parameters, this algorithm achieves the rates of the lower bound on regret, up to a logarithmic term. Formal proofs of these bounds can be found in (ref).
The proof of Theorem (ref) can be found in (ref). The adversarial lower bound follows immediately from the stochastic lower bound, since worst case regret (over possible sequences of $v_i$) is bounded below by average regret (over i.i.d.\ draws of $v_i$), for any distribution of $v_i$.
\paragraph{Sketch of proof} To prove the stochastic lower bound we construct a family of distributions $\{\mu^\epsilon\}_{\epsilon \in [-1,1]}$ for $v_i$, indexed by a parameter $\epsilon \in [-1,1]$. The distributions in this family have four points of support, $(\nicefrac{1}{4}, \nicefrac{1}{2}, \nicefrac{3}{4}, 1)$. The probability of these points is given by $$\left ( a, (1+\epsilon)b, (1-\epsilon)b, 1- a - 2b \right ).$$ The values of $a$ and $b$ are chosen such that (i) the two middle points $\nicefrac{1}{2}, \nicefrac{3}{4}$ are far from optimal, for any value of $\epsilon$, and (ii) learning which of the two end points $(\nicefrac{1}{4}, 1)$ is optimal requires sampling from the middle.\footnote{Specifically, $a \coloneqq \frac{(1-\lambda) \cdot (136 - 99\cdot \lambda)}{2 \cdot (4-3\cdot\lambda)\cdot(24-17\cdot\lambda)}$, and $b \coloneqq \frac{1-\lambda}{2 \cdot(24 - 17 \cdot \lambda)}$. These two constants are strictly greater than zero, and satisfy $1 - a - 2\cdot b > 0$.} For each $\epsilon \in [-1,1]$, denote the demand function associated to $\mu^\epsilon$ by ${\boldsymbol G}^\epsilon$, and the expected social welfare associated to ${\boldsymbol G}^\epsilon$ by ${\boldsymbol U}^\epsilon$. Property (ii) holds because of the integral term $\int_{\tfrac14}^1 {\boldsymbol G}^\epsilon(x') \mathrm{d}x'$, which shows up in ${\boldsymbol U}^\epsilon(1)-{\boldsymbol U}^\epsilon(\nicefrac{1}{4})$. This construction is illustrated in (ref). This figure shows plots of ${\boldsymbol G}^\epsilon$ and of ${\boldsymbol U}^\epsilon$ for $\lambda = .95$ and $\epsilon \in \{\pm 1\}$.
The difference in welfare ${\boldsymbol U}^\epsilon(1)-{\boldsymbol U}^\epsilon(\nicefrac{1}{4})$ of the two candidates optimal policies $\nicefrac{1}{4}$ and $1$ depends on the sign of $\epsilon$. In order not to suffer expected regret that grows as $|\epsilon| \cdot T$, any learning algorithm needs to sample policies from points that are informative about the sign of $\epsilon$. The only points that are informative are those in the region $(\nicefrac{1}{2},\nicefrac{3}{4}]$, where welfare is bounded away from optimal welfare.
More specifically, the learning algorithm has to sample on the order of $|\epsilon|^{-2}$ times from the region $(\nicefrac{1}{2},\nicefrac{3}{4}]$, to be able to detect the sign of $\epsilon$, incurring regret on the order of $|\epsilon|^{-2}$ in the process. Any learning algorithm therefore incurs regret on the order of $\min\bigl(|\epsilon|^{-2},|\epsilon| \cdot T\bigr)$, which, for $\epsilon \propto T^{-1/3})$, leads to the conclusion.
We next introduce Algorithm (ref), which allows us to essentially achieve the lower bound on regret, in terms of rates.
\paragraph{Conventional Exp3} Algorithm (ref) is a modification of the Exp3 algorithm. Conventional Exp3 auer2002nonstochastic is designed to maximize the standard bandit objective, $\sum_{i \leq T} y_i$. Exp3 maintains an unbiased running estimate of the cumulative payoff of each arm $k$, calculated using inverse probability weighting, $\widehat \mathbb G_{i,k} = \sum_{j<i} y_i \cdot \frac{\boldsymbol 1(k_i = k)}{p_{ik}}$. In period $i$, arm $k$ is chosen with probability $p_{ik} =(1-\gamma) \cdot \tfrac{ \exp(\eta \cdot \widehat \mathbb G_{ik})}{\sum_{k'}\exp(\eta \cdot \widehat \mathbb G_{ik'})} + \frac{\gamma }{K+1}$, where $\eta$ and $\gamma$ are tuning parameters. $p_{ik}$ is thus increasing in the estimated average performance $\tfrac{\widehat \mathbb G_{i,k}}{i}$ of arm $k$ in prior periods. Because $\widehat \mathbb G_{i,k}$ is not normalized by the number of time periods $k$, more weight is given to the best-performing arms over time, as estimation uncertainty for average performance decreases. In both these aspects, Exp3 is similar to the popular Upper Confidence Bound algorithm (UCB) for stochastic bandit problems lai1987adaptive,agrawal1995sample,auer2002finite. In contrast to UCB, Exp3 is a randomized algorithm. Randomization is required for adversarial performance guarantees. This is analogous to the necessity of mixed strategies in Nash equilibrium for zero-sum games.
\paragraph{Modifications relative to conventional Exp3} Relative to this algorithm, we require three modifications. First, we discretize the continuous support $[0,1]$ of $x$, restricting attention to the grid of policy values $\tilde x_k = (k-1)/K$. Second, since welfare $U_i(x)$ is not directly observed for the chosen policy $x$, we need to estimate it indirectly. In particular, we first form an estimate $\widehat \mathbb G_{i k}$ of cumulative demand for each of the policy values $\tilde x_k$, using inverse probability weighting. We then use this estimated demand, interpolated using a step-function, to form estimates of cumulative social welfare, $ \widehat \mathbb U_{ik} ={ \tilde x_k \cdot \widehat \mathbb G_{i k} + \tfrac{\lambda}{K} \cdot \sum_{k'> k} \widehat \mathbb G_{i k'}}. $ Third, we require additional exploration, relative to Exp3. Since social welfare depends on demand for counterfactual policy choices, we need to explore policies that are away from the optimum, in order to learn the relative welfare of approximately optimal policy choices. The mixing weight $\gamma$, which determines the share of policies sampled from the uniform distribution, needs to be larger relative to conventional Exp3, to ensure sufficient exploration away from the optimum.
The proof of Theorem (ref) can again be found in (ref).
\paragraph{Tuning} The statement of the theorem leaves the constants $c_1,c_2,c_3$ in the definition of the tuning parameters unspecified. Suppose we wish to choose the tuning parameters so as to optimize the upper bound obtained in Theorem (ref). Ignoring the rounding of $K$, an approximate solution to this problem is given by \bals \eta &= 1/a \cdot (\log(T)/T)^{2/3}\\ \gamma &=\lambda \sqrt{(e-2)/a} \cdot (\log(T)/T)^{1/3}\\ K &=\sqrt{3\lambda a/(e-2)} \cdot (T/\log(T) )^{1/3} \eals where $$a = \left(9(e-2)\right)^{1/3} (\sqrt{\lambda /3}+\lambda )^{2/3}.$$ This solution is obtained by taking the upper bound in Equation (ref), approximating $(K+1) / K \approx 1$ and $(2K+1) / 6 \approx K/3$, and solving the first order conditions with respect to the three tuning parameters. This approximation, and the tuning parameters specified above, yield an approximate upper bound on regret of $6 \cdot \log(T)^{1/3} T^{2/3}$.
\paragraph{Unknown time horizon} Note that the proposed tuning depends crucially on knowledge of the time horizon $T$ at which regret is to be evaluated. In order to extend our rate results to the case of unknown time horizons, we can use the so-called doubling trick; cf. Section 2.3 of cesa2006prediction: Consider a sequence of epochs (intervals of time-periods) of exponentially increasing length, and re-run Algorithm (ref) for each time-period separately, tuning the parameters over the current epoch length. This construction converts Algorithm (ref) into an “anytime algorithm” which enjoys the same regret guarantees of Theorem (ref), up to a multiplicative constant factor. Another more efficient strategy to achieve the same goal is to modify Algorithm (ref), allowing the parameters $\eta$ and $\gamma$ to change at each iteration, and splitting each bin associated with the discretization parameter $K$ whenever more precision is required.
\paragraph{The extra $\log(T)^{1/3}$ term} There is a rate discrepancy between our our upper and lower bounds on regret, corresponding to the $\log(T)^{1/3}$ term in our upper bound. We conjecture the existence of an alternative algorithm that can eliminate this extra logarithmic term, albeit at the cost of reduced computational efficiency and a less transparent theoretical analysis. Our conjecture is based on known results for the standard multi-armed bandit problem with $K$ arms. The Exp3 algorithm achieves an upper bound of order $\sqrt{ K\log(K)T }$ for this problem, which includes an extra logarithmic term compared to the known lower bound of order $\sqrt{KT}$. Exp3 is an instance of the Follow-The-Regularized-Leader (FTRL) algorithm with importance weighting and the negative entropy as the regularizer. It is known that using the $\frac{1}{2}$-Tsallis entropy as the regularizer in the FTRL algorithm with importance weighting results in regret guarantees of order $\sqrt{KT}$ for the bandit problem lattimore2020bandit. However, unlike Exp3, the FTRL with Tsallis entropy involves a more complex proof and requires solving an optimization problem in each period. Analogous statements might be true for our setting.
\paragraph{Numerical example}
For illustration, Figure (ref) plots the cumulative average regret of Tempered Exp3 for Social Welfare for the case where $v_i$ is sampled uniformly at random from $[0,1]$ each time period. Initially, the performance of our algorithm is, by construction, equal to the performance of choosing a policy uniformly at random. Over time, however, the average regret of our algorithm drops by more than half, in this numerical example. Note that the rate at which cumulative regret declines in Figure (ref) (for i.i.d. sampling from a fixed distribution) is unrelated to the regret rate of Theorem (ref) (for the worst case sequence of $v_i$, for each time horizon $T$).
Theorem (ref) in Section (ref) provides a lower bound proportional to $T^{2/3}$ for adversarial and stochastic regret in social welfare maximization. The proof of this lower bound constructs a distribution for the $v_i$. This distribution is such that expected social welfare ${\boldsymbol U}(x)$ is non-concave, as a function of $x$; two global optima are separated by a region of lower welfare. In order to learn which of two candidates for the globally optimal policy is actually optimal, it is necessary to sample policies in between. These intermediate policies yield lower welfare, and sampling them contributes to cumulative regret. This construction is illustrated in (ref).
Given that the construction relies on non-concavity of expected social welfare, could we achieve lower regret if we knew that social welfare is actually concave? The answer turns out to be yes, for the stochastic setting (in the adversarial setting, cumulative welfare is necessarily non-concave). One reason is that concavity ensures that the function is unimodal. To estimate the difference in social welfare between two policies it therefore suffices to sample policies that lie in the interval between them. These in-between policies yield social welfare exceeding the minimum of the two boundary policies. A second reason is that concavity prevents unexpected spikes in social welfare. This property allows us to test carefully chosen triples of points for extended periods, to ensure that one of them is suboptimal, without incurring significant regret.
For the stochastic setting with concave social welfare, we present an algorithm that achieves a bound on regret of order $T^{1/2}$, up to logarithmic terms. Before describing our proposed algorithm, Dyadic Search for Social Welfare, let us formally state the improved regret bounds. The proofs of these lower and upper bounds can be found in Online Appendix (ref).
\paragraph{Dyadic search} Our algorithm is based on a modification of dyadic search, as discussed in bachoc2022aNearOptimal,bachoc2022regret. At any point in time, this algorithm maintains an active interval $I_\tau$, which contains the optimal policy with high probability. Only policies within this interval are sampled going forward. As evidence accumulates, this interval is trimmed down, by excluding policies that are sub-optimal with high probability.
The algorithm proceeds in epochs $\tau$. At the start of each epoch, a sub-interval $[l,r] \subset I_\tau$ is formed, with mid-point $c = (l+r) / 2$. The points $l,c,r$ are in a dyadic grid, that is, they are of the form $k/2^m$. After sampling from $[l,r]$, we calculate confidence intervals $J_t(l,c)$, $J_t(c,r)$, and $J_t(l,r)$ for the welfare differences $\Delta(l,c)$, $\Delta(c, r)$, and $\Delta(l, r)$, where $\Delta(x,x') = {\boldsymbol U}(x') - {\boldsymbol U}(x)$.
If the confidence interval $J_t(l,c)$ or $J_t(l,r)$ lies above $0$, concavity implies that the optimal policy cannot lie to the left of $l$; we can thus trim the active interval $I_\tau$ by dropping all points to the left of $l$. Symmetrically, if the confidence interval $J_t(c,r)$ or $J_t(l,r)$ lies below $0$, we can trim $I_\tau$ by dropping all points to the right of $r$.
\paragraph{Confidence intervals for welfare differences} This procedure requires the construction of confidence intervals for welfare differences of the form \be \Delta(x,x') = {\boldsymbol U}(x') - {\boldsymbol U}(x) = x' \cdot {\boldsymbol G}(x') - x \cdot {\boldsymbol G}(x) - \lambda \int_{x}^{x'} {\boldsymbol G}(x”) \mathrm{d}x”. \ee At time $t$, we estimate demand ${\boldsymbol G}(x)$, for policies $x$ chosen in previous periods, as\footnote{We use the convention $0/0 = 0$ and $a / 0 = +\infty$ whenever $a>0$. Furthermore, every summation over an empty set of indices is understood to have value $0$.} \bals \widehat {\boldsymbol G}_t(x) &= \frac{1}{n_t(x)} \sum_{i \leq t} y_i \cdot \boldsymbol 1(x_i = x), & n_t(x) &= \sum_{i \leq t} \boldsymbol 1(x_i = x). \eals We similarly estimate integrated demand $\int_{x}^{x'} {\boldsymbol G}(x'') \mathrm{d}x''$ by $(x' - x)$ times the average of realized demand $y_i$ for observations $x_i$ in the open interval $(x, x')$. We have to be careful, however, to use a sample of $x_i$ that is (approximately) uniformly distributed over this interval. This can be achieved for our dyadic search procedure, as specified in Algorithm (ref), by truncating the time index used to estimate this average.\footnote{The sampling procedure in Algorithm (ref) samples sequentially from the dyadic grid in the active interval, refining the grid in subsequent iterations. $s(x,x',t)$ provides a truncation of the time index such that one round of such dyadic sampling has been completed.} Let $$s(x,x',t) = \max \left\{s \leq t:\; \log_2\left(1 + \sum_{i\leq s} \boldsymbol 1(x_i \in (x, x'))\right) \in \mathbb{N}\right\}.$$ We define \bals \widehat {\boldsymbol G}_t(x, x') &= \frac{1}{n_t(x, x') + 1} \sum_{i \le s(x,x',t)} y_i \cdot \boldsymbol 1(x_i \in (x, x')), & n_t(x, x') &= \sum_{i \le s(x,x',t)} \boldsymbol 1(x_i \in (x, x')). \eals At each round, Algorithm (ref) maintains estimates for welfare differences among three points $l,c,r$ (for left, center and right, respectively). The estimate of the welfare difference between $x'=c$ and $x = l$ (or between $x'=r$ and $x = c$) is given by \be \widehat \Delta_t(x,x') = x' \cdot \widehat {\boldsymbol G}_t(x') - x \cdot \widehat {\boldsymbol G}_t(x) - \lambda \cdot (x' - x) \cdot \widehat {\boldsymbol G}_t(x, x'). \ee while the estimate of the welfare difference between $r$ and $l$ is given by \be \widehat \Delta_t(l,r) = \widehat \Delta_t(l, c) + \widehat \Delta_t(c, r). \ee To construct confidence intervals for $\Delta(x,x')$, we also need to quantify the uncertainty of our demand estimates. We use the following interval half-lengths for confidence intervals for tax revenue at $x$, and for the private welfare difference between $x'$ and $x$: \bals \Gamma_t(x) &= x \cdot \sqrt{ \tfrac{1}{ 2 n_t(x)} \log \left(\tfrac{2}{\delta}\right)}, & \Gamma_t(x,x') &= \lambda \cdot (x' - x) \cdot \left(\sqrt{ \tfrac{1}{ 2 \bigl(n_t(x, x') + 1\bigr)} \log \left(\tfrac{2}{\delta}\right)} + \tfrac{2}{ n_t(x, x') + 1}\right)) + 1}} . \eals Using the shorthand $a\pm b = [a-b,a+b]$, our confidence interval for $\Delta(x,x')$, where $x'=c$ and $x=l$ (or $x'=r$ and $x=c$) is given by \be J_t(x,x') = \widehat \Delta_t(x,x') \pm \left(\Gamma_t(x') + \Gamma_t(x) + \Gamma_t(x,x') \right), \ee while our confidence interval for $\Delta(l,r)$ is given by \be J_t(l,r) = \widehat \Delta_t(l,r) \pm \left(\Gamma_t(r) + \Gamma_t(l) + \Gamma_t(l,c) + \Gamma_t(c,r) \right). \ee With these preliminaries, we are now ready to state our algorithm, Dyadic Search for Social Welfare, in Algorithm (ref).
Before concluding this section, we highlight two features of Algorithm (ref). First, two of the three points $l,c,r$, and the corresponding estimates of demand, are kept from each epoch to the next. Second, estimation of the integral term is performed by querying points following a fixed and balanced design on the dyadic grid -- instead of, for example, using a randomized Monte Carlo procedure which may lead to unbalanced exploration. This implies that the points queried to estimate the integral terms can be easily reused to obtain other integral estimates from each epoch to the next. These two features combined ensure that Algorithm (ref) recycles information very efficiently to prune the active interval as quickly as possible, which leads to better regret.
We discuss two extensions of the baseline model of optimal taxation that we introduced in Section (ref). These extensions incorporate features that are important in more realistic models of optimal taxation. For both of these extensions, we propose a properly modified version of Algorithm (ref). The first extension, discussed in this section, is a variant of the Mirrlees model of optimal income taxation Mirrlees1971, Saez2001, saez2002optimal. The second extension, discussed in Section (ref) is a variant of the Ramsey model of commodity taxation ramsey1927contribution.
Our model of income taxation generalizes our baseline model by allowing for heterogeneous wages $w_i$, welfare weights $\omega(w_i)$, extensive-margin labor supply responses determined by the cost of participation $v_i$, and non-linear income taxes $x_i = \mathbf{x}(w_i)$. Two simplifications are maintained in this model, relative to a more general model of income taxation. First, only extensive margin responses (participation decisions) by individuals are allowed; there are no intensive margin responses (hours adjustments). Second, as in the baseline model of Section (ref), there are no income effects. In imposing these assumptions, our model mirrors the model of optimal income taxation discussed in Section II.2 of saez2002optimal.
\paragraph{Setup} At each time $i = 1,2, \ldots, T$, one individual arrives who is characterized by (i) a potential wage $w_i \in [0,1]$, and (ii) an unknown cost of participation $v_i \in [0,1]$. This individual makes a binary labor supply decision $y_i$. If they participate in the labor market ($y_i=1$), they earn $w_i$, but pay a tax according to the tax rate $x_i = \mathbf{x}(w_i)$ on their earnings $w_i$. They furthermore incur a non-monetary cost of participation $v_i$.
Their optimal labor supply decision is therefore given by $y_i = \boldsymbol 1( v_i\leq w_i \cdot (1 - x_i))$, and private welfare equals $\max(w_i\cdot (1 - x_i) - v_i , 0)$. The implied public revenue is equal to the tax on earnings $x_i\cdot w_i$ if $y_i =1$, and $0$ otherwise.
We define social welfare as a weighted sum of public revenue and private welfare, with a weight $\omega(w_i)$ for the latter. Typically, $\omega$ is a decreasing function of $w$, reflecting a preference for redistribution towards those with lower earnings potential, cf. saez2013generalized. Social welfare for time period $i$, as a function of the tax schedule $\mathbf{x}( \cdot )$, is therefore given by \be U_i(\mathbf{x}(\cdot)) = \underbrace{\mathbf{x}(w_i)\cdot w_i \cdot \boldsymbol 1( v_i \leq w_i \cdot (1 - \mathbf{x}(w_i)))}_{Public revenue}\quad + \quad \omega(w_i) \cdot \underbrace{\max(w_i \cdot (1 - \mathbf{x}(w_i)) - v_i , 0)}_{Private welfare}. \ee After period $i$, we observe $y_i$ and the tax schedule $ \mathbf{x}_i( \cdot )$. If $y_i = 1$, we also observe $w_i$. Nothing else is observed.\footnote{It should be noted that in this model we take the transfer $x_0$ for individuals without other income as given. The effective tax owed by an employed individual equals $\mathbf{x}(w_i)\cdot w_i-x_0$. The “unconditional basic income” $x_0$ does not affect labor supply, given our assumption that there are no income effects, and it enters social welfare additively. It is therefore without loss of generality to omit $x_0$ from our model.}
\paragraph{Piecewise constant tax schedules} We next construct a generalization of Algorithm (ref) based on piecewise constant tax schedules, with tax rates changing at the grid-points $\mathcal W$, where $0 \in \mathcal{W}\subset [0,1]$. Formally, define $\left\lfloor w\right\rfloor = \max \{w' \in \mathcal{W}:\; w'\leq w\} $, rounding the wage $w$ down to the nearest grid-point in $\mathcal W$,\footnote{Here we use slightly non-standard notation, where $\left\lfloor \cdot \right\rfloor $ denotes rounding down to the nearest grid-point, rather than the nearest integer.} Denote $H = |\mathcal W|$, and let $$ \mathcal {X_W} = \{\mathbf{x}( \cdot ):\;\forall w \in [0,1],\; \mathbf{x}(w) = \mathbf{x}(\left\lfloor w\right\rfloor)\}. $$ For $w \in \mathcal W$ and any $x \in [0,1]$, denote $$ G_i(w, x) = w_i \cdot \boldsymbol 1( v_i\leq w_i \cdot (1 - x)) \cdot \boldsymbol 1(\left\lfloor w_i\right\rfloor = w), $$ so that $y_i \cdot w_i = G_i(w_i, \mathbf{x}_i(w_i))$. $G_i(w, x)$ is the individual labor supply function, in monetary units, interacted with an indicator for whether the wage $w_i$ falls into the tax bracket starting at $w$. With this notation, we can rewrite $$ \max(w_i\cdot (1 - x) - v_i , 0) = \int_{x}^{1} G_i(\left\lfloor w_i\right\rfloor, x') \mathrm{d}x'. $$ For piecewise constant tax rates $\mathbf{x}( \cdot )$ we get \bal U_i(\mathbf{x}(\cdot)) &= \sum_{w \in \mathcal W} \left [\mathbf{x}(w) \cdot G_i(w, \mathbf{x}(w)) + \omega(w_i) \cdot \int_{\mathbf{x}(w)}^{1} G_i(w, x') \mathrm{d}x'\right ]. \eal Cumulative social welfare is given by $\mathbb U_i= \sum_{j\leq i} U_i(\mathbf{x}_i( \cdot ))$, and we correspondingly define cumulative expected regret, in the adversarial setting, as $$ \mathcal R_T = \sup_{\mathbf{x}( \cdot ) \in \mathcal{X_W}} E\left [ \mathbb U_T(\mathbf{x}( \cdot ))- \mathbb U_T \Big| \{v_i\}_{i=1}^T, \{w_i\}_{i=1}^T \right ]. $$ The supremum here is taken over all tax schedules $\mathbf{x}( \cdot )$ that are piecewise constant between the gridpoints $w \in \mathcal W$.
\paragraph{Algorithm} Algorithm (ref) generalizes Algorithm (ref) to this setting. As before, we form an unbiased estimate $\widehat G_i$ of $G_i$ using inverse probability weighting, map this estimate into a corresponding estimate $\widehat U_i$ of $U_i$, based on Equation (ref), and cumulate across time periods to obtain $\widehat \mathbb U_i$. Note that $w_i$ is observed whenever $y_i = 1$. This implies that the estimate $\widehat G_i$ is in fact a function of observables, and the same holds for $\widehat U_i$.
Algorithm (ref) keeps track of estimated demand and social welfare for each bin (“tax bracket”), as defined by the gridpoints $w \in \mathcal W$. The algorithm then constructs a distribution $p_i(x| w)$ over tax rates $x \in \mathcal X$ given $w$, using the tempered Exp3 distribution. The tax schedule $\mathbf{x}( \cdot )$ is sampled according to these (marginal) distributions of tax rates for each bracket. Though immaterial for the following theorem, we choose the perfectly correlated coupling, across brackets, of these marginal distributions, which is implemented using the random variable $A_i$ in Algorithm (ref).
In this section, we generalize our baseline model of optimal taxation to a model of commodity taxation with multiple goods $j \in \{1,\ldots,k\}$ and continuous demand functions $y_i(x) \in [0,1]^k$, where $x \in [0,1]^k$ is a vector of tax rates. We again assume that there are no income effects. Our setup is a version of the classic Ramsey model ramsey1927contribution. We propose a generalization of Tempered Exp3 for Social Welfare to this setting. In the following, we use $\langle x, y \rangle$ to denote the Euclidean inner product between $x$ and $y$.
\paragraph{Setup} At each time $i = 1,2, \ldots, T$, one individual arrives who is characterized by a utility function $u_i: [0,1]^k \rightarrow \mathcal R$. This individual is exposed to a tax vector $x_i \in [0,1]^k$, and makes a continuous consumption decision $y_i$. Public revenue is given by $\langle x_i, y_i \rangle$. Private utility is given by $u_i(y_i)$ plus their consumption of a numeraire good, which has price normalized to $1$ and enters utility additively. The individual consumption choice $y_i$ costs $\langle x_i + p, y \rangle$, where $p$ is the (exogenously given) vector of pre-tax prices. This cost of purchasing $y_i$ reduces the consumption of the numeraire good. The optimal individual decision is therefore given by \be y_i = G_i(x_i)= \operatorname*{argmax\;}_{y \in [0,1]^k} \left [ u_i(y) - \langle x_i + p, y \rangle \right]. \ee The implied private welfare is $$ v_i(x) = v_0 + \max_{y \in [0,1]^k} \left [ u_i(y) - \langle x + p, y \rangle \right ], $$ where we have added a constant $v_0$, chosen such that $v_i(0) = 0$; this is just a normalization to simplify notation below.
We define social welfare as a weighted sum of public revenue and private welfare, with a weight $\lambda$ for the latter. Social welfare for time period $i$, as a function of the tax vector $x$, is therefore given by \be U_i(x_i) = \underbrace{\langle x_i, y_i \rangle}_{Public revenue}\quad + \quad \lambda \cdot \underbrace{v_i(x_i)}_{Private welfare}. \ee After period $i$, we observe $y_i$ and the tax vector $x_i$. Nothing else is observed.
\paragraph{Mapping demand to welfare} By the envelope theorem milgrom2002envelope, $$ \nabla_x v_i(x) = G_i(x). $$ Let $\mathcal V$ be the set of differentiable functions $v$ on $[0,1]^k$ such that $\nabla_x v \in L^2$, and such that $v(0)=0$. Consider the following operator, mapping the demand function $G$ into the corresponding indirect utility function $v$. \be \Pi (G( \cdot )) \in \operatorname*{argmin\;}_{v( \cdot ) \in \mathcal V} \int_{[0,1]^k} \left \| \nabla_x v(x) - G(x) \right \|^2 \mathrm{d}x \ee We can think of the operator $\Pi$ as combining two operators. First, the function $G$ is projected on the subspace of functions on $[0,1]^k$ which can be written as the gradient of some function $v$. Second, the projected $G$ is then integrated to get $v(x)$ for any $x$. Integration here is along some curve in $[0,1]^k$ from $0$ to $x$. Given the first projection, the choice of curve does not matter for the resulting function $v$. A formal analysis of Tempered Exp3 for Commodity Taxation would need to prove existence of the projection. We leave such a formal analysis, including lower and upper regret bounds, for future research.
\paragraph{Possible applications} The setup introduced in Section (ref) was deliberately stylized, to allow for a clear exposition of the conceptual issues that arise when adaptively maximizing social welfare. The algorithm that we proposed for this setup, and the generalizations discussed later in the paper, are nonetheless directly practically relevant. They remain appropriate in economic settings that are considerably more general than the setting described by our model.
The reasons for this generality have been elucidated by the public finance literature, cf. chetty09suff, building on the generality of the envelope theorem, cf. milgrom2002envelope,sinander2022converse. By the envelope theorem, the welfare impact of a marginal tax change on private welfare can be calculated ignoring any behavioral responses to the tax change. This holds in generalizations of our setup that allow for almost arbitrary action spaces (including discrete and continuous, multi-dimensional, and dynamic actions), and for arbitrary preference heterogeneity. The expressions for social welfare that justify our algorithms remain unchanged under such generalizations. That said, the validity of these expressions does require the absence of income effects and of externalities. If there are income effects or externalities, the algorithms need to be modified.
Our approach is motivated by applications of algorithmic decisionmaking for public policy, where a policymaker cares about welfare, but also faces a government budget constraint. Possible application domains of our algorithm include the following. In public health and development economics, field experiments such as cohen2010free vary the level of a subsidy for goods such as insecticide-treated bed nets (ITNs), estimating the impact on demand. Our algorithm could be used to find the optimal subsidy level quickly and apply it to experimental participants. A term capturing positive externalities of the use of ITNs could be added to social welfare, leaving the algorithm otherwise unchanged. In educational economics, many studies evaluate the impact of financial aid on college enrollment dynarski2023college. An adaptive experiment might vary the level of aid provided, where aid is conditional on college attendance and conditional on pre-determined criteria of need or merit. In such an experiment, a variant of our algorithm for optimal income taxation might be used, where the welfare weights $\omega$ are a function of need or merit, and the outcome $y$ is college attendance. In environmental economics, many experiments (e.g., lee2020experimental) study the impact of electricity pricing on household electricity consumption. Once again, our baseline algorithm (for binary household decisions about connecting to the grid) or our algorithm for commodity taxation (for continuous household decisions about consumption levels) could be applied, to learn optimal prices, taking into account both distributional considerations and externalities.
These examples are all drawn from public policy, where there is an intrinsic concern for social welfare. This contrasts with commercial applications, where the goal is typically to maximize (directly observable) profits by monopolist pricing den2015dynamic, or more generally by reserve price setting in auctions nedelec2022learning. Adaptive pricing algorithms are used in applications such as online ad auctions. A concern for welfare might enter in such commercial settings if there is a participation constraint that needs to be satisfied for consumers. Suppose for example that consumers or service providers need to first sign up for a platform, say for e-commerce or for gig work, and then repeatedly engage in transactions on this platform. To sign up in the first place, their expected welfare needs to exceed their outside option. This constraint might then enter the platform provider's objective, in Lagrangian form, adding a term for welfare, and leading to objectives such as those maximized by our algorithms.
\paragraph{An alternative approach: Thompson sampling} The main algorithm proposed in this paper, Tempered Exp3 for Social Welfare, is designed to perform well in the adversarial setting. In the construction of this algorithm, no probabilistic assumptions were made about the distribution of $v_i$. In the stochastic framework, a sampling distribution is assumed, for instance that the $v_i$ be i.i.d. over time. The Bayesian framework completes this by assuming a prior distribution over the parameters which govern the sampling distribution.
One popular heuristic for adaptive policy choice in the Bayesian framework is Thompson sampling thompson1933likelihood, Thompson2018, also know as probability matching, which assigns a policy with probability equal to the posterior probability that this policy is optimal. In our setting, Thompson sampling could be implemented as follows. First, form a posterior for the demand function ${\boldsymbol G}(x) = E[y| x]$, based on all the data available from previous periods $j < i$. Sample one draw $\widetilde {\boldsymbol G}( \cdot )$ from this posterior. Map this draw into a draw $\widetilde {\boldsymbol U}( \cdot )$ from the posterior for ${\boldsymbol U}( \cdot )$ via $\widetilde {\boldsymbol U}(x) = x \cdot \widetilde {\boldsymbol G}(x) + \lambda \cdot \int_x^1 \widetilde {\boldsymbol G}(x') \mathrm{d} x'$. Find the maximizer $x_i = \operatorname*{argmax\;}_x \widetilde {\boldsymbol U}(x)$. This is the policy recommended by Thompson sampling. We conjecture that this algorithm will outperform random assignment, but will under-explore relative to the optimal algorithm. Adding further forced exploration to this algorithm might improve cumulative welfare. A formal analysis of algorithms of this type is left for future research.
A natural class of priors for ${\boldsymbol G}$ are Gaussian process priors williams2006gaussian. If outcomes $y$ are conditionally normal (rather than binary, as in our baseline model), then the posterior for demand is available in closed form, and the posterior mean is equal to the best linear predictor given past outcomes $y_j$. Furthermore, since social welfare is a linear transformation of demand, the posterior for ${\boldsymbol U}$ is then also linear and available in closed form. For details, see kasy2017taxation.