Investigates sequential problems on graph structures and large action spaces.
problem Sequential decision-making on graph structures and large action spaces.
method Spectral bandits, side observations, influence maximization, kernel bandits, polymatroid bandits, function optimization, infinitely many-arms bandits.
result Contributions to graph and structured bandits.
Graph neural Thompson Sampling improves online decision-making for graph data.
problem Online decision-making with graph-structured rewards.
method GNN-TS algorithm using GNN for mean reward estimation and graph neural tangent features for uncertainty.
result GNN-TS achieves a state-of-the-art regret bound of i l d e O ( ( i l d e d T ) 1 / 2 ) ilde{\mathcal{O}}(( ilde{d} T)^{1/2}) i l d e O (( i l d e d T ) 1/2 ) . New algorithm identifies best intervention without graph knowledge.
problem Finding best intervention in causal bandit setting with unknown graph.
method Additive combinatorial linear bandit problem with action-elimination algorithm.
result One can identify best intervention without explicitly learning graph parents.
We consider stochastic multi-armed bandit problems with graph feedback, where the decision maker is allowed to observe the neighboring actions of the chosen action. We allow the graph structure to vary with time and consider both deterministic and Erdős-Rényi random graph models. For such a graph feedback model, we fir…
New algorithms for causal bandits without knowing the graph structure.
problem Causal bandit problems with unknown graph structure.
method Developed novel causal bandit algorithms for causal trees, forests, and general graphs without prior knowledge of the causal graph.
result Regret guarantees significantly improved over standard MAB algorithms under mild conditions.
This paper extends combinatorial semi-bandits to graph feedback, improving regret bounds.
problem Adversarial combinatorial semi-bandits with graph feedback.
method Introduced graph feedback in combinatorial semi-bandits, using convexified actions and online stochastic mirror descent.
result Optimal regret scales as S T + α S T S\sqrt{T}+\sqrt{αST} S T + α S T , interpolating between full and semi-bandit feedback. A graph bandit algorithm learns optimal paths on unknown graphs.
problem Optimal path selection on unknown graphs under uncertainty.
method G-UCB algorithm based on offline graph planning and optimism principle.
result Achieves tight regret bound of O ( ∣ S ∣ T log ( T ) + D ∣ S ∣ log T ) O(\sqrt{|S|T\log(T)}+D|S|\log T) O ( ∣ S ∣ T log ( T ) + D ∣ S ∣ log T ) . Graph-Triggered Bandits unify rested and restless bandits with graph-defined arm interactions.
problem Modeling sequential decision-making problems with evolving arm rewards.
method Graph-Triggered Bandits (GTBs) framework that generalizes rested and restless bandits using a graph.
result Rested and restless bandits are special cases of GTBs for suitable graphs.
We study the adversarial multi-armed bandit problem where partial observations are available and where, in addition to the loss incurred for each action, a \emph{switching cost} is incurred for shifting to a new action. All previously known results incur a factor proportional to the independence number of the feedback …
We introduce a rich class of graphical models for multi-armed bandit problems that permit both the state or context space and the action space to be very large, yet succinctly specify the payoffs for any context-action pair. Our main result is an algorithm for such models whose regret is bounded by the number of parame…
We study multi-armed bandit problems with graph feedback, in which the decision maker is allowed to observe the neighboring actions of the chosen action, in a setting where the graph may vary over time and is never fully revealed to the decision maker. We show that when the feedback graphs are undirected, the original …
We consider the partial observability model for multi-armed bandits, introduced by Mannor and Shamir. Our main result is a characterization of regret in the directed observability model in terms of the dominating and independence numbers of the observability graph. We also show that in the undirected case, the learner …
We consider an adversarial online learning setting where a decision maker can choose an action in every stage of the game. In addition to observing the reward of the chosen action, the decision maker gets side observations on the reward he would have obtained had he chosen some of the other actions. The observation str…
Algorithm identifies best arm in combinatorial bandits with semi-bandit feedback.
problem Identifying the best arm in combinatorial bandits with semi-bandit feedback.
method Interpreted as a sequential zero-sum game, developed a CombGame meta-algorithm with finite time guarantees.
result First computationally efficient algorithm that is asymptotically optimal and has competitive empirical performance.
We present and study a partial-information model of online learning, where a decision maker repeatedly chooses from a finite set of actions, and observes some subset of the associated losses. This naturally models several situations where the losses of different actions are related, and knowing the loss of one action p…
Study on individual regret in cooperative MAB with agents communicating over a graph.
problem Individual regret in cooperative stochastic multi-armed bandits with communication constraints.
method Analyzed COOP-SE algorithm, derived individual regret bounds under various communication constraints.
result First to show an individual regret bound in cooperative stochastic MAB independent of graph diameter.
IDS improves reinforcement learning with contextual information.
problem Optimizing IDS for contextual reinforcement learning.
method Investigated contextual bandit problems and proposed a computationally-efficient IDS.
result Contextual IDS outperforms conditional IDS by considering future contexts.
Optimized strategies for graph-structured bandits reduce regret efficiently.
problem Structured multi-armed bandit problem with graph constraints.
method Adapted IMED algorithm to graph-structured bandits, introducing IMED-GS ⋆ ^\star ⋆ . result IMED-GS ⋆ ^\star ⋆ is asymptotically optimal and requires minimal exploration. Simplifies large action space bandits by selecting representative actions.
problem Efficiently managing large action spaces with correlated outcomes.
method Random sampling and solving of bandit instances to identify representative actions.
result The algorithm selects a smaller set of representative actions that perform nearly as well as the full action space.
Multi-armed bandit(MAB) problem is a reinforcement learning framework where an agent tries to maximise her profit by proper selection of actions through absolute feedback for each action. The dueling bandits problem is a variation of MAB problem in which an agent chooses a pair of actions and receives relative feedback…
New algorithm for context bandits with continuous actions.
problem Efficient decision-making with unknown action structures.
method Reduction-style algorithm combining supervised learning.
result Proven to work in general and validated with experiments.
New action poisoning attacks improve LinUCB's performance by changing action signals.
problem Improving understanding of adversarial attacks on contextual bandit algorithms.
method Proposed action poisoning attacks in white-box and black-box settings.
result Action poisoning attacks can force LinUCB to pull a target arm frequently with low cost.
Study on sample complexity for pure exploration in feedback graph settings.
problem Sample complexity of pure exploration in online learning with feedback graphs.
method Derive instance-specific lower bounds and present asymptotically optimal algorithm TaS-FG.
result TaS-FG is asymptotically optimal and efficient across different graph configurations.
Two algorithms minimize regret in adversarial bandit problems with side-observation losses.
problem Minimizing regret in adversarial multi-armed bandit problems with side-observation losses.
method Proposes two algorithms for different ranges of side-observation probability.
result Regret bounds for different values of side-observation probability.
IDS algorithm optimizes sequential decisions in various monitoring settings.
problem Optimizing sequential decisions in complex monitoring scenarios.
method Information-directed sampling (IDS) algorithm for linear partial monitoring.
result IDS achieves nearly worst-case rate optimality in finite-action games.
New algorithm for bandits with delayed action effects, reducing regret.
problem Delayed impact of actions in multi-armed bandits.
method Formulated a new bandit setting with delayed action effects, proposed an algorithm with regret bound.
result Achieved a regret of i l d e O ( K T 2 / 3 ) ilde{\mathcal{O}}(KT^{2/3}) i l d e O ( K T 2/3 ) and showed a matching lower bound. Study of reinforcement learning with additional feedback observations.
problem Episodic reinforcement learning in Markov decision processes with feedback observations.
method Formalization of feedback graph, model-based algorithms leveraging feedback, regret bound analysis.
result Regret bound depends only on the size of the maximum acyclic subgraph of the feedback graph.
We study agents communicating over an underlying network by exchanging messages, in order to optimize their individual regret in a common nonstochastic multi-armed bandit problem. We derive regret minimization algorithms that guarantee for each agent v v v an individual expected regret of $\widetilde{O}\left(\sqrt{\left(…
Efficient algorithms for contextual bandits with smooth regret in continuous action spaces.
problem Efficient learning in large or continuous action spaces.
method Smooth regret notion and efficient algorithms for general function approximation.
result Statistically and computationally efficient algorithms for contextual bandits with smooth regret.
Practical algorithm for contextual bandits with large action spaces.
problem Efficient algorithms for decision making in large, continuous action spaces.
method Uses computational oracles for supervised learning and optimization over the action space.
result Achieves sample complexity, runtime, and memory independent of the size of the action space.
The paper extends Thompson Sampling to infinite action spaces using information theory.
problem Addressing the limitation of finite action spaces in Thompson Sampling.
method Information-theoretic analysis, extending rate-distortion theory to infinite action spaces.
result Derives a near-optimal regret bound for bandits with infinite and continuous action spaces.
A new framework for structured bandits using influence diagrams and variational Thompson sampling.
problem Complex statistical dependencies in structured bandit problems.
method Influence diagram framework, variational Thompson sampling, tracking structured posterior distribution.
result Empirically evaluated algorithms perform as well as or better than existing baselines.
Proposes a new algorithm for graph-based semi-parametric contextual bandits.
problem Non-stationarity in human behavior and social interaction.
method SemiGraphTS algorithm for graph-based semi-parametric reward model.
result Derives an upper bound of cumulative regret for graph-based semi-parametric model.
Paper solves stochastic contextual linear bandits using linear bandit algorithms.
problem Stochastic contextual linear bandits with unknown context distribution.
method Establishes a reduction framework to convert to linear bandit problems.
result Achieves nearly optimal regret bound of O ( d T log T ) O(d\sqrt{T\log T}) O ( d T log T ) . A new algorithm tackles graph-based contextual bandits with efficient regret bounds.
problem Predicting labels on graphs with contextual bandit methods.
method Graph-based contextual bandit algorithm using optimal stochastic bandit techniques.
result Regret bounds for line graphs and trees, and improved bounds for general graphs.
The paper tackles multi-player information asymmetry bandits in metric spaces.
problem Information asymmetry in rewards, actions, or both in multiplayer bandit problems.
method Adopted CAB and zooming algorithms for information asymmetry in rewards and actions.
result Regret bounds of the same order in all 3 problem settings.
New algorithm improves bandit with graph feedback by decomposing regret.
problem Improving performance in bandit problems with graph feedback.
method Partition-based algorithm framework using regret decomposition.
result Improved and optimal regret bounds on various graph families.
Lower bounds on eigenspectrum show rich action spaces force polynomial regret in linear bandits.
problem Understanding the minimum eigenvalue growth in linear bandits with rich action sets.
method Non-asymptotic lower bound on eigenspectrum of design matrix.
result Minimum eigenvalue of expected design matrix grows as Ω ( n ) Ω(\sqrt{n}) Ω ( n ) for sub-linear regret. Study lenient regret and good-action identification in Gaussian process bandits.
problem Optimizing function values above a certain threshold in Gaussian process bandits.
method Study lenient regret notions and introduce algorithms for finding good actions.
result Upper and lower bounds on lenient regret for GP-UCB and elimination algorithms.
Overparameterized models generalize well in offline contextual bandits, but policy-based algorithms struggle.
problem The performance gap between value-based and policy-based algorithms in offline contextual bandits with overparameterized models.
method Analysis of action-stability in objectives and formal proofs of regret bounds.
result The performance gap is due to action-stability of objectives, with value-based objectives being stable and policy-based objectives unstable.
We study adversarial attacks that manipulate the reward signals to control the actions chosen by a stochastic multi-armed bandit algorithm. We propose the first attack against two popular bandit algorithms: ε ε ε -greedy and UCB, \emph{without} knowledge of the mean rewards. The attacker is able to spend only logarithmic …
Bandit is a framework for designing sequential experiments. In each experiment, a learner selects an arm A ∈ A A \in \mathcal{A} A ∈ A and obtains an observation corresponding to A A A . Theoretically, the tight regret lower-bound for the general bandit is polynomial with respect to the number of arms ∣ A ∣ |\mathcal{A}| ∣ A ∣ . This makes ba…
We introduce the factored bandits model, which is a framework for learning with limited (bandit) feedback, where actions can be decomposed into a Cartesian product of atomic actions. Factored bandits incorporate rank-1 bandits as a special case, but significantly relax the assumptions on the form of the reward function…
BLISS optimizes GNN training by adaptively sampling nodes.
problem High computational costs in training GNNs on large graphs.
method Uses Bandit Layer Importance Sampling to dynamically select nodes.
result Improves GNN performance with reduced computational cost.
New algorithm reduces sleeping bandits' regret to O(sqrt(T)).
problem Improving sleeping bandits with stochastic actions and adversarial rewards.
method Inspired by EXP3, new algorithm with O ( T ) O(\sqrt{T}) O ( T ) regret. result Achieves O ( T ) O(\sqrt{T}) O ( T ) regret, improving over existing O ( T 2 / 3 ) O(T^{2/3}) O ( T 2/3 ) . A UCB algorithm reduces regret in cooperative multi-agent graph bandits.
problem Cooperative multi-agent decision-making on a graph with shared rewards.
method Upper Confidence Bound (UCB) algorithm for minimizing regret.
result The Multi-G-UCB algorithm achieves expected regret O ( γ N log ( T ) [ K T + D K ] ) O(γN\log(T)[\sqrt{KT} + DK]) O ( γ N log ( T ) [ K T + D K ]) . New attack manipulates UCB algorithm, new defense algorithm reduces pseudo-regret.
problem Adversarial attacks on stochastic bandit algorithms.
method Introducing action-manipulation attacks and proposing a robust defense algorithm.
result Proposed defense algorithm reduces pseudo-regret to O(max{log T, A}).
Optimizes matching in weighted graphs with semi-bandit sampling.
problem Finding optimal pairings in weighted graphs with sequential sampling.
method Leverages rank-1 assumption on adjacency matrix to reduce sample complexity and regret.
result Achieves linear dependency in the number of vertices for sample complexity and regret.