Stochastic Online Learning with Probabilistic Graph Feedback

Abstract

We consider a problem of stochastic online learning with general probabilistic graph feedback, where each directed edge in the feedback graph has probability $p_{ij}$. Two cases are covered. (a) The one-step case, where after playing arm $i$ the learner observes a sample reward feedback of arm $j$ with independent probability $p_{ij}$. (b) The cascade case where after playing arm $i$ the learner observes feedback of all arms $j$ in a probabilistic cascade starting from $i$ -- for each $(i,j)$ with probability $p_{ij}$, if arm $i$ is played or observed, then a reward sample of arm $j$ would be observed with independent probability $p_{ij}$. Previous works mainly focus on deterministic graphs which corresponds to one-step case with $p_{ij}\in \{0,1\}$, an adversarial sequence of graphs with certain topology guarantees, or a specific type of random graphs. We analyze the asymptotic lower bounds and design algorithms in both cases. The regret upper bounds of the algorithms match the lower bounds with high probability.

References in corpus (11)

• Efficient learning by implicit exploration in bandit problems with side observations
• Combinatorial Multi-Armed Bandit and Its Extension to Probabilistically Triggered Arms
• From Bandits to Experts: On the Value of Side-Observations
• Online Learning with Feedback Graphs: Beyond Bandits
• Online Influence Maximization under Independent Cascade Model with Semi-Bandit Feedback
• Improving Regret Bounds for Combinatorial Semi-Bandits with Probabilistically Triggered Arms and Its Applications
• Online learning with noisy side observations
• Influence Maximization with Bandits
• Online Learning with Feedback Graphs Without the Graphs
• Information Directed Sampling for Stochastic Bandits with Graph Feedback
• Regret Lower Bound and Optimal Algorithm in Finite Stochastic Partial Monitoring

Cited by in corpus (1)

• Thompson Sampling for Combinatorial Network Optimization in Unknown Environments