# Competitive Channel-Capacity

Michael Langberg, Oron Sabag

(April 2022)

###### Abstract

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 significant 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 main 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 adapt to the channel at use, we consider rateless
codes with a fixed number of message bits and random decoding times. We
propose two competitive metrics: the competitive ratio between the expected
rates of the two codes, and a regret defined as the difference between the
expected rates. The competitive ratio, for instance, provides a percentage
guarantee on the expected rate of the designed code when compared to the rate
of the clairvoyant code that knows the channel at hand. Our main results are
single-letter expressions for the optimal competitive-ratio and regret,
expressed as a max-min or min-max optimization. Several examples illustrate
the benefits of the competitive analysis approach to code design compared to
the compound channel.

00footnotetext: M. Langberg is with the Department of Electrical Engineering
at the University at Buffalo (State University of New York). Email:
<EMAIL_ADDRESS>O. Sabag is with the Rachel and Selim Benin School of
Computer Science and Engineering, Hebrew University of Jerusalem, Israel.
Email<EMAIL_ADDRESS>The work of M. Langberg was supported in
part by the US NSF under award CCF-1909451. A preliminary version of the
current manuscript has been accepted for presentation at ISIT 2023.

##  I Introduction

The study of communication over channels whose statistics are not fully known
can be modeled as a family of channels $\\{W_{s}\\}_{s\in\mathcal{S}}$ indexed
by a set of possible states $\mathcal{S}$. Dating back to the 1960’s, several
models for channel uncertainty have been studied: channels in which the state
is fixed over time but unknown to the encoder and decoder, i.e., the compound
channel, arbitrarily varying channels (AVC) in which the unknown state can
change arbitrarily over time (perhaps subject to constraints), finite state
channels (FSC) in which the channel state is governed by a known probability
distribution, feedback channels that enable the encoder to learn the channel
state, models in which the state is known at the encoder, and more, e.g., [1,
2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22]
and the survey in [23].

Traditionally, success criteria for communication in the presence of an
uncertain channel model require the design of a single coding scheme that
allows communication at a fixed rate no matter which channel state is
realized; this approach forces code rates to be matched to the worst-case
channel conditions, since higher rates cannot be accommodated in the worst-
case state. Variations on this strategy require reliable decoding on all but a
subset of channels, for example, with high probability over a random choice of
the state, e.g., [21]. This fixed-rate approach is complemented by a variety
of variable-rate performance criteria. Variable-rate criteria no longer
guarantee a fixed rate under (most or) all channel states; instead, they allow
the rate to vary with the channel state in operation; definitions of
reliability vary under different variable-rate models. Rateless codes,
introduced in [24, 25, 26], achieve variable-rate coding by allowing the
effective blocklength to vary with the channel state. They are useful for
analysis and code design in both the finite-length and asymptotic regimes
[27].

In this work, we study communication in the face of uncertainty through the
lens of competitive analysis. In competitive analysis, one compares the
achievable rates of solutions in which state information is not available with
those in which state information is known in advance to all parties. The
objective being the design of communications schemes that achieve rate which
is close to that achievable when the channel state is known in advance and
taken into account in code design. Common metrics in this context include the
competitive-ratio that measures the ratio between the rates achievable in the
case of limited state knowledge and that with full state knowledge, and regret
that measures the difference between the former and latter (expected) rates
described above. The design of communication schemes with a competitive ratio
$\alpha$ approaching 1 (or with regret approaching 0) guarantees that even in
the face of uncertainty, the quality of communication matches the best
possible under the given conditions. A competitive ratio $\alpha$ that is
bounded away from 1 acts as a quality measure for the communication scheme at
hand, guaranteeing that no matter what channel state is encountered during the
communication process, the achievable rate will be guaranteed to be within an
$\alpha$ multiplicative ratio of the best possible.

Competitive analysis, also referred to as “online analysis”, has seen
significant studies in the algorithmic literature in a variety of optimization
problems in which constraints appear, and decisions are made, in a causal
manner. Studied topics include for example job scheduling, self organizing
data structures, network routing, caching/paging (or more generally the
$k$-server problem), metrical task systems, resource allocation, covering and
packing problems, and more, e.g., [28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38,
39]. In the area of communication and storage systems, competitive analysis
has seen previous studies in the context of power management in energy
harvesting or, alternatively, fading Gaussian systems [40, 41, 42, 43, 44, 45,
46, 47, 48, 49, 50, 51, 52, 53, 54, 55, 56, 57], and on other topics such as
opportunistic network coding, opportunistic spectrum access in wireless
systems, wear leveling in flash memory, estimation, and control [58, 59, 60,
61].

###  I-A Our results and related work

Our work studies communication over an unknown memoryless channel taken from a
collection $\\{W_{s}\\}_{s\in\mathcal{S}}$ of channels using the framework of
rateless codes. The channel in use is unknown in advance to the encoder and
decoder. For a fixed message length $k$, our objective is to design a single
rateless code $\mathcal{C}_{k}$ that optimizes the competitive metric under
study, be it the competitive ratio ($\operatorname*{\mathbf{CR}}$) or the
regret ($\operatorname*{\mathbf{Regret}}$). Roughly speaking, a rateless code
$\mathcal{C}_{k}$ has a competitive ratio of $\alpha\leq 1$ if, for any
channel $W_{s}$ in use, successful decoding is achieved at time no more than
$1/\alpha$ times the optimal decoding time had one used a code designed with
knowledge of $W_{s}$. Stated in terms of rate, code $\mathcal{C}_{k}$ has a
competitive ratio of $\alpha\leq 1$ if, for any channel $W_{s}$ in use,
successful decoding is achieved at rate no less than $\alpha$ times the
channel capacity. Here, in the variable-rate setting, the communication rate
of a message of $k$ bits is defined to be $k$ divided by the expected decoding
time. (All definitions are given in detail in Section II.) Similarly, in the
$\operatorname*{\mathbf{Regret}}$ objective, we consider the minimization of
the difference between the described above rates.

In this work, we present single-letter expressions characterizing the optimal
achievable competitive metrics of $\operatorname*{\mathbf{CR}}$ and
$\operatorname*{\mathbf{Regret}}$. Our expressions are given in Theorems 1 and
3 of Section III and include an optimization over $|\mathcal{S}|$ input
distributions; one input distribution per channel state. Code design is
obtained through a randomized construction involving the optimizing
distributions above. Specifically, our optimal codes are not derived from a
collection of random code symbols in which each entry is identically
distributed. Rather, such constructions are shown to be in general suboptimal.
Accordingly, our code design uses a collection of $|\mathcal{S}|$ input
distributions, where one switches between distributions at predetermined times
that depend on the channel family at hand. Several examples are outlined in
Section IV.

####  I-A1 Related work

While much of the theory for rateless codes relies on fixed, known channel
statistics, most relevant to our work are a collection of results in the
unknown and time-varying channel regimes, e.g., [62, 63, 64, 65, 66, 67, 68,
69, 70, 71, 72, 73, 74, 75], in which rateless codes are used (with or without
feedback) to obtain a communication rate that varies with the channel
realization.111Several of the works above use a variant of rateless codes in
which the blocklength is fixed while the message length is unlimited. In this
setting, variability in rate is obtained by decoding a variable length prefix
of the message. In Appendix -A we compare the two rateless models showing that
the rate region of the unlimited blocklnegth variant strictly includes that of
the unlimited message-length variant; a comparison that may be of independent
interest. A common theme among the works above is the design of codes whose
rate for a given (unknown in advance) channel realization is tied to single-
letter information theoretic quantities that vary with the realization at
hand. For example, in the context of arbitrarily varying channels [8, 10], or
more generally the universal channel model [73], using feedback and common
randomness [67, 73] achieve a communication rate that may exceed the AVC
capacity and equals the capacity of the time-averaged channel.

In this work, we study variable rate communication over an unknown channel
$W_{s}$, chosen from a predefined collection of channels
$\\{W_{s}\\}_{s\in\mathcal{S}}$, without the use of feedback or common
randomness. Most relevant to the setting at hand are [62, 63] (or in a more
general setting, [74]) that study the broadcast of a common message, termed
static broadcast, using rateless codes to a collection of terminals
$\\{t_{s}\\}_{s\in\mathcal{S}}$, each connected from the transmitter by the
corresponding channel in $\\{W_{s}\\}_{s\in\mathcal{S}}$. As different
terminals can decode at different times, a rateless encoder and decoder imply
variable rate decoding even given a common message. Thus, in this setting, the
static-broadcast rate-region $\operatorname{\mathcal{R}}$ includes achievable
rate tuples $\\{R_{s}\\}_{s\in\mathcal{S}}$, i.e., rate $R_{s}$ for terminal
$t_{s}$ connected from the transmitter by $W_{s}$. In this context, an
achievable tuple $\\{R_{s}\\}_{s\in\mathcal{S}}$ in the broadcast setting
corresponds naturally to the achievable rate $R_{s}$ in point-to-point
communication over a “partially” unknown channel $W_{s}$ from
$\\{W_{s}\\}_{s\in\mathcal{S}}$, i.e., $W_{s}$ is unknown to the encoder but
known to the decoder. In [62, 63], the rate-region
$\operatorname{\mathcal{R}}$ is described using a variant of an $n$-letter
(for unbounded block length $n$) information-theoretic expression (the example
of $|\mathcal{S}|=2$ is further discussed in [62, 63] to obtain a single
letter characterization of $\operatorname{\mathcal{R}}$ in that case). The
rate-region $\operatorname{\mathcal{R}}$ can be used to derive competitive
metrics; here, for the setting of state-information known only to the decoder.
For example, roughly speaking, denoting the capacity of $W_{s}$ by $C_{s}$,
the corresponding competitive ratio is
$\max_{\\{R_{s}\\}_{s\in\mathcal{S}}\in\operatorname{\mathcal{R}}}\min_{s\in\mathcal{S}}{R_{s}}/{C_{s}}$.

Beyond the fact that, in our study, channel state is unknown to both the
encoder and decoder,222Later we show in our achievability that decoder state
knowledge does not impact the achievable rates. the work at hand differs from
that of [62, 63] (and the additional works mentioned above) in its explicit
focus on a single-letter characterization of the competitive metrics of the
channel family $\\{W_{s}\\}_{s\in\mathcal{S}}$. As discussed above, we present
$\operatorname*{\mathbf{CR}}$ and $\operatorname*{\mathbf{Regret}}$ as an
optimization over $|\mathcal{S}|$ distributions, one corresponding to each
channel in $\\{W_{s}\\}_{s\in\mathcal{S}}$. Our definitions, given in Section
II, follow those common in the finite-blocklength literature, e.g., [27], and
thus our definition of rate slightly differs from that in [62, 63] in the
sense that we determine the achievable rate using an expected decoding time.
Our results hold for the rate model of [62, 63] as well. It is interesting to
note that [62] also studies the family $\\{W_{s}\\}_{s\in\mathcal{S}}$ of all
binary input channels, and shows that codes designed using the uniform
distribution achieve a (surprisingly high, albeit potentially suboptimal)
competitive ratio of $0.94$. However, this phenomenon does not hold for
general inputs, as we later present, in Section IV, example channels (with
$|\operatorname{\mathcal{X}}|=4$) for which a code randomly designed by any
single distribution (including the uniform one) has competitive ratio at most
$0.5$ whereas the optimal competitive ratio is approximately $1$.

##  II Model: Competitive analysis for communication

We consider a family of memoryless channels $W_{s}(y|x)$ that are
parameterized with state $s\in[1:|\mathcal{S}|]$. The channel to be used among
the $|\mathcal{S}|$ channels is unknown to the encoder and the decoder so that
the code design is oblivious to the true channel in the given family. At the
the high-level, our objective is to design codes that _perform well_ for all
possible channels in a competitive manner.

The alphabets of the channel input, output and the state are assumed to be
finite, i.e.,
$|\operatorname{\mathcal{X}}|,|\operatorname{\mathcal{Y}}|,|\mathcal{S}|<\infty$.
The message $M$ is uniformly distributed over
$\mathcal{M}\triangleq[1:2^{k}]$. Note that message size is not parameterized
with a blocklength or rate. Instead, we consider rateless communication where
the fixed-size message $M$ should be decoded with the least number of channel
uses. That is, the decoder observes a stream of channel outputs and decides at
each time if it wants to proceed with the communication or to abort
communication and decode the message $M$.

###  II-A Code

For a fixed number of bits, $k$, a rateless code
$\mathcal{C}_{k}\triangleq(E,\\{D_{i}\\},\\{H_{i}\\})$ is defined by three
mappings. The first is a sequence of decoder decisions functions

$\displaystyle H_{i}:\mathcal{Y}^{i}\to\\{0,1\\},\ \ i=1,2,\dots$ (1)

If the decoder decides to decode at time $i$, $H_{i}(Y^{i})=1$, the message is
decoded with the mapping

$\displaystyle D_{i}:\mathcal{Y}^{i}\to\mathcal{M}.$ (2)

In all other times (i.e., $H_{i}=0$), we can arbitrarily define
$D_{i}(Y^{i})=1$. The encoder is defined by the mapping

$\displaystyle E:\mathcal{M}\to\mathcal{X}^{\infty}.$ (3)

The stopping time is defined as

$\displaystyle\tau_{k}=\min_{i}\\{i:H_{i}(Y^{i})=1\\}.$ (4)

For a fixed code, probability of error for a channel $s\in\mathcal{S}$ is

$\displaystyle P_{e}(s)$ $\displaystyle\triangleq\Pr(M\neq
D_{\tau_{k}}(Y^{\tau_{k}})|S=s),$ (5)

and $P_{e}=\max_{s}P_{e}(s)$ denotes the maximal error among all channels.

The expected decoding time for channel $s\in\mathcal{S}$ is denoted by

$\displaystyle\tau_{s}(k)$
$\displaystyle=\operatorname{\mathbb{E}}[\tau_{k}|S=s].$ (6)

To define the competitive metrics, as our superior yet impractical baseline,
we choose codes where the encoder and the decoder mappings have access to the
channel in use. We denote by $\mathcal{C}^{\ast}_{k}$ the set of these
clairvoyant codes, and their corresponding expected stopping time as
$\tau_{s}^{\ast}(k)=\mathbb{E}_{s}[\tau_{k}^{\ast}]$.

We can now formally define the competitive ratio that measures the (expected)
effective rate of the suggested codes in term of the optimal (expected)
effective rate of the clairvoyant code. For rateless codes, the expected
effective rate is $\frac{k}{\tau_{s}(k)}$.

###### Definition 1

The competitive ratio for a message with $k$ bits and error probability
$\epsilon$ is defined as

$\displaystyle\operatorname*{\mathbf{CR}}(k,\epsilon)$
$\displaystyle=\sup_{\mathcal{C}_{k}:P_{e}\leq\epsilon}\min_{s\in\mathcal{S}}\left(\frac{\frac{k}{\tau_{s}(k)}}{\frac{k}{\inf\limits_{\mathcal{C}^{*}_{k}:P_{e}\leq\epsilon}\tau^{\ast}_{s}(k)}}\right)=\sup_{\mathcal{C}_{k}:P_{e}\leq\epsilon}\min_{s\in\mathcal{S}}\left(\frac{\inf\limits_{\mathcal{C}^{*}_{k}:P_{e}\leq\epsilon}\tau^{\ast}_{s}(k)}{\tau_{s}(k)}\right).$
(7)

