FTPL
A class of algorithmic frameworks in online learning in which a random perturbation is applied to the cumulative loss vector each round, after which the action minimizing the perturbed loss is selected; known for its simplicity and theoretical guarantees.
Timeline (last 90 days)
The paper "Nearly Linear-Time Follow-the-Perturbed-Leader for Weakly Observable Graph Bandits" proposes a new FTPL strategy that achieves best-of-both-worlds guarantees for adversarial and stochastic environments in weakly observable graph bandits, with expected time complexity that is nearly linear.
In the adversarial environment, the regret of the paper's algorithm is \tilde{\mathcal{O}}(δ_*^{1/3} T^{2/3}), where δ_* is the fractional weak domination number.
In the stochastic environment, the regret of the paper's algorithm is \tilde{\mathcal{O}}(δ_* \log T / Δ_{\min}^2), where Δ_{\min} is the minimum suboptimality gap.
Through the design of conditional geometric resampling and surrogate probabilities, the algorithm requires only a constant number of graph operations per update, thereby achieving nearly linear expected time without explicitly enumerating all unobserved nodes.
All Facts (4)
The paper "Nearly Linear-Time Follow-the-Perturbed-Leader for Weakly Observable Graph Bandits" proposes a new FTPL strategy that achieves best-of-both-worlds guarantees for adversarial and stochastic environments in weakly observable graph bandits, with expected time complexity that is nearly linear.
50%UnverifiedIn the adversarial environment, the regret of the paper's algorithm is \tilde{\mathcal{O}}(δ_*^{1/3} T^{2/3}), where δ_* is the fractional weak domination number.
50%UnverifiedIn the stochastic environment, the regret of the paper's algorithm is \tilde{\mathcal{O}}(δ_* \log T / Δ_{\min}^2), where Δ_{\min} is the minimum suboptimality gap.
50%UnverifiedThrough the design of conditional geometric resampling and surrogate probabilities, the algorithm requires only a constant number of graph operations per update, thereby achieving nearly linear expected time without explicitly enumerating all unobserved nodes.
50%