Richard Combes
Current Organizations / Institutes
The organizations/institutes from the scholar's latest article
Richard Combes has a total of 8 co-authors. Here are the top co-authors by number of shared publications:
- Thomas Bonald
TELECOM ParisTech Paris France
2 shared publications Habib Sidi
1 shared publication- Mari Kobayashi
LSS Gif-sur-Yvette CentraleSupélec France
1 shared publication - Raymond Zhang
Laboratoire des signaux et systèmes Université Paris-Saclay CNRS CentraleSupélec 91190 Gif-sur-Yvette France
1 shared publication - Salah Eddine Elayoubi
92130 Orange Labs Issy Les Moulineaux France
1 shared publication - Sheng Yang
Laboratory of Signals and Systems, Centrale-Suplec, CNRS, Universit Paris-Sud, Gif-sur-Yvette, France
1 shared publication
Latest Publications
- Open Access
Multimodal Bandits: Regret Lower Bounds and Optimal Algorithms
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 computationally tractable algorithm for computing the solution to the Graves-Lai optimization problem, which in turn enables the implementation of asymptotically optimal algorithms for this bandit problem. The code for the proposed algorithms is publicly available at https://github.com/wilrev/MultimodalBandits
Open AccessMultimodal Bandits: Regret Lower Bounds and Optimal Algorithms
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 computationally tractable algorithm for computing the solution to the Graves-Lai optimization problem, which in turn enables the implementation of asymptotically optimal algorithms for this bandit problem. The code for the proposed algorithms is publicly available at https://github.com/wilrev/MultimodalBandits
- Open Access
Thompson Sampling For Combinatorial Bandits: Polynomial Regret and Mismatched Sampling Paradox
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 exponentially with the dimension of the problem. We further show the "mismatched sampling paradox": A learner who knows the rewards distributions and samples from the correct posterior distribution can perform exponentially worse than a learner who does not know the rewards and simply samples from a well-chosen Gaussian posterior. The code used to generate the experiments is available at https://github.com/RaymZhang/CTS-Mismatched-Paradox
Open AccessThompson Sampling For Combinatorial Bandits: Polynomial Regret and Mismatched Sampling Paradox
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 exponentially with the dimension of the problem. We further show the "mismatched sampling paradox": A learner who knows the rewards distributions and samples from the correct posterior distribution can perform exponentially worse than a learner who does not know the rewards and simply samples from a well-chosen Gaussian posterior. The code used to generate the experiments is available at https://github.com/RaymZhang/CTS-Mismatched-Paradox
- Open Access
Asymptotic Capacity of 1-Bit MIMO Fading Channels
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 analyze the asymptotic regime with a large number of receive antennas. In the coherent case, where the channel state information (CSI) is known at the receiver's side, we completely characterize the asymptotic capacity and provide the exact scaling in the extreme regimes of signal-to-noise ratio (SNR) and the number of transmit antennas. In the non-coherent case, where the CSI is unknown but remains constant during T symbol periods, we first obtain the exact asymptotic capacity for T<=3. Then, we propose a scheme involving uniform signaling in the covariance space and derive a non-asymptotic lower bound on the capacity for an arbitrary block size T. Furthermore, we propose a genie-aided upper bound where the channel is revealed to the receiver. We show that the upper and lower bounds coincide when T is large. In the low SNR regime, we derive the asymptotic capacity up to a vanishing term, which, remarkably, matches our capacity lower bound.
Open AccessAsymptotic Capacity of 1-Bit MIMO Fading Channels
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 analyze the asymptotic regime with a large number of receive antennas. In the coherent case, where the channel state information (CSI) is known at the receiver's side, we completely characterize the asymptotic capacity and provide the exact scaling in the extreme regimes of signal-to-noise ratio (SNR) and the number of transmit antennas. In the non-coherent case, where the CSI is unknown but remains constant during T symbol periods, we first obtain the exact asymptotic capacity for T<=3. Then, we propose a scheme involving uniform signaling in the covariance space and derive a non-asymptotic lower bound on the capacity for an arbitrary block size T. Furthermore, we propose a genie-aided upper bound where the channel is revealed to the receiver. We show that the upper and lower bounds coincide when T is large. In the low SNR regime, we derive the asymptotic capacity up to a vanishing term, which, remarkably, matches our capacity lower bound.
- Open Access
Device-to-Device Aided Multicasting
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. We propose a simple computationally efficient scheme requiring only statistical channel knowledge at transmitter. Our analysis in general topologies reveals that, when the number of receivers $K$ grows to infinity, the proposed scheme guarantees a multicast rate of ${1 \over 2} \log_2(1 + \beta \ln K )$ with high probability for any $\beta < \beta^\star$ where $\beta^\star$ depends on the network topology. This scheme undergoes a phase transition at threshold $\beta^\star \ln K$ where transmissions are successful/unsuccessful with high probability when the SNR is above/below this threshold. We also analyze the outage rate of the proposed scheme in the same setting.Open AccessDevice-to-Device Aided Multicasting
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. We propose a simple computationally efficient scheme requiring only statistical channel knowledge at transmitter. Our analysis in general topologies reveals that, when the number of receivers $K$ grows to infinity, the proposed scheme guarantees a multicast rate of ${1 \over 2} \log_2(1 + \beta \ln K )$ with high probability for any $\beta < \beta^\star$ where $\beta^\star$ depends on the network topology. This scheme undergoes a phase transition at threshold $\beta^\star \ln K$ where transmissions are successful/unsuccessful with high probability when the SNR is above/below this threshold. We also analyze the outage rate of the proposed scheme in the same setting. - Open Access
Multipath streaming: fundamental limits and efficient algorithms
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 some random delay. After a start-up time called pre-buffering time, received chunks are played at a fixed speed. There is starvation if the chunk to be played has not yet arrived. We provide lower bounds (fundamental limits) on the starvation probability of any policy. We further propose simple, order-optimal policies that require no feedback. For general delay distributions, we provide tractable upper bounds for the starvation probability of the proposed policies, allowing to select the pre-buffering time appropriately. We specialize our results to: (i) links that employ CSMA or opportunistic scheduling at the packet level, (ii) links shared with a primary user (iii) links that use fair rate sharing at the flow level. We consider a generic model so that our results give insight into the design and performance of media streaming over (a) wired networks with several paths between the source and destination, (b) wireless networks featuring spectrum aggregation and (c) multi-homed wireless networks.
Open AccessMultipath streaming: fundamental limits and efficient algorithms
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 some random delay. After a start-up time called pre-buffering time, received chunks are played at a fixed speed. There is starvation if the chunk to be played has not yet arrived. We provide lower bounds (fundamental limits) on the starvation probability of any policy. We further propose simple, order-optimal policies that require no feedback. For general delay distributions, we provide tractable upper bounds for the starvation probability of the proposed policies, allowing to select the pre-buffering time appropriately. We specialize our results to: (i) links that employ CSMA or opportunistic scheduling at the packet level, (ii) links shared with a primary user (iii) links that use fair rate sharing at the flow level. We consider a generic model so that our results give insight into the design and performance of media streaming over (a) wired networks with several paths between the source and destination, (b) wireless networks featuring spectrum aggregation and (c) multi-homed wireless networks.
- Open Access
Crowdsourcing: Low complexity, Minimax Optimal Algorithms
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 lower bound on the minimax estimation error which applies to any estimation procedure. We further propose Triangular Estimation (TE), an algorithm for estimating the reliability of workers. TE has low complexity, may be implemented in a streaming setting when labels are provided by workers in real time, and does not rely on an iterative procedure. We further prove that TE is minimax optimal and matches our lower bound. We conclude by assessing the performance of TE and other state-of-the-art algorithms on both synthetic and real-world data sets.
Open AccessCrowdsourcing: Low complexity, Minimax Optimal Algorithms
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 lower bound on the minimax estimation error which applies to any estimation procedure. We further propose Triangular Estimation (TE), an algorithm for estimating the reliability of workers. TE has low complexity, may be implemented in a streaming setting when labels are provided by workers in real time, and does not rely on an iterative procedure. We further prove that TE is minimax optimal and matches our lower bound. We conclude by assessing the performance of TE and other state-of-the-art algorithms on both synthetic and real-world data sets.
- Open Access
A Streaming Algorithm for Crowdsourced Data Classification
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 of other labellers on the same tasks and uses this information to minimize the prediction error rate on each task. We provide performance guarantees of our algorithm for a fixed population of independent labellers. In particular, we show that our algorithm is optimal in the sense that the cumulative regret compared to the optimal decision with known labeller error probabilities is finite, independently of the number of tasks to label. The complexity of the algorithm is linear in the number of labellers and the number of tasks, up to some logarithmic factors. Numerical experiments illustrate the performance of our algorithm compared to existing algorithms, including simple majority voting and expectation-maximization algorithms, on both synthetic and real datasets.
Open AccessA Streaming Algorithm for Crowdsourced Data Classification
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 of other labellers on the same tasks and uses this information to minimize the prediction error rate on each task. We provide performance guarantees of our algorithm for a fixed population of independent labellers. In particular, we show that our algorithm is optimal in the sense that the cumulative regret compared to the optimal decision with known labeller error probabilities is finite, independently of the number of tasks to label. The complexity of the algorithm is linear in the number of labellers and the number of tasks, up to some logarithmic factors. Numerical experiments illustrate the performance of our algorithm compared to existing algorithms, including simple majority voting and expectation-maximization algorithms, on both synthetic and real datasets.