Shinji Ito

Prediction with Expert Advice under Heavy-Tailed Losses

Yuki Shibukawa, Shinji Ito

We study prediction with expert advice over $T$ rounds with $K$ experts under heavy-tailed losses whose $(1 + ε)$ -moment is bounded by $θ > 0$ for some $ε \in (0, 1]$ . In this setting, ex…

A Perturbation Approach to Unconstrained Linear Bandits

Andrew Jacobsen, Dorian Baudry, Shinji Ito +1

We revisit the standard perturbation-based approach of Abernethy et al. (2008) in the context of unconstrained Bandit Linear Optimization (uBLO). We show the surprising result that…

Combinatorial Allocation Bandits with Nonlinear Arm Utility

Yuki Shibukawa, Koichi Tanaka, Yuta Saito +1

A matching platform is a system that matches participants of different types, such as companies and job-seekers. In such a platform, maximizing matches may concentrate assignments…

cs.GT2026

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…

Reinforcement Learning from Adversarial Preferences in Tabular MDPs

Taira Tsuchiya, Shinji Ito, Haipeng Luo

We introduce a new framework of episodic tabular Markov decision processes (MDPs) with adversarial preferences, which we refer to as preference-based MDPs (PbMDPs). Unlike standard…

stat.ML2025

Optimal Regret of Bernoulli Bandits under Global Differential Privacy

Achraf Azize, Yulian Wu, Junya Honda +3

As sequential learning algorithms are increasingly applied to real life, ensuring data privacy while maintaining their utilities emerges as a timely question. In this context, regr…

Bandit Max-Min Fair Allocation

Tsubasa Harada, Shinji Ito, Hanna Sumita

In this paper, we study a new decision-making problem called the bandit max-min fair allocation (BMMFA) problem. The goal of this problem is to maximize the minimum utility among a…

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…

cs.GT2024

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…

Learning with Posterior Sampling for Revenue Management under Time-varying Demand

Kazuma Shimizu, Junya Honda, Shinji Ito +1

This paper discusses the revenue management (RM) problem to maximize revenue by pricing items or services. One challenge in this problem is that the demand distribution is unknown…

A Simple and Adaptive Learning Rate for FTRL in Online Learning with Minimax Regret of $Θ (T^{2/3})$ 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…

math.OC2024

Contaminated Online Convex Optimization

Tomoya Kamijima, Shinji Ito

In online convex optimization, some efficient algorithms have been designed for each of the individual classes of objective functions, e.g., convex, strongly convex, and exp-concav…

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…

stat.ML2024

Follow-the-Perturbed-Leader with Fréchet-type Tail Distributions: Optimality in Adversarial Bandits and Best-of-Both-Worlds

Jongyeong Lee, Junya Honda, Shinji Ito +1

This paper studies the optimality of the Follow-the-Perturbed-Leader (FTPL) policy in both adversarial and stochastic $K$ -armed bandits. Despite the widespread use of the Follow-th…

LC-Tsallis-INF: Generalized Best-of-Both-Worlds Linear Contextual Bandits

Masahiro Kato, Shinji Ito

We investigate the \emph{linear contextual bandit problem} with independent and identically distributed (i.i.d.) contexts. In this problem, we aim to develop a \emph{Best-of-Both-W…

math.OC2024

Prediction-Correction Algorithm for Time-Varying Smooth Non-Convex Optimization

Hidenori Iwakiri, Tomoya Kamijima, Shinji Ito +1

Time-varying optimization problems are prevalent in various engineering fields, and the ability to solve them accurately in real-time is becoming increasingly important. The predic…

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…