We note that the competitive ratio is always smaller than $1$ since the
clairvoyant code $\mathcal{C}_{k}^{\ast}$ can always achieve the performance
of the code $\mathcal{C}_{k}$. Thus, the competitive ratio serves as a
percentage measure to indicate how close the performance is to the optimal
one. The universality of the code with respect to the channel in use is
reflected in the inner minimization over the states $\mathcal{S}$. We also
note that $\operatorname*{\mathbf{CR}}$ can be viewed both as a ratio of
expected rates and a ratio of expected decoding times. Indeed, the rate and
the (normalized) decoding time are reciprocal. We use both perspectives
interchangeably in this work.

The competitive ratio guarantees are multiplicative. Alternatively, one may be
interested in an additive performance guarantee such as delay or rate when
compared to the optimal code.

###### Definition 2

The regret for a message with $k$ bits and a probability error $\epsilon$ is
defined as

$\displaystyle\operatorname*{\mathbf{Regret}}(k,\epsilon)$
$\displaystyle=\inf_{\mathcal{C}_{k}:P_{e}\leq\epsilon}\max_{s\in\mathcal{S}}\left(\frac{k}{\inf\limits_{\mathcal{C}^{*}_{k}:P_{e}\leq\epsilon}\tau^{\ast}_{s}(k)}-\frac{k}{\tau_{s}(k)}\right).$
(8)

Note that, in contrast to $\operatorname*{\mathbf{CR}}(\epsilon,k)$ where we
maximize the metric over codes, here we seek codes that minimize the rates
difference.

In this paper, our focus is on the regime of vanishing probability of error
$\epsilon$ as $k\to\infty$. This is formalized in the following definition.

###### Definition 3

A family of channels $\mathcal{W}$ is $\alpha$-competitive if there exists a
sequence $\epsilon_{k}\to 0$ such that

$\displaystyle\limsup_{k\to\infty}\operatorname*{\mathbf{CR}}(k,\epsilon_{k})\geq\alpha.$
(9)

The supremum over all $\alpha$ that are competitive is referred to as the
optimal competitive ratio, or alternatively the “competitive capacity”, and is
denoted by $\operatorname*{\mathbf{CR}}$.

Similarly, we can define the optimal regret.

###### Definition 4

A family of channels $\operatorname{\mathcal{W}}$ achieves a
$\rho-\operatorname*{\mathbf{Regret}}$ if there exists a sequence
$\epsilon_{k}\to 0$ such that

$\displaystyle\liminf_{k\to\infty}\operatorname*{\mathbf{Regret}}(k,\epsilon_{k})\leq\rho.$
(10)

The infimum over all such $\rho$ is the _optimal regret_ and is denoted by
$\operatorname*{\mathbf{Regret}}$.

##  III Main results

In this section, we present a closed-form, single-letter formula for the
optimal competitive ratio (and accordingly for regret). To build intuition, we
start with a rough description of a simple lower bound for the competitive
ratio that corresponds to codes designed according to a single distribution.

###  III-A Simple lower bound

Let $p\in\mathcal{P}(\mathcal{X})$ be a distribution over channel inputs.
Consider a code designed randomly according to the distribution $p$. Let $X$
be a random variable with distribution $p$. The expected rate for channel
$W_{s}$ with such codes is roughly $I_{s}(X;Y)$. Thus, loosely speaking, we
can achieve

$\displaystyle\operatorname*{\mathbf{CR}}\geq\max_{p}\min_{s\in{\mathcal{S}}}\frac{I_{s}(X;Y)}{C_{s}},$
(11)

where $C_{s}=\max_{p(x)}I_{s}(X;Y)$ is the channel capacity when the encoder
and the decoder know $s$. As it turns out, this lower bound is not optimal.

We can think of the competitive setting as a broadcast channel with a single
message (multicast), where the $s$’th decoder observes its channel output
generated by $P_{s}(y|x)$. While this comparison to the broadcast channel is
not completely accurate due to decoder state information as discussed
previously, we add the discussion that follows to build intuition. Consider a
special case with two decoders. If we use a code governed by a single input
distribution $p$, then one of the decoders, e.g., the first, will likely be
able to decode the message prior to the other decoder. In this case, to
optimize the remaining time until the second decoder decodes, one can improve
on code design by modifying the input distribution for the remaining code
entries to that optimizing the second decoder’s channel.333Note that the
encoder is not aware of the (random) time index in which the first decoder
decodes the message, but our achievability shows that it is sufficient to
switch the input distribution at roughly the expected decoding time. In the
next section, we formalize these ideas with a characterization to the
competitive capacity which optimizes over $|\mathcal{S}|$-distributions.

###  III-B The competitive capacity $\operatorname*{\mathbf{CR}}$ and optimal
$\operatorname*{\mathbf{Regret}}$.

Let ${\bf p}=p_{1},\dots,p_{|\mathcal{S}|}$ be $|\mathcal{S}|$ channel input
distributions over $\mathcal{X}$, and let $X_{j}$ be the corresponding random
variable with distribution $p_{j}$. In our definitions below, we also use an
ordering ${\bf s}=(s_{1},\dots,s_{|\mathcal{S}|})$ of $\mathcal{S}$ which
specifies the order in which decoding occurs. Our first definition of
$\operatorname*{\mathbf{CR}}$ consists of an optimization over both ${\bf p}$
and ${\bf s}$. We later show that the optimal ordering ${\bf s}$ can be
determined by ${\bf p}$, giving us an equivalent competitive capacity
expression (15) as an optimization over ${\bf p}$ only.

In what follows, given ${\bf p}$ and ${\bf s}$, the variables
$T_{i}^{\operatorname*{{(\bf p,\bf s)}}}$ are defined inductively and
correspond to the (normalized) decoding time of a receiver viewing the output
of the $i$’th channel in $\mathcal{S}$ according to the order ${\bf s}$. Let
$T_{0}^{\operatorname*{{(\bf p,\bf s)}}}=0$. For general $i$, let
$T_{i}^{\operatorname*{{(\bf p,\bf s)}}}=\Delta_{i}\operatorname*{{(\bf p,\bf
s)}}+T_{i-1}^{\operatorname*{{(\bf p,\bf s)}}}$ where the decoding-time
increments $\Delta_{i}$ are defined by

$\displaystyle\Delta_{i}\operatorname*{{(\bf p,\bf
s)}}\triangleq\frac{\\{1-\sum_{j=1}^{i-1}\Delta_{j}\operatorname*{{(\bf p,\bf
s)}}I_{s_{i}}(X_{j};Y)\\}_{+}}{I_{s_{i}}(X_{i};Y)},$ (12)

The expression above corresponds to a code designed using the input
distributions ${\bf p}$, where distribution $p_{1}$ is used for the first
$k\Delta_{1}$ coordinates, distribution $p_{2}$ is used for the next
$k\Delta_{2}$ coordinates, and so on. Using such a code, a receiver of channel
$s_{i}$ will be able to decode once the corresponding cumulative mutual
information $\sum_{j}k\Delta_{j}\operatorname*{{(\bf p,\bf
s)}}I_{s_{i}}(X_{j};Y)$ exceeds $k$. Accordingly, $T_{1}^{\operatorname*{{(\bf
p,\bf s)}}}=\Delta_{1}$ is set such that $\Delta_{1}\operatorname*{{(\bf p,\bf
s)}}=\frac{1}{I_{s_{1}}(X_{1};Y)}$; $T_{2}^{\operatorname*{{(\bf p,\bf
s)}}}=\Delta_{1}+\Delta_{2}$ is set such that $\Delta_{2}$ is the residual
normalized decoding time for $s_{2}$ (normalized by $k$ and the rate
$I_{2}(X_{2};Y)$ experienced by channel $s_{2}$ with input distribution
$p_{2}$) and corresponds to the term $1-\Delta_{1}\operatorname*{{(\bf p,\bf
s)}}I_{s_{2}}(X_{1};Y)$; and in general, $T_{i}^{\operatorname*{{(\bf p,\bf
s)}}}=\sum_{j=1}^{i}\Delta_{j}\operatorname*{{(\bf p,\bf s)}}$ where
$\Delta_{i}$ is the residual decoding time for a receiver of channel $s_{i}$
(normalized by $k$ and $I_{s_{i}}(X_{s_{i}};Y)$) and corresponds to the term
$1-\sum_{j=1}^{i-1}\Delta_{j}\operatorname*{{(\bf p,\bf
s)}}I_{s_{i}}(X_{j};Y)$. The following result formalizes the competitive
capacity.

######  Theorem 1 (Competitive Channel Capacity)

The competitive capacity is given by

$\displaystyle\operatorname*{\mathbf{CR}}$ $\displaystyle=\max_{\bf p,\bf
s}\min_{i\in[|\mathcal{S}|]}\frac{T^{\ast}_{s_{i}}}{\sum_{j=1}^{i}\Delta_{j}\operatorname*{{(\bf
p,\bf s)}}}=\max_{\bf p,\bf
s}\min_{i\in[|\mathcal{S}|]}\frac{T^{\ast}_{s_{i}}}{T_{i}^{\operatorname*{{(\bf
p,\bf s)}}}},$ (13)

where $T^{\ast}_{s}=\inf_{p_{X}}\frac{1}{I_{s}(X;Y)}=\frac{1}{C_{s}}$.

A trivial special case is when there is a single channel, i.e.,
$|\mathcal{S}|=1$ where $\operatorname*{\mathbf{CR}}=1$ and $p_{1}$ is the
capacity-achieving distribution. In the general case,
$\operatorname*{\mathbf{CR}}$ is defined as an optimization over both ${\bf
p}$ and ${\bf s}$. In what follows, we show that the optimization can be
simplified with a _greedy decoding order_.

For a fixed ${\bf p}=p_{1},\dots,p_{|\mathcal{S}|}$, we define the greedy
decoding order corresponding to ${\bf p}$ in which
$s_{1}^{\operatorname*{{(\bf p)}}}$ is set to be the first channel for which a
receiver is able to decode using a code governed by the distribution $p_{1}$.
Denote the first decoding time as $k\overline{\Delta}_{1}(\bf p)$. Then,
switching to the distribution $p_{2}$, state $s_{2}^{\operatorname*{{(\bf
p)}}}$ is set to be the second channel for which a receiver can decode (using
code design that starts with $p_{1}$ for $k\overline{\Delta}_{1}({\bf p})$
steps and then switches to $p_{2}$). Denote the second decoding time as
$k(\overline{\Delta}_{1}({\bf p})+\overline{\Delta}_{2}({\bf p}))$. In each
phase, we switch to the next $p_{i}$ and set $s_{i}^{\operatorname*{{(\bf
p)}}}$ to be the next channel to allow decoding. In what follows, we show that
this natural order ${\bf s}^{({\bf p})}=s_{1}^{\operatorname*{{(\bf
p)}}},\dots,s_{|\mathcal{S}|}^{\operatorname*{{(\bf p)}}}$ is indeed optimal.
Namely, given ${\bf p}$, the variables $T_{i}^{\operatorname*{{(\bf
p)}}}=\sum_{j=1}^{i}\overline{\Delta}_{1}({\bf p})$ are defined inductively
and correspond to the (normalized) decoding time of a receiver viewing the
output of the $i$’th channel according to the greedy ordering. Let
$T_{0}^{\operatorname*{{(\bf p)}}}=0$. For any $i$, define (inductively)
$T_{i}^{\operatorname*{{(\bf p)}}}={\overline{\Delta}}_{i}(\operatorname*{\bf
p})+T_{i-1}^{\operatorname*{{(\bf p)}}}$, where the decoding-time increments,
$\overline{\Delta}_{i}\operatorname*{{(\bf p)}}=T_{i}^{\operatorname*{{(\bf
p)}}}-T_{i-1}^{\operatorname*{{(\bf p)}}}$, are defined as

$\displaystyle\overline{\Delta}_{i}(\operatorname*{\bf p})\triangleq
T_{i}^{\operatorname*{{(\bf p)}}}-T_{i-1}^{\operatorname*{{(\bf
p)}}}=\min_{s\in\mathcal{S}\setminus\\{s^{\operatorname*{{(\bf
p)}}}_{1},\dots,s^{\operatorname*{{(\bf
p)}}}_{i-1}\\}}\frac{1-\sum_{j=1}^{i-1}\overline{\Delta}_{j}\operatorname*{{(\bf
p)}}I_{s}(X_{j};Y)}{I_{s}(X_{i};Y)},$ (14)

and $s_{i}^{\operatorname*{{(\bf p)}}}$ is defined (recursively) as the
$\arg\min$ of (14) (ties are broken arbitrarily). Intuitively, the numerator
in the right-hand side of (14) can be thought of as the remaining information
to be decoded, and the denominator corresponds to the information rate. Notice
that, using the notation above and that presented before Theorem 1, it holds
that $\overline{\Delta}_{i}(\operatorname*{\bf
p})=\Delta_{i}(\operatorname*{\bf p},\operatorname*{\bf
s}^{(\operatorname*{\bf p})})$ and $T_{i}^{\operatorname*{{(\bf
p)}}}=T_{i}^{(\operatorname*{\bf p},\operatorname*{\bf s}^{(\operatorname*{\bf
p})})}$.

######  Corollary 2 (Competitive Channel Capacity, revisited)

The competitive capacity is given by

$\displaystyle\operatorname*{\mathbf{CR}}$ $\displaystyle=\max_{\bf
p}\min_{i\in[|\mathcal{S}|]}\frac{T^{\ast}_{s^{(\operatorname*{\bf
p})}_{i}}}{\sum_{j=1}^{i}\Delta_{j}(\operatorname*{\bf p},\operatorname*{\bf
s}^{(\operatorname*{\bf p})})}=\max_{\bf
p}\min_{i\in[|\mathcal{S}|]}\frac{T^{\ast}_{s^{(\operatorname*{\bf
p})}_{i}}}{T_{i}^{(\operatorname*{\bf p})}},$ (15)

where $T^{\ast}_{s}=\inf_{p_{X}}\frac{1}{I_{s}(X;Y)}=\frac{1}{C_{s}}$.

Corollary 2 is proven in Appendix -B. Similar to the
$\operatorname*{\mathbf{CR}}$ measure in Corollary 2, we obtain a single-
letter expression for $\operatorname*{\mathbf{Regret}}$.

######  Theorem 3 (Optimal regret)

The optimal regret is given by

$\displaystyle\operatorname*{\mathbf{Regret}}$ $\displaystyle=\min_{\bf
p}\max_{i\in[|\mathcal{S}|]}\left(\frac{1}{T^{\ast}_{s_{i}^{\operatorname*{{(\bf
p)}}}}}-\frac{1}{\sum_{j=1}^{i}\Delta_{j}(\operatorname*{\bf
p},\operatorname*{\bf s}^{(\operatorname*{\bf p})})}\right)=\min_{\bf
p}\max_{i\in[|\mathcal{S}|]}\left(\frac{1}{T^{\ast}_{s_{i}^{\operatorname*{{(\bf
p)}}}}}-\frac{1}{T_{j}^{(\operatorname*{\bf p})}}\right),$ (16)

