Policy-Based Branch-and-Bound Decoding with Horizon-Variant Reinforcement Learning for Binary Deletion-Insertion Channel
Kai Jin · 2025
Decoding over synchronization channels, such as the binary deletion channel (BDC) and the binary insertion channel (BIC), is inherently challenging due to positional deviations caused by deletion and insertion errors. While prior works in the literature have established that deletion and insertion errors can be precisely modeled using deletion and insertion matrices, the resulting optimization problem is a binary integer linear programming problem, which cannot be solved optimally in polynomial time. The exhaustive search branch-and-bound (ESBB) decoder achieves optimal decoding accuracy but incurs exponential computational complexity. To this end, the policybased branch-and-bound (PoBB) decoder leverages a learned policy to guide the search process efficiently, enabling polynomialtime decoding while balancing performance and complexity. This paper introduces a horizon-variant reinforcement learning framework for optimizing decoding policies. The framework systematically integrates both short-horizon and long-horizon training episodes to promote robust policy generalization. Furthermore, we design and assess three policy models grounded in distinct neural network architectures, each tailored to accommodate varying episode lengths. Extensive simulation studies demonstrate that the proposed PoBB decoders, which employ diverse combinations of learning strategies and policy models, consistently surpass state-of-the-art baselines in terms of decoding accuracy and computational efficiency.