Competitive Channel-Capacity

We consider communication over channels whose statistics are not known in full, but can be parameterized as a finite family of memoryless channels. A typical approach to address channel uncertainty is to design codes for the worst channel in the family, resulting in the well-known compound channel capacity. Although this approach is robust, it may suffer a loss of performance if the capacity-achieving distribution of the worst channel attains low rates over other channels. In this work, we cope with channel uncertainty through the lens of competitive analysis. The idea is to optimize a relative metric that compares the performance of the designed code and a clairvoyant code that has access to the true channel. To allow communication rates that can adapt to the channel at use, we consider rateless codes with a fixed number of information bits and random decoding times. We propose two competitive metrics: the competitive ratio between the decoding times of the two codes, and a regret defined as the difference between the expected rates. Our main results are single-letter expressions for the competitive-ratio and the regret, expressed as a max-min or min-max optimization. Several examples illustrate our results and the benefits of the competitive analysis approach to code design.