where $T^{\ast}_{s}=\inf_{p_{X}}\frac{1}{I_{s}(X;Y)}=\frac{1}{C_{s}}$.

The achievability and converse proofs for Theorem 3 closely follow the lines
of proof given later for Theorem 1. Thus, in the proof of Theorem 1, in
Sections V and VI, we briefly mention the modifications needed to prove
Theorem 3. The optimal competitive ratio and regret expressions are different
in the nature of their guarantees, but their solutions involve the same time
increments. Nevertheless, the sequences of input distributions that attain the
optimum in (13) and (16) can differ. Below, we show connections between the
optimizing distributions for $\operatorname*{\mathbf{CR}}$ and
$\operatorname*{\mathbf{Regret}}$ in the asymptotic regime.

###  III-C Connecting $\operatorname*{\mathbf{CR}}$ and
$\operatorname*{\mathbf{Regret}}$

To connect the $\operatorname*{\mathbf{CR}}$ and
$\operatorname*{\mathbf{Regret}}$ metrics, we first introduce corresponding
weighted variants. In particular, for ${\bf
w}=w_{1},\dots,w_{|S|}\in(0,\infty)^{|S|}$, define the weighted version of
$\operatorname*{\mathbf{CR}}$ as

$\displaystyle\operatorname*{\mathbf{CR}}(k,\epsilon,\bf{w})$
$\displaystyle=\sup_{\mathcal{C}_{k}:P_{e}\leq\epsilon}\min_{s\in\mathcal{S}}\
\
w_{s}\cdot\left(\frac{\inf\limits_{\mathcal{C}^{*}_{k}:P_{e}\leq\epsilon}\tau^{\ast}_{s}(k)}{\tau_{s}(k)}\right).$
(17)

For ${\bf r}=r_{1},\dots,r_{|S|}\in(0,\infty)^{|S|}$, define the weighted
version of $\operatorname*{\mathbf{Regret}}$ as

$\displaystyle\operatorname*{\mathbf{Regret}}(k,\epsilon,{\bf r})$
$\displaystyle=\inf_{\mathcal{C}_{k}:P_{e}\leq\epsilon}\max_{s\in\mathcal{S}}\
\
r_{s}\cdot\left(\frac{k}{\inf\limits_{\mathcal{C}^{*}_{k}:P_{e}\leq\epsilon}\tau^{\ast}_{s}(k)}-\frac{k}{\tau_{s}(k)}\right).$
(18)

The asymptotic, weighted, competitive-ratio and regret are denoted by
$\operatorname*{\mathbf{CR}}(\bf{w})$ and
$\operatorname*{\mathbf{Regret}}({\bf r})$ respectively and are defined
following the lines of (9) and (10). Similar to the proof of Theorem 1, one
can show that

$\displaystyle\operatorname*{\mathbf{CR}}({\bf{w}})=\max_{\operatorname*{{(\bf
p,\bf s)}}}\min_{i\in[|\mathcal{S}|]}\ \
w_{s_{i}}\frac{T^{*}_{s_{i}}}{\sum_{j=1}^{i}\Delta_{j}\operatorname*{{(\bf
p,\bf s)}}},$ (19)

and

$\displaystyle\operatorname*{\mathbf{Regret}}({\bf
r})=\min_{\operatorname*{{(\bf p,\bf s)}}}\max_{i\in[|\mathcal{S}|]}\ \
r_{s_{i}}\left(\frac{1}{T^{*}_{s_{i}}}-\frac{1}{\sum_{j=1}^{i}\Delta_{j}\operatorname*{{(\bf
p,\bf s)}}}\right)$ (20)

We proceed to show that the competitive ratio and the regret problems are
equivalent when considering their generalized weighted versions. Namely, we
show that the ability to find the optimal $\operatorname*{{(\bf p,\bf s)}}$ in
one implies the same for the other. Towards that end, denote by ${\tt
Regret}_{\bf r}$ and ${\tt CR}_{\bf w}$ the arguments that achieve the optimum
in (19) and (20), respectively.

###### Proposition 1

For every ${\bf w}$, there exists an ${\bf r}$ such that ${\tt Regret}_{\bf
r}\subseteq{\tt CR}_{\bf w}$. Moreover, one can find ${\bf r}$ by solving
(multiple instances) of (20). In the other direction, for every ${\bf r}$,
there exists a ${\bf w}$ such that ${\tt CR}_{\bf w}\subseteq{\tt Regret}_{\bf
r}$ and it can be found by solving (multiple instances) of (19).

Proposition 1 suggests that one can solve a weighted regret problem using a
solution to the weighted competitive ratio and vice versa. Proof of the
proposition, i.e., the reductive analysis, is given in Appendix -C.

##  IV Examples

In this section, we study several examples to illustrate different aspects of
the competitive approach of our problem formulation and its solution. Consider
a family of channels $W_{s}(y|x)$ with $|\mathcal{S}|=2$. In this case, the
competitive ratio in Theorem 1 can be written explicitly. A similar analysis
(in a different context) appears in [62, 63]. Fix a distribution $p_{1}$ on
$\mathcal{X}$, and let $s_{1}$ be such that $I_{s_{1}}(X;Y)\geq
I_{s_{2}}(X;Y)$. Here $X$ is distributed according to $p_{1}$. Let $p_{2}$ be
the capacity-achieving distribution of channel $s_{2}$. For
$\operatorname*{\bf p}=(p_{1},p_{2})$ and $\operatorname*{\bf
s}=(s_{1},s_{2})$, using (12), the first decoding increment corresponding to
$s_{1}$ is $\Delta_{1}=\frac{1}{I_{s_{1}}(X;Y)}$. This implies a competitive
ratio for channel $s_{1}$ of $\frac{I_{s_{1}}(X;Y)}{C_{s_{1}}}$. For $s_{2}$,
roughly speaking, our analysis shows that the fraction of message bits decoded
until time $k\Delta_{1}$ is $\Delta_{1}I_{s_{2}}(X;Y)$. Thus, for the
remaining $1-\Delta_{1}I_{s_{2}}(X;Y)$ fraction, the corresponding time
increment is set to $\Delta_{2}=\frac{1-\Delta_{1}I_{s_{2}}(X;Y)}{C_{s_{2}}}$.
The overall normalized decoding time for channel $s_{2}$ is thus

$\displaystyle\Delta_{1}+\Delta_{2}$
$\displaystyle=\frac{1}{I_{s_{1}}(X;Y)}+\frac{1-\frac{1}{I_{s_{1}}(X;Y)}I_{s_{2}}(X;Y)}{C_{s_{2}}}.$
(21)

We can simplify the induced competitive ratio for $s_{2}$ as
$\frac{I_{s_{1}}(X;Y)}{C_{s_{2}}+I_{s_{1}}(X;Y)-I_{s_{2}}(X;Y)}$. To conclude,
denoting $p_{1}$ by $p$ below, the competitive ratio is

$\displaystyle\operatorname*{\mathbf{CR}}$
$\displaystyle=\max_{p(x)}\min_{s_{1}(p)}\left\\{\frac{I_{s_{1}}(X;Y)}{C_{s_{1}}},\frac{I_{s_{1}}(X;Y)}{C_{s_{2}}+I_{s_{1}}(X;Y)-I_{s_{2}}(X;Y)}\right\\},$
(22)

where $s_{1}(p)$ is the channel $s_{1}\in\operatorname{\mathcal{S}}$ for which
$I_{s_{1}}(X;Y)\geq I_{s_{2}}(X;Y)$ when $X$ has distribution $p$. For the
regret, (21) implies that in families of two channels,

$\displaystyle\operatorname*{\mathbf{Regret}}$
$\displaystyle=\min_{p(x)}\max_{s_{1}(p)}\left\\{C_{s_{1}}-I_{s_{1}}(X;Y),C_{s_{2}}-C_{s_{2}}\frac{I_{s_{1}}(X;Y)}{C_{s_{2}}+I_{s_{1}}(X;Y)-I_{s_{2}}(X;Y)}\right\\}.$
(23)

Figure 1: The Z-S channel

A few concrete examples of case studies follow.

$\bullet$ The Z-S channel family: Consider a family of channels consisting of
the Z- and the S- channels with transition parameters $z$ and $s$,
respectively (see Fig. 1). In Fig. 2, we plot in $(a)$ the lower bound on the
competitive ratio based on a single (optimized) input distribution in (11),
and in (b) the optimal competitive ratio. In both plots, the competitive ratio
is in the range $[0.94,1]$. This fits the interesting result that, for binary-
input channels, a uniform input distribution achieves no less than a $94\%$ of
the capacity [62]. Our objective here is to illustrate the potential
improvement of the optimal competitive ratio over the single input
distribution lower bound in (11). This can be observed by comparing the blue
and the yellow regions in Fig. 2. Next, we study channels with non-binary
inputs where the competitive ratio obtained by single-distribution codes can
be significantly lower than $\operatorname*{\mathbf{CR}}$.

Figure 2: The competitive ratio for the Z-S channel family. $(a)$ The lower
bound induced from a single distribution. $(b)$ The optimal competitive ratio
$\operatorname*{\mathbf{CR}}$. It can be noted that there is an improvement
for most channel parameters.

$\bullet$ A channel family corresponding to a bilingual speaker: The following
example represents a scenario where a bilingual speaker aims to communicate
with two receivers that are only able to understand one of the spoken
languages [62]. Each receiver is modeled as a different channel. We illustrate
that gains can be made due to the competitive approach with respect to the
compound capacity.

Let $W_{i}$ be the number of symbols in each language. The channel inputs
alphabet $\mathcal{X}=[1:W_{1}+W_{2}]$ and $|\mathcal{Y}_{i}|=[1:W_{1}+W_{2}]$
for $i=1,2$. The first channel conveys noiselessly the first $W_{1}$ symbols:

$\displaystyle Y_{1}=\begin{cases}X&\text{if}\ X\in\\{1,\dots,W_{1}\\}\\\
Unif([W_{1}+1:W_{1}+W_{2}])&\text{else},\end{cases}$ (24)

while the second channels conveys the last $W_{2}$ symbols

$\displaystyle Y_{2}=\begin{cases}X&\text{if}\
X\in\\{W_{1}+1,\dots,W_{1}+W_{2}\\}\\\ Unif([1:W_{1}])&\text{else}\end{cases}$
(25)

The capacity of the channels are $C_{i}=\log_{2}(W_{i}+1)$ for $i=1,2$
attained, e.g., with a uniform distribution over the clean symbols and one of
the noisy symbols.

For $p\in[0,1]$ we consider the distribution on $\operatorname{\mathcal{X}}$
that allocates probability $p/|W_{1}|$ to elements of $W_{1}$ and
$(1-p)/|W_{2}|$ to elements of $W_{2}$. It suffices to study such
distributions as they dominate (in capacity for both the first and second
channel) other distributions over $\operatorname{\mathcal{X}}$. The achievable
rates are $R_{1}(p)=H(p)+p\log_{2}(W_{1})$ for the first channel and
$R_{2}(p)=H(p)+(1-p)\log_{2}(W_{2})$ for the second. For illustration
purposes, we fix $W_{1}=31$ and $W_{2}=2$ that imply the corresponding channel
capacities $C_{1}=5$ and $C_{2}=1.58$.

In Fig. 3, we plot in (a) the achievable rates $R_{i}(p)$, in (b) the
achievable rates normalized by their corresponding capacities, and in (c) the
competitive ratio (22) obtained on each channel as a function of $p$. In all
plots, red curves correspond to the first channel while blue curves correspond
to the second channel.

In Fig. 3 (a), the max-min point corresponds to the compound channel capacity.
In particular, the capacity is $R\sim 1.5$ (achieved with $p\sim 0.83$). In
Fig. 3 (b), the achievable rates are normalized by their corresponding
capacity. The max-min point here corresponds to the (single distribution)
lower bound on the competitive ratio. We note that Fig. 3 (b) implies
$\operatorname*{\mathbf{CR}}\geq 0.82$, achievable with $p=0.36$. That is, the
max-min point guarantees that no matter what the channel is, a code generated
according to $p=0.36$ achieves at least $82\%$ of the capacity for both
channels. If the optimal parameter of the compound channel $p=0.83$ was to be
used, we would achieve $94\%$ out of the capacity in channel $2$ (blue curve),
but this would come at the cost of achieving only $30\%$ of the first channel
(red curve).

Lastly, in Fig. 3 (c), we illustrate the optimal competitive ratio. The max-
min point corresponds to the competitive ratio. For $p\leq 0.83$, we have
$R_{1}(p)\geq R_{2}(p)$ (see Fig. 3 (a)) and thus the first (red) channel
decodes first. Thus, for $p\leq 0.83$, the red curve is the same as in Fig. 3
(b) . After the first (red) channel decodes, the capacity-achieving
distribution of the second (blue) channel is used and we observe the
improvement in its normalized decoding time when compared to Fig. 3 (b). The
opposite occurs for $p>0.83$. For optimal $p$, such a code achieves $90\%$ of
the capacity for both channels, improving on that obtained using single-
distribution codes. This gap can be further enlarged by increasing
$W_{2}/W_{1}$. At an extreme, when both $W_{1}$ and $W_{2}/W_{1}$ tend to
infinity, the competitive ratio corresponding to single-distribution codes
approaches $0.5$ whereas that corresponding to a code designed using two
distributions approaches 1. Specifically, in this setting, $R_{1}(p)\simeq
p\log{W_{1}}\simeq pC_{1}$ and
$R_{2}(p)\simeq(1-p)\log{W_{2}}\simeq(1-p)C_{2}$. Thus, for any single-
distribution code governed by $p$, we obtain a competitive ratio of
approximately $\min\\{p,1-p\\}$, while the optimal competitive ratio
approaches 1 using the analysis in (22). An alternative example (with
alphabets of bounded size $4$) for which the competitive ratio of single
distribution codes is 0.5 while the optimal one approaches $1$ is given next.

Figure 3: Illustration of the different design approaches for the Bilingual
speaker example in (24). In (a), the achievable rates of the two channels are
plotted as a function of the channel input parameter $p$. The max-min point
corresponds to the compound channel capacity. In (b), the achievable rates
normalized by their corresponding capacity show that the highest competitive
ratio that can be achieved using a single input distribution rateless code is
$82\%$. As a comparison, if we consider the optimal code for the compound
setting with $p\sim 0.83$, we obtain $94\%$ of the second (blue) channel
capacity, but only $30\%$ of the first (red) channel’s capacity. In $(c)$, our
optimal competitive ratio is illustrated by looking at the normalized decoding
times using two input distributions. In particular, if we use max-min point of
this plot ($p\sim 0.25$) until the first channel decodes and then switch to
the capacity-achieving distribution of the blue channel, the competitive ratio
is significantly improved to $90\%$ and is the highest one can obtain.

