2 citations · 4 across the 18 of their papers we have counts for
20 papers
Sublogarithmic Swap Regret in Multiplayer General-Sum Games via Hybrid Regularization
Taira Tsuchiya
Swap regret governs the rate at which uncoupled learning dynamics converge to correlated equilibria in multiplayer general-sum games. Under full-information feedback, the best prev…
Scale-Invariant Fast Convergence in Games
Taira Tsuchiya, Haipeng Luo, Shinji Ito
Scale-invariance in games has recently emerged as a widely valued desirable property. Yet, almost all fast convergence guarantees in learning in games require prior knowledge of th…
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…
Corrupted Learning Dynamics in Games
Taira Tsuchiya, Shinji Ito, Haipeng Luo
Learning in games refers to scenarios where multiple players interact in a shared environment, each aiming to minimize their regret. An equilibrium can be computed at a fast rate o…
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…
Minimax Optimal Algorithms for Fixed-Budget Best Arm Identification
Junpei Komiyama, Taira Tsuchiya, Junya Honda
We consider the fixed-budget best arm identification problem where the goal is to find the arm of the largest mean with a fixed number of samples. It is known that the probability…
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…
Analysis and Design of Thompson Sampling for Stochastic Partial Monitoring
Taira Tsuchiya, Junya Honda, Masashi Sugiyama
We investigate finite stochastic partial monitoring, which is a general model for sequential learning with limited feedback. While Thompson sampling is one of the most promising al…
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…