  We study a discrete-time model where each packet has a cost of not being sent
-- this cost might depend on the packet content. We study the tradeoff between
the age and the cost where the sender is confined to packet-based strategies.
The optimal tradeoff is found by an appropriate formulation of the problem as a
Markov Decision Process (MDP). We show that the optimal tradeoff can be
attained with finite-memory policies and we devise an efficient policy
iteration algorithm to find these optimal policies. We further study a related
problem where the transmitted packets are subject to erasures. We show that the
optimal policies for our problem are also optimal for this new setup. Allowing
coding across packets significantly extends the packet-based strategies. We
show that when the packet payloads are small, the performance can be improved
by coding.