$\bullet$ Modified bilingual speaker with erasures: In this example, we
consider a modified version of the previous example. The objective is to
demonstrate a setting with small input and output alphabets for which codes
designed with a single input distribution attain a low competitive ratio while
those designed with multiple (two) input distributions attain a competitive
ratio that is arbitrarily close to $1$. There are two modifications from the
previous example: if a channel input is used over the _wrong channel_ , then
channel output is uniform over the entire output alphabet. The second
modification is that the output of the first channel is erased with
probability $1-\epsilon$. The competitive ratio is invariant to the number of
symbols, and we choose $W_{1}=W_{2}=2$ for simplicity. Thus, the input
alphabet is $\mathcal{X}=\\{1,2,3,4\\}$, the first channel’s output alphabet
is $\mathcal{Y}_{1}=\\{1,2,3,4,?\\}$, and that of the second channel is
$\mathcal{Y}_{2}=\\{1,2,3,4\\}$. The first channel from $X$ to $Y_{1}$ is
represented as a concatenation of the channel

$\displaystyle\tilde{Y}_{1}=\begin{cases}X&\text{if}\ X\in\\{1,2\\}\\\
Unif([1:4])&\text{otherwise},\end{cases}$ (26)

and an erasure channel with erasure probability $1-\epsilon$. The output of
the erasure channel is denoted by $Y_{1}$. The second channel in the family is

$\displaystyle Y_{2}=\begin{cases}X&\text{if}\ X\in\\{3,4\\}\\\
Unif([1:4])&\text{else}\end{cases}$ (27)

The capacity of the first channel is $C(s_{1})=\epsilon$ and that of the
second channel is $C(s_{2})=1$.

By the problem symmetry, it is sufficient to compute the competitive ratio
with uniform distribution over the first two inputs and the last two inputs.
That is, $P(X\in\\{1,2\\})=\frac{p}{2}$ and $P(X\in\\{3,4\\})=\frac{1-p}{2}$.
The lower bound on the competitive ratio using a single input distribution is

$\displaystyle\operatorname*{\mathbf{CR}}$
$\displaystyle\geq\max_{p}\min\\{p,1-p\\}\operatorname*{}$
$\displaystyle=0.5.$ (28)

The optimal competitive ratio is computed next. For the case
$p\geq\frac{1}{1+\epsilon}$, the channel $X\to Y_{1}$ decodes first and the
resulting competitive ratio by (22) is

$\displaystyle\max_{p\geq\frac{1}{1+\epsilon}}\min\left\\{p,\frac{\epsilon}{1+\epsilon}\right\\}$
$\displaystyle=\frac{\epsilon}{1+\epsilon}.$ (29)

In the other case, $p\leq\frac{1}{1+\epsilon}$, the second channel decodes
first, and we have

$\displaystyle\operatorname*{\mathbf{CR}}$
$\displaystyle=\max_{p\leq\frac{1}{1+\epsilon}}\min\left\\{1-p,\frac{1-p}{\epsilon+1-p-\epsilon
p}\right\\}$ (30) $\displaystyle=\frac{1}{1+\epsilon}.$ (31)

Thus, the policy attaining the optimal competitive ratio is $p=0$ followed by
$p=1$. In other words, we utilize the capacity-achieving distributions one
after the other. It is quite remarkable that this strategy achieves a ratio
that is arbitrarily close to $1$ while the lower bound in (IV) can only
achieve $0.5$.

For the regret, codes governed by a single distribution obtain

$\displaystyle\operatorname*{\mathbf{Regret}}$
$\displaystyle\geq\min_{p}\max\left\\{\epsilon(1-p),p\right\\}=\frac{\epsilon}{1+\epsilon}.$
(32)

Considering general codes, it can be easily shown that it is optimal to decode
the second channel first, which implies the constraint
$p\leq\frac{1}{1+\epsilon}$. The optimal regret is then

$\displaystyle\operatorname*{\mathbf{Regret}}$
$\displaystyle=\min_{p\leq\frac{1}{1+\epsilon}}\max\left\\{p,\epsilon(1-\frac{1-p}{\epsilon+1-p-\epsilon
p})\right\\}=\min_{p\leq\frac{1}{1+\epsilon}}\max\left\\{p,\frac{\epsilon^{2}}{1+\epsilon}\right\\}=\frac{\epsilon^{2}}{1+\epsilon}.$
(33)

That is, by using two input distributions, we can improve the regret by a
factor of $\epsilon$. It is also interesting to note that the optimal regret
can be attained by any $p$ in the range $[0,\frac{\epsilon^{2}}{1+\epsilon}]$.

##  V Proof of Theorem 1: Achievability

To prove the achievability of Theorem 1, below, for a given channel family,
any $\alpha<\operatorname*{\mathbf{CR}}$, and sufficiently large $k$, we
design a code ${\mathcal{C}}_{k}$ that is $\alpha$-competitive.

###### Theorem 4

