10 research outputs found
On the Proximity of Markets with Integral Equilibria
No full textWe study Fisher markets that admit equilibria wherein each good is integrally assigned to some agent. While strong existence and computational guarantees are known for equilibria of Fisher markets with additive valuations (Eisenberg and Gale 1959; Orlin 2010), such equilibria, in general, assign goods fractionally to agents. Hence, Fisher markets are not directly applicable in the context of indivisible goods. In this work we show that one can always bypass this hurdle and, up to a bounded change in agents’ budgets, obtain markets that admit an integral equilibrium. We refer to such markets as pure markets and show that, for any given Fisher market (with additive valuations), one can efficiently compute a “near-by,” pure market with an accompanying integral equilibrium.Our work on pure markets leads to novel algorithmic results for fair division of indivisible goods. Prior work in discrete fair division has shown that, under additive valuations, there always exist allocations that simultaneously achieve the seemingly incompatible properties of fairness and efficiency (Caragiannis et al. 2016); here fairness refers to envyfreeness up to one good (EF1) and efficiency corresponds to Pareto efficiency. However, polynomial-time algorithms are not known for finding such allocations. Considering relaxations of proportionality and EF1, respectively, as our notions of fairness, we show that fair and Pareto efficient allocations can be computed in strongly polynomial time
Data-driven Error Estimation: Upper Bounding Multiple Errors with No Technical Debt
No full textWe formulate the problem of constructing multiple simultaneously valid
confidence intervals (CIs) as estimating a high probability upper bound on the
maximum error for a class/set of estimate-estimand-error tuples, and refer to
this as the error estimation problem. For a single such tuple, data-driven
confidence intervals can often be used to bound the error in our estimate.
However, for a class of estimate-estimand-error tuples, nontrivial high
probability upper bounds on the maximum error often require class complexity as
input -- limiting the practicality of such methods and often resulting in loose
bounds. Rather than deriving theoretical class complexity-based bounds, we
propose a completely data-driven approach to estimate an upper bound on the
maximum error. The simple and general nature of our solution to this
fundamental challenge lends itself to several applications including: multiple
CI construction, multiple hypothesis testing, estimating excess risk bounds (a
fundamental measure of uncertainty in machine learning) for any
training/fine-tuning algorithm, and enabling the development of a contextual
bandit pipeline that can leverage any reward model estimation procedure as
input (without additional mathematical analysis)
Towards Costless Model Selection in Contextual Bandits: A Bias-Variance Perspective
No full textModel selection in supervised learning provides costless guarantees as if the
model that best balances bias and variance was known a priori. We study the
feasibility of similar guarantees for cumulative regret minimization in the
stochastic contextual bandit setting. Recent work [Marinov and Zimmert, 2021]
identifies instances where no algorithm can guarantee costless regret bounds.
Nevertheless, we identify benign conditions where costless model selection is
feasible: gradually increasing class complexity, and diminishing marginal
returns for best-in-class policy value with increasing class complexity. Our
algorithm is based on a novel misspecification test, and our analysis
demonstrates the benefits of using model selection for reward estimation.
Unlike prior work on model selection in contextual bandits, our algorithm
carefully adapts to the evolving bias-variance trade-off as more data is
collected. In particular, our algorithm and analysis go beyond adapting to the
complexity of the simplest realizable class and instead adapt to the complexity
of the simplest class whose estimation variance dominates the bias. For short
horizons, this provides improved regret guarantees that depend on the
complexity of simpler classes
Effects of COVID-19 on national tuberculosis elimination programme strategies during March to May 2020 on Tumkur district, India
No full textBackground: the nation-wide lockdown due global pandemic has disrupted a vital strategic intervention resulting in overall 60% decrease in presumptive and diagnostic TB cases during the lockdown period.Methods: A discrete choice experimental (DCE) exploratory operational research conducted during March to May 2020.Results: Health care services were affected 25% reduction in the outpatient department (OPD) in comparison to the previous year the same period. A gradual reduction in negative sputum cases undergoing chest radiography from 54% to 14%. Due to restricted movement LPA tests have been reduced 25% among the diagnosed TB cases, and private referrals to cartridge based nucleic acid amplification test (CBNAAT) services were reduced to 20%.Conclusions: Health services, including national programmes to combat TB, need to be actively engaged in ensuring an effective and rapid response to COVID-19 while ensuring that TB services are maintained. While experience on COVID-19 infection in TB patients remains limited, it is anticipated that people ill with both TB and COVID-19 may have poorer treatment outcomes, especially if TB treatment is interrupted. TB patients should take precautions as advised by health authorities to be protected from COVID-19 and continue their TB treatment as prescribed
Proportional Response: Contextual Bandits for Simple and Cumulative Regret Minimization
No full textIn many applications, e.g. in healthcare and e-commerce, the goal of a
contextual bandit may be to learn an optimal treatment assignment policy at the
end of the experiment. That is, to minimize simple regret. However, this
objective remains understudied. We propose a new family of computationally
efficient bandit algorithms for the stochastic contextual bandit setting, where
a tuning parameter determines the weight placed on cumulative regret
minimization (where we establish near-optimal minimax guarantees) versus simple
regret minimization (where we establish state-of-the-art guarantees). Our
algorithms work with any function class, are robust to model misspecification,
and can be used in continuous arm settings. This flexibility comes from
constructing and relying on "conformal arm sets" (CASs). CASs provide a set of
arms for every context, encompassing the context-specific optimal arm with a
certain probability across the context distribution. Our positive results on
simple and cumulative regret guarantees are contrasted with a negative result,
which shows that no algorithm can achieve instance-dependent simple regret
guarantees while simultaneously achieving minimax optimal cumulative regret
guarantees
Proportional Response: Contextual Bandits for Simple and Cumulative Regret Minimization
No full textIn many applications, e.g. in healthcare and e-commerce, the goal of a contextual bandit may be to learn an optimal treatment assignment policy at the end of the experiment. That is, to minimize simple regret. However, this objective remains understudied. We propose a new family of computationally efficient bandit algorithms for the stochastic contextual bandit setting, where a tuning parameter determines the weight placed on cumulative regret minimization (where we establish near-optimal minimax guarantees) versus simple regret minimization (where we establish state-of-the-art guarantees). Our algorithms work with any function class, are robust to model misspecification, and can be used in continuous arm settings. This flexibility comes from constructing and relying on “conformal arm sets" (CASs). CASs provide a set of arms for every context, encompassing the context-specific optimal arm with a certain probability across the context distribution. Our positive results on simple and cumulative regret guarantees are contrasted with a negative result, which shows that no algorithm can achieve instance-dependent simple regret guarantees while simultaneously achieving minimax optimal cumulative regret guarantees.</p
Contextual Bandits in a Survey Experiment on Charitable Giving: Within-Experiment Outcomes versus Policy Learning
No full textWe design and implement an adaptive experiment (a ``contextual bandit'') to
learn a targeted treatment assignment policy, where the goal is to use a
participant's survey responses to determine which charity to expose them to in
a donation solicitation. The design balances two competing objectives:
optimizing the outcomes for the subjects in the experiment (``cumulative regret
minimization'') and gathering data that will be most useful for policy
learning, that is, for learning an assignment rule that will maximize welfare
if used after the experiment (``simple regret minimization''). We evaluate
alternative experimental designs by collecting pilot data and then conducting a
simulation study. Next, we implement our selected algorithm. Finally, we
perform a second simulation study anchored to the collected data that evaluates
the benefits of the algorithm we chose. Our first result is that the value of a
learned policy in this setting is higher when data is collected via a uniform
randomization rather than collected adaptively using standard cumulative regret
minimization or policy learning algorithms. We propose a simple heuristic for
adaptive experimentation that improves upon uniform randomization from the
perspective of policy learning at the expense of increasing cumulative regret
relative to alternative bandit algorithms. The heuristic modifies an existing
contextual bandit algorithm by (i) imposing a lower bound on assignment
probabilities that decay slowly so that no arm is discarded too quickly, and
(ii) after adaptively collecting data, restricting policy learning to select
from arms where sufficient data has been gathered
Selective Uncertainty Propagation in Offline RL
No full textWe consider the finite-horizon offline reinforcement learning (RL) setting,
and are motivated by the challenge of learning the policy at any step h in
dynamic programming (DP) algorithms. To learn this, it is sufficient to
evaluate the treatment effect of deviating from the behavioral policy at step h
after having optimized the policy for all future steps. Since the policy at any
step can affect next-state distributions, the related distributional shift
challenges can make this problem far more statistically hard than estimating
such treatment effects in the stochastic contextual bandit setting. However,
the hardness of many real-world RL instances lies between the two regimes. We
develop a flexible and general method called selective uncertainty propagation
for confidence interval construction that adapts to the hardness of the
associated distribution shift challenges. We show benefits of our approach on
toy environments and demonstrate the benefits of these techniques for offline
policy learning
Selective Uncertainty Propagation in Offline RL
No full textWe consider the finite-horizon offline reinforcement learning (RL) setting, and are motivated by the challenge of learning the policy at any step h in dynamic programming (DP) algorithms. To learn this, it is sufficient to evaluate the treatment effect of deviating from the behavioral policy at step h after having optimized the policy for all future steps. Since the policy at any step can affect next-state distributions, the related distributional shift challenges can make this problem far more statistically hard than estimating such treatment effects in the stochastic contextual bandit setting. However, the hardness of many real-world RL instances lies between the two regimes. We develop a flexible and general method called selective uncertainty propagation for confidence interval construction that adapts to the hardness of the associated distribution shift challenges. We show benefits of our approach on toy environments and demonstrate the benefits of these techniques for offline policy learning
