| Two major topics are discussed in this thesis: side information in the context of learning vs. control and capacity-approaching error correcting codes for non-standard channels.; Side information in bandit problems. The two-armed bandit problem is a classical model characterizing the conflict between learning and control. The decision maker samples one arm at each time instant in order to maximize the total reward (the control task), while the reward distribution for each individual arm must be learned through the same sampling process as well (the learning task). In this thesis, an extension of this traditional setting is studied, under which the decision maker has access to some side information before deciding which arm to pull. Various degrees of improvement are identified and proven when considering general evenly distributed side information random processes, including independent and identically distributed random processes, Markov chains, and deterministic periodic sequences as special cases. In particular, it is shown that the well-known logarithmic lower bound for the regret in traditional bandit problems can be surpassed by explicit algorithms, achieving new, more favorable performance bounds. These results can be applied to a broad range of problems including clinical trials, early exercise strategies for the American put options, and beam selection in multiple antenna communication systems.; Low-density parity-check codes on non-symmetric channels. The near-Shannon-capacity performance of Low-Density Parity-Check (LDPC) and turbo codes has stimulated considerable research in coding theory in recent years, and significant successes have been established for standard memoryless binary-input/symmetric-output channels. In this work, the density evolution method is generalized for non-symmetric memoryless channels. This is achieved by complementing the asymptotic performance concentration theorem with a perfect projection convergence theorem. Some implications of these results include stability conditions for non-symmetric channels, the local optimality of belief propagation decoding, and the typicality of linear LDPC codes, which further justifies the application of other existing tools, e.g. EXtrinsic InformaTion (EXIT) chart analysis, on non-symmetric channels. This new powerful density evolution method successfully bridges the gap between symmetric channels and general memoryless channels, and is demonstrated on a simple non-symmetric model for optical storage channels. Various finite-dimensional bounds on the decodable thresholds are derived, including the best bound for fading channels to date. |