Let $\\{W_{s}(y|x)\\}_{s\in\mathcal{S}}$ be a family of channels. Let
$\alpha<\operatorname*{\mathbf{CR}}$. Then for any sufficiently large $k$,
there exists a code ${\mathcal{C}}_{k}=\\{(E,\\{D_{i}\\},\\{H_{i}\\})_{k}$
that is $\alpha$-competitive.

###### Proof:

The proof follows by applying ideas appearing, for example, in the study of
finite blocklength coding theorems for discrete memoryless channels, e.g.
[76], or in the study of rateless codes in the context of channel uncertainty,
e.g., [65, 63]. We here present proof for completeness (without trying to
optimize the decoding error).

Let ${\bf p^{*}}=p_{1},\dots,p_{|\mathcal{S}|}$ and ${\bf
s^{(\operatorname*{\bf p}^{*})}}=(s_{1},\dots,s_{|\mathcal{S}|})$ be the
optimizing distribution and ordering on ${\mathcal{S}}$ from the definition of
$\operatorname*{\mathbf{CR}}$ in (15), let
$T_{1},\dots,T_{|\mathcal{S}|}=T^{({\bf
p^{*}})}_{1},\dots,T_{|\mathcal{S}|}^{({\bf p^{*}})}$ be the corresponding
normalized stopping times (we here use the notation defined above (14)) let
$X_{1},\dots,X_{|\mathcal{S}|}$ be the corresponding random variables, with
$X_{i}$ distributed according to $p_{i}$. Let $\varepsilon>0$ satisfy
$\operatorname*{\mathbf{CR}}(1-\varepsilon)=\alpha$. Let $\delta>0$ be a
sufficiently small constant such that $\delta<\frac{\epsilon}{4}$, and let $k$
be a sufficiently large constant to be defined shortly.

Encoding: Consider a random code
$\operatorname{\mathcal{C}}_{k}:[2^{k}]\rightarrow\operatorname{\mathcal{X}}^{\infty}$
in which for each message $m\in[2^{k}]$ the $i$’th coordinate $x_{i}(m)$ of
$\operatorname{\mathcal{C}}_{k}(m)$ is independently distributed according to
the distribution $\pi_{i}$ over $\operatorname{\mathcal{X}}$, where
$\pi_{i}=p_{j}$ if $\frac{i}{k}\in[(1+\delta)T_{j-1},(1+\delta)T_{j}]$. Here,
we define $T_{0}$ to be 0. The prefix of length $t$ of
$\operatorname{\mathcal{C}}_{k}(m)$ is denoted by $x^{t}(m)$. For
$i>(1+\delta)T_{|\mathcal{S}|}k$ the codeword coordinates are set to 0.

Decoding: Let $i_{i,s}(x;y)=\log\left(\frac{W_{s}(y|x)}{q_{i,s}(y)}\right)$
for $q_{i,s}(y)=\sum_{x\in\operatorname{\mathcal{X}}}\pi_{i}(x)W_{s}(y|x)$,
and let $i_{s}(x^{t};y^{t})=\sum_{i=1}^{t}i_{i,s}(x_{i};y_{i})$. For every
$t$, the decoder, given $y^{t}$, decodes a message $m$ (and stops) if there
exists an $s\in\mathcal{S}$ such that $i_{s}(x^{t}(m);y^{t})\geq
k(1+\delta/2)$. If after $t=(1+\delta)T_{|\mathcal{S}|}k$, no message has been
decoded, the decoder stops and decodes to an arbitrary message. We show below
that such a decoder succeeds with probability $1-\frac{1}{\sqrt{k}}$ when
$\sqrt{k}>\max{\left(\frac{T_{{|\mathcal{S}|}}(1+\delta)}{T_{1}\delta},\frac{8T_{{|\mathcal{S}|}}(1+\delta)|\mathcal{S}|{\tt
V}}{\delta^{2}}\right)}$, where ${\tt
V}=\max_{(i,s)\in[(1+\delta)T_{|\mathcal{S}|}]\times{\mathcal{S}}}{\tt
Var}[i_{i,s}(\pi_{i};Y_{i,s})]$.

Analysis: Let $s$ be the correct channel in use. For any $t$, let
$I_{s}^{t}(X;Y)=\sum_{i=1}^{t}I(\pi_{i};Y_{i,s})$ where the pair
$(\pi_{i},Y_{i,s})$ is distributed according to $\pi_{i}(x)W_{s}(y|x)$. Let
$T=kT_{s}(1+\delta)$. Notice that, by our definitions and setting of
parameters, $I_{s}^{T}(X;Y)=(1+\delta)k$ as $T_{s}^{(\operatorname*{\bf
p}^{*})}$ defined in (14) is designed to satisfy
$I_{s}^{kT_{s}^{(\operatorname*{\bf p}^{*})}}(X;Y)=k$. A first error event,
corresponding to the case in which for the transmitted message $m$ and the
correct $s$, $i_{s}(x^{T}(m);y^{T})<k(1+\delta/2)$, can be bounded by above,
by $\frac{1}{2|\mathcal{S}|\sqrt{k}}$ using, e.g., Chebyshev’s inequality.
This follows from the fact that
$E[i_{s}(X^{T};Y^{T})]=I_{s}^{T}(X;Y)=k(1+\delta)$ and by our assumption on
$k$. Thus, for any chosen channel $s$ and for any message $m$

$\Pr_{C_{k},W_{s}}\left[i_{s}(X^{T}(m);Y^{T})<k(1+\delta/2)\right]\leq\frac{1}{2|\mathcal{S}|\sqrt{k}}$

A second error event, corresponding to the case that we decode to
$m^{\prime}\neq m$, occurs when for some $t\leq T$ and some
$s^{\prime}\in\mathcal{S}$, $i_{s^{\prime}}(x^{t}(m^{\prime});y^{t})\geq
k(1+\delta/2)$. (Here, $s^{\prime}$ is arbitrary and may be equal to the
chosen channel $s$.) Given the monotonicity of
$i_{s^{\prime}}(x^{t}(m^{\prime});y^{t})$ in $t$, the second error event is
bounded from above by the probability that
$i_{s^{\prime}}(x^{T}(m^{\prime});y^{T})\geq k(1+\delta/2)$, which in turn,
using the independence of $X_{k}^{T}(m^{\prime})$ and $Y^{T}$, is bounded by

$\displaystyle\Pr[i_{s^{\prime}}(X^{T}(m^{\prime});Y^{T})\geq k(1+\delta/2)]$
$\displaystyle=\Pr[2^{i_{s^{\prime}}(X^{T}(m^{\prime});Y^{T})}\geq
2^{k(1+\delta/2)}]\leq
2^{-k(1+\delta/2)}E\left[2^{i_{s^{\prime}}(X^{T}(m^{\prime});Y^{T})}\right]$
$\displaystyle=2^{-k(1+\delta/2)}\sum_{x^{T},y^{T}}\left(\prod_{i=1}^{T}\pi_{i}(x_{i})\right)\cdot\left(\prod_{i=1}^{T}q_{i,s}(y_{i})\right)\cdot\left(\prod_{i=1}^{T}\frac{W_{s^{\prime}}(y_{i}|x_{i})}{q_{i,s^{\prime}}(y_{i})}\right)$
$\displaystyle=2^{-k(1+\delta/2)}\sum_{y^{T}}\left(\prod_{i=1}^{T}q_{i,s}(y_{i})\right)\sum_{x^{T}}\left(\prod_{i=1}^{T}\frac{\pi_{i}(x_{i})W_{s^{\prime}}(y_{i}|x_{i})}{q_{i,s^{\prime}}(y_{i})}\right)$
$\displaystyle=2^{-k(1+\delta/2)}\sum_{y^{T}}\left(\prod_{i=1}^{T}q_{i,s}(y_{i})\right)\prod_{i=1}^{T}\left(\sum_{x\in\operatorname{\mathcal{X}}}\frac{\pi_{i}(x)W_{s^{\prime}}(y_{i}|x)}{q_{i,s^{\prime}}(y_{i})}\right)$
$\displaystyle=2^{-k(1+\delta/2)}\sum_{y^{T}}\left(\prod_{i=1}^{T}q_{i,s}(y_{i})\right)\cdot
1=2^{-k(1+\delta/2)}.$

Thus, using the union bound over all $(2^{k}-1)|\mathcal{S}|$ pairs
$(m^{\prime},s^{\prime})$, we conclude that the second error event is bounded
by $|\mathcal{S}|2^{-k\delta/2}<\frac{1}{2|\mathcal{S}|\sqrt{k}}$ by our
setting of parameters. Namely,

$\Pr_{C_{k},W_{s}}\left[\exists s^{\prime},\exists m^{\prime}\neq m,\exists
t\leq T:\ \ i_{s^{\prime}}(X^{t}(m^{\prime});Y^{t})\geq
k(1+\delta/2)\right]\leq\frac{1}{2|\mathcal{S}|\sqrt{k}}.$

The above now implies by considering both error events and taking a union
bound over $s\in\mathcal{S}$, that no matter which channel $s$ is in use, with
probability over code design and over uniform messages $M$, successful
decoding with stopping time at most ${k}T_{s}(1+\delta)$ holds with
probability at least $1-\frac{1}{\sqrt{k}}$. Namely,

$\Pr_{C_{k},\\{W_{s}\\},M}\left[\forall s,\forall s^{\prime},\forall
m^{\prime}\neq M,\forall t\leq T=kT_{s}(1+\delta):\ \
i_{s}(X^{T}(m);Y^{T})\geq k(1+\delta/2)\ \ \text{and}\ \
i_{s^{\prime}}(X^{t}(m^{\prime});Y^{t})<k(1+\delta/2)\right]\geq
1-\frac{1}{\sqrt{k}}$

This in turn implies a deterministic code with average error at most
$1-\frac{1}{\sqrt{k}}$.

To conclude, we address the competitive ratio of the code at hand. When
channel $s$ is in use, the expected stopping time of the suggested scheme is
at most

$\displaystyle\tau_{s}(k)$
$\displaystyle=\left(1-\frac{1}{\sqrt{k}}\right)kT_{s}(1+\delta)+\frac{1}{\sqrt{k}}kT_{|\mathcal{S}|}(1+\delta)\leq(1+2\delta)kT_{s}$
(34)

(here we use the bound
$\sqrt{k}>\frac{T_{|\mathcal{S}|}(1+\delta)}{T_{1}\delta}$). As for any
$s_{j}$ it holds that
$\operatorname*{\mathbf{CR}}\leq\frac{T^{*}_{s_{j}}}{T_{j}}$, we conclude (for
our setting of $\delta$) that

$\displaystyle\frac{\mathbb{E}[\tau^{\ast}|S=s_{j}]}{\mathbb{E}[{\tau}|S=s_{j}]}=\frac{\tau^{\ast}_{s_{j}}(k)}{\tau_{s_{j}}(k)}\geq\frac{(1-\delta)T^{*}_{s_{j}}k}{(1+2\delta)T_{j}k}\geq\operatorname*{\mathbf{CR}}(1-4\delta)>\operatorname*{\mathbf{CR}}(1-\epsilon)=\alpha.$
(35)

Here, we use the fact that for any constant $\delta>0$, and any sequence of
codes $(E^{*},\\{D^{*}_{i}\\},\\{H^{*}_{i}\\})_{k}$ with vanishing (in $k$)
decoding error, $\tau^{\ast}_{s_{j}}(k)\geq(1-\delta)T^{*}_{s_{j}}k$, which
holds from Fano’s inequality (see, e.g., analysis appearing later in (VI)).

Similar arguments to those presented above suffice to prove the achievability
of Theorem 3 as well. Specifically, as in (35) we have for any $s_{j}$ and
sufficiently small $\delta$ that

$\displaystyle\frac{k}{\tau^{\ast}_{s_{i}}(k)}-\frac{k}{\tau_{s_{j}}(k)}\leq\frac{1}{(1-\delta)T^{*}_{s_{j}}}-\frac{1}{(1+2\delta)T_{j}}\leq\frac{1+2\delta}{T^{*}_{s_{j}}}-\frac{1-2\delta}{T_{j}}\leq\frac{1}{T^{*}_{s_{j}}}-\frac{1}{T_{j}}+\frac{4\delta}{T^{*}_{s_{j}}}\leq\operatorname*{\mathbf{Regret}}+4\delta
C_{s_{j}}.$

∎

##  VI Proof of Theorem 1: Converse

Let $\epsilon>0$. Let $\mathcal{W}=\\{W_{s}(y|x)\\}_{s\in\mathcal{S}}$ be a
family of channels. Consider any sequence of codes
$\\{\operatorname{\mathcal{C}}_{k}\\}_{k}=\\{(E,\\{D_{i}\\},\\{H_{i}\\})_{k}\\}_{k}$
with corresponding error $\epsilon_{k}=P_{e}(\operatorname{\mathcal{C}}_{k})$
that tends to zero as $k$ tends to infinity. Let
$\operatorname*{\mathbf{CR}}(\operatorname{\mathcal{C}}_{k})$ correspond to
the competitive ratio of $\operatorname{\mathcal{C}}_{k}$. To prove the
converse, we show that

$\displaystyle\limsup_{k\to\infty}\operatorname*{\mathbf{CR}}(\operatorname{\mathcal{C}}_{k})\leq\operatorname*{\mathbf{CR}}+\epsilon.$
(36)

More specifically, for any sufficiently large $k$ and sufficiently small
corresponding $\epsilon_{k}$ (both may depend on $\epsilon$), we show that
$\operatorname*{\mathbf{CR}}(\operatorname{\mathcal{C}}_{k})\leq\operatorname*{\mathbf{CR}}+\epsilon$.

Considering $\operatorname{\mathcal{C}}_{k}$, recall that
$\tau_{s}(k)=\operatorname{\mathbb{E}}[\tau_{k}|S=s]$ is the expected decoding
time for a state $s\in\operatorname{\mathcal{S}}$. Based on the decoding
times, we define the decoding order of $\operatorname{\mathcal{C}}_{k}$ as
${\bf s}=(s_{1},\dots,s_{|\mathcal{S}|})$ such that

$\displaystyle\tau_{s_{1}}(k)\leq\tau_{s_{2}}(k)\leq\dots\leq\tau_{s_{|\mathcal{S}|}}(k).$
(37)

To simplify notation, we may use $\tau_{i}(k)$ for $\tau_{s_{i}}(k)$ when it
is clear from the context. For any $s$, the main steps of the converse proof
can be summarized as follows

$\displaystyle\frac{\inf\limits_{\mathcal{C}^{*}_{k}:P_{e}\leq\epsilon_{k}}\tau^{\ast}_{s}(k)}{\tau_{s}(k)}\stackrel{{\scriptstyle(a)}}{{\leq}}\frac{kT^{\ast}_{s}}{\tau_{s}(k)}+\frac{\epsilon}{2}\stackrel{{\scriptstyle(b)}}{{\leq}}\frac{T^{\ast}_{s}}{T_{s}^{\operatorname*{{(\bf
p,\bf s)}}}}+\epsilon,$ (38)

where $(a)$ follows, for sufficiently large $k$, from (34) in the
achievability proof given in Section V when one considers $|S|=1$, and $(b)$
follows for sufficiently large $k$ (through sufficiently small $\epsilon_{k}$)
from Lemma 1 below with $\bf s$ defined in (37) and $\bf p$ to be defined
soon. Thus, if the chain of inequalities above holds for all $s$, we conclude

$\displaystyle\operatorname*{\mathbf{CR}}(\operatorname{\mathcal{C}}_{k})=\min_{s\in\mathcal{S}}\left(\frac{\inf\limits_{\mathcal{C}^{*}_{k}:P_{e}\leq\epsilon}\tau^{\ast}_{s}(k)}{\tau_{s}(k)}\right)$
$\displaystyle\leq\min_{s\in\mathcal{S}}\frac{T^{*}_{s}}{T_{s}^{\operatorname*{{(\bf
p,\bf
s)}}}}+\epsilon\stackrel{{\scriptstyle(a)}}{{\leq}}\max_{\operatorname*{\bf
p},\operatorname*{\bf
s}}\min_{s\in\mathcal{S}}\frac{T^{*}_{s}}{T_{s}^{\operatorname*{{(\bf p,\bf
s)}}}}+\epsilon=\operatorname*{\mathbf{CR}}+\epsilon.$ (39)

An important point to emphasize for inequality $(a)$ of (39) is that $\bf p$
(defined below) does not depend on the state variable $s$ of the minimization.
The regret formulation follows from a similar line of argument,

$\displaystyle\operatorname*{\mathbf{Regret}}(\mathcal{C}_{k})\geq\max_{s\in\operatorname{\mathcal{S}}}\left(\frac{k}{\inf\limits_{\mathcal{C}^{*}_{k}:P_{e}\leq\epsilon}\tau^{\ast}_{s}(k)}-\frac{k}{\tau_{s}(k)}\right)\stackrel{{\scriptstyle(a)}}{{\geq}}\max_{s\in\operatorname{\mathcal{S}}}\left(\frac{1}{T_{s}^{\ast}}-\frac{k}{\tau_{s}(k)}\right)-\frac{\epsilon}{2}\stackrel{{\scriptstyle(b)}}{{\geq}}\max_{s\in\operatorname{\mathcal{S}}}\left(\frac{1}{T_{s}^{\ast}}-\frac{1}{T_{s}^{\operatorname*{{(\bf
p,\bf s)}}}}\right)-\epsilon,$ (40)

where $(a)-(b)$ follow from the same argument as in (38).

The remainder of this section focuses on proving step $(b)$ in (38),(40),
which includes several challenges. We start by connecting the expected
stopping time $\tau_{s}(k)$ induced by $\operatorname{\mathcal{C}}_{k}$ with
$T_{1}^{\operatorname*{{(\bf p,\bf s)}}},T_{2}^{\operatorname*{{(\bf p,\bf
s)}}},\dots$ determined by our definition of $\operatorname*{\bf p}$ described
below.

###### Definition 5

[Construction of $\operatorname*{\bf p}$] Consider the code
$\operatorname{\mathcal{C}}_{k}$. The construction f $\operatorname*{\bf p}$
is done in two steps depicted in Figure 4:

  1. 1.

For $i\in[|\operatorname{\mathcal{S}}|]$, let $X_{i}$ be the distribution over
$\operatorname{\mathcal{X}}$ of the $i^{\prime}th$ coordinate of codewords in
$\operatorname{\mathcal{C}}_{k}$ and let $\overline{X}_{i}$ be the random
variable over $\operatorname{\mathcal{X}}$ that is distributed according to
the convex combination of $X_{i}$ from time $\tau_{i-1}(k)+1$ to
$\tau_{i}(k)$. That is,

$\displaystyle P(\overline{X}_{i}=x)$
$\displaystyle=\frac{1}{\tau_{i}(k)-\tau_{i-1}(k)}\sum_{j=\tau_{i-1}(k)+1}^{\tau_{i}(k)}P(X_{j}=x)$
(41)

  2. 2.

We now recursively define random variables
$\\{\overline{\overline{X}}_{i}\\}_{i}$ over $\operatorname{\mathcal{X}}$ with
corresponding distributions $\\{p_{i}\\}$. Here, for
$i=1,\dots,|\mathcal{S}|$, $p_{i}$ is the distribution of
$\overline{\overline{X}}_{i}$. The first distribution $p_{1}$ borrows its
distribution law from $\overline{X}_{1}$, i.e.,
$\overline{\overline{X}}_{1}=\overline{X}_{1}$. The distribution $p_{i}$ of
the $i$’th random variable $\overline{\overline{X}}_{i}$ is either
$\overline{X}_{i}$ or the convex combination of
$\overline{\overline{X}}_{i-1}$ and $\overline{X}_{i}$. Specifically,

$\displaystyle P(\overline{\overline{X}}_{i}=x)$
$\displaystyle=\frac{1}{\tau_{i}(k)-\min\\{kT_{i-1}^{\operatorname*{{(\bf
p,\bf
s)}}},\tau_{i-1}(k)\\}}\left(\\{(\tau_{i-1}(k)-kT_{i-1}^{\operatorname*{{(\bf
p,\bf s)}}})\\}_{+}\cdot
P(\overline{\overline{X}}_{i-1}=x)+(\tau_{i}(k)-\tau_{i-1}(k))P(\overline{X}_{i}=x)\right)$
(42)

Notice that $T_{i-1}^{\operatorname*{{(\bf p,\bf s)}}}$ depends only on
$p_{1},\dots,p_{i-1}$ and thus (42) is sound.

Figure 4: Illustration of Definition 5. In the first stage, the variables
$\overline{X}_{i}$ are formed as a convex combination of certain codebook-
induced distributions. In the second stage, we form
$\overline{\overline{X}}_{i}$ by computing the convex combinations of the grey
areas with their subsequent intervals. If the grey area does not exist, then
$\overline{\overline{X}}_{i}=\overline{X}_{i}$.

###### Lemma 1

For $s_{i}$,

$\displaystyle\frac{\tau_{i}(k)}{k}\geq T_{i}^{\operatorname*{{(\bf p,\bf
s)}}}-\gamma_{i}(k),$ (43)

where ${\bf s}=(s_{1},s_{2},\dots,s_{|\mathcal{S}|})$ is defined in (37), $\bf
p$ is defined in Definition 5, and for each $i\in[|\mathcal{S}|]$,
$\gamma_{i}(k)$ tends to zero as $k$ tends to infinity.

###### Proof:

We prove the lemma using an induction argument. The induction propagates
through $s_{1},s_{2},\dots$ with two induction hypotheses – Equation (43) and

$\displaystyle\sum_{j=1}^{i}\left[(\tau_{j}(k)-\tau_{j-1}(k))I_{s}(\overline{X}_{j};Y)\right]\leq\sum_{j=1}^{i-1}\left[(kT_{j}^{\operatorname*{{(\bf
p,\bf s)}}}-kT_{j-1}^{\operatorname*{{(\bf p,\bf
s)}}})I_{s}(\overline{\overline{X}}_{j};Y)\right]+(\tau_{i}(k)-kT_{i-1}^{\operatorname*{{(\bf
p,\bf s)}}})I_{s}(\overline{\overline{X}}_{i};Y)+k\delta_{i}(k),$ (44)

for all $s\in\mathcal{S}$. For
$\epsilon_{k}^{\prime}=\sqrt{\epsilon_{k}}+\frac{1}{k}$, let
$\gamma_{1}(k)=T_{1}^{\operatorname*{{(\bf p,\bf s)}}}\epsilon^{\prime}_{k}$
and $\delta_{1}(k)=0$. Let
$\delta_{i}(k)=\gamma_{i-1}(k)\log|\mathcal{Y}|+\delta_{i-1}(k)$ and
$\gamma_{i}(k)=\frac{\delta_{i}(k)+\epsilon^{\prime}_{k}}{I_{s_{i}}(\overline{\overline{X}}_{i};Y)}$.
As $\epsilon_{k}^{\prime}$ tends to zero when $k$ tends to infinity, the same
hold for both $\delta_{i}(k)$ and $\gamma_{i}(k)$ for every
$i\in[|\mathcal{S}|]$.

For $s_{1}$, (44) is immediately satisfied (with $\delta_{1}(k)=0$). We show
(43) using the following chain of inequalities

$\displaystyle k$
$\displaystyle=H(M)=I_{s_{1}}(M;Y^{\tau_{s_{1}}(k)})+H(M|Y^{\tau_{s_{1}}(k)})\operatorname*{}$
$\displaystyle\stackrel{{\scriptstyle(a)}}{{\leq}}I_{s_{1}}(M;Y^{\tau_{s_{1}}(k)})+k\epsilon^{\prime}_{k}\operatorname*{}$
$\displaystyle\stackrel{{\scriptstyle(b)}}{{\leq}}\tau_{s_{1}}(k)I_{s_{1}}(\overline{X}_{1};Y)+k\epsilon^{\prime}_{k}\operatorname*{}$
$\displaystyle\stackrel{{\scriptstyle(c)}}{{=}}\tau_{s_{1}}(k)\frac{1}{T_{1}^{\operatorname*{{(\bf
p,\bf s)}}}}+k\epsilon^{\prime}_{k},$ (45)

where $(a)$ follows from Lemma 2 given below. This step can be viewed as an
application of Fano’s inequality (modified to address expected decoding time
$\tau_{s_{1}}(k)$). Step $(b)$ follows from the concavity of the mutual
information and Definition 5. In particular, recall by Definition 5 that
$\overline{X}_{1}$ is distributed according to uniform convex combination of
the first $\tau_{1}(k)=\tau_{s_{1}}(k)$ channel inputs. Step $(c)$ follows
from the definition of $T_{s}^{\operatorname*{{(\bf p,\bf s)}}}$ in (12) with
the first coordinate of $\operatorname*{\bf p}$ taken as $p_{1}$ from
Definition 5 (and the remaining coordinates can be chosen arbitrarily).
Rearranging (VI), we obtain (43) for the base case of $s_{1}$ with
$\gamma_{1}(k)=T_{1}^{\operatorname*{{(\bf p,\bf s)}}}\epsilon^{\prime}_{k}$.

For the induction step, we assume that (43) and (44) hold for
$s_{1},\dots,s_{i-1}$. We begin with showing (44),

$\displaystyle\sum_{j=1}^{i}\left[(\tau_{j}(k)-\tau_{j-1}(k))I_{s}(\overline{X}_{j};Y)\right]$
$\displaystyle\stackrel{{\scriptstyle(a)}}{{\leq}}\sum_{j=1}^{i-2}\left[(kT_{j}^{\operatorname*{{(\bf
p,\bf s)}}}-kT_{j-1}^{\operatorname*{{(\bf p,\bf
s)}}})I_{s}(\overline{\overline{X}}_{j};Y)\right]+(\tau_{i-1}(k)-kT_{i-2}^{\operatorname*{{(\bf
p,\bf s)}}})I_{s}(\overline{\overline{X}}_{i-1};Y)\operatorname*{}$
$\displaystyle+(\tau_{i}(k)-\tau_{i-1}(k))I_{s}(\overline{X}_{i};Y)+k\delta_{i-1}(k)\operatorname*{}$
$\displaystyle\stackrel{{\scriptstyle(b)}}{{=}}\sum_{j=1}^{i-1}\left[(kT_{j}^{\operatorname*{{(\bf
p,\bf s)}}}-kT_{j-1}^{\operatorname*{{(\bf p,\bf
s)}}})I_{s}(\overline{\overline{X}}_{j};Y)\right]+(\tau_{i-1}(k)-kT_{i-1}^{\operatorname*{{(\bf
p,\bf s)}}})I_{s}(\overline{\overline{X}}_{i-1};Y)\operatorname*{}$
$\displaystyle\
+(\tau_{i}(k)-\tau_{i-1}(k))I_{s}(\overline{X}_{i};Y)+k\delta_{i-1}(k)\operatorname*{}$
$\displaystyle\stackrel{{\scriptstyle(c)}}{{\leq}}\sum_{j=1}^{i-1}\left[(kT_{j}^{\operatorname*{{(\bf
p,\bf s)}}}-kT_{j-1}^{\operatorname*{{(\bf p,\bf
s)}}})I_{s}(\overline{\overline{X}}_{j};Y)\right]+(\tau_{i}(k)-kT_{i-1}^{\operatorname*{{(\bf
p,\bf s)}}})I_{s}(\overline{\overline{X}}_{i};Y)\operatorname*{}$
$\displaystyle+k\gamma_{i-1}(k)\log|\mathcal{Y}|+k\delta_{i-1}(k)\operatorname*{}$
$\displaystyle=\sum_{j=1}^{i-1}\left[(kT_{j}^{\operatorname*{{(\bf p,\bf
s)}}}-kT_{j-1}^{\operatorname*{{(\bf p,\bf
s)}}})I_{s}(\overline{\overline{X}}_{j};Y)\right]+(\tau_{i}(k)-kT_{i-1}^{\operatorname*{{(\bf
p,\bf s)}}})I_{s}(\overline{\overline{X}}_{i};Y)+k\delta_{i}(k),$ (46)

where $(a)$ follows from the induction hypothesis. Step $(b)$ follows from
splitting the term $(\tau_{i-1}(k)-kT_{i-2}^{\operatorname*{{(\bf p,\bf
s)}}})$ into $(\tau_{i-1}(k)-kT_{i-1}^{\operatorname*{{(\bf p,\bf
s)}}})+(T_{i-1}^{\operatorname*{{(\bf p,\bf
s)}}}(k)-kT_{i-2}^{\operatorname*{{(\bf p,\bf s)}}})$. Step $(c)$ is shown
based on the sign of $\tau_{i-1}(k)-kT_{i-1}^{\operatorname*{{(\bf p,\bf
s)}}}$. If $\tau_{i-1}(k)-kT_{i-1}^{\operatorname*{{(\bf p,\bf s)}}}>0$, we
can use the concavity of the mutual information function combined with the
definition of $\overline{\overline{X}}_{i}$ (Definition 5) as follows

$\displaystyle(\tau_{i-1}(k)-kT_{i-1}^{\operatorname*{{(\bf p,\bf
s)}}})I_{s}(\overline{\overline{X}}_{i-1};Y)+(\tau_{i}(k)-\tau_{i-1}(k))I_{s}(\overline{X}_{i};Y)$
$\displaystyle\leq(\tau_{i}(k)-kT_{i-1}^{\operatorname*{{(\bf p,\bf
s)}}})I_{s}(\overline{\overline{X}}_{i};Y).$ (47)

For the other case, $\tau_{i-1}(k)-kT_{i-1}^{\operatorname*{{(\bf p,\bf
s)}}}\leq 0$, we have

$\displaystyle(\tau_{i-1}(k)-kT_{i-1}^{\operatorname*{{(\bf p,\bf
s)}}})I_{s}(\overline{\overline{X}}_{i-1};Y)+(\tau_{i}(k)-\tau_{i-1}(k))I_{s}(\overline{X}_{i};Y)$
$\displaystyle=(\tau_{i-1}(k)-kT_{i-1}^{\operatorname*{{(\bf p,\bf
s)}}})(I_{s}(\overline{\overline{X}}_{i-1};Y)-I_{s}(\overline{X}_{i};Y))$ (48)
$\displaystyle\ \ \ +(\tau_{i}(k)-kT_{i-1}^{\operatorname*{{(\bf p,\bf
s)}}})I_{s}(\overline{X}_{i};Y)\operatorname*{}$
$\displaystyle=(\tau_{i-1}(k)-kT_{i-1}^{\operatorname*{{(\bf p,\bf
s)}}})(I_{s}(\overline{\overline{X}}_{i-1};Y)-I_{s}(\overline{X}_{i};Y))$ (49)
$\displaystyle\ \ \ +(\tau_{i}(k)-kT_{i-1}^{\operatorname*{{(\bf p,\bf
s)}}})I_{s}(\overline{\overline{X}}_{i};Y)\operatorname*{}$ $\displaystyle\leq
k\gamma_{i-1}(k)\log|\mathcal{Y}|+(\tau_{i}(k)-kT_{i-1}^{\operatorname*{{(\bf
p,\bf s)}}})I_{s}(\overline{\overline{X}}_{i};Y)$ (50)

where the second equality follows by Definition 5 that implies that
$\overline{\overline{X}}_{i}=\overline{X}_{i}$ in this case, and the
inequality follows from the induction hypothesis in (43).

To show the induction step (43) for $s_{i}$, consider

$\displaystyle k$
$\displaystyle\stackrel{{\scriptstyle(a)}}{{\leq}}I_{s_{i}}(M;Y^{\tau_{i}(k)})+k\epsilon^{\prime}_{k}\operatorname*{}$
$\displaystyle\stackrel{{\scriptstyle(b)}}{{\leq}}\sum_{j=1}^{i}\left[(\tau_{j}(k)-\tau_{j-1}(k))I_{s_{i}}(\overline{X_{j}};Y)\right]+k\epsilon^{\prime}_{k}\operatorname*{}$
$\displaystyle\stackrel{{\scriptstyle(c)}}{{\leq}}\sum_{j=1}^{i-1}\left[(kT_{j}^{\operatorname*{{(\bf
p,\bf s)}}}-kT_{j-1}^{\operatorname*{{(\bf p,\bf
s)}}})I_{s_{i}}(\overline{\overline{X}}_{j};Y)\right]+(\tau_{i}(k)-kT_{i-1}^{\operatorname*{{(\bf
p,\bf
s)}}})I_{s_{i}}(\overline{\overline{X}}_{i};Y)+k\delta_{i}(k)+k\epsilon^{\prime}_{k},$
(51)

where $(a)-(b)$ follow from the same reasoning in (VI). Step $(c)$ follows
from (VI) above. Rearranging (VI), we obtain

$\displaystyle\frac{\tau_{i}(k)}{k}\geq T_{i-1}^{\operatorname*{{(\bf p,\bf
s)}}}+\frac{1-\sum_{j=1}^{i-1}\left[(T_{j}^{\operatorname*{{(\bf p,\bf
s)}}}-T_{j-1}^{\operatorname*{{(\bf p,\bf
s)}}})I_{s_{i}}(\overline{\overline{X}}_{j};Y)\right]}{I_{s_{i}}(\overline{\overline{X}}_{i};Y)}-\frac{\delta_{i}(k)+\epsilon^{\prime}_{k}}{I_{s_{i}}(\overline{\overline{X}}_{i};Y)}.$
(52)

On the other hand, recall from (12) that

$\displaystyle T_{i}^{\operatorname*{{(\bf p,\bf s)}}}$
$\displaystyle=T_{i-1}^{\operatorname*{{(\bf p,\bf
s)}}}+\frac{\left\\{1-\sum_{j=1}^{i-1}\left[(T_{j}^{\operatorname*{{(\bf p,\bf
s)}}}-T_{j-1}^{\operatorname*{{(\bf p,\bf
s)}}})I_{s_{i}}(X_{j};Y)\right]\right\\}_{+}}{I_{s_{i}}(X_{i};Y)},$ (53)

where $\operatorname*{\bf p}$ is taken from Definition 5. The proof is
concluded by recalling that $\overline{\overline{X}}_{i}$ is distributed
according to $p_{i}$, so we can compare directly the right hand sides of (52)
with (53). In particular, if
$\left\\{1-\sum_{j=1}^{i-1}\left[(T_{j}^{\operatorname*{{(\bf p,\bf
s)}}}-T_{j-1}^{\operatorname*{{(\bf p,\bf
s)}}})I_{s_{i}}(X_{j};Y)\right]\right\\}_{+}>0$, we have

$\frac{\tau_{i}(k)}{k}\geq T_{i}^{\operatorname*{{(\bf p,\bf
s)}}}-\frac{\delta_{i}(k)+\epsilon^{\prime}_{k}}{I_{s_{i}}(\overline{\overline{X}}_{i};Y)}=T_{i}^{\operatorname*{{(\bf
p,\bf s)}}}-\gamma_{i}(k).$

Otherwise, we have by our induction hypothesis that

$\displaystyle\frac{\tau_{i}(k)}{k}$
$\displaystyle\geq\frac{\tau_{i-1}(k)}{k}\operatorname*{}$ $\displaystyle\geq
T_{i-1}^{\operatorname*{{(\bf p,\bf s)}}}-\gamma_{i-1}(k)\operatorname*{}$
$\displaystyle=T_{i}^{\operatorname*{{(\bf p,\bf s)}}}-\gamma_{i-1}(k).$ (54)

∎

We proceed to present the lemma that was utilized in the proof of Lemma 1. The
lemma compares the probability of error at a random decoding time with an
error probability at (roughly) the expected decoding time, and shows that the
two have a negligible difference.

###### Lemma 2

[Fano’s inequality] Consider the sequence
$\\{\operatorname{\mathcal{C}}_{k}\\}$ of codes and their corresponding error
bound
$P_{e}(\operatorname{\mathcal{C}}_{k})=\epsilon_{k}=\max_{s\in\mathcal{S}}\Pr(M\neq\hat{M}_{\tau}|S=s)$.
For each $k$, let $\epsilon^{\prime}_{k}=\sqrt{\epsilon_{k}}+\frac{1}{k}$,
then $H_{s}(M|Y^{T_{s}(\epsilon_{k})})\leq k\epsilon^{\prime}_{k}$ for all
$s\in\mathcal{S}$ where
$T_{s}(\epsilon_{k})\triangleq\tau_{s}(k)\frac{1+\sqrt{\epsilon_{k}}}{1-\sqrt{\epsilon_{k}}}$.

###### Proof:

For a fixed $s$, we prove the claim by contradiction. With some abuse of
notation, we omit the dependence of all probabilities, expectations and errors
on the state $s$. Suppose
$H(M|Y^{T_{s}(\epsilon_{k})})>k\epsilon^{\prime}_{k}$. It follows that
$H(M|Y^{t})>k\epsilon^{\prime}_{k}$ for all $t\leq T_{s}(\epsilon_{k})$. By
the standard derivation of Fano’s inequality

$\displaystyle H(M|Y^{t})$ $\displaystyle\leq
H(M,\mathbb{1}\\{M\neq\hat{M}_{t}\\}|Y^{t})\operatorname*{}$
$\displaystyle\leq
H(\mathbb{1}\\{M\neq\hat{M}_{t}\\}|Y^{t})+\Pr(M\neq\hat{M}_{t})\log(|\mathcal{M}|-1),$
(55)

where the equality follows from the fact that the indicator
$\mathbb{1}\\{M\neq\hat{M}_{t}\\}$ is a deterministic function of $(M,Y^{t})$,
and the inequality follows from
$H(M|\mathbb{1}\\{M\neq\hat{M}_{t}\\},Y^{t})\leq\log(|\mathcal{M}|-1)$.
Further, we can use (VI) to lower bound the probability of error as
$\Pr(M\neq\hat{M}_{t})>\epsilon^{\prime}_{k}-\frac{1}{k}=\sqrt{\epsilon_{k}}$
for all $t\leq T_{s}(\epsilon_{k})$. We can now directly show that

$\displaystyle\epsilon_{k}$
$\displaystyle\geq\Pr(M\neq\widehat{M}_{\tau})=\sum_{t=1}^{\infty}\Pr(\tau=t)\Pr(M\neq\widehat{M}_{t})>\Pr(\tau\leq
T_{s}(\epsilon_{k}))\sqrt{\epsilon_{k}},$ (56)

which in turn implies $\Pr(\tau>T_{s}(\epsilon_{k}))>1-\sqrt{\epsilon_{k}}$.
Finally, we bound the expected decoding time as

$\displaystyle\tau_{s}(k)$ $\displaystyle\geq
T_{s}(\epsilon_{k})\Pr(\tau>T_{s}(\epsilon_{k}))>T_{s}(\epsilon_{k})(1-\sqrt{\epsilon_{k}})=\tau_{s}(k)(1+\sqrt{\epsilon_{k}}),$
(57)

resulting in a contradiction. ∎

##  VII Conclusions

We study rateless codes for communication in the face of uncertain channel
statistics through the lens of competitive analysis and present single-letter
expressions for the competitive-ratio and regret metrics in the asymptotic
regime. Our model considers a finite family of channels that do not vary over
time and without feedback or shared randomness. The competitive analysis, in
the asymptotic and/or finite-message length regime (see, (7) and (8)), under
more general models is an interesting subject of future studies.

###  -A Comparison between rateless models

In this section we compare the achievable rate region of the “unlimited
blocklegth” rateless model used here and, e.g., in [62, 63, 72] to the rate
region of the “unlimited message-length” rateless model used, e.g., in the
works of [66, 67, 70, 71, 73]. Loosely speaking, in the former model,
communication is done over an unlimited (i.e., infinite) blocklength, while
the message $M$ consists of $k$ bits. For a channel family
$\operatorname{\mathcal{W}}=\\{W_{s}\\}_{s\in\mathcal{S}}$, rate tuple ${\bf
R}=\\{R_{s}\\}_{s\in\mathcal{S}}$ is achievable if there exists a coding
scheme that allows successful decoding when channel $W_{s}$ is in use after
$\frac{k}{R_{s}}$ channel uses. We refer to the rate region in this case by
$\operatorname{\mathcal{R}}(\operatorname{\mathcal{W}})$. In the latter model,
again, loosely speaking, communication is done over a fixed blocklength $n$,
while the message $M^{\infty}$ consists of a bit-string of unlimited length.
For a channel family
$\operatorname{\mathcal{W}}=\\{W_{s}\\}_{s\in\mathcal{S}}$, rate tuple ${\bf
R^{\infty}}=\\{R^{\infty}_{s}\\}_{s\in\mathcal{S}}$ is achievable if when
channel $W_{s}$ is in use, the prefix $M_{1}^{\ell_{s}}$ for
$\ell_{s}=R_{s}^{\infty}n$ of $M^{\infty}$ is decoded after $n$ channel uses.
We refer to the rate region in this case by
$\operatorname{\mathcal{R}}^{\infty}(\operatorname{\mathcal{W}})$. For a
detailed model, see the works mentioned above.

###### Theorem 5

$\operatorname{\mathcal{R}}^{\infty}(\operatorname{\mathcal{W}})\subsetneq\operatorname{\mathcal{R}}(\operatorname{\mathcal{W}})$.

###### Proof:

Let ${\bf
R}^{\infty}=\\{R^{\infty}_{s}\\}_{s\in\mathcal{S}}\in\operatorname{\mathcal{R}}^{\infty}(\operatorname{\mathcal{W}})$.
To show that ${\bf
R}^{\infty}\in\operatorname{\mathcal{R}}(\operatorname{\mathcal{W}})$, one can
concatenate the $n$-blocklength code achieving ${\bf R}^{\infty}$ in the
unlimited message-length model several times in such a way that allows
obtaining the rate tuple ${\bf R}=\\{R_{s}\\}_{s\in\mathcal{S}}$ with
$R_{s}=R^{\infty}_{s}$ for all $s\in\mathcal{S}$ in the unlimited blocklength
model. Below, we give an example with $|\mathcal{S}|=3$ that can naturally be
extended to general $\mathcal{S}$. Let $R_{1}^{\infty}\geq R_{2}^{\infty}\geq
R_{3}^{\infty}$. Let $k$ be a sufficiently large integer such that all
expressions below are integers. We start by using the original code
$\frac{k}{R_{1}^{\infty}n}$ times. During this process, channel $s=1$ can
decode all $k$ bits, channel $s=2$ can decode a subset $k_{2}$ of the $k$ bits
of size $k\frac{R^{\infty}_{2}}{R^{\infty}_{1}}$, and channel $s=3$ can decode
a subset $k_{3}$ of the $k$ bits of size
$k\frac{R^{\infty}_{3}}{R^{\infty}_{1}}$. This implies that the decoding time
for channel $s=1$ is $T_{1}=\frac{k}{R_{1}^{\infty}}$ and that the achievable
rate for $s=1$ is $R_{1}=R_{1}^{\infty}$ accordingly. Note that
$k_{3}\subseteq k_{2}$. We now focus on channels $s=2$ and $s=3$, and use the
original code
$\frac{k-k_{2}}{R^{\infty}_{2}n}=\frac{k}{n}\left(\frac{1}{R^{\infty}_{2}}-\frac{1}{R^{\infty}_{1}}\right)$
times on the message consisting of the $k-k_{2}$ bits not yet decoded by
channel $s=2$. After this process, channel $s=2$ had decoded all $k$ bits,
implying a total decoding time of $T_{2}$ of $\frac{k}{R_{1}^{\infty}}$ from
the first phase and
$k\left(\frac{1}{R^{\infty}_{2}}-\frac{1}{R^{\infty}_{1}}\right)$ from the
second. Thus $T_{2}=\frac{k}{R_{2}^{\infty}}$ implying that rate
$R_{2}=R_{2}^{\infty}$ is achieved for channel $s=2$ accordingly. We are left
with
$k\left(1-\frac{R^{\infty}_{3}}{R^{\infty}_{1}}-\left(\frac{R^{\infty}_{3}}{R^{\infty}_{2}}-\frac{R^{\infty}_{3}}{R^{\infty}_{1}}\right)\right)=k\left(1-\frac{R^{\infty}_{3}}{R^{\infty}_{2}}\right)$
bits to decode at channel $s=3$. This can be done using the original code
$\frac{k}{R_{3}^{\infty}n}\left(1-\frac{R^{\infty}_{3}}{R^{\infty}_{2}}\right)$
times applied to the bits not yet decoded at channel $s=3$. All in all,
channel $s=3$ decodes after
$T_{3}=\frac{k}{R_{1}^{\infty}}+K\left(\frac{1}{R^{\infty}_{2}}-\frac{1}{R^{\infty}_{1}}\right)+k\left(\frac{1}{R^{\infty}_{3}}-\frac{1}{R^{\infty}_{2}}\right)=\frac{k}{R^{\infty}_{3}}$
implying a corresponding achievable rate of $R_{3}=R^{\infty}_{3}$ for channel
$s=3$. The general case with $|\mathcal{S}|$ channels can be derived
similarly.

To show that the inclusion is tight, namely, that not all ${\bf
R}\in\operatorname{\mathcal{R}}(\operatorname{\mathcal{W}})$ are in
$\operatorname{\mathcal{R}}^{\infty}(\operatorname{\mathcal{W}})$, consider
the bilingual speaker example from Section IV. Denote the channel family by
$\operatorname{\mathcal{W}}$. It can be shown that the rate tuple ${\bf
R}=\left(5,1.2\right)$ is in
$\operatorname{\mathcal{R}}(\operatorname{\mathcal{W}})$. However, roughly
speaking, to obtain ${\bf
R^{\infty}}=(R_{1}^{\infty},R_{2}^{\infty})\in\operatorname{\mathcal{R}}^{\infty}(\operatorname{\mathcal{W}})$
with $R_{1}^{\infty}=5$, one must use codebooks in which the elements
$\\{W_{1}+1,\dots,W_{1}+W_{2}\\}$ appear sparsely, implying that
$R_{2}^{\infty}\leq 1$. Thus, ${\bf
R^{\infty}}=\left(5,1.2\right)\not\in\operatorname{\mathcal{R}}^{\infty}(\operatorname{\mathcal{W}})$.
∎

###  -B Proof of Corollary 2

###### Proof:

For any distribution sequence $\operatorname*{\bf p}$ and order
$\operatorname*{\bf s}$, we present the existence of another distribution
$\operatorname*{\bf p}^{*}$ such that
$\operatorname*{\mathbf{CR}}(\operatorname*{\bf p}^{*},\operatorname*{\bf
s}^{(\operatorname*{\bf
p}^{*})})\geq\operatorname*{\mathbf{CR}}(\operatorname*{\bf
p},\operatorname*{\bf s})$. Here,
$\operatorname*{\mathbf{CR}}(\operatorname*{\bf p},\operatorname*{\bf
s})=\min_{i}\frac{T^{\ast}_{s_{i}}}{\sum_{j=1}^{i}\Delta_{j}\operatorname*{{(\bf
p,\bf s)}}}$ and by (13),
$\operatorname*{\mathbf{CR}}=\max_{\operatorname*{\bf p},\operatorname*{\bf
s}}\operatorname*{\mathbf{CR}}(\operatorname*{\bf p},\operatorname*{\bf s})$.
This suffices to prove the corollary.

Let $\operatorname{\mathcal{S}}=\\{1,2,\dots,|{\mathcal{S}}|\\}$. Consider any
pair $\operatorname*{\bf p}=p_{1},\dots,p_{|\mathcal{S}|}$ and
$\operatorname*{\bf s}=s_{1},\dots,s_{|\mathcal{S}|}$. Assume that
$\operatorname*{\bf s}^{(\operatorname*{\bf p})}=(1,2,\dots,|\mathcal{S}|)$ is
the order induced by the greedy choice of decoding. Let $i$ be the minimal
index for which $s_{i}\neq i$. Let $k>i$ be the location of $i$ in
$\operatorname*{\bf s}$, i.e., $s_{k}=i$. Notice, that this implies
$\Delta_{k}(\operatorname*{\bf p},\operatorname*{\bf s})=0$, as for channel
$i$ we have $\Delta_{i}(\operatorname*{\bf p},\operatorname*{\bf
s}^{(\operatorname*{\bf p})})\leq\Delta_{i}(\operatorname*{\bf
p},\operatorname*{\bf s})$ due to the greedy nature of $\operatorname*{\bf
s}^{(\operatorname*{\bf p})}$. Define a new ordering $\operatorname*{\bf
s}^{\prime}=s^{\prime}_{1},\dots,s^{\prime}_{\mathcal{S}}$ that is obtained by
setting $s^{\prime}_{j}=s_{j}$ for $j<i$, $s^{\prime}_{i}=i$,
$s^{\prime}_{j+1}=s_{j}$ for $i\leq j<k$, and $s^{\prime}_{j}=s_{j}$ for
$j>k$. Namely, $\operatorname*{\bf s}^{\prime}$ is obtained from
$\operatorname*{\bf s}$ by inserting $s^{\prime}_{i}=i$ and shifting the
remaining entries of $\operatorname*{\bf s}^{\prime}$ to the right. For
example, $\operatorname*{\bf s}=(1,3,5,2,4)$ translates to $\operatorname*{\bf
s}^{\prime}=(1,2,3,5,4)$. Moreover, define a corresponding $\operatorname*{\bf
p}^{\prime}$ in which $p^{\prime}_{j}=p_{j}$ for $j\leq i$,
$p^{\prime}_{i+1}=p_{i}$, $p^{\prime}_{j}=p_{j-1}$ for $i+2\leq j\leq k$, and
$p^{\prime}_{j}=p_{j}$ for $j>k$. Namely, $\operatorname*{\bf p}^{\prime}$ is
obtained from $\operatorname*{\bf p}$ by duplicating $p_{i}$ in locations
$p^{\prime}_{i}=p^{\prime}_{i+1}=p_{i}$ and by removing $p_{k}$ from
$\operatorname*{\bf p}^{\prime}$. For our example, if $\operatorname*{\bf
p}=p_{1},p_{2},p_{3},p_{4},p_{5}$ then $\operatorname*{\bf
p}^{\prime}=p_{1},p_{2},p_{2},p_{3},p_{5}$.

It now holds by our definitions that
$\operatorname*{\mathbf{CR}}(\operatorname*{\bf p}^{\prime},\operatorname*{\bf
s}^{\prime})\geq\operatorname*{\mathbf{CR}}(\operatorname*{\bf
p},\operatorname*{\bf s})$. Specifically, for each channel $s\neq i$, let
$\ell(s)$ be its location in $\operatorname*{\bf s}$ (i.e., $s_{\ell(s)}=s$)
and $\ell^{\prime}(s)$ be its location in $\operatorname*{\bf s}^{\prime}$
(i.e., $s^{\prime}_{\ell^{\prime}(s)}=s$). Then,
$\sum_{j=1}^{\ell(s)}\Delta_{j}(\operatorname*{\bf p},\operatorname*{\bf
s})=\sum_{j=1}^{\ell^{\prime}(s)}\Delta_{j}(\operatorname*{\bf
p}^{\prime},\operatorname*{\bf s}^{\prime}).$ Moreover, for the channel $s=i$,
$\sum_{j=1}^{k}\Delta_{j}(\operatorname*{\bf p},\operatorname*{\bf
s})\geq\sum_{j=1}^{i}\Delta_{j}(\operatorname*{\bf
p}^{\prime},\operatorname*{\bf s}^{\prime}).$

We conclude that, after starting from the pair $(\operatorname*{\bf
p},\operatorname*{\bf s})$ in which $i$ was the first entry for which
$s_{i}\neq s^{(\operatorname*{\bf p})}_{i}$, we designed a new pair
$(\operatorname*{\bf p}^{\prime},\operatorname*{\bf s}^{\prime})$ for which
the first entry $i^{\prime}$ (if such exists) in which
$s^{\prime}_{i^{\prime}}\neq s^{(\operatorname*{\bf
p}^{\prime})}_{i^{\prime}}$ satisfies $i^{\prime}>i$. Moreover,
$\operatorname*{\mathbf{CR}}(\operatorname*{\bf p}^{\prime},\operatorname*{\bf
s}^{\prime})\geq\operatorname*{\mathbf{CR}}(\operatorname*{\bf
p},\operatorname*{\bf s})$. We can now continue with $(\operatorname*{\bf
p}^{\prime},\operatorname*{\bf s}^{\prime})$ and perform the process above
again, or in general multiple times, each time increasing the value of $i$ for
which $s_{i}\neq s^{(\operatorname*{\bf p})}_{i}$ (for the current
$\operatorname*{\bf s}$), and increasing the value of the corresponding
competitive ratio, until we obtain a pair $(\operatorname*{\bf
p}^{*},\operatorname*{\bf s}^{*})$ for which $\operatorname*{\bf
s}^{*}=\operatorname*{\bf s}^{(\operatorname*{\bf p}^{*})}$ and
$\operatorname*{\mathbf{CR}}(\operatorname*{\bf p}^{*},\operatorname*{\bf
s}^{(\operatorname*{\bf
p}^{*})})\geq\operatorname*{\mathbf{CR}}(\operatorname*{\bf
p},\operatorname*{\bf s})$ as asserted. This concludes our proof. ∎

###  -C Proof of Proposition 1

##  Appendix A Relating $\operatorname*{\mathbf{CR}}(\bf w)$ and
$\operatorname*{\mathbf{Regret}}(\bf{r})$ (Proof of Proposition 1)

###### Proof:

Assume that $\operatorname*{\mathbf{Regret}}>0$, as otherwise the assertion is
immediate. Let ${\bf w}=w_{1},\dots,w_{|S|}\in(0,\infty)^{|S|}$. For
$\alpha\geq 0$ let ${\bf r}^{\alpha}$ be defined by
$r^{\alpha}_{j}=\frac{w_{j}T^{*}_{j}}{w_{j}-\alpha}$. Denote the value of
$\operatorname*{\mathbf{Regret}}({\bf r}^{\alpha})$ by $\rho^{*}_{{\bf
r}^{\alpha}}$. As ${\bf r}^{\alpha}$ is monotone increasing with $\alpha$ (in
each coordinate) it follows that $\rho^{*}_{{\bf r}^{\alpha}}$ is increasing
with $\alpha$ as well. Using the continuity of $\rho^{*}_{{\bf r}^{\alpha}}$
as a function of $\alpha$, let $\alpha^{*}$ satisfy $\rho^{*}_{{\bf
r}^{\alpha^{*}}}=1$, as $\alpha=0$ implies $\rho^{*}_{{\bf r}^{\alpha}}\leq 1$
and $\alpha\to\min_{j}w_{j}$ implies $\rho^{*}_{{\bf r}^{\alpha}}\to\infty$.
To simplify notation, denote ${\bf r}^{\alpha^{*}}$ by ${\bf r}$. It now
follows for any $({\bf p},{\bf s})\in{\tt Regret_{{\bf r}}}$ and any
$j\in[|S|]$ that

$\displaystyle
r_{s_{j}}\left(\frac{1}{T^{*}_{s_{j}}}-\frac{1}{T^{\operatorname*{{(\bf p,\bf
s)}}}_{s_{j}}}\right)=\frac{w_{s_{j}}T^{*}_{s_{j}}}{w_{s_{j}}-\alpha^{\ast}}\left(\frac{1}{T^{*}_{s_{j}}}-\frac{1}{T^{\operatorname*{{(\bf
p,\bf s)}}}_{s_{j}}}\right)\leq\rho^{*}_{\bf r}=1$

which can be re-arranged as

$\displaystyle w_{s_{j}}\frac{T^{*}_{s_{j}}}{T^{({\bf p},{\bf
s})}_{s_{j}}}\geq\alpha^{*}.$

To conclude the first part of our assertion, we need to show that
$\alpha^{*}=\operatorname*{\mathbf{CR}}({\bf w})$ and thus $({\bf p},{\bf
s})\in{\tt CR_{{\bf w}}}$. Assume by contradiction that $\alpha^{*}$ is
strictly less than $\operatorname*{\mathbf{CR}}({\bf w})$. Then there exists
$({\bf p_{w}},{\bf s_{w}})\in{\tt CR_{{\bf w}}}$ such that

$\displaystyle\min_{j}w_{{(s_{w})}_{j}}\frac{T^{*}_{{(s_{w})}_{j}}}{T^{({\bf
p_{w}},{\bf s_{w}})}_{{(s_{w})}_{j}}}\geq\operatorname*{\mathbf{CR}}({\bf
w})>\alpha^{*}.$

However, using the equivalences above, this implies for all $j$ that

$\displaystyle
r_{{(s_{w})}_{j}}\left(\frac{1}{T^{*}_{{(s_{w})}_{j}}}-\frac{1}{T^{({\bf
p_{w}},{\bf s_{w}})}_{{(s_{w})}_{j}}}\right)<1$

In contradiction to the fact that $\rho^{*}_{\bf r}=1$. This concludes the
determination of $\operatorname*{\mathbf{CR}}({\bf w})$ and optimizing $({\bf
p},{\bf s})\in{\tt CR_{{\bf w}}}$ using the solution for
$\operatorname*{\mathbf{Regret}}({\bf r})$ (multiple times, until finding the
correct $\alpha$ for which $\rho^{*}_{{\bf r}^{\alpha}}=1$).

The other direction of the proof works similarly by choosing weights
$w_{j}^{\rho}=\frac{r_{j}}{r_{j}-\rho T^{*}_{j}}$ for $\rho>0$. ∎

## References

  * [1] R. L. Dobrushin.  Optimum information transmission through a channel with unknown parameters.  Radio Eng. Electron, 4(12):1–8, 1959.
  * [2] D. Blackwell, L. Breiman, and A. J. Thomasian.  The capacity of a class of channels.  The Annals of Mathematical Statistics, pages 1229–1241, 1959.
  * [3] J. Wolfowitz.  Simultaneous channels.  Archive for Rational Mechanics and Analysis, 4(1):371–386, 1959\.
  * [4] W. L. Root and P. P. Varaiya.  Capacity of classes of Gaussian channels.  SIAM Journal on Applied Mathematics, 16(6):1350–1393, 1968.
  * [5] J. Ziv.  Universal decoding for finite-state channels.  IEEE Transactions on Information Theory, 31(4):453–460, 1985.
  * [6] N. Merhav.  Universal decoding for memoryless Gaussian channels with a deterministic interference.  IEEE Transactions on Information Theory, 39(4):1261–1269, 1993\.
  * [7] I. Csiszar and J. Körner.  Information theory: coding theorems for discrete memoryless systems.  Cambridge University Press, 2011.
  * [8] D. Blackwell, L. Breiman, and A. J. Thomasian.  The capacities of certain channel classes under random coding.  The Annals of Mathematical Statistics, pages 558–567, 1960.
  * [9] R. Ahlswede and J. Wolfowitz.  Correlated decoding for channels with arbitrarily varying channel probability functions.  Information and Control, 14:457–473, 1969.
  * [10] R. Ahlswede.  Elimination of correlation in random codes for arbitrarily varying channels.  Z. Wahrsch. Verw. Gebiete, 33:159–175, 1978.
  * [11] I. Csiszár and P. Narayan.  Arbitrarily varying channels with constrained inputs and states.  IEEE Transactions on Information Theory, 34(1):27–34, 1988.
  * [12] I. Csiszár and P. Narayan.  The capacity of the arbitrarily varying channel revisited: Positivity, constraints.  IEEE Transactions on Information Theory, 34(2):181–193, 1988.
  * [13] A. D. Sarwate.  Robust and adaptive communication under uncertain interference.  PhD thesis, University of California, Berkeley, 2008.
  * [14] R. Bassily and A. Smith.  Causal Erasure Channels.  In Proceedings of the ACM-SIAM Symposium on Discrete Algorithms, pages 1844–1857, 2014.
  * [15] R. G. Gallager.  Information theory and reliable communication, volume 588.  Springer, 1968.
  * [16] H. S. Wang and N. Moayeri.  Finite-state markov channel-a useful model for radio communication channels.  IEEE transactions on vehicular technology, 44(1):163–171, 1995\.
  * [17] C. E. Shannon.  Channels with side information at the transmitter.  IBM journal of Research and Development, 2(4):289–293, 1958.
  * [18] M. Costa.  Writing on dirty paper.  IEEE transactions on information theory, 29(3):439–441, 1983.
  * [19] R. Ahlswede.  Arbitrarily varying channels with states sequence known to the sender.  IEEE transactions on information theory, 32(5):621–629, 1986.
  * [20] E. Biglieri, J. Proakis, and S. Shamai.  Fading channels: Information-theoretic and communications aspects.  IEEE Transactions on Information Theory, 44(6):2619–2692, 1998\.
  * [21] S. Verdú and T. S. Han.  A general formula for channel capacity.  IEEE Transactions on Information Theory, 40(4):1147–1157, 1994\.
  * [22] M. Effros, A. Goldsmith, and Y. Liang.  Generalizing capacity: New definitions and capacity theorems for composite channels.  IEEE Transactions on Information Theory, 56(7):3069–3087, 2010\.
  * [23] A. Lapidoth and P. Narayan.  Reliable communication under channel uncertainty.  IEEE Transactions on Information Theory, 44(6):2148–2177, 1998\.
  * [24] M. Luby.  LT codes.  In Proceedings of the 43rd Annual IEEE Symposium on Foundations of Computer Science, pages 271–280, 2002.
  * [25] D. J. C. MacKay.  Fountain codes.  IEE Proceedings-Communications, 152(6):1062–1068, 2005.
  * [26] A. Shokrollahi.  Raptor codes.  IEEE Transactions on Information Theory, 52(6):2551–2567, 2006\.
  * [27] Y. Polyanskiy, H. V. Poor, and S. Verdú.  Feedback in the non-asymptotic regime.  IEEE Transactions on Information Theory, 57(8):4903–4925, 2011\.
  * [28] D. D. Sleator and R. E. Tarjan.  Self-adjusting binary search trees.  Journal of the ACM (JACM), 32(3):652–686, 1985.
  * [29] D. D. Sleator and R. E. Tarjan.  Amortized efficiency of list update and paging rules.  Communications of the ACM, 28(2):202–208, 1985.
  * [30] M. Manasse, L. McGeoch, and D. Sleator.  Competitive algorithms for on-line problems.  In Proceedings of the twentieth annual ACM symposium on Theory of computing, pages 322–333, 1988.
  * [31] A. Borodin, N. Linial, and M. E. Saks.  An optimal on-line algorithm for metrical task system.  Journal of the ACM (JACM), 39(4):745–763, 1992.
  * [32] E. Koutsoupias and C. H. Papadimitriou.  On the k-server conjecture.  Journal of the ACM (JACM), 42(5):971–983, 1995.
  * [33] S. Albers.  Better bounds for online scheduling.  SIAM Journal on Computing, 29(2):459–473, 1999.
  * [34] A. Fiat and M. Mendel.  Better algorithms for unfair metrical task systems and applications.  SIAM Journal on Computing, 32(6):1403–1422, 2003.
  * [35] K. Pruhs, J. Sgall, and E. Torng.  Online scheduling., 2004.
  * [36] A Borodin and R. El-Yaniv.  Online computation and competitive analysis.  Cambridge university press, 2005.
  * [37] N. Alon, B. Awerbuch, Y. Azar, N. Buchbinder, and J. Naor.  The online set cover problem.  SIAM Journal on Computing, 39(2):361–370, 2009.
  * [38] N. Buchbinder and J. S. Naor.  The design of competitive online algorithms via a primal–dual approach.  Foundations and Trends® in Theoretical Computer Science, 3(2–3):93–263, 2009.
  * [39] N. Bansal, N. Buchbinder, A. Madry, and J. Naor.  A polylogarithmic-competitive algorithm for the k-server problem.  Journal of the ACM, 62(5):1–49, 2015.
  * [40] N. Merhav and M. Feder.  Universal prediction.  IEEE Transactions on Information Theory, 44(6):2124–2147, 1998\.
  * [41] Oron Sabag and Babak Hassibi.  Regret-optimal filtering for prediction and estimation.  IEEE Transactions on Signal Processing, 70:5012–5024, 2022.
  * [42] N. Buchbinder, L. Lewin-Eytan, I. Menache, J. Naor, and A. Orda.  Dynamic power allocation under arbitrary varying channels-the multi-user case.  In Proceedings of IEEE INFOCOM, pages 1–9, 2010.
  * [43] O. Ozel, K. Tutuncuoglu, J. Yang, S. Ulukus, and A. Yener.  Transmission with energy harvesting nodes in fading wireless channels: Optimal policies.  IEEE Journal on Selected Areas in Communications, 29(8):1732–1743, 2011.
  * [44] N. Buchbinder, L. Lewin-Eytan, I. Menache, J. Naor, and A. Orda.  Dynamic power allocation under arbitrary varying channels: an online approach.  IEEE/ACM Transactions on Networking (TON), 20(2):477–487, 2012\.
  * [45] P. Blasco, D. Gunduz, and M. Dohler.  A learning theoretic approach to energy harvesting communication system optimization.  IEEE Transactions on Wireless Communications, 12(4):1872–1882, 2013\.
  * [46] D. Zhao, C. Huang, Y. Chen, and S. Cui.  Competitive analysis of online throughput maximization schemes for multiple access channels with a shared renewable energy source.  In Proceedings of the IEEE Global Conference on Signal and Information Processing, pages 375–378, 2013.
  * [47] R. Vaze.  Competitive ratio analysis of online algorithms to minimize packet transmission time in energy harvesting communication system.  In Proceedings IEEE INFOCOM, pages 115–1123, 2013.
  * [48] R. Vaze, R. Garg, and N. Pathak.  Dynamic power allocation for maximizing throughput in energy-harvesting communication system.  IEEE/ACM Transactions on Networking (TON), 22(5):1621–1630, 2014\.
  * [49] J. Gomez-Vilardebo and D. Gündüz.  Competitive analysis of energy harvesting wireless communication systems.  In Proceedings of the 20th European Wireless Conference, pages 1–6. VDE, 2014.
  * [50] D. Zhao, C. Huang, Y. Chen, F. Alsaadi, and S. Cui.  Resource allocation for multiple access channel with conferencing links and shared renewable energy sources.  IEEE Journal on Selected Areas in Communications, 33(3):423–437, 2015.
  * [51] P. Mertikopoulos and A. L. Moustakas.  Learning in an uncertain world: Mimo covariance matrix optimization with imperfect feedback.  IEEE Transactions on Signal Processing, 64(1):5–18, 2015.
  * [52] I. Stiakogiannakis, P. Mertikopoulos, and C. Touati.  Adaptive power allocation and control in time-varying multi-carrier MIMO networks.  arXiv preprint arXiv:1503.02155, 2015.
  * [53] S. Satpathi, R. Nagda, and R. Vaze.  Optimal offline and competitive online strategies for transmitter–receiver energy harvesting.  IEEE Transactions on Information Theory, 62(8):4674–4695, 2016\.
  * [54] X. Wei and M. J. Neely.  Delay optimal power aware opportunistic scheduling with mutual information accumulation.  In Proceedings of the 14th International Symposium on Modeling and Optimization in Mobile, Ad Hoc, and Wireless Networks (WiOpt), pages 1–7. IEEE, 2016.
  * [55] P. Mertikopoulos and E. V. Belmega.  Learning to be green: Robust energy efficiency maximization in dynamic MIMO–OFDM systems.  IEEE Journal on Selected Areas in Communications, 34(4):743–757, 2016.
  * [56] H. Yu and M. J. Neely.  Dynamic power allocation in MIMO fading systems without channel distribution information.  In Proceedings of IEEE INFOCOM, pages 1–9, 2016.
  * [57] J. Gómez-Vilardebó.  Competitive design of energy harvesting communications in wireless fading channels.  IEEE/ACM Transactions on Networking (TON), 25(6):3863–3872, 2017\.
  * [58] A. Ben-Aroya and S. Toledo.  Competitive analysis of flash-memory algorithms.  In Proceedings of the European Symposium on Algorithms, pages 100–111. Springer, 2006.
  * [59] N. B. Chang and M. Liu.  Competitive analysis of opportunistic spectrum access strategies.  In Proceedings of IEEE INFOCOM, pages 1535–1542, 2008.
  * [60] Y.P. Hsu and A. Sprintson.  Opportunistic network coding: Competitive analysis.  In Proceedings of the International Symposium on Network Coding (NetCod), pages 191–196. IEEE, 2012.
  * [61] O. Sabag, S. Lale, and B. Hassibi.  Optimal competitive-ratio control.  arXiv preprint arXiv:2206.01782, 2022.
  * [62] N. Shulman and M. Feder.  Static broadcasting.  In IEEE International Symposium on Information Theory, page 23, 2000\.
  * [63] N. Shulman.  Communication over an unknown channel via common broadcasting.  Ph.D. dissertation, Tel Aviv University, 2003.
  * [64] O. Shayevitz and M. Feder.  Communicating using feedback over a binary channel with arbitrary noise sequence.  In IEEE International Symposium on Information Theory (ISIT), pages 1516–1520, 2005.
  * [65] A. Tchamkerten and E. I. Telatar.  Variable length coding over an unknown channel.  IEEE Transactions on Information Theory, 52(5):2126–2145, 2006\.
  * [66] K. Eswaran, A. D. Sarwate, A. Sahai, and M. Gastpar.  Using zero-rate feedback on binary additive channels with individual noise sequences.  In International Symposium on Information Theory, pages 1431–1435. IEEE, 2007.
  * [67] K. Eswaran, A. D Sarwate, A. Sahai, and M. C. Gastpar.  Zero-rate feedback can achieve the empirical capacity.  IEEE Transactions on Information Theory, 56(1):25–39, 2009.
  * [68] O. Shayevitz and M. Feder.  Achieving the empirical capacity using feedback: Memoryless additive models.  IEEE Transactions on Information Theory, 55(3):1269–1295, 2009\.
  * [69] A. D. Sarwate and M. Gastpar.  Rateless codes for AVC models.  IEEE Transactions on Information Theory, 56(7):3105–3114, 2010\.
  * [70] K. Woyach, K. Harrison, G. Ranade, and A. Sahai.  Comments on unknown channels.  In Information Theory Workshop, pages 172–176. IEEE, 2012.
  * [71] Y. Lomnitz and M. Feder.  Communication over individual channels–a general framework.  arXiv preprint arXiv:1203.1406, 2012.
  * [72] N. Blits.  Rateless codes for finite message set.  M.Sc. dissertation, Tel-Aviv University, 2012.
  * [73] Y. Lomnitz and M. Feder.  Universal communication over arbitrarily varying channels.  IEEE Transactions on Information Theory, 59(6):3720–3752, 2013\.
  * [74] M. Langberg and M. Effros.  Beyond capacity: The joint time-rate region.  arXiv preprint arXiv:2101.12236, 2021.
  * [75] P. Joshi, A. Purkayastha, Y. Zhang, A. J. Budkuley, and S. Jaggi.  On the Capacity of Additive AVCs with Feedback.  In International Symposium on Information Theory (ISIT), pages 504–509. IEEE, 2022.
  * [76] Yury Polyanskiy, H. Vincent Poor, and Sergio Verdú.  Channel coding rate in the finite blocklength regime.  IEEE Transactions on Information Theory, 56(5):2307–2359, 2010\.