Stochastic Online Learning with Probabilistic Graph Feedback
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.
Code (0)
등록된 구현이 없습니다.
Similar Papers 제목 키워드 기반
Stochastic MPC with Online-optimized Policies and Closed-loop Guarantees
This paper proposes a stochastic model predictive control method for linear systems affected by additive Gaussian disturbances. Closed-loop satisfaction of probabilistic constraints and recursive feasibility of the under…
Model Predictive ControlOnline Learning with Dependent Stochastic Feedback Graphs
A general framework for online learning with partial information is one where feedback graphs specify which losses can be observed by the learner. We study a challenging scenario where feedback graphs vary stochastically…
Online Learning with Feedback Graphs Without the Graphs
We study an online learning framework introduced by Mannor and Shamir (2011) in which the feedback is specified by a graph, in a setting where the graph may vary from round to round and is \emph{never fully revealed} to …
A Near-Optimal Best-of-Both-Worlds Algorithm for Online Learning with Feedback Graphs
We consider online learning with feedback graphs, a sequential decision-making framework where the learner's feedback is determined by a directed graph over the action set. We present a computationally efficient algorith…
Decision MakingSequential Decision MakingFast Stochastic MPC using Affine Disturbance Feedback Gains Learned Offline
We propose a novel Stochastic Model Predictive Control (MPC) for uncertain linear systems subject to probabilistic constraints. The proposed approach leverages offline learning to extract key features of affine disturban…
Computational EfficiencyModel Predictive Control