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.
Improved statistical efficiency of Thompson Sampling for combinatorial semi-bandits.
problem Efficiency of policies in stochastic combinatorial multi-armed bandits with semi-bandit feedback.
method Analysis of Combinatorial Thompson Sampling (CTS) using Beta and Gaussian priors for mutually independent and multivariate sub-Gaussian outcomes.
result CTS provides an efficient policy with optimal asymptotic regret for both mutually independent and multivariate sub-Gaussian outcomes.
The paper identifies network bottlenecks using minimax paths in stochastic networks.
problem Identifying bottlenecks in networks with stochastic weights.
method Modeling as combinatorial semi-bandit problem, applying combinatorial Thompson Sampling, and approximating the original objective due to computational intractability.
result Established an upper bound on Bayesian regret and evaluated Thompson Sampling performance on real-world networks.
We address online combinatorial optimization when the player has a prior over the adversary's sequence of losses. In this framework, Russo and Van Roy proposed an information-theoretic analysis of Thompson Sampling based on the information ratio, resulting in optimal worst-case regret bounds. In this paper we introduce…
We analyze the regret of combinatorial Thompson sampling (CTS) for the combinatorial multi-armed bandit with probabilistically triggered arms under the semi-bandit feedback setting. We assume that the learner has access to an exact optimization oracle but does not know the expected base arm outcomes beforehand. When th…
In this paper, we study the combinatorial multi-armed bandit problem (CMAB) with probabilistically triggered arms (PTAs). Under the assumption that the arm triggering probabilities (ATPs) are positive for all arms, we prove that a class of upper confidence bound (UCB) policies, named Combinatorial UCB with exploration …
The paper emphasizes the importance of joint predictions over marginal predictions for decision-making.
problem The need for accurate joint predictions in decision-making problems.
method The paper analyzes combinatorial decision problems, sequential predictions, and multi-armed bandits, introducing an approximate Thompson sampling algorithm and new regret bounds.
result Accurate joint predictions are essential for good performance in decision-making problems.
This paper introduces and addresses a wide class of stochastic bandit problems where the function mapping the arm to the corresponding reward exhibits some known structural properties. Most existing structures (e.g. linear, Lipschitz, unimodal, combinatorial, dueling, ...) are covered by our framework. We derive an asy…
A stochastic combinatorial semi-bandit is an online learning problem where at each step a learning agent chooses a subset of ground items subject to combinatorial constraints, and then observes stochastic weights of these items and receives their sum as a payoff. In this paper, we consider efficient learning in large-s…
Influence maximization, adaptive routing, and dynamic spectrum allocation all require choosing the right action from a large set of alternatives. Thanks to the advances in combinatorial optimization, these and many similar problems can be efficiently solved given an environment with known stochasticity. In this paper, …
Thompson sampling provides a solution to bandit problems in which new observations are allocated to arms with the posterior probability that an arm is optimal. While sometimes easy to implement and asymptotically optimal, Thompson sampling can be computationally demanding in large scale bandit problems, and its perform…
In this paper we consider an online recommendation setting, where a platform recommends a sequence of items to its users at every time period. The users respond by selecting one of the items recommended or abandon the platform due to fatigue from seeing less useful items. Assuming a parametric stochastic model of user …
New Thompson sampling uses local uncertainty for better decision making.
problem Sequential decision making with exploration-exploitation dilemma.
method Proposes a new probabilistic modeling framework using local latent variable uncertainty for Thompson sampling, with variational inference and semi-implicit structure.
result Thompson sampling guided by local uncertainty achieves state-of-the-art performance with low computational complexity.
Thompson sampling has impressive empirical performance for many multi-armed bandit problems. But current algorithms for Thompson sampling only work for the case of conjugate priors since these algorithms require to infer the posterior, which is often computationally intractable when the prior is not conjugate. In this …
Thompson sampling, a Bayesian method for balancing exploration and exploitation in bandit problems, has theoretical guarantees and exhibits strong empirical performance in many domains. Traditional Thompson sampling, however, assumes perfect compliance, where an agent's chosen action is treated as the implemented actio…
We define combinatorial analogues of stable and unstable minimal surfaces in the setting of weighted pseudomanifolds. We prove that, under mild conditions, such combinatorial minimal surfaces always exist. We use a technique, adapted from work of Johnson and Thompson, called thin position. Thin position is defined usin…
Thompson Sampling, one of the oldest heuristics for solving multi-armed bandits, has recently been shown to demonstrate state-of-the-art performance. The empirical success has led to great interests in theoretical understanding of this heuristic. In this paper, we approach this problem in a way very different from exis…