2 citations · 4 across the 18 of their papers we have counts for
15 papers · 1 filter
Adversarial Learning in Games with Bandit Feedback: Logarithmic Pure-Strategy Maximin Regret
Shinji Ito, Haipeng Luo, Arnab Maiti +2
Learning to play zero-sum games is a fundamental problem in game theory and machine learning. While significant progress has been made in minimizing external regret in the self-pla…
Adapting to Stochastic and Adversarial Losses in Episodic MDPs with Aggregate Bandit Feedback
Shinji Ito, Kevin Jamieson, Haipeng Luo +2
We study online learning in finite-horizon episodic Markov decision processes (MDPs) under the challenging aggregate bandit feedback model, where the learner observes only the cumu…
Tight Regret Upper and Lower Bounds for Optimistic Hedge in Two-Player Zero-Sum Games
Taira Tsuchiya
In two-player zero-sum games, the learning dynamic based on optimistic Hedge achieves one of the best-known regret upper bounds among strongly-uncoupled learning dynamics. With an…
From Dueling Bandits to Episodic MDPs: Learning with Adversarial Preference Feedback
Taira Tsuchiya, Shinji Ito, Haipeng Luo
In dueling bandits, the learner compares two arms in each round and observes only which one is preferred. This paper asks what changes when the compared pair also affects the next…
Instance-Dependent Regret Bounds for Learning Two-Player Zero-Sum Games with Bandit Feedback
Shinji Ito, Haipeng Luo, Taira Tsuchiya +1
No-regret self-play learning dynamics have become one of the premier ways to solve large-scale games in practice. Accelerating their convergence via improving the regret of the pla…
A Simple and Adaptive Learning Rate for FTRL in Online Learning with Minimax Regret of and its Application to Best-of-Both-Worlds
Taira Tsuchiya, Shinji Ito
Follow-the-Regularized-Leader (FTRL) is a powerful framework for various online learning problems. By designing its regularizer and learning rate to be adaptive to past observation…
Adaptive Learning Rate for Follow-the-Regularized-Leader: Competitive Analysis and Best-of-Both-Worlds
Shinji Ito, Taira Tsuchiya, Junya Honda
Follow-The-Regularized-Leader (FTRL) is known as an effective and versatile approach in online learning, where appropriate choice of the learning rate is crucial for smaller regret…
Fast Rates in Stochastic Online Convex Optimization by Exploiting the Curvature of Feasible Sets
Taira Tsuchiya, Shinji Ito
In this work, we explore online convex optimization (OCO) and introduce a new condition and analysis that provides fast rates by exploiting the curvature of feasible sets. In onlin…
Exploration by Optimization with Hybrid Regularizers: Logarithmic Regret with Adversarial Robustness in Partial Monitoring
Taira Tsuchiya, Shinji Ito, Junya Honda
Partial monitoring is a generic framework of online decision-making problems with limited feedback. To make decisions from such limited feedback, it is necessary to find an appropr…
Best-of-Both-Worlds Algorithms for Linear Contextual Bandits
Yuko Kuroki, Alberto Rumi, Taira Tsuchiya +2
We study best-of-both-worlds algorithms for -armed linear contextual bandits. Our algorithms deliver near-optimal regret bounds in both the adversarial and stochastic regimes, w…
Stability-penalty-adaptive follow-the-regularized-leader: Sparsity, game-dependency, and best-of-both-worlds
Taira Tsuchiya, Shinji Ito, Junya Honda
Adaptivity to the difficulties of a problem is a key property in sequential decision-making problems to broaden the applicability of algorithms. Follow-the-regularized-leader (FTRL…
Best-of-Both-Worlds Algorithms for Partial Monitoring
Taira Tsuchiya, Shinji Ito, Junya Honda
This study considers the partial monitoring problem with -actions and -outcomes and provides the first best-of-both-worlds algorithms, whose regrets are favorably bounded bot…
Adversarially Robust Multi-Armed Bandit Algorithm with Variance-Dependent Regret Bounds
Shinji Ito, Taira Tsuchiya, Junya Honda
This paper considers the multi-armed bandit (MAB) problem and provides a new best-of-both-worlds (BOBW) algorithm that works nearly optimally in both stochastic and adversarial set…
Nearly Optimal Best-of-Both-Worlds Algorithms for Online Learning with Feedback Graphs
Shinji Ito, Taira Tsuchiya, Junya Honda
This study considers online learning with general directed feedback graphs. For this problem, we present best-of-both-worlds algorithms that achieve nearly tight regret bounds for…
Semi-Supervised Ordinal Regression Based on Empirical Risk Minimization
Taira Tsuchiya, Nontawat Charoenphakdee, Issei Sato +1
Ordinal regression is aimed at predicting an ordinal class label. In this paper, we consider its semi-supervised formulation, in which we have unlabeled data along with ordinal-lab…