Near-Optimal Online Learning with Non-Stochastic and Unbounded Erroneous Feedback

Abstract

Online learning is a foundational machine learning paradigm in both academia and industry. Most existing online learning techniques are designed for idealized scenarios where the feedback on the decision costs observed by the learner is assumed reliable, i.e., the same as the ground truth. Many recent efforts that attempted to investigate erroneous feedbacks considered errors with unrealistic settings, such as restrictive stochasticity and/or error bounds (e.g., bounded corruption magnitudes or budget of deviations from the ground truths). In this work, we consider a novel and challenging problem of full-information online learning in the presence of feedback with non-stochastic and unbounded errors. According to our analysis, existing representative techniques suffer unbounded regret when applied to our problem. To tackle such erroneous feedback, we propose a robust online learning strategy with a tailored FTRL-like decision-making approach based on a coordinate-wise trimmed sum mechanism, which we prove can achieve a near-optimal, sublinear regret bound of ${\mathcal{O}}\left({\sqrt T }\right)$ under certain justified conditions. We compare our solution against four representative approaches by evaluating them in three exemplary networking applications. The results not only corroborate our theoretical analysis but also clearly demonstrate the robustness of our algorithm in comparison to the baselines.