We develop a general framework for clustering and distribution matching problems with bandit feedback. We consider a K-armed bandit model where some subset of K arms is partitioned into M groups. Within each group, the random variable associated to each arm follows the same distribution on a finite alphabet. At each time step, the decision maker pulls an arm and observes its outcome from the random variable associated to that arm. Subsequent arm pulls depend on the history of arm pulls and their outcomes. The decision maker has no knowledge of the distributions of the arms or the underlying partitions. The task is to devise an online algorithm to learn the underlying partition of arms with the least number of arm pulls on average and with an error probability not exceeding a pre-determined value$\delta $. Several existing problems fall under our general framework, including finding M pairs of arms, odd arm identification, and N-ary clustering of K arms belong to our general framework. We derive a non-asymptotic lower bound on the average number of arm pulls for any online algorithm with an error probability not exceeding$\delta $. Furthermore, we develop a computationally-efficient online algorithm based on the Track-and-Stop method and Frank-Wolfe algorithm, and show that the average number of arm pulls of our algorithm asymptotically matches that of the lower bound. Our refined analysis also uncovers a novel bound on the speed at which the average number of arm pulls of our algorithm converges to the fundamental limit as$\delta $vanishes.

We study variable-length feedback (VLF) codes with noiseless feedback for discrete memoryless channels. We present a novel non-asymptotic bound, which analyzes the average error probability and average decoding time of our modified Yamamoto-Itoh scheme. We then optimize the parameters of our code in the asymptotic regime where the average error probability$\epsilon $remains a constant as the average decoding timeNapproaches infinity. Our second-order achievability bound is an improvement of Polyanskiy et al.’s (2011) achievability bound. We also develop a universal VLF code that does not rely on the knowledge of the underlying channel parameters. Our universal VLF code employs the empirical mutual information as its decoding metric and universalizes the code by Polyanskiy et al. (2011). We derive a second-order achievability bound for universal VLF codes. Our results for both VLF and universal VLF codes are extended to the additive white Gaussian noise channel with an average power constraint. The former yields an improvement over Truong and Tan’s (2017) achievability bound. The proof of our results for universal VLF codes uses a refined version of the method of types and an asymptotic expansion from the nonlinear renewal theory literature.

We study variable-length feedback (VLF) codes with noiseless feedback for discrete memoryless channels. We present a novel non-asymptotic bound, which analyzes the average error probability and average decoding time of our modified Yamamoto-Itoh scheme. We then optimize the parameters of our code in the asymptotic regime where the average error probability$\epsilon$remains a constant as the average decoding time$N$approaches infinity. Our second-order achievability bound refines Polyanskiy et al.'s (2011) achievability bound. We also universal-ize our code by employing the empirical mutual information in our decoding metric and derive a second-order achievability bound for universal VLF codes. The proof of our result for universal VLF codes uses a refined version of the method of types and an asymptotic expansion from the nonlinear renewal theory literature.

This paper investigates variable-length stop-feedback codes for memoryless channels in point-to-point, multiple access, and random access communication scenarios. The proposed codes employ $L$ decoding times $n_1, n_2, \dots, n_L$ for the point-to-point and multiple access channels and $KL + 1$ decoding times for the random access channel with at most $K$ active transmitters. In the point-to-point and multiple access channels, the decoder uses the observed channel outputs to decide whether to decode at each of the allowed decoding times $n_1, \dots, n_L$, at each time telling the encoder whether or not to stop transmitting using a single bit of feedback. In the random access scenario, the decoder estimates the number of active transmitters at time $n_0$ and then chooses among decoding times $n_{k, 1}, \dots, n_{k, L}$ if it believes that there are $k$ active transmitters. In all cases, the choice of allowed decoding times is part of the code design; given fixed value $L$, allowed decoding times are chosen to minimize the expected decoding time for a given codebook size and target average error probability. The number $L$ in each scenario is assumed to be constant even when the blocklength is allowed to grow; the resulting code therefore requires only sparse feedback. The central results are asymptotic approximations of achievable rates as a function of the error probability, the expected decoding time, and the number of decoding times. A converse for variable-length stop-feedback codes with uniformly-spaced decoding times is included for the point-to-point channel.

This paper studies the third-order characteristic of nonsingular discrete memoryless channels and the Gaussian channel with a maximal-power constraint. The third-order term in our expansions employs a new quantity here called the channel skewness, which affects the approximation accuracy more significantly as the error probability decreases. For the Gaussian channel, evaluating Shannon’s 1959 random coding bound and Vazquez-Vilar’s 2021 meta-converse bound in the central limit theorem (CLT) regime enables exact computation of the channel skewness. For discrete memoryless channels, this work generalizes Moulin’s 2017 bounds on the asymptotic expansion of the maximum achievable message set size for nonsingular channels from the CLT regime to include the moderate deviations (MD) regime, thereby refining Altuğ and Wagner’s 2014 MD result. For an example binary symmetric channel and most practically important$(n, \epsilon)$pairs, including$n \in [{100, 500}]$and$\epsilon \in [10^{-10}, 10^{-1}]$, an approximation up to the channel skewness is the most accurate among several expansions in the literature. A derivation of the third-order term in the type-II error exponent of binary hypothesis testing in the MD regime is also included; the resulting third-order term is similar to the channel skewness.

