To feed or not to feed back

We establish results assessing the fundamental limits on reliable communication over Finite State Channels (FSCs), when the encoder and the decoder can control the availability or the quality of the feedback. The instantaneous feedback is a function of a cost constrained action taken by the encoder, a cost constrained action taken by the decoder, and the channel output. Achievability is through construction of a sequence of convergent achievable rates, using a simple scheme based on `code tree´ generation, that generates channel input symbols along with encoder and decoder actions. For a given block length N, we give an upper bound on the maximum achievable rate. For stationary indecomposable channels without intersymbol interference (ISI), the capacity is given as the limit of normalized directed information between the input and output sequence, maximized over an appropriate set of causally conditioned distributions. As important special cases, we characterize (a) the framework of `to feed or not to feed back´ where either the encoder or the decoder takes binary actions to determine whether current channel output will be fed back to the encoder, with a constraint on the fraction of channel outputs that are fed back, (b) the capacity of `coding on the backward link´ in FSCs, i.e., when the decoder sends limited-rate instantaneous coded noise-free feedback on the backward link.