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.
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 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…
Develops a method to tackle high-dimensional linear bandits with knapsacks using online sparse estimation and dual variables.
Quantum algorithms improve regret bounds for bandits with knapsacks.
Algorithm tackles constrained reinforcement learning with concave-convex and knapsack constraints.
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…
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…
New algorithm tackles dynamic assortment optimization with knapsack constraints.
Optimal algorithm for maximizing rewards in contextual bandits with resource constraints.
Study non-stationary bandits with resource constraints.
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…
A new stochastic method handles ensemble creation with cost constraints.
Paper tackles non-monotonic resource utilization in sequential decision-making.
This paper optimizes multi-channel sequential advertising to maximize cumulative revenue.
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…
New method reduces total cost constraints in CBwK to sqrt(T) with fairness application.
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…
Improves bandits with knapsacks guarantees for partially stochastic workloads.
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…
Paper relaxes set-valued prediction in hierarchical classification by considering representation complexity.
Study optimal policies under budget and coverage constraints.
New framework handles online decisions with replenishable resources, improving both adversarial and stochastic performance.
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 …
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…
The paper introduces SuccessProbaMax to optimize policy success probability in online advertising.
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…
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…
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…
Dynamic promotion optimization for e-commerce platforms within financial constraints.
Adaptive policies solve a linear program to maximize rewards while minimizing costs in sales with discounts.
Neural Index Policy for multi-action bandits with heterogeneous budgets.
The paper optimizes A/B tests by balancing lift and cost in large-scale settings.
This paper optimizes ad bids and daily budgets for multiple campaigns in pay-per-click advertising.
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…
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…
New model enhances SPIM for solving low-rank combinatorial optimization and statistical learning problems.
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…
A new algorithm tackles submodular bandit problems with multiple constraints.
Neural model learns efficient, general algorithms for various problems.
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…
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…
New loss function handles uncertain constraints in CSLO problems.
In this paper, we investigate the possibility of improving the performance of multi-objective optimization solution approaches using machine learning techniques. Specifically, we focus on multi-objective binary linear programs and employ one of the most effective and recently developed criterion space search algorithms…
Improved algorithms solve multi-period multi-class packing problems with bandit feedback.
Unified framework for combinatorial and rounding algorithms in experimental design.
New algorithm for contextual bandits with linear constraints using regression.