We study variable-length codes for point-to-point discrete memoryless channels with noiseless unlimited-rate feed-back that occurs in L bursts. We term such codes variable-length bursty-feedback (VLBF) codes. Unlike classical codes with feedback after each transmitted code symbol, bursty feedback fits better with protocols that employ sparse feedback after a packet is sent and also with half-duplex end devices that cannot transmit and listen to the channel at the same time. We present a novel non-asymptotic achievability bound for VLBF codes with L bursts of feedback over any discrete memoryless channel. We numerically evaluate the bound over the binary symmetric channel (BSC). We perform optimization over the time instances at which feedback occurs for both our own bound and Yavas et al.’s non-asymptotic achievability bound for variable-length stop-feedback (VLSF) codes, where only a single bit is sent at each feedback instance. Our results demonstrate the advantages of richer feedback: VLBF codes significantly outperform VLSF codes at short blocklengths, especially as the error probability ϵ decreases. Remarkably, for BSC(0.11) and error probability 10−10, our VLBF code with L = 5 and expected decoding time N ≤ 400 outperforms the achievability bound given by Polyanskiy et al. for VLSF codes with L = ∞, and our VLBF code with L = 3.

In this paper, we are interested in the performance of a variable-length stop-feedback (VLSF) code with m optimal decoding times for the binary-input additive white Gaussian noise channel. We first develop tight approximations to the tail probability of length-n cumulative information density. Building on the work of Yavas et al., for a given information density threshold, we formulate the integer program of minimizing the upper bound on average blocklength over all decoding times subject to the average error probability, minimum gap and integer constraints. Eventually, minimization of locally optimal upper bounds over all thresholds yields the globally minimum upper bound and the above method is called the two-step minimization. Relaxing to allow positive real-valued decoding times activates the gap constraint. We develop gap-constrained sequential differential optimization (SDO) procedure to find the optimal, gap-constrained, real-valued decoding times. In the error regime of practical interest, Polyanskiy's scheme of stopping at zero does not help. In this region, the achievability bounds estimated by the two-step minimization and gap-constrained SDO show that Polyanskiy’s achievability bound for VLSF codes can be approached with a small number of decoding times.

The channel coding problem in the moderate deviations regime is studied; here, the error probability sub-exponentially decays to zero, and the rate approaches the capacity slower than $O(1/\sqrt n )$. The main result refines Altuğ and Wagner’s moderate deviations result by deriving lower and upper bounds on the third-order term in the asymptotic expansion of the maximum achievable message set size. The third-order term of the expansion employs a new quantity called the channel skewness. For the binary symmetric channel and most practically important (n,ϵ) pairs, including n ∈ [100, 500] and ϵ ∈ [10−10,10−1], an approximation up to the channel skewness is the most accurate among several expansions in the literature.

We investigate variable-length feedback (VLF) codes for the Gaussian point-to-point channel under maximal power, average error probability, and average decoding time constraints. Our proposed strategy chooses$K < \infty$decoding times$n_{1}, n_{2}, \ldots, n_{K}$rather than allowing decoding at any time$n=0,1,2, \ldots$. We consider stop-feedback, which is one-bit feedback transmitted from the receiver to the transmitter at times$n_{1}, n_{2},\ldots$only to inform her whether to stop. We prove an achievability bound for VLF codes with the asymptotic approximation$\ln M \approx \frac{NC(P)}{1-\epsilon}-\sqrt{N\ \ln_{(K-1)}(N)\frac{V(P)}{1-\epsilon}}$, where$\ln(K)(\cdot)$denotes the$K$-fold nested logarithm function,$N$is the average decoding time, and$C(P)$and$V(P)$are the capacity and dispersion of the Gaussian channel, respectively. Our achievability bound evaluates a non-asymptotic bound and optimizes the decoding times$n_{1}, \ldots, n_{K}$within our code architecture.

This paper investigates variable-length feedback codes for discrete memoryless channels in point-to-point, multiple access, and random access communication. The proposed nested code employs L decoding times $n_{1}, n_{2}, \ldots, n_{L}$ for the point-to-point and multiple access channels and KL decoding times $\left\{n_{k, \ell}: 1 \leq k \leq K, 1 \leq \ell \leq L\right\}$ for the random access channel with at most K active transmitters; in the latter case, decoding times $n_{k, \ell}, 1 \leq \ell \leq L$ are reserved for decoding in the scenario where the decoder believes that the number of active transmitters is k. The code has a nested structure, i.e., codewords used to decode messages from k active transmitters are prefix of codewords used to decode messages from $k+1$ active transmitters. The code employs single-bit, scheduled feedback from the receiver to the transmitters at each potential decoding time to inform the transmitters whether or not it is able to decode. Transmitters cease transmission, thereby truncating their codewords, when no further transmissions are required by the decoder. The choice of decoding times is optimized to minimize the expected decoding time subject to an error probability constraint, and second order achievability bounds are derived.

