arXiv:2502.01827v2 Announce Type: replace Abstract: Linguistic steganography aims to conceal information within natural language text without being detected. An effective steganography approach should encode the secret message bits into a minimal number of language tokens while preserving the natural appearance and fluency of the stego-texts. We present a new framework to enhance the embedding efficiency by framing the steganographic embedding procedure as a Constrained Markov Decision Process (CMDP), which takes into consideration the long-term dependencies instead of merely the immediate effects. We constrain the solution space such that the discounted expected cumulative total variation between the selected conditional probability distribution and the original one given by the LLM is below a threshold. To find the optimal policy, we first show that the functional optimization problem can be simplified to a convex problem with a finite number of variables. For the binary-state model, we give a full characterization of the optimal policy, including closed-form expressions in several regimes, and show that it displays water-filling-like behavior in certain cases. The solution indicates that states with highly deterministic transition distributions are preferable for adjustment in the binary-state case. For larger state spaces, the optimal solution is more complex and explicit solutions are difficult to obtain, but the optimal policies show similar structural behaviors.