Publications (43)
Distributed coordination of self-organizing mechanisms in communication networks
Abdoulaye Tall, Richard Combes, Zwi Altman +1
The fast development of the Self-Organizing Network (SON) technology in mobile networks renders the problem of coordinating SON functionalities operating simultaneously critical. S…
From Bayesian Asymptotics to General Large-Scale MIMO Capacity
Sheng Yang, Richard Combes
We present a unifying framework that bridges Bayesian asymptotics and information theory to analyze the asymptotic Shannon capacity of general large-scale MIMO channels including o…
Solving Bernoulli Rank-One Bandits with Unimodal Thompson Sampling
Cindy Trinh, Emilie Kaufmann, Claire Vernade +1
Stochastic Rank-One Bandits (Katarya et al, (2017a,b)) are a simple framework for regret minimization problems over rank-one matrices of arms. The initially proposed algorithms are…
Learning-Based Channel Access in Wi-Fi: A Multi-Armed Bandit Approach
Miguel Casasnovas, Francesc Wilhelmi, Richard Combes +6
Due to its static protocol design, IEEE 802.11 (aka Wi-Fi) channel access lacks adaptability to address dynamic network conditions, resulting in inefficient spectrum utilization, u…
Performance Evaluation of Multi-Armed Bandit Algorithms for Wi-Fi Channel Access
Miguel Casasnovas, Francesc Wilhelmi, Richard Combes +6
The adoption of dynamic, self-learning solutions for real-time wireless network optimization has recently gained significant attention due to the limited adaptability of existing p…
Towards Optimal Algorithms for Multi-Player Bandits without Collision Sensing Information
Wei Huang, Richard Combes, Cindy Trinh
We propose a novel algorithm for multi-player multi-armed bandits without collision sensing information. Our algorithm circumvents two problems shared by all state-of-the-art algor…
Lipschitz Bandits: Regret Lower Bounds and Optimal Algorithms
Stefan Magureanu, Richard Combes, Alexandre Proutiere
We consider stochastic multi-armed bandit problems where the expected reward is a Lipschitz function of the arm, and where the set of arms is either discrete or continuous. For dis…
Tractable Instances of Bilinear Maximization: Implementing LinUCB on Ellipsoids
Raymond Zhang, Hédi Hadiji, Richard Combes
We consider the maximization of over , with convex and an ellipsoid. This…
Utility Optimal Scheduling for Coded Caching in General Topologies
Richard Combes, Asma Ghorbel, Mari Kobayashi +1
We consider coded caching over the fading broadcast channel, where the users, equipped with a memory of finite size, experience asymmetric fading statistics. It is known that a nai…
Statistically Efficient, Polynomial Time Algorithms for Combinatorial Semi Bandits
Thibaut Cuvelier, Richard Combes, Eric Gourdin
We consider combinatorial semi-bandits over a set of arms where rewards are uncorrelated across items. For this problem, the algorithm ESCB yields the…
Stochastic Online Shortest Path Routing: The Value of Feedback
M. Sadegh Talebi, Zhenhua Zou, Richard Combes +2
This paper studies online shortest path routing over multi-hop networks. Link costs or delays are time-varying and modeled by independent and identically distributed random process…
Combinatorial Bandits Revisited
Richard Combes, M. Sadegh Talebi, Alexandre Proutiere +1
This paper investigates stochastic and adversarial combinatorial multi-armed bandit problems. In the stochastic setting under semi-bandit feedback, we derive a problem-specific reg…
Multimodal Bandits: Regret Lower Bounds and Optimal Algorithms
William Réveillard, Richard Combes
We consider a stochastic multi-armed bandit problem with i.i.d. rewards where the expected reward function is multimodal with at most m modes. We propose the first known computatio…
An extension of McDiarmid's inequality
Richard Combes
We generalize McDiarmid's inequality for functions with bounded differences on a high probability set, using an extension argument. Those functions concentrate around their conditi…
Unimodal Bandits without Smoothness
Richard Combes, Alexandre Proutiere
We consider stochastic bandit problems with a continuous set of arms and where the expected reward is a continuous and unimodal function of the arm. No further assumption is made r…
Asymptotic Capacity of 1-Bit MIMO Fading Channels
Sheng Yang, Richard Combes
In this work, we investigate the capacity of multi-antenna fading channels with 1-bit quantized output per receive antenna. Specifically, leveraging Bayesian statistical tools, we…
On the Suboptimality of Thompson Sampling in High Dimensions
Raymond Zhang, Richard Combes
In this paper we consider Thompson Sampling (TS) for combinatorial semi-bandits. We demonstrate that, perhaps surprisingly, TS is sub-optimal for this problem in the sense that its…
Asymptotically Optimal Strategies For Combinatorial Semi-Bandits in Polynomial Time
Thibaut Cuvelier, Richard Combes, Eric Gourdin
We consider combinatorial semi-bandits with uncorrelated Gaussian rewards. In this article, we propose the first method, to the best of our knowledge, that enables to compute the s…
Optimal Rate Sampling in 802.11 Systems
Richard Combes, Alexandre Proutiere, Donggyu Yun +2
In 802.11 systems, Rate Adaptation (RA) is a fundamental mechanism allowing transmitters to adapt the coding and modulation scheme as well as the MIMO transmission mode to the radi…
Dynamic Rate and Channel Selection in Cognitive Radio Systems
Richard Combes, Alexandre Proutiere
In this paper, we investigate dynamic channel and rate selection in cognitive radio systems which exploit a large number of channels free from primary users. In such systems, trans…
Minimizing Human Intervention in Online Classification
William Réveillard, Vasileios Saketos, Alexandre Proutiere +1
Training or fine-tuning large language model (LLM)-based systems often requires costly human feedback, yet there is limited understanding of how to minimize such intervention while…
A High Performance, Low Complexity Algorithm for Multi-Player Bandits Without Collision Sensing Information
Cindy Trinh, Richard Combes
Motivated by applications in cognitive radio networks, we consider the decentralized multi-player multi-armed bandit problem, without collision nor sensing information. We propose…
Hierarchical Beamforming: Resource Allocation, Fairness and Flow Level Performance
Julien Floquet, Richard Combes, Zwi Altman
We consider hierarchical beamforming in wireless networks. For a given population of flows, we propose computationally efficient algorithms for fair rate allocation including propo…
Multipath streaming: fundamental limits and efficient algorithms
Richard Combes, Habib Sidi, Salah-Eddine Elayoubi
We investigate streaming over multiple links. A file is split into small units called chunks that may be requested on the various links according to some policy, and received after…
Linear Bandits on Ellipsoids: Minimax Optimal Algorithms
Raymond Zhang, Hedi Hadiji, Richard Combes
We consider linear stochastic bandits where the set of actions is an ellipsoid. We provide the first known minimax optimal algorithm for this problem. We first derive a novel infor…
Device-to-Device Aided Multicasting
Thomas Varela Santana, Richard Combes, Mari Kobayashi
We consider a device-to-device (D2D) aided multicast channel, where a transmitter wishes to convey a common message to many receivers and these receivers cooperate with each other.…
Coordination of autonomic functionalities in communications networks
Richard Combes, Zwi Altman, Eitan Altman
Future communication networks are expected to feature autonomic (or self-organizing) mechanisms to ease deployment (self-configuration), tune parameters automatically (self-optimiz…
Mixed Polling with Rerouting and Applications
Veeraruna Kavitha, Richard Combes
Queueing systems with a single server in which customers wait to be served at a finite number of distinct locations (buffers/queues) are called discrete polling systems. Polling sy…
Flow-level performance of random wireless networks
Richard Combes, Eitan Altman
We study the flow-level performance of random wireless networks. The locations of base stations (BSs) follow a Poisson point process. The number and positions of active users are d…
Minimal Exploration in Structured Stochastic Bandits
Richard Combes, Stefan Magureanu, Alexandre Proutiere
This paper introduces and addresses a wide class of stochastic bandit problems where the function mapping the arm to the corresponding reward exhibits some known structural propert…
Towards Specialized Wireless Networks Using an ML-Driven Radio Interface
Kamil Szczech, Maksymilian Wojnar, Katarzyna Kosek-Szott +8
Future wireless networks will need to support diverse applications (such as extended reality), scenarios (such as fully automated industries), and technological advances (such as t…
Thompson Sampling For Combinatorial Bandits: Polynomial Regret and Mismatched Sampling Paradox
Raymond Zhang, Richard Combes
We consider Thompson Sampling (TS) for linear combinatorial semi-bandits and subgaussian rewards. We propose the first known TS whose finite-time regret does not scale exponentiall…
Computationally Efficient Estimation of the Spectral Gap of a Markov Chain
Richard Combes, Mikael Touati
We consider the problem of estimating from sample paths the absolute spectral gap of a reversible, irreducible and aperiodic Markov chain over a f…
A Streaming Algorithm for Crowdsourced Data Classification
Thomas Bonald, Richard Combes
We propose a streaming algorithm for the binary classification of data based on crowdsourcing. The algorithm learns the competence of each labeller by comparing her labels to those…
Unimodal Bandits: Regret Lower Bounds and Optimal Algorithms
Richard Combes, Alexandre Proutiere
We consider stochastic multi-armed bandits where the expected reward is a unimodal function over partially ordered arms. This important class of problems has been recently investig…
Solving Random Parity Games in Polynomial Time
Richard Combes, Mikael Touati
We consider the problem of solving random parity games. We prove that parity games exibit a phase transition threshold above , so that when the degree of the graph that define…
Contextual Linear Bandits under Noisy Features: Towards Bayesian Oracles
Jung-hun Kim, Se-Young Yun, Minchan Jeong +3
We study contextual linear bandit problems under feature uncertainty, where the features are noisy and have missing entries. To address the challenges posed by this noise, we analy…
A Minimax Optimal Algorithm for Crowdsourcing
Thomas Bonald, Richard Combes
We consider the problem of accurately estimating the reliability of workers based on noisy labels they provide, which is a fundamental question in crowdsourcing. We propose a novel…
Opportunistic Content Delivery in Fading Broadcast Channels
Asma Ghorbel, Khac-Hoang Ngo, Richard Combes +2
We consider content delivery over fading broadcast channels. A server wants to transmit K files to K users, each equipped with a cache of finite size. Using the coded caching schem…
An Approximate ML Detector for MIMO Channels Corrupted by Phase Noise
Richard Combes, Sheng Yang
We consider the multiple-input multiple-output (MIMO) communication channel impaired by phase noises at both the transmitter and receiver. We focus on the maximum likelihood (ML) d…
Mismatched Exponents for Deterministic and Randomised Noise-Guessing Decoding
Henrique K. Miyamoto, Richard Combes, Sheng Yang
We study both the deterministic and randomised variants of noise-guessing decoding in additive memoryless channels. The error and complexity exponents of such decoding schemes are…
The association problem in wireless networks: a Policy Gradient Reinforcement Learning approach
Richard Combes, Ilham El Bouloumi, Stephane Senecal +1
The purpose of this paper is to develop a self-optimized association algorithm based on PGRL (Policy Gradient Reinforcement Learning), which is both scalable, stable and robust. Th…
Online Learning for Function Placement in Serverless Computing
Wei Huang, Richard Combes, Andrea Araldo +2
We study the placement of virtual functions aimed at minimizing the cost. We propose a novel algorithm, using ideas based on multi-armed bandits. We prove that these algorithms lea…