This study investigates the fundamental limits of variable-length compression in which prefix-free constraints are not imposed (i.e., one-to-one codes are studied) and non-vanishing error probabilities are permitted. Due in part to a crucial relation between the variable-length and fixed-length compression problems, our analysis requires a careful and refined analysis of the fundamental limits of fixed-length compression in the setting where the error probabilities are allowed to approach either zero or one polynomially in the blocklength. To obtain the refinements, we employ tools from moderate deviations and strong large deviations. Finally, we provide the third-order asymptotics for the problem of variable-length compression with non-vanishing error probabilities. We show that unlike several other information-theoretic problems in which the third-order asymptotics are known, for the problem of interest here, the third-order term depends on the permissible error probability.

Consider a random access communication scenario over a channel whose operation is defined for any number of possible transmitters. As in the model recently introduced by Polyanskiy for the Multiple Access Channel (MAC) with a fixed, known number of transmitters, the channel is assumed to be invariant to permutations on its inputs, and all active transmitters employ identical encoders. Unlike the Polyanskiy model, in the proposed scenario, neither the transmitters nor the receiver knows which transmitters are active. We refer to this agnostic communication setup as the Random Access Channel (RAC). Scheduled feedback of a finite number of bits is used to synchronize the transmitters. The decoder is tasked with determining from the channel output the number of active transmitters, k, and their messages but not which transmitter sent which message. The decoding procedure occurs at a time ntdepending on the decoder's estimate, t, of the number of active transmitters, k, thereby achieving a rate that varies with the number of active transmitters. Single-bit feedback at each time ni, i ≤ t, enables all transmitters to determine the end of one coding epoch and the start of the next. The central result of this work demonstrates the achievability on a RAC of performance that is first-order optimal for the MAC in operation during each coding epoch. While prior multiple access schemes for a fixed number of transmitters require 2k- 1 simultaneous threshold rules, the proposed scheme uses a single threshold rule and achieves the same dispersion.

This paper presents finite-blocklength achievability bounds for the Gaussian multiple access channel (MAC) and random access channel (RAC) under average-error and maximal-power constraints. Using random codewords uniformly distributed on a sphere and a maximum likelihood decoder, the derived MAC bound on each transmitter’s rate matches the MolavianJazi-Laneman bound (2015) in its first- and second-order terms, improving the remaining terms to$\frac {1}2\frac {\log {n}}{n}+{O} \left ({\frac {1}{n}}\right)$bits per channel use. The result$\vphantom {\sum ^{R}}$then extends to a RAC model in which neither the encoders nor the decoder knows which of${K}$possible transmitters are active. In the proposed rateless coding strategy, decoding occurs at a time${n}_{t}$that depends on the decoder’s estimate${t}$of the number of active transmitters${k}$. Single-bit feedback from the decoder to all encoders at each potential decoding time${n}_{i}$,${i} \leq {t}$, informs the encoders when to stop transmitting. For this RAC model, the proposed code achieves the same first-, second-, and third-order performance as the best known result for the Gaussian MAC in operation.

This paper presents finite-blocklength achievabil- ity bounds for the Gaussian multiple access channel (MAC) and random access channel (RAC) under average-error and maximal-power constraints. Using random codewords uniformly distributed on a sphere and a maximum likelihood decoder, the derived MAC bound on each transmitter's rate matches the MolavianJazi-Laneman bound (2015) in its first- and second-order terms, improving the remaining terms to 1/2 (log n)/n + O(1/n) bits per channel use. The result then extends to a RAC model in which neither the encoders nor the decoder knows which of K possible transmitters are active. In the proposed rateless coding strategy, decoding occurs at a time ntthat depends on the decoder's estimate t of the number of active transmitters k. Single-bit feedback from the decoder to all encoders at each potential decoding time ni, i ≤ t, informs the encoders when to stop transmitting. For this RAC model, the proposed code achieves the same first-, second-, and third-order performance as the best known result for the Gaussian MAC in operation.

Consider a random access communication scenario over a channel whose operation is defined for any number of possible transmitters. Inspired by the model recently introduced for the Multiple Access Channel (MAC) with a fixed, known number of transmitters by Polyanskiy, we assume that the channel is invariant to permutations on its inputs, and that all active transmitters employ identical encoders. Unlike Polyanskiy, we consider a scenario in which neither the transmitters nor the receiver know which or how many transmitters are active. We refer to this agnostic communication setup as the Random Access Channel, or RAC. Limited feedback is used to ensure that the collection of active transmitters remains fixed during each epoch. The decoder is tasked with determining from the channel output the number of active transmitters (k) and their messages but not which transmitter sent which message. The central result of this work demonstrates the achievability on a RAC of performance that is first-order optimal for the MAC in operation during each coding epoch. While prior multiple access schemes for a fixed number of transmitters require 2k- 1 simultaneous threshold rules, the proposed scheme uses a single threshold rule and achieves the same dispersion.