A locally-built, LLM-digested index of recent arXiv papers in quant finance, geometry/topology, and statistical ML — keyword search served straight from SQLite on this machine.
Neural networks solve Knapsack problems with provable guarantees.
Develops a method to tackle high-dimensional linear bandits with knapsacks using online sparse estimation and dual variables.
Algorithm tackles constrained reinforcement learning with concave-convex and knapsack constraints.
New algorithm tackles dynamic assortment optimization with knapsack constraints.
Adaptive policies solve a linear program to maximize rewards while minimizing costs in sales with discounts.
We consider a contextual version of multi-armed bandit problem with global knapsack constraints. In each round, the outcome of pulling an arm is a scalar reward and a resource consumption vector, both dependent on the context, and the global knapsack constraints require the total consumption for each resource to be bel…
We present a new Bitcoin coin selection algorithm, "coin selection with leverage", which aims to improve upon cost savings than that of standard knapsack like approaches. Parameters to the new algorithm are available to be tuned at the users discretion to address other goals of coin selection. Our approach naturally fi…
Bandits with Knapsacks (BwK) is a general model for multi-armed bandits under supply/budget constraints. While worst-case regret bounds for BwK are well-understood, we present three results that go beyond the worst-case perspective. First, we provide upper and lower bounds which amount to a full characterization for lo…
Study optimal policies under budget and coverage constraints.
0-1 knapsack is of fundamental importance in computer science, business, operations research, etc. In this paper, we present a deep learning technique-based method to solve large-scale 0-1 knapsack problems where the number of products (items) is large and/or the values of products are not necessarily predetermined but…
We consider Bandits with Knapsacks (henceforth, BwK), a general model for multi-armed bandits under supply/budget constraints. In particular, a bandit algorithm needs to solve a well-known knapsack problem: find an optimal packing of items into a limited-size knapsack. The BwK problem is a common generalization of nume…
We present a new approach for studying the problem of optimal hedging of a European option in a finite and complete discrete-time market model. We consider partial hedging strategies that maximize the success probability or minimize the expected shortfall under a cost constraint and show that these problems can be trea…
Quantum algorithms improve regret bounds for bandits with knapsacks.
Neural network pruning reduces the computational cost of an over-parameterized network to improve its efficiency. Popular methods vary from -norm sparsification to Neural Architecture Search (NAS). In this work, we propose a novel pruning method that optimizes the final accuracy of the pruned network and distil…
Optimal algorithm for maximizing rewards in contextual bandits with resource constraints.
This paper optimizes multi-channel sequential advertising to maximize cumulative revenue.
Paper tackles non-monotonic resource utilization in sequential decision-making.
A new stochastic method handles ensemble creation with cost constraints.
Improves bandits with knapsacks guarantees for partially stochastic workloads.
Study non-stationary bandits with resource constraints.
New method reduces total cost constraints in CBwK to sqrt(T) with fairness application.
The stochastic knapsack has been used as a model in wide ranging applications from dynamic resource allocation to admission control in telecommunication. In recent years, a variation of the model has become a basic tool in studying problems that arise in revenue management and dynamic/flexible pricing; and it is in thi…
This paper studies the impact of limited switches on resource-constrained dynamic pricing with demand learning. We focus on the classical price-based blind network revenue management problem and extend our results to the bandits with knapsacks problem. In both settings, a decision maker faces stochastic and distributio…
The paper optimizes A/B tests by balancing lift and cost in large-scale settings.
We consider the linear contextual bandit problem with resource consumption, in addition to reward generation. In each round, the outcome of pulling an arm is a reward as well as a vector of resource consumptions. The expected values of these outcomes depend linearly on the context of that arm. The budget/capacity const…
Paper relaxes set-valued prediction in hierarchical classification by considering representation complexity.
A typical viral marketing model identifies influential users in a social network to maximize a single product adoption assuming unlimited user attention, campaign budgets, and time. In reality, multiple products need campaigns, users have limited attention, convincing users incurs costs, and advertisers have limited bu…
This paper investigates the adversarial Bandits with Knapsack (BwK) online learning problem, where a player repeatedly chooses to perform an action, pays the corresponding cost, and receives a reward associated with the action. The player is constrained by the maximum budget that can be spent to perform actions, an…
New framework handles online decisions with replenishable resources, improving both adversarial and stochastic performance.
The paper introduces SuccessProbaMax to optimize policy success probability in online advertising.
Neural Index Policy for multi-action bandits with heterogeneous budgets.
Dynamic promotion optimization for e-commerce platforms within financial constraints.
We study the online saddle point problem, an online learning problem where at each iteration a pair of actions need to be chosen without knowledge of the current and future (convex-concave) payoff functions. The objective is to minimize the gap between the cumulative payoffs and the saddle point value of the aggregate …
FMDP-BF algorithm improves RL in factored MDPs with exponential regret reduction.
This paper optimizes ad bids and daily budgets for multiple campaigns in pay-per-click advertising.
The typical algorithmic problem in viral marketing aims to identify a set of influential users in a social network, who, when convinced to adopt a product, shall influence other users in the network and trigger a large cascade of adoptions. However, the host (the owner of an online social platform) often faces more con…
Multi-armed bandits a simple but very powerful framework for algorithms that make decisions over time under uncertainty. An enormous body of work has accumulated over the years, covered in several books and surveys. This book provides a more introductory, textbook-like treatment of the subject. Each chapter tackles a p…
This paper presents a framework to tackle combinatorial optimization problems using neural networks and reinforcement learning. We focus on the traveling salesman problem (TSP) and train a recurrent network that, given a set of city coordinates, predicts a distribution over different city permutations. Using negative t…
In this paper, we introduce a novel technique for constrained submodular maximization, inspired by barrier functions in continuous optimization. This connection not only improves the running time for constrained submodular maximization but also provides the state of the art guarantee. More precisely, for maximizing a m…
Robust Optimization is becoming increasingly important in machine learning applications. This paper studies the problem of robust submodular minimization subject to combinatorial constraints. Constrained Submodular Minimization arises in several applications such as co-operative cuts in image segmentation, co-operative…
Robust optimization is becoming increasingly important in machine learning applications. In this paper, we study a unified framework of robust submodular optimization. We study this problem both from a minimization and maximization perspective (previous work has only focused on variants of robust submodular maximizatio…
Algorithm tackles clustered contextual bandits with resource constraints.
Optimal experiments tighten causal effect bounds efficiently.
Unified framework for combinatorial and rounding algorithms in experimental design.
New algorithm for contextual bandits with linear constraints using regression.
In recent years, RTB(Real Time Bidding) becomes a popular online advertisement trading method. During the auction, each DSP(Demand Side Platform) is supposed to evaluate current opportunity and respond with an ad and corresponding bid price. It's essential for DSP to find an optimal ad selection and bid price determina…
Neural model learns efficient, general algorithms for various problems.
New model enhances SPIM for solving low-rank combinatorial optimization and statistical learning problems.