  This paper investigates the capacity of finite-state channels (FSCs) with
feedback. We derive an upper bound on the feedback capacity of FSCs by
extending the duality upper bound method from mutual information to the case of
directed information. The upper bound is expressed as a multi-letter expression
that depends on a test distribution on the sequence of channel outputs. For any
FSC, we show that if the test distribution is structured on a $Q$-graph, the
upper bound can be formulated as a Markov decision process (MDP) whose state
being a belief on the channel state. In the case of FSCs and states that are
either unifilar or have a finite memory, the MDP state simplifies to take
values in a finite set. Consequently, the MDP consists of a finite number of
states, actions, and disturbances. This finite nature of the MDP is of
significant importance, as it ensures that dynamic programming algorithms can
solve the associated Bellman equation to establish analytical upper bounds,
even for channels with large alphabets. We demonstrate the simplicity of
computing bounds by establishing the capacity of a broad family of Noisy Output
is the State (NOST) channels as a simple closed-form analytical expression.
Furthermore, we introduce novel, nearly optimal analytical upper bounds on the
capacity of the Noisy Ising channel.
