Online Social Welfare Function-based Resource Allocation Kanad Pardeshi, Samsara Foubert, Aarti Singh Abstract In many real-world settings, a centralized decision-maker must repeatedly allocate finite resources to a population over multiple time steps. Individuals who receive a resource derive some stochastic utility; to characterize the population-level effects of an allocation, the expected individual utilities are then aggregated using a social welfare function (SWF). We formalize this setting and present a general confidence sequence framework for SWF-based online learning and inference, valid for any monotonic, concave, and Lipschitz-continuous SWF. Our key insight is that monotonicity alone suffices to lift confidence sequences from individual utilities to anytime-valid bounds on optimal welfare. Building on this foundation, we propose SWF-UCB, a SWF-agnostic online learning algorithm that achieves near-optimal 𝒪 ~ ​ ( n + n ​ k ​ T ) \tilde{\mathcal{O}}(n+\sqrt{nkT}) regret (for k k resources distributed among n n individuals at each of T T time steps). We instantiate our framework on three normatively distinct SWF families: Weighted Power Mean, Kolm, and Gini, providing bespoke oracle algorithms for each. Experiments confirm T \sqrt{T} scaling and reveal rich interactions between k k and SWF parameters. This framework naturally supports inference applications such as sequential hypothesis testing, optimal stopping, and policy evaluation. 1 Introduction Decision-makers routinely face the problem of allocating limited resources to a population over time: a park service assigning ranger patrols to backcountry zones, a chronic care program allocating community health worker visits among patients, or a school district allotting tutoring slots among students. Evaluating such allocations requires aggregating individual outcomes into a coherent measure of collective welfare. Social Welfare Functions (SWFs) provide a principled method for this aggregation, with axiomatic foundations from welfare economics that encode fairness-efficiency tradeoffs in a form amenable to optimization. Recent ML work has formalized SWFs within learning theory, providing sample complexity bounds for welfare estimation from batch data ( 8 ; 23 ) . Real-world resource allocation is inherently sequential: individual utilities are unknown and must be learned from observed outcomes, yet decisions cannot be deferred while data accumulate. Each resource allocation affects the population’s welfare and losses from suboptimal decisions accumulate over time. There are two intertwined challenges. First, decision-makers must allocate resources effectively even when utility estimates are uncertain, somehow balancing strategies to reduce uncertainty with the real costs of suboptimal assignments. Second, they need valid statistical assessments and guarantees of welfare on demand: has the current policy achieved their desired welfare threshold? Is uncertainty low enough to commit to the current policy and deploy it at scale? These questions arise adaptively, driven by externalities like budget cycles, stakeholder reviews, or shifting priorities. Both challenges therefore demand statistical guarantees that remain valid regardless of when they are invoked. Recent work has begun studying online welfare optimization in bandits, aggregating welfare across the temporal sequence of decisions to measure fairness over time (see Section 2 for details). We instead consider settings where a fixed population receives resources repeatedly and welfare measures fairness within this persistent population at each decision point. This fixed-population formulation has distinct structure: allocation policies are continuous probability vectors over individuals rather than discrete arm selections, multiple resources are distributed per round, and decisions are coupled through the constraint that allocation probabilities must sum to the number of available resources. The optimal policy thus depends on the relative utilities across all individuals, creating interdependencies absent from standard bandit problems. We address both challenges through a unified confidence sequence-based framework. Confidence sequences are interval estimates that remain valid at arbitrary stopping times, a property useful for guiding policy decisions or certifying statistical conclusions. Our framework requires three natural assumptions on SWFs—monotonicity, concavity, and Lipschitz continuity—each playing a distinct, minimal role. Our key insight is that monotonicity of the SWF alone suffices to lift coordinate-wise confidence sequences for individual utilities into anytime-valid bounds on population welfare of the current allocation (Theorem 4.1 ). This lifting principle connects a versatile statistical primitive to information that decision-makers actually need: guarantees on the optimal welfare value over the expected utilities that hold uniformly over time. The same machinery that enables optimistic allocation policies for online learning also supports inference applications—sequential hypothesis testing, optimal stopping, and policy evaluation—as natural byproducts. We make the following contributions. First, we formalize the problem of resource allocation over a population over multiple time steps, with the objective being given by an SWF-based aggregation of the ex-ante utilities. Second, we establish a confidence sequence lifting theorem that provides anytime-valid welfare bounds under monotonicity alone. Third, we instantiate this framework on three axiomatically distinct SWF families—Weighted Power Mean, Kolm, and Gini, spanning the spectrum from utilitarian to egalitarian objectives—and develop bespoke efficient oracles for policy optimization in each case. Fourth, we propose SWF-UCB, a general algorithm for online welfare maximization, and prove that it achieves near-optimal \tilde{\mathcal{O}}(n+\sqrt{nkT}) regret for k resources over a population of n in time T . Fifth, we present experiments confirming the predicted \sqrt{T} scaling and revealing that intermediate values of k yield the highest regret—a non-monotonic dependence suggesting rich structure in how resource scarcity interacts with learning difficulty. Finally, we comment on how the same confidence sequence framework can naturally be applied to meaningful inference tasks such as sequential hypothesis testing, optimal stopping, and policy evaluation (Appendix A.1 ). 2 Related Work Our framework unifies several research threads spanning multi-armed bandits, fair allocation, and welfare economics, through a common lens of online welfare maximization and time-uniform statistical inference. However, unlike prior work on welfare-aware or fair bandits, which either focus on specific objectives or learning guarantees alone, our approach supports general monotone SWFs, provides near-optimal regret guarantees, and enables anytime-valid inference for optimized welfare under partial feedback. Multi-armed bandit variants. Multi-play bandits ( 1 ; 10 ) consider the sum of the arm rewards when multiple arms can be pulled, which corresponds to utilitarian welfare in our setting. Combinatorial bandits ( 5 ; 19 ) study finding the best set of arms to pull for the greatest reward. To contrast, in our setting, all individuals need to be given a resource with non-zero probability, and thus we find the best allocation probabilities for the greatest welfare. ( 6 ) study combinatorial bandits with non-linear super-arm rewards assuming monotonicity and bounded smoothness. We use monotonicity of SWFs to establish a general confidence sequence lifting result (Theorem 4.1 ) and develop efficient and exact oracles for optimal allocation in our algorithm (SWF-UCB). Fair multi-armed bandits. Fairness in multi-armed bandits usually involves each arm being played a minimum number of times ( 7 ; 27 ) or meritocratic fairness ( 15 ; 16 ) . ( 20 ) study multi-play multi-armed bandits, where each play corresponds to a user, and they measure regret using the performance of the worst-off user, i.e., egalitarian welfare. Our work subsumes egalitarian welfare and provides a framework for learning and inference when allocating resources among a population. Welfare-based regret in bandits. ( 3 ) and ( 26 ) introduce Nash regret for the bandit setting, measuring cumulative loss via the geometric mean of per-round regrets . ( 25 ) and ( 18 ) extend this idea to the p -mean welfare family. This line of work aggregates utilities across time steps, whereas our work aggregates utilities across the population at every time step. We also provide a general framework for different social welfare functions, and the p -mean welfare family arises as a special case of the welfare families we consider, under a different axis of aggregation. Social welfare functions. The axiomatic foundations of our SWF families originate in welfare economics. 2 introduced inequality-averse welfare functions parameterized by a single parameter controlling the equity-efficiency tradeoff: our WPM family. 17 characterized the Kolm-Pollak family via translation invariance, while 29 formalized generalized Gini welfare through rank-dependent weights. In machine learning, 8 ; 9 provide Hölder continuity bounds enabling PAC-style learning guarantees. 23 addressed the complementary problem of learning SWFs from preference data. To our knowledge, our work contributes the first online learning and time-uniform inference framework for allocation using these welfare families with provable regret guarantees. 3 Problem setup We consider a population of n individuals among which a centralized decision-maker allocates identical, indivisible resources at discrete time steps. At each time step t , k\leq n resources arrive and are distributed among the population. Each individual receives at most one resource, and the utility of individual i when receiving a resource at time t is u_{t,i}\stackrel{{\scriptstyle iid}}{{\sim}}\mathcal{D}_{i} , where \mathcal{D}_{i} is an unknown distribution with mean \mu_{i}=\mathbb{E}_{U\sim\mathcal{D}_{i}}[U] . We assume that \mu_{i}>0 , and the utility of an individual not receiving a resource is zero. Allocation occurs according to a (randomized) policy , given by the vector \mathbf{p}\in[0,1]^{n} , where \sum_{i}p_{i}=k . Each p_{i} is the marginal probability that individual i receives one of the k resources. The ex-ante expected utility of the policy \mathbf{p} for individual i is thus given by \mu_{i}p_{i} . We denote the vector of expected utilities by \boldsymbol{\mu}\odot\mathbf{p} . Our model assumes that the distributions \left\{\mathcal{D}_{i}\right\}_{i\in[n]} of individual utilities remain static and do not change with time. Instead, we allow the allocation policy \mathbf{p} to change over time and conduct online learning and inference about the allocation policy. The effectiveness of the allocation is determined by aggregating the ex-ante expected utilities using a social welfare function (SWF), denoted by M(\boldsymbol{\mu}\odot\mathbf{p}) . We consider ex-ante utilities for two reasons. First, ex-ante utilities represent expected utilities prior to allocation. In contrast, post-allocation realized utilities assign zero utility to all individuals who do not receive a resource at a given time step, which can render several commonly studied social welfare functions degenerate or uninformative under partial allocation. As a result, ex-post welfare is not a meaningful object for optimization or comparison in our setting. Second, ex-ante utilities admit a natural long-run interpretation: for a fixed allocation policy \mathbf{p} , the vector \boldsymbol{\mu}\odot\mathbf{p} corresponds to the time-averaged utilities obtained when resources are repeatedly allocated according to \mathbf{p} . This interpretation is particularly important in inference-oriented settings—such as policy evaluation, sequential testing, and optimal stopping—where a single policy is to be deployed repeatedly and performance is assessed via long-run averages. We consider families of SWFs satisfying three natural assumptions: (A1) Monotonicity : Let \mathbf{v}_{1},\mathbf{v}_{2}\in\mathbb{R}_{+}^{n} be two utility vectors. If v_{1,i}\geq v_{2,i} for all i\in[n] , then M(\mathbf{v}_{1})\geq M(\mathbf{v}_{2}) . (A2) Concavity : M(\mathbf{v}) is concave in \mathbf{v} . (A3) Lipschitz continuity : M(\mathbf{v}) is Lipschitz continuous in \mathbf{v} w r.t. the \ell_{\infty} norm. Each assumption is used in our framework in a modular manner. Monotonicity is used to construct a confidence sequence for M(\boldsymbol{\mu}\odot\mathbf{p}) from observed utilities (Section 4 ), which is our core statistical insight. Concavity enables tractable policy optimization and efficient computation of the optimal solution (Section 5.1 ). Finally, Lipschitz continuity supports our theoretical analysis and regret guarantees (Section 5.2 ) concerning the optimality of our algorithm for online SWF maximization. 3.1 SWF Families We consider three popular families of SWFs. 1. Weighted power mean (WPM) has parameters \mathbf{w}\in\Delta_{n-1} and q\in(-\infty,1]\cup\{-\infty\} . It is defined as \begin{aligned} M_{\text{WPM}}(\boldsymbol{\mu}\odot\mathbf{p};\mathbf{w},q)=\begin{cases}\min_{i\in[n]}\mu_{i}p_{i}\quad&\text{if}\ q=-\infty\\ \prod_{i}\left(\mu_{i}p_{i}\right)^{w_{i}}\quad&\text{if}\ q=0\\ \left(\sum_{i}w_{i}\left(\mu_{i}p_{i}\right)^{q}\right)^{1/q}\quad&\text{otherwise}\end{cases}\end{aligned} . Intuitively, \mathbf{w} encodes the relative weights given to the individuals. q encodes the notion of fairness used: q=0 corresponds to Nash social welfare, whereas q=1 corresponds to utilitarian social welfare ( M_{\text{WPM}}=\sum_{i}w_{i}\mu_{i}p_{i} ). WPM satisfies relative inequality aversion ( 9 ) : for any a>0 , then M_{\text{WPM}}(a\mathbf{u})=aM_{\text{WPM}}(\mathbf{u}) . 2. (Weighted) Kolm social welfare has parameters \mathbf{w}\in\Delta_{n-1} and q\in(-\infty,0]\cup\{-\infty\} . It is defined as \begin{aligned} M_{\text{Kolm}}(\boldsymbol{\mu}\odot\mathbf{p};\mathbf{w},q)=\begin{cases}\min_{i\in[n]}\mu_{i}p_{i}\quad&\text{if}\ q=-\infty\\ \sum_{i}w_{i}\mu_{i}p_{i}\quad&\text{if}\ q=0\\ \frac{1}{q}\cdot\log\left(\sum_{i}w_{i}\exp\left(q\mu_{i}p_{i}\right)\right)\quad&\text{otherwise}\end{cases}\end{aligned} . \mathbf{w} and q encode individuals’ relative weights and fairness notion (same as WPM). Kolm SWF satisfies the axiom of absolute inequality aversion ( 17 ) : for any a>0 M_{\text{Kolm}}(\mathbf{u}+a\boldsymbol{1}_{n})=M_{\text{Kolm}}(\mathbf{u})+a . 3. Gini social welfare has parameters \mathbf{w}\in[0,1]^{n} such that w_{1}\geq w_{2}\geq\ldots\geq w_{n}\geq 0 , and \displaystyle M_{\text{Gini}}(\boldsymbol{\mu}\odot\mathbf{p};\mathbf{w})=\sum_{i}w_{i}(\boldsymbol{\mu}\odot\mathbf{p})_{(i)}, where (\boldsymbol{\mu}\odot\mathbf{p})_{(i)} denotes the i -th smallest element in the vector \boldsymbol{\mu}\odot\mathbf{p} . We note that with appropriate choices of \mathbf{w} , M_{\text{Gini}} is identical to the utilitarian welfare ( \mathbf{w}=\boldsymbol{1}_{n} ) and egalitarian welfare ( w_{1}=1 , w_{i}=0 for i\geq 2 ) with appropriate \mathbf{w} . The Gini SWF satisfies rank-based inequality sensitivity ( 29 ) , where the order of the utilities matter but not their identities. All three SWF families span the space of social welfare formulations from egalitarian welfare to utilitarian welfare in different manners. Crucially, all three SWFs satisfy our assumptions ( A1 )-( A3 ). Proposition 3.1 . M_{\text{WPM}}(\mathbf{v}) , M_{\text{Kolm}}(\mathbf{v}) , and M_{\text{Gini}}(\mathbf{v}) are all monotonic and concave in \mathbf{v} . Moreover, 1. Let u_{t,i}\in[u_{\min},u_{\max}] , where u_{\max}\geq u_{\min}>0 . Then, M_{\text{WPM}} is Lipschitz continuous w.r.t. the \ell_{\infty} norm with constant upper bounded by u_{\max}/u_{\min} . 2. M_{\text{Kolm}} is Lipschitz continuous w.r.t. the \ell_{\infty} norm with constant 1 . 3. M_{\text{Gini}} is Lipschitz continuous w.r.t the \ell_{\infty} norm with constant \sum_{i}w_{i} . We prove this result in Appendix B.1 . Remark 3.2 . While our upper bound of u_{\max}/u_{\min} for the Lipschitz constant for the WPM family holds for all q\in(-\infty,1]\cup\left\{-\infty\right\} , ( 8 ) provide tighter Lipschitz continuity bounds for q<0 and Hölder continuity bounds for q\in[0,1] . These bounds can be used for tighter theoretical guarantees (for instance, by plugging into Theorem 5.2 ). We define the optimal allocation \mathbf{p}^{*} w.r.t. the SWF M(\cdot) as \displaystyle\mathbf{p}^{*}=\arg\max_{\mathbf{p}\in\mathcal{P}_{k}}M(\boldsymbol{\mu}\odot\mathbf{p}), where \mathcal{P}_{k}=\left\{\mathbf{p}\in[0,1]^{n}\mid\sum_{i}p_{i}=k\right\} . 4 Confidence Sequence Framework Using Monotonicity We begin by constructing a confidence sequence (CS) for the optimal welfare value M(\boldsymbol{\mu}\odot\mathbf{p}^{*}) , which will serve as the statistical backbone for learning, testing, and stopping procedures. Given observed data \left\{x_{t}\right\}_{t\geq 1} and some \delta\in(0,1) , a valid (1-\delta) CS for a target quantity \theta consists of a sequence of intervals \left\{[x_{t}^{\downarrow},x_{t}^{\uparrow}]\right\}_{t\geq 1} such that x_{t}^{\downarrow} and x_{t}^{\uparrow} depend on the past data \left\{x_{s}\right\}_{sW_{0}. From the first part of Corollary A.1 , we get the test: reject null at \tau=\inf\left\{t:W^{\downarrow}_{\mathbf{p},t}>W_{0}\right\} . Because of the time-uniform nature of the CS, we have \displaystyle\mathbb{P}_{H_{0}}(\exists t:W^{\downarrow}_{\mathbf{p},t}>W_{0})\leq\delta, which means that the test is valid. 2. Dynamic policy \mathbf{p}_{t} : In this case, the decision-maker would want to know if the optimal allocation policy \mathbf{p}^{*} achieves a welfare exceeding a certain value W^{*} . Here, both the policy and welfare are data-dependent. The hypotheses to be tested are \displaystyle H_{0}:M(\boldsymbol{\mu}\odot\mathbf{p}^{*})W_{0}. From the second part of Corollary A.1 , we get the test: reject null at \tau=\inf\left\{t:W^{\downarrow}_{t}>W_{0}\right\} . Because of the time-uniform nature of the CS, we have \displaystyle\mathbb{P}_{H_{0}}(\exists t:W^{\downarrow}_{t}>W_{0})\leq\delta, which means that the test is valid. Since the bound is time-uniform, this testing can be adaptive, where the experiment can be stopped once enough evidence has been gathered for the null to be rejected ( 24 ) . This idea can also be applied to test for the allocation achieving a value below a certain threshold W_{*} by considering upper confidence sequences \left\{M(\boldsymbol{\mu}^{\uparrow}_{t}\odot\mathbf{p}^{\uparrow}_{t})\right\}_{t\geq 1} . Optimal stopping. Consider a decision-making setting where a policy is to be learned dynamically in a testing phase. The testing phase is stopped when the social welfare achieved by the current allocation exceeds a certain value W_{0} , after which the policy is deployed. Unlike sequential testing, the goal here is not hypothesis rejection but deciding when to transition from exploration to deployment. Let \mathcal{E}=\left\{\forall t\geq 1:\boldsymbol{\mu}^{\downarrow}_{t}\preceq\boldsymbol{\mu}\right\} , which holds with probability at least (1-\delta) . On \mathcal{E} , since M is a monotone function, for all t , M(\boldsymbol{\mu}\odot\mathbf{p}^{\downarrow}_{t})\geq M(\boldsymbol{\mu}^{\downarrow}_{t}\odot\mathbf{p}^{\downarrow}_{t})=W^{\downarrow}_{t} Our stopping guarantee in this case is thus: at \tau=\inf\left\{t:W^{\downarrow}_{t}>W_{0}\right\} , \mathbb{P}(M(\boldsymbol{\mu}\odot\mathbf{p}^{\downarrow}_{\tau})>W_{0})\geq 1-\delta. After stopping the experiment, we deploy \mathbf{p}^{\downarrow}_{\tau} . Policy evaluation. Our method can also be used to compare the social welfare for two policies \mathbf{p}_{(1)} and \mathbf{p}_{(2)} . This allows us to compare the policies and choose the better one among them for deployment in an adaptive fashion. Interestingly, either of these policies (or a combination of them) can be used to gather the data,provided the induced sampling process ensures coverage of all individuals (e.g., p_{t,i}\geq\gamma>0 for all i ), since we only require CSs on the individual utilities \mu_{t,i} . Based on the first part of Corollary A.1 , we construct (1-\delta/2) welfare CSs for \mathbf{p}_{(1)} and \mathbf{p}_{(2)} , denoting them by \left\{[W^{\downarrow}_{(1),t},W^{\uparrow}_{(1),t}]\right\}_{t\geq 1} and \left\{[W^{\downarrow}_{(2),t},W^{\uparrow}_{(2),t}]\right\}_{t\geq 1} . Policy i can be chosen for deployment over policy j with confidence (1-\delta) when W^{\downarrow}_{(i),t}>W^{\uparrow}_{(j),t} . A.2 Extension: Stochastic Utilities for non-allocation In Sections 3 – 6 , we assume that the utility when an individual does not receive a resource is zero. We now discuss how the CS-based framework can be extended to stochastically observed utilities for non-allocation. Let u_{t,i}^{(1)}\stackrel{{\scriptstyle iid}}{{\sim}}\mathcal{D}_{i}^{(1)} and u_{t,i}^{(0)}\stackrel{{\scriptstyle iid}}{{\sim}}\mathcal{D}_{i}^{(0)} be the stochastic utilities at time t when an individual i is allocated and not allocated a resource, respectively. Let \mu_{i}^{(1)} and \mu_{i}^{(0)} respectively be the mean utilities for allocation and non-allocation to individual i . The ex-ante utility for allocation policy \mathbf{p} is thus given by \overline{\boldsymbol{\mu}}(\mathbf{p})=\boldsymbol{\mu}^{(1)}\odot\mathbf{p}+\boldsymbol{\mu}^{(0)}\odot(\boldsymbol{1}_{n}-\mathbf{p}), and the social welfare is thus M\left(\overline{\boldsymbol{\mu}}(\mathbf{p})\right) . Thus, allocating a resource to individual i yields an effective utility gain of \mu_{i}^{(1)}-\mu_{i}^{(0)} relative to non-allocation. Extending confidence sequences. Using the observed values, we can construct (1-\delta/2n) two-sided CSs for \mu_{i}^{(1)} and \mu_{i}^{(0)} , denoted by \left\{[\mu_{t,i}^{(1)\uparrow},\mu_{t,i}^{(1)\downarrow}]\right\}_{t\geq 1} and \left\{[\mu_{t,i}^{(0)\downarrow},\mu_{t,i}^{(0)\uparrow}]\right\}_{t\geq 1} . By the union bound, we get the following (1-\delta) CS for \overline{\boldsymbol{\mu}}(\mathbf{p}) : \left\{\left[\left(\boldsymbol{\mu}_{t}^{(1)\downarrow}-\boldsymbol{\mu}_{t}^{(0)\uparrow}\right)\mathbf{p}+\boldsymbol{\mu}_{t}^{(0)\downarrow},\left(\boldsymbol{\mu}_{t}^{(1)\uparrow}-\boldsymbol{\mu}_{t}^{(0)\downarrow}\right)\mathbf{p}+\boldsymbol{\mu}_{t}^{(0)\uparrow}\right]\right\}_{t\geq 1}. If we let \displaystyle\mathbf{p}^{\downarrow}_{t} \displaystyle=\arg\max_{\mathbf{p}\in\mathcal{P}_{\leq k}}\left(\boldsymbol{\mu}_{t}^{(1)\downarrow}-\boldsymbol{\mu}_{t}^{(0)\uparrow}\right)\mathbf{p}+\boldsymbol{\mu}_{t}^{(0)\downarrow},\quad\text{and} \displaystyle\mathbf{p}^{\uparrow}_{t} \displaystyle=\arg\max_{\mathbf{p}\in\mathcal{P}_{\leq k}}\left(\boldsymbol{\mu}_{t}^{(1)\uparrow}-\boldsymbol{\mu}_{t}^{(0)\downarrow}\right)\mathbf{p}+\boldsymbol{\mu}_{t}^{(0)\uparrow}, we then have the following (1-\delta) CS: \left\{\left[\left(\boldsymbol{\mu}_{t}^{(1)\downarrow}-\boldsymbol{\mu}_{t}^{(0)\uparrow}\right)\mathbf{p}^{\downarrow}_{t}+\boldsymbol{\mu}_{t}^{(0)\downarrow},\left(\boldsymbol{\mu}_{t}^{(1)\uparrow}-\boldsymbol{\mu}_{t}^{(0)\downarrow}\right)\mathbf{p}^{\uparrow}_{t}+\boldsymbol{\mu}_{t}^{(0)\uparrow}\right]\right\}_{t\geq 1}. Owing to the monotonicity of M(\cdot) and proceeding through a similar sequence of inequalities as in Theorem 4.1 , we get the following (1-\delta) CS for M(\overline{\boldsymbol{\mu}}(\mathbf{p})) \left\{\left[M\left(\left(\boldsymbol{\mu}_{t}^{(1)\downarrow}-\boldsymbol{\mu}_{t}^{(0)\uparrow}\right)\mathbf{p}^{\downarrow}_{t}+\boldsymbol{\mu}_{t}^{(0)\downarrow}\right),M\left(\left(\boldsymbol{\mu}_{t}^{(1)\uparrow}-\boldsymbol{\mu}_{t}^{(0)\downarrow}\right)\mathbf{p}^{\uparrow}_{t}+\boldsymbol{\mu}_{t}^{(0)\uparrow}\right)\right]\right\}_{t\geq 1}. Extending oracle algorithms. Our oracle algorithm has to solve a problem of the form \displaystyle\mathbf{p}^{\uparrow}_{t} \displaystyle=\arg\max_{\mathbf{p}\in\mathcal{P}_{\leq k}}M\left(\left(\boldsymbol{\mu}_{t}^{(1)\uparrow}-\boldsymbol{\mu}_{t}^{(0)\downarrow}\right)\mathbf{p}+\boldsymbol{\mu}_{t}^{(0)\uparrow}\right). For some individual i , if \boldsymbol{\mu}_{t,i}^{(0)\downarrow}>\boldsymbol{\mu}_{t,i}^{(1)\uparrow} , we can infer with high confidence that not allocating a resource gives them higher utility. In this case, allocating a resource to individual i can only decrease the welfare objective with high probability, and monotonicity implies that setting p_{i}=0 is optimal. Thus, such individuals can be excluded from the allocation, and the optimization problem can be solved only for the remaining individuals. This in turn raises the possibility of less than k resources being allocated to the population, which results in our feasible set for \mathbf{p} becoming \mathcal{P}_{\leq k}=\left\{\mathbf{p}\in[0,1]^{n}:\sum_{i}p_{i}=s,s\in\mathbb{N},s\leq k\right\} Appendix B Proofs B.1 Proof of Proposition 3.1 Proof. Monotonicity and concavity : Monotonicity is guaranteed by the axioms of social welfare for M_{\text{WPM}} , M_{\text{Kolm}} , and M_{\text{Gini}} . We now establish concavity of the three SWF families. • WPM : We begin by noting that for q=-\infty , M_{\text{WPM}}(\mathbf{v})=\min_{i}v_{i} is concave in \mathbf{v} , since for two valid vectors \mathbf{v}_{1} and \mathbf{v}_{2} , \displaystyle\min_{i}\lambda v_{1,i}+(1-\lambda)v_{2,i} \displaystyle\geq\lambda\min_{i}v_{1,i}+(1-\lambda)\min_{j}v_{2,j} For q\in(-\infty,1) , we express the WPM SWF as \displaystyle M_{\text{WPM}}(\mathbf{v};\mathbf{w};q)=\left(\sum_{i}\left(w_{i}^{1/q}v_{i}\right)^{q}\right)^{1/q} Let \mathbf{v}_{1} and \mathbf{v}_{2} be two valid vectors. Applying the reverse Minkowski inequality, we get \displaystyle M_{\text{WPM}}(\lambda\mathbf{v}_{1}+(1-\lambda)\mathbf{v}_{2};\mathbf{w},q) \displaystyle=\left(\sum_{i}\left(\lambda w_{i}^{1/q}v_{1,i}+(1-\lambda)w_{i}^{1/q}v_{2,i}\right)^{q}\right)^{1/q} \displaystyle\geq\left(\sum_{i}\left(\lambda w_{i}^{1/q}v_{1,i}\right)^{q}\right)^{1/q}+\left(\sum_{i}\left((1-\lambda)w_{i}^{1/q}v_{w,i}\right)^{q}\right)^{1/q} \displaystyle=\lambda M_{\text{WPM}}(\mathbf{v}_{1};\mathbf{w},q)+(1-\lambda)M_{\text{WPM}}(\mathbf{v}_{2};\mathbf{w},q) • Kolm : Since q=-\infty is the egalitarian case and q=0 is the utilitarian case, they have already been shown to be concave via the WPM SWF. For q\in(-\infty,0) , the concavity of M_{\text{Kolm}} follows from the log-sum-exp function being convex, and it being pre-multiplied by 1/q (a negative quantity). • Gini : The Gini SWF can also be expressed as M_{\text{Gini}}(\mathbf{v};\mathbf{w})=\min_{\sigma}\sum_{i}w_{\sigma(i)}v_{i}, where \sigma is a permutation of the set \{1,\ldots,n\} . Since we are taking the minimum of a set of affine functions, the resultant is a concave function. Lipschitz continuity : We now establish the Lipschitz continuity of the SWF families. By the mean value theorem we know that for two valid vectors \mathbf{v}_{1} and \mathbf{v}_{2} , there is a vector \mathbf{x} such that \displaystyle M(\mathbf{v}_{1})-M(\mathbf{v}_{2}) \displaystyle=\nabla M(\mathbf{x})\cdot(\mathbf{v}_{1}-\mathbf{v}_{2}) \displaystyle\left|M(\mathbf{v}_{1})-M(\mathbf{v}_{2})\right| \displaystyle=\left|\nabla M(\mathbf{x})\cdot(\mathbf{v}_{1}-\mathbf{v}_{2})\right|\stackrel{{\scriptstyle(i)}}{{\leq}}\left\|\nabla M(\mathbf{x})\right\|_{1}\cdot\left\|\mathbf{v}_{1}-\mathbf{v}_{2}\right\|_{\infty}, where (i) uses Hölder’s inequality. Thus, to show Lipschitz continuity w.r.t. the \ell_{\infty} norm, we provide bounds on \left\|\nabla M(\mathbf{x})\right\|_{1} • WPM : Let v_{i}\in[v_{\min},v_{\max}] for v_{\max}\geq v_{\min}>0 . We then have, for q\in(-\infty,0)\cup(0,1] , \displaystyle M_{\text{WPM}}(\mathbf{v};\mathbf{w},q) \displaystyle=\left(\sum_{i}w_{i}v_{i}^{q}\right)^{1/q} \displaystyle\frac{\partial}{\partial v_{i}}M_{\text{WPM}}(\mathbf{v};\mathbf{w},q) \displaystyle=\frac{1}{q}\cdot\left(\sum_{i}w_{i}v_{i}^{q}\right)^{1/q-1}\cdot qw_{i}v_{i}^{q-1} \displaystyle=M_{\text{WPM}}(\mathbf{v};\mathbf{w},q)\cdot\frac{w_{i}v_{i}^{q}}{\sum_{i}w_{i}v_{i}^{q}}\cdot\frac{1}{v_{i}} \displaystyle\implies\sum_{i}\left|\frac{\partial}{\partial v_{i}}M_{\text{WPM}}(\mathbf{v};\mathbf{w},q)\right| \displaystyle\leq\frac{M}{v_{\min}}\leq\frac{v_{\max}}{v_{\min}}. For q=0 , we have \displaystyle M_{\text{WPM}}(\mathbf{v};\mathbf{w},0) \displaystyle=\prod_{i}v_{i}^{w_{i}} \displaystyle\frac{\partial}{\partial v_{i}} \displaystyle=\prod_{i}v_{i}^{w_{i}}\cdot\frac{w_{i}}{v_{i}}=M(\mathbf{v};\mathbf{w},0)\cdot\frac{w_{i}}{v_{i}} \displaystyle\implies\sum_{i}\left|\frac{\partial}{\partial v_{i}}M_{\text{WPM}}(\mathbf{v};\mathbf{w},q)\right| \displaystyle\leq\frac{M}{v_{\min}}\leq\frac{v_{\max}}{v_{\min}}. For q=-\infty , we observe that the sum of all subgradients is upper bounded by 1, which is clearly less than v_{\max}/v_{\min} . Thus, v_{\max}/v_{\min} is the Lipschitz constant. We additionally note that for q=1 , M_{\text{WPM}}(\mathbf{v};\mathbf{w},1)=\sum_{i}w_{i}v_{i} has \left\|\nabla M_{\text{WPM}}(\mathbf{v};\mathbf{w},1)\right\|_{1}=\sum_{i}w_{i}=1 . • Kolm : The case of q=-\infty (egalitarian) and q=0 (utilitarian) is already considered in the WPM case. For q\in(-\infty,0) , we have \displaystyle M_{\text{Kolm}}(\mathbf{v};\mathbf{w},q) \displaystyle=\frac{1}{q}\log\left(\sum_{i}\exp(qv_{i})\right) \displaystyle\frac{\partial}{\partial v_{i}}M_{\text{Kolm}}(\mathbf{v};\mathbf{w},q) \displaystyle=\frac{1}{q}\cdot\frac{1}{\sum_{i}w_{i}\exp(qu_{i})}\cdot w_{i}q\exp(qu_{i})=\frac{w_{i}\exp(qu_{i})}{\sum_{i}w_{i}\exp(qu_{i})} \displaystyle\implies\sum_{i}\left|\frac{\partial}{\partial v_{i}}M_{\text{Kolm}}(\mathbf{v};\mathbf{w},q\right| \displaystyle=1 • Gini : We consider the alternate expression for the Gini SWF: M_{\text{Gini}}(\mathbf{v};\mathbf{w})=\min_{\sigma}\sum_{i}w_{\sigma(i)}v_{i}. We note that this is the minimum over affine functions f_{\sigma}(\mathbf{v})=\sum_{i}w_{\sigma_{i}}v_{i} , each of which has \left\|\nabla f_{\sigma}\right\|_{1}=\sum_{i}w_{i}=L . Thus, the subgradient of M_{\text{Gini}} is such that \left\|\partial M_{\text{Gini}}(\mathbf{v};\mathbf{w})\right\|_{1}\leq L . ∎ B.2 Proof of Theorem 4.1 Proof. For all i\in[n] , let \left\{[\mu^{\downarrow}_{t,i},\mu^{\uparrow}_{t,i}]\right\}_{t\geq 1} be a (1-\delta/n) confidence sequence for i . That is, \displaystyle\mathbb{P}\left(\exists t\in\mathbb{N}:\mu_{i}\not\in[\mu^{\downarrow}_{t,i},\mu^{\uparrow}_{t,i}]\right)\leq\frac{\delta}{n} By the union bound, we thus have that for the sequence \left\{[\boldsymbol{\mu}^{\downarrow}_{t},\boldsymbol{\mu}^{\uparrow}_{t}]\right\}_{t\geq 1} \displaystyle\mathbb{P}\left(\exists t\in\mathbb{N}:\boldsymbol{\mu}\not\in[\boldsymbol{\mu}^{\downarrow}_{t},\boldsymbol{\mu}^{\uparrow}_{t}]\right)\leq\delta, where \mathbf{x}\in[\mathbf{x}^{\downarrow}_{t},\mathbf{x}^{\uparrow}_{t}] means that x_{i}\in[x^{\downarrow}_{t,i},x^{\uparrow}_{t,i}] for all i\in[n] . Thus, with probability (1-\delta) we have \displaystyle M(\boldsymbol{\mu}\odot\mathbf{p}^{*}) \displaystyle\stackrel{{\scriptstyle(i)}}{{\geq}}M(\boldsymbol{\mu}\odot\mathbf{p}^{\downarrow}_{t})\stackrel{{\scriptstyle(ii)}}{{\geq}}M(\boldsymbol{\mu}^{\downarrow}_{t}\odot\mathbf{p}^{\downarrow}_{t}),\quad\text{and} \displaystyle M(\boldsymbol{\mu}\odot\mathbf{p}^{*}) \displaystyle\stackrel{{\scriptstyle(iii)}}{{\leq}}M(\boldsymbol{\mu}^{\uparrow}_{t}\odot\mathbf{p}^{*})\stackrel{{\scriptstyle(iv)}}{{\leq}}M(\boldsymbol{\mu}^{\uparrow}_{t}\odot\mathbf{p}^{\uparrow}_{t}). (i) results from \mathbf{p}^{*} being optimal for \boldsymbol{\mu} , and (ii) results from the CS bound and the monotonicity of M(\cdot) . (iii) comes from the CS bound and the monotonicity of M(\cdot) , and (iv) comes from \mathbf{p}^{\uparrow}_{t} being optimal for \boldsymbol{\mu}^{\uparrow}_{t} . This means that \displaystyle\mathbb{P}(\exists t\in\mathbb{N}:M(\boldsymbol{\mu}\odot\mathbf{p}^{*})\not\in[M(\boldsymbol{\mu}^{\downarrow}_{t}\odot\mathbf{p}^{\downarrow}_{t}),M(\boldsymbol{\mu}^{\uparrow}_{t}\odot\mathbf{p}^{\uparrow}_{t})])\leq\delta ∎ B.3 Proof of Theorem 5.2 Proof. Let \left\{\boldsymbol{\mu}^{\uparrow}_{t}\right\}_{t\geq 1} be a (1-\delta/2) confidence sequence for \boldsymbol{\mu} . From Theorem 4.1 , we know that, with probability (1-\delta/2) \displaystyle M(\boldsymbol{\mu}\odot\mathbf{p}^{*}) \displaystyle\stackrel{{\scriptstyle(iii)}}{{\leq}}M(\boldsymbol{\mu}^{\uparrow}_{t}\odot\mathbf{p}^{*})\stackrel{{\scriptstyle(iv)}}{{\leq}}M(\boldsymbol{\mu}^{\uparrow}_{t}\odot\mathbf{p}^{\uparrow}_{t}). Thus, we have, with probability (1-\delta/2) , \displaystyle R(T) \displaystyle=\sum_{t=1}^{T}M(\boldsymbol{\mu}\odot\mathbf{p}^{*})-M(\boldsymbol{\mu}\odot\mathbf{p}^{\uparrow}_{t}) \displaystyle\leq\sum_{t=1}^{T}M(\boldsymbol{\mu}^{\uparrow}_{t}\odot\mathbf{p}^{*})-M(\boldsymbol{\mu}\odot\mathbf{p}^{\uparrow}_{t}) \displaystyle\leq\sum_{t=1}^{T}M(\boldsymbol{\mu}_{t}^{\uparrow}\odot\mathbf{p}_{t}^{\uparrow})-M(\boldsymbol{\mu}\odot\mathbf{p}_{t}^{\uparrow}) If we now assume that M is L -Lipschitz w.r.t. \left\|\cdot\right\|_{\infty} (the maximum value), we get \displaystyle R(T) \displaystyle\leq\sum_{t=1}^{T}M(\boldsymbol{\mu}_{t}^{\uparrow}\odot\mathbf{p}_{t}^{\uparrow})-M(\boldsymbol{\mu}\odot\mathbf{p}_{t}^{\uparrow}) \displaystyle\leq\sum_{t=1}^{T}L\left\|\boldsymbol{\mu}_{t}^{\uparrow}\odot\mathbf{p}^{\uparrow}_{t}-\boldsymbol{\mu}\odot\mathbf{p}^{\uparrow}_{t}\right\|_{\infty} Thus, we have bounded the regret in terms of the confidence sequence for \boldsymbol{\mu} . By Hölder’s inequality, we thus have \displaystyle\sum_{t=1}^{T}L\|\boldsymbol{\mu}^{\uparrow}_{t}\odot\mathbf{p}^{\uparrow}_{t}-\boldsymbol{\mu}\odot\mathbf{p}^{\uparrow}_{t}\|_{\infty} \displaystyle\leq\sum_{t=1}^{T}L\|\boldsymbol{\mu}^{\uparrow}_{t}\odot\mathbf{p}^{\uparrow}_{t}-\boldsymbol{\mu}\odot\mathbf{p}^{\uparrow}_{t}\|_{1} \displaystyle=L\sum_{t=1}^{T}\sum_{i=1}^{n}|\mu_{t,i}^{\uparrow}-\mu_{i}|p^{\uparrow}_{t,i} \displaystyle\lesssim L\sum_{t=1}^{T}\sum_{i=1}^{n}p_{t,i}\sqrt{\frac{\log\log(N_{t,i}+1)+\log(n/\delta)}{N_{t,i}+1}} \displaystyle\lesssim L\sqrt{\log\log T+\log(n/\delta)}\underbrace{\sum_{i=1}^{n}\sum_{t=1}^{T}\frac{p_{t,i}}{\sqrt{N_{t,i}+1}}}_{S} We now bound the term S . We observe that N_{t,i} is the sum of Bernoulli random variables N_{t,i}=\sum_{s=1}^{t}X_{s,i} , where X_{s,i}\sim\text{Ber}(p_{s,i}) . We then have the following anytime-valid guarantee (from the Master theorem in ( 13 ) ): \displaystyle\mathbb{P}\left(\exists t\in\mathbb{N}:\sum_{s=1}^{t}(p_{s,i}-X_{s,i})\geq a+b\sum_{s=1}^{t}p_{s,i}\right)\leq\exp\left(-\frac{2ab}{1+b}\right) We set b=0.5 , and a=(3/2)\cdot\log(2n/\delta) , so that the upper bound above is \delta/2n . We then have that with probability (1-\delta/2n) , for all t\in\mathbb{N} , \displaystyle\sum_{s=1}^{t}(p_{s,i}-X_{s,i}) \displaystyle\leq a+b\sum_{s=1}^{t}p_{s,i} \displaystyle\implies N_{t,i}=\sum_{s=1}^{t}X_{s,i} \displaystyle\geq 0.5\sum_{s=1}^{t}p_{s,i}-a We can now consider two cases: 1. \sum_{s=1}^{t}p_{s,i}\leq 2a : Here, we can say \displaystyle\sum_{s=1}^{t}\frac{p_{s,i}}{\sqrt{N_{s,i}+1}}\leq\sum_{s=1}^{t}p_{s,i}\leq 2a, which is a constant. Thus in this case, the regret is upper-bounded by a constant. 2. \sum_{s=1}^{t}p_{s,i}>2a : Let this be true for t\geq t_{0} . We then have, with probability (1-2\delta) , \displaystyle\sum_{s=t_{0}}^{t}\frac{p_{s,i}}{\sqrt{N_{s,i}+1}} \displaystyle\leq\sum_{s=t_{0}}^{t}\frac{1}{\sqrt{0.5(\sum_{k=1}^{s}p_{k,i})-a}} \displaystyle\leq 2\sqrt{2}\cdot\sqrt{\left(\sum_{s=1}^{t}p_{s,i}\right)-2a} We thus have \displaystyle\sum_{t=1}^{T}\frac{p_{s,i}}{\sqrt{N_{s,i}+1}} \displaystyle\lesssim a+\sqrt{\left(\sum_{t=1}^{T}p_{t,i}\right)-a} \displaystyle\implies\sum_{i=1}^{n}\sum_{t=1}^{T}\frac{p_{t,i}}{\sqrt{N_{t,i}+1}} \displaystyle\lesssim na+\sum_{i=1}^{n}\sqrt{\left(\sum_{t=1}^{T}p_{t,i}\right)-a} \displaystyle\leq na+\sqrt{nkT-na} Thus, we have \displaystyle R(T)\lesssim L\sqrt{\log\log T+\log\left(\frac{2n}{\delta}\right)}\left[n\log\left(\frac{2n}{\delta}\right)+\sqrt{nkT-n\log\left(\frac{2n}{\delta}\right)}\right] We thus get a rate of the form \mathcal{O}(\sqrt{\log\log T+\log n}(n\log n+\sqrt{nkT})) . ∎ Appendix C Details of Theorem 5.1 C.1 WPM SWF C.1.1 Deriving proposed solution Our objective can be stated as maximize \displaystyle M_{\text{WPM}}(\mathbf{u}\odot\mathbf{p};\mathbf{w},q)=\left(\sum_{i}w_{i}(u_{i}p_{i})^{q}\right)^{1/q} s.t. \displaystyle\sum_{i}p_{i}=k \displaystyle p_{i}-1\leq 0 \displaystyle-p_{i}\leq 0 First, let us consider the case where the p_{i} ’s are unrestricted. After differentiation w.r.t. p_{i} , at the optimal point, we would want \displaystyle\frac{\partial}{\partial p_{i}}M_{\text{WPM}} \displaystyle=\lambda^{\prime} \displaystyle\lambda^{\prime} \displaystyle=\frac{1}{q}\cdot\left(\sum_{i}w_{i}(u_{i}p_{i})^{q}\right)^{(1/q-1)}\cdot w_{i}u_{i}^{q}\cdot qp_{i}^{q-1} \displaystyle=M_{\text{WPM}}(\mathbf{u}\odot\mathbf{p};\mathbf{w},q)\cdot\frac{w_{i}u_{i}^{q}}{\sum_{i}w_{i}(u_{i}p_{i})^{q}}p_{i}^{q-1} \displaystyle p_{i} \displaystyle=\lambda(w_{i}u_{i}^{q})^{1/(1-q)}, where \lambda=\left(\frac{\lambda^{\prime}\cdot\sum_{i}w_{i}(u_{i}p_{i}^{q})}{M_{\text{WPM}}(\mathbf{u}\odot\mathbf{p};\mathbf{w},q}\right)^{1/(q-1)} Our proposed solution is thus p_{i}=\left[\lambda(w_{i}u_{i}^{q})^{1/(1-q)}\right]_{[0,1]}, which is p_{i} restricted to be between 0 and 1, with \lambda chosen such that \sum_{i}p_{i}=k . C.1.2 Proving optimality via KKT conditions The Lagrangian for the objective is \displaystyle\mathcal{L}(\mathbf{p},\boldsymbol{\alpha},\boldsymbol{\beta},\gamma) \displaystyle=-M_{\text{WPM}}(\mathbf{u}\odot\mathbf{p};\mathbf{w},q)+\sum_{i}\alpha_{i}(p_{i}-1)+\sum_{i}\beta_{i}(-p_{i})+\gamma(\sum_{i}p_{i}-k) Recall that KKT conditions require the following: 1. Stationarity : For all i , \displaystyle\frac{\partial}{\partial p_{i}}\mathcal{L}=-M_{\text{WPM}}(\mathbf{u}\odot\mathbf{p};\mathbf{w},q)\cdot\frac{w_{i}(u_{i}p_{i})^{q}}{\sum_{i}w_{i}(u_{i}p_{i})^{q}}\cdot\frac{1}{p_{i}}+\alpha_{i}-\beta_{i}+\gamma=0 2. Primal feasibility : \sum_{i}p_{i}=k , and p_{i}\in[0,1] for all i . 3. Dual feasibility : \alpha_{i}\geq 0 , \beta_{i}\geq 0 for all i . 4. Complementary slackness : \alpha_{i}(1-p_{i})=0 and \beta_{i}p_{i}=0 for all i . We choose our proposed solution \mathbf{p}^{*} in Equation such that 0rem then 21: t_{final}\leftarrow rem/R_{i} {Remaining mass doesn’t fill any more containers fully} 22: p_{\pi(j)}\leftarrow t_{final}\cdot r_{(j)} for j\in\{i,\dots,n\} 23: rem\leftarrow 0 ; break 24: else 25: p_{\pi(i)}\leftarrow 1.0 26: rem\leftarrow rem-1 27: end if 28: end for 29: return p C.2 Kolm SWF C.2.1 Deriving proposed solution We want to optimize the Kolm social welfare under constraints. The problem is given by, for q<0 , \displaystyle\text{maximize} \displaystyle M_{\text{Kolm}}(\mathbf{u};\mathbf{w},q)=\frac{1}{q}\log\left(\sum_{i}w_{i}\exp(qu_{i}p_{i})\right) \displaystyle\text{s.t.} \displaystyle p_{i}\in[0,1]\qquad\forall i \displaystyle\sum_{i}p_{i}=k, where k\in[n] . First, let us consider the case where the p_{i} ’s are unrestricted. After differentiation w.r.t. p_{i} , at the optimal point, we would want \displaystyle\frac{\partial}{\partial p_{i}}M_{\text{Kolm}} \displaystyle=\lambda \displaystyle\lambda \displaystyle=\frac{1}{q}\cdot\frac{1}{\sum_{i}w_{i}\exp(qu_{i}p_{i})}\cdot w_{i}qu_{i}\exp(qu_{i}p_{i}) \displaystyle p_{i} \displaystyle=\log\left(\frac{\lambda^{\prime}}{w_{i}u_{i}}\right)\cdot\frac{1}{qu_{i}}, where \lambda^{\prime}=\lambda\cdot\left(\sum_{i}w_{i}\exp(qu_{i}p_{i})\right) . The general solution for Kolm SWF is thus \displaystyle p_{i} \displaystyle=\left[\log\left(\frac{\lambda^{\prime}}{w_{i}u_{i}}\right)\cdot\frac{1}{qu_{i}}\right]_{[0,1]} \displaystyle=\left[\frac{\eta+\log(w_{i}u_{i})}{|q|u_{i}}\right]_{[0,1]}, where \eta=-\log\lambda^{\prime} , and p_{i} is clamped to [0,1] such that \sum_{i}p_{i}=k . This is a harder problem than the WPM case, since here \eta=\log\lambda^{\prime} is additive rather than multiplicative . Thus both constraints p_{i}\geq 0 and p_{i}\leq 1 might be active. We think of water-filling in terms of \eta . C.2.2 Proving optimality through KKT conditions We note that M_{\text{Kolm}}(\mathbf{u}\odot\mathbf{p};\mathbf{w},q)=\frac{1}{q}\log\left(\sum_{i}w_{i}\exp(qu_{i}p_{i})\right), and \displaystyle\frac{\partial}{\partial p_{i}}M_{\text{Kolm}}(\mathbf{u}\odot\mathbf{p};\mathbf{w},q) \displaystyle=\frac{1}{q}\cdot\frac{w_{i}\exp(qu_{i}p_{i})}{\sum_{i}w_{i}\exp(qu_{i}p_{i})}\cdot qu_{i} \displaystyle=\frac{w_{i}\exp(qu_{i}p_{i})}{\sum_{i}w_{i}\exp(qu_{i}p_{i})}\cdot u_{i} Since q\leq 0 , we note that \partial M_{\text{Kolm}}/\partial p_{i} is a non-increasing function of p_{i} . Our optimization objective is: \displaystyle\text{maximize} \displaystyle\frac{1}{q}\log\left(\sum_{i}w_{i}\exp(qu_{i}p_{i})\right) \displaystyle\text{s.t.} \displaystyle-p_{i}\leq 0\qquad\forall i \displaystyle p_{i}-1\leq 0\qquad\forall i \displaystyle\sum_{i}p_{i}=k The Lagrangian for this expression with the optimal solution \mathbf{p}^{*} is \displaystyle\mathcal{L} \displaystyle=-M_{K}(\mathbf{u}\odot\mathbf{p}^{*};\mathbf{w},q)-\sum_{i}\alpha_{i}p_{i}^{*}+\sum_{i}\beta_{i}(p_{i}^{*}-1)+\gamma(\sum_{i}p_{i}^{*}-k) The partial derivative w.r.t. p_{i} is \displaystyle\left.\frac{\partial}{\partial p_{i}}\mathcal{L}\right|_{\mathbf{p}=\mathbf{p}^{*}} \displaystyle=-\frac{w_{i}\exp(qu_{i}p_{i}^{*})}{\sum_{i}w_{i}\exp(qu_{i}p_{i}^{*})}\cdot u_{i}-\alpha_{i}+\beta_{i}+\gamma The KKT conditions require: 1. Stationarity : 0\in\partial\mathcal{L}/\partial p_{i} , which implies that 0=-\frac{w_{i}\exp(qu_{i}p_{i}^{*})}{\sum_{i}w_{i}\exp(qu_{i}p_{i}^{*})}\cdot u_{i}-\alpha_{i}+\beta_{i}+\gamma 2. Primal feasibility : \displaystyle-p_{i}^{*} \displaystyle\leq 0\qquad\forall i \displaystyle p_{i}^{*}-1 \displaystyle\leq 0\qquad\forall i \displaystyle\sum_{i}p_{i}^{*}=k All primal feasibility conditions are satisfied by our construction of \mathbf{p}^{*} . 3. Dual feasibility : \displaystyle\alpha_{i} \displaystyle\geq 0\qquad\forall i \displaystyle\beta_{i} \displaystyle\geq 0\qquad\forall i \displaystyle\gamma \displaystyle\geq 0 4. Complementary slackness : \displaystyle\alpha_{i}p_{i}^{*} \displaystyle=0\qquad\forall i \displaystyle\beta_{i}(p_{i}^{*}-1) \displaystyle=0\qquad\forall i We consider three cases: • p_{i}^{*}\in(0,1) : This means that p_{i}^{*}=\frac{\eta^{*}+\log(w_{i}u_{i})}{|q|u_{i}}, which in turn implies \displaystyle\left.\frac{\partial}{\partial p_{i}}M_{\text{Kolm}}(\mathbf{u}\odot\mathbf{p};\mathbf{w},q)\right|_{\mathbf{p}=\mathbf{p}^{*}} \displaystyle=\frac{w_{i}\exp(-\eta^{*})/(w_{i}u_{i})}{\sum_{i}w_{i}\exp(qu_{i}p_{i}^{*})}\cdot u_{i} \displaystyle=\frac{\exp(-\eta^{*})}{\sum_{i}w_{i}\exp(qu_{i}p_{i}^{*})} Moreover, due to complementary slackness, we have \alpha_{i}=0 and \beta_{i}=0 . Thus, for stationarity to hold, \gamma=\frac{\exp(-\eta^{*})}{\sum_{i}w_{i}\exp(qu_{i}p_{i}^{*})}, which we note is independent of the index i . • p_{i}^{*}=0 : This implies that p_{i}^{*}=0\geq\frac{\eta^{*}+\log(w_{i}u_{i})}{|q|u_{i}}. Since \partial M_{\text{Kolm}}/\partial p_{i} is a decreasing function of p_{i} , we have \begin{aligned} -\left.\frac{\partial}{\partial p_{i}}M_{\text{Kolm}}(\mathbf{u}\odot\mathbf{p};\mathbf{w},q)\right|_{\mathbf{p}=\mathbf{p}^{*}}&\geq-\frac{\exp(-\eta^{*})}{\sum_{i}w_{i}\exp(qu_{i}p_{i}^{*})}\\ -\left.\frac{\partial}{\partial p_{i}}M_{\text{Kolm}}(\mathbf{u}\odot\mathbf{p};\mathbf{w},q)\right|_{\mathbf{p}=\mathbf{p}^{*}}+\gamma\geq 0\end{aligned}. Complementary slackness implies that \beta_{i}=0 . For stationarity to hold, we should thus have 0=-\frac{\partial}{\partial p_{i}}M_{\text{Kolm}}(\mathbf{u}\odot\mathbf{p};\mathbf{w},q)-\alpha_{i}+\gamma, which can be achieved by some \alpha_{i}>0 . Thus, dual feasibility is also satisfied. • p_{i}^{*}=1 : This implies that p_{i}^{*}=1\leq\frac{\eta^{*}+\log(w_{i}u_{i})}{|q|u_{i}}. Since \partial M_{\text{Kolm}}/\partial p_{i} is a decreasing function of p_{i} , we have \begin{aligned} -\left.\frac{\partial}{\partial p_{i}}M_{\text{Kolm}}(\mathbf{u}\odot\mathbf{p};\mathbf{w},q)\right|_{\mathbf{p}=\mathbf{p}^{*}}&\leq-\frac{\exp(-\eta^{*})}{\sum_{i}w_{i}\exp(qu_{i}p_{i}^{*})}\\ -\left.\frac{\partial}{\partial p_{i}}M_{\text{Kolm}}(\mathbf{u}\odot\mathbf{p};\mathbf{w},q)\right|_{\mathbf{p}=\mathbf{p}^{*}}+\gamma\leq 0\end{aligned}. Complementary slackness implies that \alpha_{i}=0 . For stationarity to hold, we should thus have 0=-\frac{\partial}{\partial p_{i}}M_{\text{Kolm}}(\mathbf{u}\odot\mathbf{p};\mathbf{w},q)+\beta_{i}+\gamma, which can be achieved by some \beta_{i}>0 . Thus, dual feasibility is also satisfied. Thus, the necessary conditions for KKT are satisfied. Since the constraints on our objective are all affine functions, the necessary conditions are also sufficient. This means that \mathbf{p}^{*} is the optimal solution. C.2.3 Algorithm We describe the algorithm for the Kolm allocation oracle in Algorithm 3 . Intuitively, the algorithm proceeds by calculating filling rates for allocation probabilities over the individuals. The critical difference from the WPM algorithm is that since \lambda is an additive factor here, we keep track of two events: 1) when individual i ’s probability first becomes non-zero, at which point they are included in the active set; and 2) when individual i ’s probability becomes p_{i}=1 , at which point they are excluded from the active set. When the fastest-filling individual i reaches p_{i}=1 , that individual is excluded from further allocation. This proceeds until \sum_{i}p_{i}=k . The sorting of the water-filling rates (Line 17) dominates the time complexity, resulting in an \mathcal{O}(n\log n) total complexity. However, we implement a \mathcal{O}(n^{2}) algorithm for simplicity here. Algorithm 3 Kolm Social Welfare Allocation 1: Input: Utilities u\in\mathbb{R}^{n} , weights w , power parameter q\leq 0 , resources k 2: Output: Allocation probabilities p\in[0,1]^{n} 3: // Step 1: Compute individual allocation rates 4: if q=-\infty then 5: r_{i}\leftarrow 1/u_{i} for all i 6: else if q=0 then 7: p\leftarrow set 1.0 for k indices with largest (w_{i}\cdot u_{i}) , else 0.0 ; return p 8: else 9: r_{i}\leftarrow 1/(-q\cdot u_{i}) for all i 10: end if 11: // Step 2: Identify critical event times (hitting 0 or 1) 12: if q=-\infty then 13: T^{start}_{i}\leftarrow 0 , T^{end}_{i}\leftarrow u_{i} for all i 14: else 15: T^{start}_{i}\leftarrow-\ln(w_{i}u_{i}) , T^{end}_{i}\leftarrow-qu_{i}-\ln(w_{i}u_{i}) for all i 16: end if 17: Sort all 2n times \{T^{start}_{i},T^{end}_{i}\} into a sequence \tau_{1},\tau_{2},\dots,\tau_{2n} 18: // Step 3: Water-filling over time intervals 19: Initialize p\leftarrow\mathbf{0} , \text{ActiveArms}\leftarrow\emptyset , t_{prev}\leftarrow\tau_{1} 20: for j=2 to 2n do 21: \Delta t\leftarrow\tau_{j}-t_{prev} 22: m_{interval}\leftarrow\sum_{i\in\text{ActiveArms}}r_{i}\cdot\Delta t 23: if \text{sum}(p)+m_{interval}>k then 24: \Delta t_{final}\leftarrow(k-\text{sum}(p))/\sum_{i\in\text{ActiveArms}}r_{i} 25: p_{i}\leftarrow p_{i}+r_{i}\cdot\Delta t_{final} for all i\in\text{ActiveArms} ; break 26: else 27: p_{i}\leftarrow p_{i}+r_{i}\cdot\Delta t for all i\in\text{ActiveArms} 28: Update ActiveArms based on whether \tau_{j} is a T^{start} (add) or T^{end} (remove) 29: t_{prev}\leftarrow\tau_{j} 30: end if 31: end for 32: return p C.3 Gini SWF For the Gini SWF, the optimization objective is: \displaystyle\text{maximize} \displaystyle M_{\text{Gini}}(\boldsymbol{\mu}^{\uparrow}\odot\mathbf{p};\mathbf{w})=\sum_{i}w_{i}(\boldsymbol{\mu}^{\uparrow}\odot\mathbf{p})_{(i)} \displaystyle\text{s.t.} \displaystyle p_{i}\in[0,1]\qquad\forall i \displaystyle\sum_{i}p_{i}=k Here, the vector of weights \mathbf{w} is such that w_{1}\geq w_{2}\geq\ldots\geq w_{n}\geq 0 . Moreover, (\boldsymbol{\mu}^{\uparrow}\odot\mathbf{p})_{(i)} specifies the i -th order statistic for the vector \mathbf{u}\odot\mathbf{p} . C.3.1 Optimal Order of Individuals Proposition C.1 . There exists an optimal solution \mathbf{p}^{*} such that, if \pi is the permutation such that \displaystyle\mu^{\uparrow}_{\pi(1)}\leq\mu^{\uparrow}_{\pi(2)}\leq\ldots\leq\mu^{\uparrow}_{\pi(n)}, (1) then \displaystyle\mu^{\uparrow}_{\pi(1)}p_{\pi(1)}^{*}\leq\mu^{\uparrow}_{\pi(2)}p_{\pi(2)}^{*}\leq\ldots\mu^{\uparrow}_{\pi(n)}p_{\pi(n)}^{*}. (2) That is, the optimal order for \mu^{\uparrow}_{\pi(i)}p_{\pi(i)} is along a non-decreasing order of \mu^{\uparrow}_{\pi(i)} . Interpretation : We may index individuals by non-decreasing \mu_{i} and restrict attention to allocations with \mu_{i}p_{i} non-decreasing; then optimizing over p suffices. Proof. For ease of notation, we relabel the indices such that \pi(i)=i . Thus, \mu^{\uparrow}_{1}\leq\mu^{\uparrow}_{2}\leq\ldots\mu^{\uparrow}_{n} . Let \mathbf{p} be the optimal solution. Let u_{i}=\mu_{i}p_{i} , and let \sigma be a permutation such that \sigma(i) is the i -th smallest element of \left\{u_{k}\right\} . We choose \sigma such that ties are broken to minimize inversions, i.e., iu_{j} . When the u_{i} ’s are sorted according to \sigma , we get ‘blocks‘ of equal values of u_{i} . Since inversions are minimized, each block has its \mu_{i} ’s in non-decreasing order. If these blocks are such that \mu_{i} ’s are in non-decreasing order across the blocks, we are done. Otherwise, let there be two blocks B_{1} and B_{2} (with B_{1} containing smaller values of u_{i} than B_{2} ) such that \mu_{i} ’s are not in non-decreasing order across these blocks. Let r be the rightmost element of B_{1} and l be the leftmost element of B_{2} . We thus have u_{r}\mu_{l} (since \mu_{i} ’s are not in non-decreasing order). Let r^{\prime} be the element to the right of r when sorted according to \sigma , and let l^{\prime} be the element to the left of l . Since l and r form the extremities of their blocks, we must have u_{r}0 such that p_{r}^{\prime}=p_{r}+\epsilon\in[0,1] , p_{l}^{\prime}=p_{l}-\epsilon\in[0,1] , u_{r}^{\prime}:=\mu_{r}p_{r}^{\prime}\leq u_{r^{\prime}} , and u_{l^{\prime}}\leq u_{l}^{\prime}:=\mu_{l}p_{l}^{\prime} . Thus, swapping this small \epsilon probability from l to r does not violate the order constraints. However, this swap results in a change in the Gini SWF of \Delta M_{\text{Gini}}=\epsilon(w_{\sigma(r)}\mu_{r}-w_{\sigma(l)}\mu_{l})\geq 0, since w_{\sigma(r)}\geq w_{\sigma(l)} and \mu_{r}>\mu_{l} . If w_{\sigma(r)}>0 , then this inequality is strict, implying that \mathbf{p} is not optimal. If w_{\sigma(r)}=0 , we have \Delta M_{\text{Gini}}=0 , which would mean that the swapping of probabilities does not decrease the objective. Repeating this swap (which never decreases the objective) until no such pair of blocks exists yields an optimal solution satisfying \mu_{1}p_{1}\leq\ldots\leq\mu_{n}p_{n} . ∎ C.3.2 Theoretical Properties of Oracle Algorithm We express the Gini SWF objective as a parametric LP problem. Let \tau\in[0,k] be the parameter controlling the sum of the probabilities. WLOG, we assume that \mu^{\uparrow}_{i} ’s are sorted in non-decreasing order. Our objective is \displaystyle\text{maximize } \displaystyle\sum_{i}w_{i}\mu^{\uparrow}_{i}p_{i} \displaystyle\text{such that } \displaystyle\sum_{i}p_{i}=\tau \displaystyle p_{i}\in[0,1]\quad\forall\ i \displaystyle\mu^{\uparrow}_{i-1}p_{i-1}\leq\mu^{\uparrow}_{i}p_{i}\quad\forall i\in\left\{2,\ldots,n\right\} Let \mathbf{p}_{\tau} be the solution encountered by the algorithm for parameter \tau . Our algorithm starts at \tau=0 , with \mathbf{p}_{0}=\boldsymbol{0}_{n} being the optimal solution. The algorithm proceeds by choosing a subset of indices S(\tau) for each \tau and increasing the probabilities for these indices as \tau increases, ensuring that no constraints are violated. The set S(\tau) and the rates r_{p}(i) for the increase in probabilities are chosen to maximize the rate of increase of the Gini objective. Proposition C.2 . The algorithm has the following properties: 1. The set of chosen indices and their rates of increase are changed when some element i in S(\tau) has p_{\tau,i}=1 . 2. The chosen indices for each \tau correspond to a block of consecutive indices B(\tau) . 3. The choice of indices B(\tau) have their probabilities increased at the rate \displaystyle r_{p}(\tau,i)=\frac{1/\mu^{\uparrow}_{i}}{\sum_{j\in B(\tau)}1/\mu^{\uparrow}_{j}}, and this results in a rate of increase of the Gini objective of \displaystyle r_{o}(B(\tau))=\frac{\sum_{i\in B(\tau)}w_{i}}{\sum_{i\in B(\tau)}1/\mu^{\uparrow}_{i}} 4. Among all feasible infinitesimal directions at any \tau , the block B(\tau) chosen by the algorithm and the above rates of increase of the probabilities maximizes the instantaneous rate of increase of the objective. 5. At each \tau where the set B(\tau) is changed, we have a sequence of blocks, with the value of \mu_{i}p_{i} being the same within a block. These blocks are separated from each other by indices i with p_{i}=1 . Proof. We prove this result through induction on the set of points where S(\tau) is changed. Since the objective is linear and the constraint set is a convex polytope, this change only occurs a finite number of times. Base case : We begin with \tau=0 , where \mathbf{p}_{\tau}=\boldsymbol{0}_{n} is the trivially optimal solution. Part (1) is trivially satisfied here, since this is the first choice of indices and rates we make. Part (5) is also trivially satisfied at \tau=0 , since we only have one block. With increasing \tau , any permissible increase will involve a suffix block of elements, since the order constraint \mu_{i-1}p_{i-1}\leq\mu_{i}p_{i} is violated otherwise. Thus, Part (2) is also satisfied. Let B be some suffix block. Our choice of rate for the probabilities within this block is \displaystyle r_{p}(i)=\frac{1/\mu^{\uparrow}_{i}}{\sum_{j\in B}1/\mu^{\uparrow}_{j}}. This choice results in a rate of increase of utility of \displaystyle r_{u}(i)=\mu^{\uparrow}_{i}\cdot r_{p}(i)=\frac{1}{\sum_{j\in B}1/\mu^{\uparrow}_{j}}. This rate of increase is the same for all elements within the block, and thus the order constraint is not violated. Moreover, this results in an increase in Gini SWF at the rate \displaystyle r_{o}(B)=\sum_{i\in B}w_{i}r_{u}(i)=\frac{\sum_{i\in B}w_{i}}{\sum_{i\in B}1/\mu^{\uparrow}_{i}}. Thus, part (3) of our proposition is a consequence of having to satisfy the order constraints. Let B^{\prime} be a suffix block which is a subset of B such that r_{o}(B^{\prime})>r_{o}(B) , that is, the rate of Gini SWF increase is greater if all the utility is allocated to this sub-block. Then, B is a sub-optimal choice for the block, and we should choose B^{\prime} . Note that switching to a sub-block of B does not violate the order constraint. We can repeat this argument starting from B=[n] to reach a suffix block which has the greatest value of r_{o}(B) . This will be our choice of B(\tau) . We have thus characterized this block for Part (4), showing that it provides the maximum rate of increase while satisfying the constraints. As we increase the probabilities of this block, the leftmost index l(B) is filled fastest, since it has the smallest value of \mu_{i} , and hence the highest filling rate. Thus, this choice of block and filling rates is no longer valid when we have p_{l(B)}=1 , which satisfies Part (1). At this instance, we have two blocks of equal values of \mu^{\uparrow}_{i}p_{i} (0 for the left block, \mu_{l(B)} for the right) separated by p_{l(B)}=1 , which satisfies Part (5). Induction case : Let \tau be some intermediate value where the set of chosen indices and their rates of increase have to be changed. We assume Part (5) holds, i.e., we have a sequence of blocks separated by indices i with p_{i}=1 . We note that a block in this sequence is similar to the bigger block of [n] for B=0 . Thus, if our choice of S(\tau) is to be within a block, all Parts (1)-(5) would be naturally satisfied. We now show that this is indeed the case. Let us assume the contrary, i.e., our choice of S(\tau) spans across blocks. In this case, the optimal solution will have suffixes from all the blocks. Any feasible infinitesimal direction decomposes as a convex combination of suffix directions within individual blocks. Since the objective slope is linear, an optimal direction concentrates all mass on a single block with maximal slope (ties arbitrary). Thus, Parts (1)-(5) would be satisfied. ∎ Because the objective is linear and the feasible region is a convex polytope, following a direction that maximizes instantaneous objective increase keeps the solution on an optimal face of the LP until a constraint becomes tight. C.3.3 Gini SWF Oracle Algorithm We describe the block-based water-filling algorithm in Algorithm 4 . The algorithm proceeds by filling probabilities in blocks, ensuring that the order constraints are not violated. The chosen block is such that it provides the greatest rate of increase in the Gini SWF value while following the order constraints. Each block calculation takes \mathcal{O}(n) time, and there are at most k block calculations, resulting in a time complexity of \mathcal{O}(kn) . Algorithm 4 Gini Water-Filling Solver 1: Input: Vector of mean utilities u\in\mathbb{R}^{n} , weight vector w (where w_{1}\geq w_{2}\geq\dots\geq w_{n}\geq 0 ), number of resources k . 2: Output: Optimal allocation policy p\in[0,1]^{n} maximizing M_{Gini}(\mu\odot p;w) . 3: Sort u in non-decreasing order: u_{(1)}\leq u_{(2)}\leq\dots\leq u_{(n)} . 4: Let \pi be the permutation such that u_{(i)}=u_{\pi(i)} . 5: Initialize p_{i}=0 for all i\in[n] , rem=k , and initial block set \mathcal{B}=\{[1,n]\} . 6: Precompute suffix sums W_{i}=\sum_{j=i}^{n}w_{j} and inverse utility sums I_{i}=\sum_{j=i}^{n}1/u_{(j)} . 7: while rem>0 do 8: Find block B\in\mathcal{B} maximizing the rate: r(B)=\frac{\sum_{i\in B}w_{i}}{\sum_{j\in B}1/u_{(j)}} . Rate of SWF increase 9: Let l(B) be the leftmost index of block B and R be the rightmost index. 10: \Delta t\leftarrow(1-p_{\pi(l(B))})\cdot u_{(l(B))} Time until p_{l(B)}=1 11: m\leftarrow\left(\sum_{j\in B}1/u_{(j)}\right)\cdot\Delta t Total probability mass required to fill block B 12: if m\leq rem then 13: for j\in B do 14: p_{\pi(j)}\leftarrow p_{\pi(j)}+\Delta t/u_{(j)} 15: end for 16: rem\leftarrow rem-m 17: \mathcal{B}\leftarrow(\mathcal{B}\setminus\{B\})\cup\{[l(B)+1,R]\} Leftmost index is now fully allocated 18: Update precomputed suffix sums for remaining sub-blocks. 19: else 20: \text{rate\_sum}\leftarrow\sum_{j\in B}1/u_{(j)} 21: for j\in B do 22: p_{\pi(j)}\leftarrow p_{\pi(j)}+\frac{rem}{\text{rate\_sum}\cdot u_{(j)}} 23: end for 24: rem\leftarrow 0 25: end if 26: end while 27: return p Appendix D Algorithm for Dependent Rounding We use the dependent rounding algorithm ( 11 ; 12 ) to sample a set S_{t} given the allocation policy vector \mathbf{p}_{t} such that \mathbb{P}(i\in S_{t})=p_{t,i} . This idea is also known as \pi -PS sampling, and is popularly used in survey design when samples need to be drawn from a population with unequal probabilities across individuals/groups. Algorithm 5 provides the pseudocode for dependent rounding. Algorithm 5 \pi -ps sampling (pairwise dependent rounding) 0: \pi\in[0,1]^{N} with \sum_{i}\pi_{i}=n 0: Sample S\subseteq[N] , |S|=n 1: while there exist at least two fractional entries in \pi do 2: pick distinct fractional indices i\neq j 3: s\leftarrow\pi_{i}+\pi_{j} ,  draw r\sim\mathrm{Unif}[0,1] 4: if s\leq 1 then 5: (\pi_{i},\pi_{j})\leftarrow\begin{cases}(0,s)&\text{w.p. }\pi_{j}/s\\ (s,0)&\text{w.p. }\pi_{i}/s\end{cases} 6: else 7: (\pi_{i},\pi_{j})\leftarrow\begin{cases}(1,s-1)&\text{w.p. }(1-\pi_{j})/(2-s)\\ (s-1,1)&\text{w.p. }(1-\pi_{i})/(2-s)\end{cases} 8: end if 9: end while 10: 11: return S\leftarrow\{i:\pi_{i}=1\} Appendix E More Experiments: Linear Weight Decay We considered an exponential decay of the weight vector in Section 6 , which puts greater weight on a few individuals. In this section, we consider a gentler linear decay of the weights, with w_{i}=(1+(i-1)/(n-1))/S , where S=\sum_{i=1}^{n}(1+(i-1)/(n-1)) . We use the exact same experimental setup as in Section 6 , with n=50 , U_{i}\sim 0.1+0.9X_{i} , with each X_{i} being Beta-distributed with parameters (\alpha_{i},\beta_{i}) identical to those in Section 6 . Varying horizon T . We let q=-2 and vary T the range [10^{3},1.28\cdot 10^{5}] . We plot the regret against T with varying k in Figure 4 . For all three SWFs, we observe that the regret roughly scales as \mathcal{O}(\sqrt{T}) when compared with the reference dotted line, consistent with our theoretical guarantees. Generally, we find that the regret increases with across T , then decreasing as k is further increased. However, the relative ordering of regret with changing k varies with increasing T . We also observe that the trends are quite different from those in Figure 1 ; In general, we observe a faster decrease in the normalized regret with increasing T , indicating that the optimal allocation vector is easier to learn. (a) WPM SWF (b) Kolm SWF (c) Gini SWF Figure 4 : Normalized regret R(T)/\sqrt{T} versus time horizon T for WPM, Kolm, and Gini SWFs with linear decay in weights. The normalized regret remains bounded across two orders of magnitude in T , consistent with our theoretical \tilde{\mathcal{O}}(\sqrt{T}) guarantee. Varying power value q . We now plot the observed regret with different values of q while varying the number of allocated resources k in Figure 5 . The regret values are the same for q=-\infty for both WPM and Kolm, which is expected since the weights do not matter for egalitarian welfare. However, the trends for finite q are significantly different. We observe that there is significantly more order in the regret for WPM SWF with increasing q . For Kolm SWF, the trends for different k are significantly more unstructured, a phenomenon not seen in the exponential weight decay case. (a) WPM SWF (b) Kolm SWF Figure 5 : Trends with varying power value q for WPM and Kolm SWFs with linear decay in weights. q=-\infty corresponds to egalitarian welfare for both, whereas q=1 for SWF and q=0 for Kolm correspond to utilitarian welfare. We observe that while there is a smooth change in the observed regret, there is significant variability with changing k . Varying number of allocated resources k . We plot the observed regret with different number of allocated resources per time step k in Figure 6 . For the WPM SWF, there is a more marked increase in regret with k for finite q , which is different from the non-monotonic behavior observed in Figure 3 . The Kolm SWF also exhibits similar behavior. The Gini SWF resembles utilitarian welfare, which corresponds to q=1 and q=0 for WPM SWF and Kolm SWF respectively. (a) WPM SWF (b) Kolm SWF (c) Gini SWF Figure 6 : Trends with varying number of allocated resources k for all three SWFs. We observe that there is a sharp decrease after k=20 for egalitarian welfare. The changes with increasing q becomes less gradual for both WPM and Kolm SWFs. Linear weights have some similarity with utilitarian welfare, and we see a similar pattern with varying k for Gini SWF.