Pith. sign in

REVIEW 2 major objections 4 minor 54 references

Relatively-Secure LLM-Based Steganography via Constrained Markov Decision Processes

T0 review · 2 major / 4 minor · reviewed 2026-08-09 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

Pith's one-line read This paper establishes that the optimal replacement distribution for LLM-based steganography, under a discounted total-variation budget, is a deterministic piecewise water-filling policy: first adjust only the state farthest from uniform…

desk verdict Solid convex-analysis result for a two-state CMDP toy model, packaged with an LLM title it doesn't actually support. read the letter →

arxiv 2502.01827 v1 pith:JKQI5BVD submitted 2025-02-03 cs.IT math.IT

Yu-Shin Huang , Chao Tian , Krishna Narayanan , Lizhong Zheng This is my paper · ORCID
classification cs.ITmath.IT MSC 94A6068P3090C2590C40
keywords steganographylargelanguagemodelsconstrainedMarkovdecisionprocessestotalvariationdistanceembeddingefficiencywater-fillingclosed-formoptimalpolicyarithmeticcoding
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

Generative steganography hides secret bits by sampling from a modified version of an LLM's next-token distribution; the more uniform the replacement distribution, the more bits can be embedded, but the larger the deviation from natural text. This paper treats the sequential choice of replacement distributions as a constrained Markov decision process, with entropy as the reward and a discounted total-variation budget as the cost. The paper's central claim is a complete closed-form characterization of the optimal policy for a two-state Markov abstraction of the LLM. The optimal policy is deterministic and has a water-filling structure: with a tight budget, spend it only on the state whose transition distribution is least random, then adjust both states together until both reach the uniform distribution. If the abstraction captures real LLM behavior, the result gives a direct rule for how to spend a deviation budget to maximize embedding rate.

What carries the argument

The load-bearing object is the constrained Markov decision process (CMDP) formulated in terms of occupancy measures: the state is the preceding token context abstracted to two states, the action $a \in [0,1]$ is the probability that the next token is state 0, the reward is the binary entropy $H(a)$, and the cost is the total-variation distance $2|a - p_s|$. Theorem 1 shows that any randomized policy can be replaced without loss of optimality by a deterministic policy using one action per state, because entropy is concave and total variation is convex, so Jensen's inequality makes a weighted average of actions at least as good. That reduction turns the functional linear program into the convex problem P3, and solving its KKT conditions yields the closed-form water-filling formulas in Theorems 2 and 3.

What would settle it

On a real LLM, compute the optimal replacement policy numerically with the full context-dependent transition probabilities and compare its entropy gain per unit total-variation budget against the two-state closed-form policy; if the numerical optimum beats the closed-form policy at the same budget, the two-state abstraction is falsified.

Watch

Extended reading notes

Core claim

For the two-state abstraction with transition probabilities $p_s = P(S_{t+1}=0 \mid S_t=s)$, the problem of maximizing discounted cumulative binary entropy subject to a discounted total-variation budget $b$ has a deterministic optimal policy, given in closed form by Theorems 2 and 3. When both $p_0,p_1 \ge 1/2$, the solution has three regimes: for small $b$, only the state farther from $1/2$ is adjusted toward $1/2$; for intermediate $b$, both states are set to the same adjusted value; for large $b$, both are set to $1/2$. When the states lie on opposite sides of uniform, the intermediate regime follows a unique curve described by a pair of equations rather than a single shared value. The proof works by replacing the infinite-dimensional optimization over policies with an equivalent four-variable convex program.

Load-bearing premise

The closed-form policy assumes an LLM's next-token distribution can be summarized by a stationary two-state Markov chain with fixed transition probabilities; real LLM distributions change with every new token in the context.

Editorial extensions

If this is right

  • At each state the optimal policy is deterministic: the agent always picks one adjusted distribution, and randomness in the generated text comes only from the secret bits.
  • With a tight deviation budget, effort should be concentrated on the state whose transition distribution is least random; spreading the budget evenly across states is suboptimal.
  • As the budget grows, both states should be adjusted toward a common distribution, and beyond a threshold both should be replaced by the uniform distribution, maximizing the embedding rate.
  • The closed form gives an explicit entropy-versus-deviation tradeoff, so the optimal replacement can be computed from $p_0$, $p_1$, $\gamma$, and $b$ without solving a general CMDP numerically.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • The same concavity-convexity reduction should carry over to an $n$-state Markov abstraction of a language model, producing a finite convex program and a candidate multi-state water-filling policy; the paper proves only the two-state case.
  • In practice the transition probabilities would have to be estimated from the LLM's context window, and the paper does not test whether the closed-form policy survives that estimation error.
  • The security guarantee is relative: with unbounded computation and full knowledge of the LLM, an eavesdropper could still distinguish stego-text at a rate governed by the total-variation budget, so the scheme is not perfectly secure.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

2 major / 4 minor

Summary. The paper proposes a constrained Markov decision process (CMDP) formulation for relatively-secure LLM-based steganography. The sequential embedding process is abstracted to a two-state Markov chain whose action is a binary next-token probability; the reward is binary entropy and the cost is discounted total variation from the original LLM transition probabilities. The authors first reduce the functional linear program P1 to a finite four-variable problem P2 via a Jensen-based deterministic-policy argument, reparameterize it to a convex problem P3, and then solve the KKT conditions to obtain closed-form optimal policies. The claimed optimal policy is deterministic and piecewise water-filling: in the low-budget regime only the state further from uniform is adjusted, in the intermediate regime both states are adjusted together, and for a large budget both actions become uniform. The paper concludes that the result offers insights for adjusting LLM output distributions, with proofs deferred in part to an accompanying long version.

Significance. The mathematical route is genuinely interesting: the reduction from a functional optimization over occupancy measures to a finite convex program, and the observation that a deterministic policy is optimal, are clean and potentially transferable to other CMDP formulations with convex costs and concave rewards. If the closed-form characterization is correct, it gives a complete, parameter-free description of the optimal policy for the two-state abstraction. At the same time, the advertised object is 'LLM-based steganography,' and the manuscript provides no mapping from real LLM next-token distributions to the two-state model and no empirical validation. The paper is best assessed as a theory/insight contribution; its significance for actual LLM steganography depends on an unverified modeling assumption. The central theorem also contains an algebraic error in the displayed intermediate-regime formula, which must be corrected before the main claim can be accepted.

major comments (2)
  1. [Theorem 2, Eq. (35); Appendix B, Eq. (121)] The closed-form formula for the intermediate regime is algebraically incorrect. For a0=a1=a and p0,p1≥1/2, the active cost constraint from (22) is b/2=d0(p0-a)+d1(p1-a)=d0p0+d1p1-a. Substituting d0=dγ0+γa and d1=dγ1+γ(1-a) (which follow from (20)-(21) when a0=a1=a) gives b/2=dγ0p0+(dγ1+γ)p1-a(1-γp0+γp1), so the correct expression is a=M(dγ0p0+(dγ1+γ)p1-b/2), not -M(b/2-dγ0p0-dγ1p1). A numerical check with γ=0.5, dγ0=0.4, dγ1=0.1, p0=0.6, p1=0.9, b=0.25 makes the discrepancy concrete: the printed formula gives a≈0.178, whereas the constraint requires a≈0.570. Because this formula appears in the statement of Theorem 2 and in the KKT assignment of Appendix B, the main characterization is not correct as written.
  2. [Section II.B / III.A; title and abstract] The practical claim that this is an LLM-based steganography method is not supported by the manuscript. The optimization is solved for an abstract two-state Markov chain whose transition probabilities ps=P(St+1=0|St=s) are introduced without any mapping from an LLM's next-token distribution over a large vocabulary to these two states, and no p0 or p1 are estimated from any LLM or language corpus. Theorems 2 and 3 characterize the optimal policy of that abstract chain; the conclusion itself describes the result as providing 'insights.' The title and abstract should either be reframed as a theoretical abstraction, or the authors should supply evidence that real LLM next-token distributions are well approximated by such a binary-state Markov model.
minor comments (4)
  1. [Appendix B, Eq. (62)] The Lagrangian term for the state-1 absolute-value constraint duplicates β0; it should be β1(x1-d1p1-c1), consistent with the stationarity conditions (63)-(68).
  2. [Appendix B, Eqs. (126) and (163)] The dual variables ρ0 and ρ1 are introduced without definition and do not appear elsewhere; they should presumably be ν0 and ν1 as used in the KKT system.
  3. [Theorem 3, Eqs. (46)-(47)] The sentence following these equations appears to reverse the assignment of ψ0 and ψ1: from the defining inverse relations, ψ0 solves Ψp1=0 and ψ1 solves Ψp0=0, whereas the text states the opposite.
  4. [Section II.A] The relationship between the discounted-entropy reward in the CMDP and the total number of embeddable bits in a finite-length arithmetic-coding stego-text is not quantified; the discounted objective is a proxy, and the connection to the length-n procedure in Fig. 3 would benefit from an explicit statement.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the optimal-policy derivation is solved from the stated CMDP objective and constraints, with no fitted parameter or load-bearing self-citation.

full rationale

The central claim is a theorem about a defined CMDP: maximize discounted entropy subject to a discounted total-variation budget. The derivation chain P1 -> P2 -> P3 -> KKT -> Theorems 2 and 3 is self-contained. Theorem 1 is proved from Jensen's inequality using concavity of the binary entropy function and convexity of total variation, reducing the functional optimization to a finite convex problem; the closed-form policies are then obtained by solving the KKT conditions, not by reading them off from data or from any fitted constant. The two-state abstraction is explicitly acknowledged as a simplifying model ('To gain insights into how p'_t should be selected, we abstract and simplify the LM into the simplest finite state model'), so the theorems are conditional mathematical consequences of that stated model rather than empirical predictions. The only self-citation, [24], is invoked as background ('this token-wise problem was studied in [24]') and is not used to set any parameter, constraint, or equation in the present derivation; it is motivation, not load-bearing evidence. No quantity is fitted to a subset of data and then reported as a prediction, and no uniqueness or optimality result is imported from the authors' prior work. Any concern about whether a real LLM's context-dependent next-token distribution is well approximated by a two-state Markov chain is a modeling and validation risk, not a circularity in the derivation itself.

Assumptions & free parameters 0 free parameters · 5 assumptions · 0 invented entities

The derivation is parameter-free in the optimization sense, but it rests on three modeling assumptions that are not empirically validated: the two-state Markov abstraction of an LLM, the use of total variation distance as the imperceptibility cost, and the discounted infinite-horizon entropy objective. It also relies on standard tools (Jensen, KKT, arithmetic coding capacity). No new entities or fitted constants are introduced.

assumptions (5)
  • domain assumption The LLM's context-dependent next-token distribution can be abstracted as a stationary two-state Markov chain with transition probabilities p0 and p1.
    Invoked in Section II.B, where the state space is reduced to a binary state model. This is the chief simplification and is not empirically validated.
  • domain assumption Total variation distance between the selected and original probability distributions is the correct cost for imperceptibility and security.
    Used in Section III.A equation (10) and throughout the constraint (16). No comparison to other perceptual or statistical distance measures is given.
  • domain assumption Discounted infinite-horizon cumulative entropy is the correct objective for steganographic embedding efficiency.
    Problem P1 in Section III.B maximizes the discounted sum of entropies; actual finite-block arithmetic coding capacity is a sum over a finite horizon, and the choice of discount factor is not justified.
  • standard math Arithmetic coding embeds at the entropy rate for any declared sequence of distributions p't.
    Section II.A relies on arithmetic coding [29] to map secret bits to tokens, a standard result in steganography.
  • standard math Convex optimization theory, Jensen's inequality, and KKT conditions are applicable to P3.
    Appendix A uses Jensen's inequality; Appendix B uses KKT for the convex program. These are standard tools.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Relatively-Secure LLM-Based Steganography via Constrained Markov Decision Processes." pith.science (2026). https://pith.science/paper/JKQI5BVD

@misc{pith2026250201827,
  author       = {Pith},
  title        = {Pith review of: Relatively-Secure LLM-Based Steganography via Constrained Markov Decision Processes},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/JKQI5BVD}},
  note         = {Machine review of arXiv:2502.01827}
}
read the original abstract

Linguistic steganography aims to conceal information within natural language text without being detected. An effective steganography approach should encode the secret message into a minimal number of language tokens while preserving the natural appearance and fluidity of the stego-texts. We present a new framework to enhance the embedding efficiency of stego-texts generated by modifying the output of a large language model (LLM). The novelty of our approach is in abstracting the sequential steganographic embedding process 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 accumulative total variation divergence between the selected probability distribution and the original distribution 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 optimization problem with a finite number of variables. A closed-form solution for the optimal policy is then presented to this equivalent problem. It is remarkable that the optimal policy is deterministic and resembles water-filling in some cases. The solution suggests that usually adjusting the probability distribution for the state that has the least random transition probability should be prioritized, but the choice should be made by taking into account the transition probabilities at all states instead of only the current state.

Figures

Figures reproduced from arXiv: 2502.01827 by the authors.

Figure 1
Figure 1. Steganography system more efficient encoding of hidden information compared to traditional approaches [8]–[18]. In this approach (discussed in detail in Section II), a language model (LM) is used to produce the conditional probabilities p(xt|xt−1, . . . , xt−k) for the token at time t and the secret message is embedded in the sampling process that samples from pt to generate xt. It is known that P t H(pt) bits of in… view at source ↗
Figure 2
Figure 2. Relatively-secure LM-based steganography system [PITH_FULL_IMAGE:figures/full_fig_p002_2.png] view at source ↗
Figure 3
Figure 3. Arithmetic coding based steganography actions a ∈ A(s) for states s ∈ S in order to maximize the cumulative discounted reward over the entire timeframe, i.e., R = E "X∞ t=0 γ t r(st, at) # , (1) subject to the constraint C = E "X∞ t=0 γ t g(st, at) # ≤ b. (2) It is often more convenient to consider the discounted state￾action pair visitation frequency d(s, a) than the policy π(a|s), also known as the occupancy measu… view at source ↗
Figures from the paper (3 more)
Figure 4
Figure 4. Figure 4: Steganography with CMDP B. CMDP Formulation With the components given above, we can utilize the general CMDP framework and write out our specific problem in terms of the visitation frequency d(s, a), denoted as P1 below. P1 : max d(s,a) : X 1 s=0 Z 1 0 H(pa)d(s, a) da …
Figure 5
Figure 5. Figure 5: a0, a1 value v.s. b constraint with d = [0.8, 0.2] We further note that the visitation frequency ds can be expressed in terms of a0 and a1 using equation (49): d0 = d γ 0 + γa1 1 − γa0 + γa1 , d1 = 1 − γa0 − d γ 0 1 − γa0 + γa1 (49) V. CONCLUSION In this study, we pres…
Figure 6
Figure 6. Figure 6: The proof in appendix B-C b) Dual variables: α0 = α1 = β0 = β1 = ρ0 = ρ1 = λ = 0. (163) All the dual variables are assigned using (92)-(94). With the primal and dual variables displayed above, we confirm that (63)-(68), (69)-(75), (76)-(80), and (81)-(87) are satisfied…

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

54 extracted references · 45 canonical work pages

  1. [1]

    On the limits of steganography,

    R. J. Anderson and F. A. Petitcolas, “On the limits of steganography,” IEEE Journal on selected areas in communications , vol. 16, no. 4, pp. 474–481, 1998

    work page 1998

  2. [2]

    I. Cox, M. Miller, J. Bloom, J. Fridrich, and T. Kalker, Digital water- marking and steganography . Morgan kaufmann, 2007

    work page 2007

  3. [3]

    Hide and seek: An introduction to steganography,

    N. Provos and P. Honeyman, “Hide and seek: An introduction to steganography,”IEEE security & privacy, vol. 1, no. 3, pp. 32–44, 2003

    work page 2003

  4. [4]

    The prisoners’ problem and the subliminal channel,

    G. J. Simmons, “The prisoners’ problem and the subliminal channel,” in Advances in Cryptology: Proceedings of Crypto 83 . Springer, 1984, pp. 51–67

    work page 1984

  5. [5]

    The hiding virtues of ambiguity: quantifiably resilient watermarking of natural language text through synonym substitutions,

    U. Topkara, M. Topkara, and M. J. Atallah, “The hiding virtues of ambiguity: quantifiably resilient watermarking of natural language text through synonym substitutions,” in Proceedings of the 8th workshop on Multimedia and security , 2006, pp. 164–174

    work page 2006

  6. [6]

    Linguistic steganography using automatically generated paraphrases,

    C. Y . Chang and S. Clark, “Linguistic steganography using automatically generated paraphrases,” in Human Language Technologies: The 2010 Annual Conference of the North American Chapter of the Association for Computational Linguistics , 2010, pp. 591–599

    work page 2010

  7. [7]

    Matryoshka: Hiding secret communication in plain sight,

    I. Safaka, C. Fragouli, and K. Argyraki, “Matryoshka: Hiding secret communication in plain sight,” in 6th USENIX Workshop on Free and Open Communications on the Internet (FOCI 16) , 2016

    work page 2016

  8. [8]

    Generating Steganographic Text with LSTMs

    T. Fang, M. Jaggi, and K. Argyraki, “Generating steganographic text with LSTMs,” arXiv preprint arXiv:1705.10742 , 2017

    work page Pith review arXiv 2017

Show all 54 references
  1. [9]

    RNN-stega: Linguistic steganography based on recurrent neural net- works,

    Z.-L. Yang, X.-Q. Guo, Z.-M. Chen, Y .-F. Huang, and Y .-J. Zhang, “RNN-stega: Linguistic steganography based on recurrent neural net- works,” IEEE Transactions on Information Forensics and Security , vol. 14, no. 5, pp. 1280–1295, 2018

    2018

  2. [10]

    Neural linguistic steganography,

    Z. Ziegler, Y . Deng, and A. M. Rush, “Neural linguistic steganography,” in Proceedings of the 2019 Conference on Empirical Methods in Natural Language Processing and the 9th International Joint Conference on Natural Language Processing (EMNLP-IJCNLP), 2019, pp. 1210–1215

    2019

  3. [11]

    A novel linguistic steganog- raphy based on synonym run-length encoding,

    L. Xiang, X. Wang, C. Yang, and P. Liu, “A novel linguistic steganog- raphy based on synonym run-length encoding,” IEICE transactions on Information and Systems , vol. 100, no. 2, pp. 313–322, 2017

    2017

  4. [12]

    V AE- Stega: linguistic steganography based on variational auto-encoder,

    Z.-L. Yang, S.-Y . Zhang, Y .-T. Hu, Z.-W. Hu, and Y .-F. Huang, “V AE- Stega: linguistic steganography based on variational auto-encoder,”IEEE Transactions on Information Forensics and Security , vol. 16, pp. 880– 895, 2020

    2020

  5. [13]

    GAN-TStega: Text steganography based on generative adversarial networks,

    Z. Yang, N. Wei, Q. Liu, Y . Huang, and Y . Zhang, “GAN-TStega: Text steganography based on generative adversarial networks,” inDigital Forensics and Watermarking: 18th International Workshop, IWDW 2019, Chengdu, China, November 2–4, 2019, Revised Selected Papers 18 . Springer...

    2019

  6. [14]

    Perfectly secure steganography using minimum entropy coupling,

    C. S. de Witt, S. Sokota, J. Z. Kolter, J. Foerster, and M. Strohmeier, “Perfectly secure steganography using minimum entropy coupling,” arXiv preprint arXiv:2210.14889 , 2022

    2022 arXiv

  7. [15]

    Meteor: Cryptographically secure steganography for realistic distributions,

    G. Kaptchuk, T. M. Jois, M. Green, and A. D. Rubin, “Meteor: Cryptographically secure steganography for realistic distributions,” in Proceedings of the 2021 ACM SIGSAC Conference on Computer and Communications Security, 2021, pp. 1529–1548

    2021

  8. [16]

    Provably secure public-key steganography based on elliptic curve cryptography,

    X. Zhang, K. Chen, J. Ding, Y . Yang, W. Zhang, and N. Yu, “Provably secure public-key steganography based on elliptic curve cryptography,” IEEE Transactions on Information Forensics and Security , 2024

    2024

  9. [17]

    Provably secure generative linguistic steganography,

    S. Zhang, Z. Yang, J. Yang, and Y . Huang, “Provably secure generative linguistic steganography,” arXiv preprint arXiv:2106.02011 , 2021

    2021 arXiv

  10. [18]

    Dis- cop: Provably secure steganography in practice based on

    J. Ding, K. Chen, Y . Wang, N. Zhao, W. Zhang, and N. Yu, “Dis- cop: Provably secure steganography in practice based on" distribution copies",” in 2023 IEEE Symposium on Security and Privacy (SP). IEEE, 2023, pp. 2238–2255

    2023

  11. [19]

    Towards near-imperceptible steganographic text,

    F. Dai and Z. Cai, “Towards near-imperceptible steganographic text,” in Proceedings of the 57th Annual Meeting of the Association for Computational Linguistics, 2019, pp. 4303–4308

    2019

  12. [20]

    Near-imperceptible neural linguistic steganography via self-adjusting arithmetic coding,

    J. Shen, H. Ji, and J. Han, “Near-imperceptible neural linguistic steganography via self-adjusting arithmetic coding,” in Proceedings of the 2020 Conference on Empirical Methods in Natural Language Processing (EMNLP), 2020, pp. 303–313

    2020

  13. [21]

    Co-Stega: Collaborative linguistic steganography for the low capacity challenge in social media,

    G. Liao, J. Yang, K. Pang, and Y . Huang, “Co-Stega: Collaborative linguistic steganography for the low capacity challenge in social media,” in Proceedings of the 2024 ACM Workshop on Information Hiding and Multimedia Security, 2024, pp. 7–12

    2024

  14. [22]

    Semantic steganogra- phy: A framework for robust and high-capacity information hiding using large language models,

    M. Bai, J. Yang, K. Pang, Y . Huang, and Y . Gao, “Semantic steganogra- phy: A framework for robust and high-capacity information hiding using large language models,” arXiv preprint arXiv:2412.11043 , 2024

    2024 arXiv

  15. [23]

    FreStega: A plug-and-play method for boosting impercepti- bility and capacity in generative linguistic steganography for real-world scenarios,

    K. Pang, “FreStega: A plug-and-play method for boosting impercepti- bility and capacity in generative linguistic steganography for real-world scenarios,” arXiv preprint arXiv:2412.19652 , 2024

    2024 arXiv

  16. [24]

    OD-Stega: LLM- based near-imperceptible steganography via optimized distributions,

    Y .-S. Huang, P. Just, K. Narayanan, and C. Tian, “OD-Stega: LLM- based near-imperceptible steganography via optimized distributions,” arXiv preprint arXiv:2410.04328 , 2024

    2024

  17. [25]

    Altman, Constrained Markov decision processes

    E. Altman, Constrained Markov decision processes . Routledge, 2021

    2021

  18. [26]

    Attention is all you need,

    A. Vaswani, “Attention is all you need,” Advances in Neural Information Processing Systems, 2017

    2017

  19. [27]

    Language models are few-shot learners,

    T. B. Brown, “Language models are few-shot learners,” arXiv preprint arXiv:2005.14165, 2020

    2005 arXiv

  20. [28]

    Llama: Open and efficient foundation language models,

    H. Touvron, T. Lavril, G. Izacard, X. Martinet, M.-A. Lachaux, T. Lacroix, B. Rozière, N. Goyal, E. Hambro, F. Azhar et al. , “Llama: Open and efficient foundation language models,” arXiv preprint arXiv:2302.13971, 2023

    2023 arXiv

  21. [29]

    Arithmetic coding,

    J. Rissanen and G. G. Langdon, “Arithmetic coding,” IBM Journal of research and development, vol. 23, no. 2, pp. 149–162, 1979

    1979

  22. [30]

    R. E. Bellman and S. E. Dreyfus, Applied dynamic programming . Princeton university press, 2015, vol. 2050

    2015

  23. [31]

    R. S. Sutton and A. G. Barto, Reinforcement learning: An introduction . MIT press, 2018

    2018

  24. [32]

    Convex optimization,

    S. Boyd and L. Vandenberghe, “Convex optimization,” Cambridge University Press, 2004. APPENDIX A PROOF OF THEOREM 1 Assuming a general optimal solution ˜d(s, a) exists for problem P1, we claim that a new solution d⋆(s, a) = d⋆ sδ(a⋆ s) is at least as good, where ( d⋆ s = R 1 0...

    2004

  25. [33]

    Therefore d⋆(s, a) satisfies the constraint (17) and (18)

    Constraints (14), (17) and (18): It is clear that d⋆ s is positive for all s ∈ {0, 1} and P1 s=0 d⋆ s sum up to 1. Therefore d⋆(s, a) satisfies the constraint (17) and (18). For constraint (14), Z 1 0 (1 − γa)d⋆(0, a)da − Z 1 0 γad⋆(1, a)da = d⋆ 0 − γa⋆ 0d⋆ 0 − γa⋆ 1d⋆ 1 = Z 1...

  26. [34]

    Constraint (16): We write b ≥ Z 1 0 TV0(a) ˜d(0, a) + TV1(a) ˜d(1, a)da = Z 1 0 d⋆ 0TV0(a) ˜d(0, a) d⋆ 0 ! + d⋆ 1TV1(a) ˜d(1, a) d⋆ 1 ! da ≥ d⋆ 0TV0 Z 1 0 a ˜d(0, a) d⋆ 0 ! da ! + d⋆ 1TV1 Z 1 0 a ˜d(1, a) d⋆ 1 ! da ! = d⋆ 0TV0(a⋆

  27. [35]

    + d⋆ 1TV1(a⋆ 1) = Z 1 0 d⋆(0, a)TV0(a) + d⋆(1, a)TV1(a)da (52) where the inequality follows the Jensen’s inequality since the total variation divergence is convex

  28. [36]

    The objective function: We wish to show that d⋆(s, a) achieves a value equal to or exceeding that of ˜d(s, a). For this purpose, we write: Z 1 0 H(a) ˜d(0, a)da + Z 1 0 H(a) ˜d(1, a)da = d⋆ 0 Z 1 0 H(a) ˜d(0, a) d⋆ 0 da + d⋆ 1 Z 1 0 H(a) ˜d(1, a) d⋆ 1 da ≤ d⋆ 0H( Z 1 0 a ˜d(0,...

  29. [37]

    We can now conclude that d⋆(s, a) is also an optimal solution to the optimization problem

    + d⋆ 1H(a⋆ 1) = Z 1 0 H(a)d⋆(0, a)da + Z 1 0 H(a)d⋆(1, a)da, (53) where again the inequality is due to Jensen’s inequality since the entropy function is concave. We can now conclude that d⋆(s, a) is also an optimal solution to the optimization problem. The solution d⋆(s, a) fu...

  30. [38]

    Stationarity: ∂L ∂x0 = − log d0 − x0 x0 − α0 + β0 − γω0 − ν0 + µ0 = 0 (63) ∂L ∂x1 = − log d1 − x1 x1 − α1 + β1 − γω0 − ν1 + µ1 = 0 (64) ∂L ∂d0 = −H( x0 d0 ) + x0 d0 log d0 − x0 x0 + α0p0 − β0p0 + ω0 + ω1 − µ0 = 0 (65) ∂L ∂d1 = −H( x1 d1 ) + x1 d1 log d1 − x1 x1 + α1p1 − β1p1 +...

  31. [39]

    Primal feasibility: c0 + c1 ≤ b 2 (69) − c0 − x0 + d0p0 ≤ 0, − c1 − x1 + d1p1 ≤ 0 (70) x0 − d0p0 − c0 ≤ 0, x1 − d1p1 − c1 ≤ 0 (71) d0 = dγ 0 + γ(x0 + x1) (72) d0 + d1 = 1 (73) x0 ≥ 0, x1 ≥ 0 (74) x0 − d0 ≤ 0, x1 − d1 ≤ 0 (75)

  32. [40]

    Dual feasibility: λ ≥ 0 (76) α0 ≥ 0, α1 ≥ 0 (77) β0 ≥ 0, β1 ≥ 0 (78) ν0 ≥ 0, ν1 ≥ 0 (79) µ0 ≥ 0, µ1 ≥ 0 (80)

  33. [41]

    The expression formulas for the primal variables xs, ds and the dual variables ωs, νs, µs where s ∈ {0, 1} are identical across all scenarios, as presented below

    Complementary slackness: λ c0 + c1 − b 2 = 0 (81) α0(−c0 − x0 + d0p0) = α1(−c1 − x1 + d1p1) = 0 (82) β0(x0 − d0p0 − c0) = β1(x1 − d1p1 − c1) = 0 (83) ω0 (d0 − dγ 0 − γ(x0 + x1)) = 0 (84) ω1 (d0 + d1 − 1) = 0 (85) ν0x0 = ν1x1 = 0 (86) µ0(x0 − d0) = µ1(x1 − d1) = 0 (87) The solu...

  34. [42]

    With the solution of a0, a1 given in the theorem, and in the given range of b, the range of a0 and a1 are a0 = p0, a1 ∈ [p0, p1], (97) The variable assignments are as follows

    The regime b ∈ [0, bl): In this regime, the two cases p1 ≥ p0 ≥ 1 2 and p0 > p1 ≥ 1 2 lead to different solution expressions, and let us consider the first case for now. With the solution of a0, a1 given in the theorem, and in the given range of b, the range of a0 and a1 are a...

  35. [43]

    (109) The variable assignments are as follows

    We can determine the range of a0 and a1 as a0 = [p1, p0], a1 = p1. (109) The variable assignments are as follows. a) Primal variable assignments: a0 = η− 0 (b), a 1 = p1 (110) c0 = b 2 , c 1 = 0 (111) Using (88)-(91), all the primal variables are assigned. Observe that x0 and ...

  36. [44]

    This establishes that α0, α1, β1, λare all non-negative

  37. [45]

    a) Primal variable assignments: a0 = a1 = −M ( b 2 − dγ 0 p0 − dγ 1 p1) (121) c0 = d0(p0 − a0), c 1 = d1(p1 − a1)

    b ∈ [bl, bh): In this regime, we have the following assignments. a) Primal variable assignments: a0 = a1 = −M ( b 2 − dγ 0 p0 − dγ 1 p1) (121) c0 = d0(p0 − a0), c 1 = d1(p1 − a1). (122) Using (88)-(91), all the primal variables are assigned. Observe that x0 and x1 will not be ...

  38. [46]

    (125) Using (88)-(91), all the primal variables are assigned

    b ∈ [bh, ∞): In this regime, we have a) Primal variables: a0 = a1 = 1 2 (124) c0 = d0(p0 − 1 2 ), c 1 = d1(p1 − 1 2 ). (125) Using (88)-(91), all the primal variables are assigned. Observe that x0 and x1 will not be zero here as well. b) Dual variables: α0 = α1 = β0 = β1 = ρ0 ...

  39. [47]

    The regime b ∈ [0, b′ l): In this regime, the two cases | 1 2 − p1| ≥ |1 2 − p0| and | 1 2 − p1| < | 1 2 − p0| lead to different solution expressions, and let us consider the first case for now. Observe that in the first case implies that p1 + p0 − 1 ≥ 0, b′ l in this case can...

  40. [48]

    Now let us turn our attention to the case when | 1 2 − p1| < | 1 2 − p0|, implying 1 − p1 − p0 ≥ 0

    The above establishes that α0, α1, β0, λare all non- negative. Now let us turn our attention to the case when | 1 2 − p1| < | 1 2 − p0|, implying 1 − p1 − p0 ≥ 0. b′ l in this case can be written as: b′ l = 2 dγ 0 + γp1 1 − γψ0 + γp1 (ψ0 − p0) (141) again by the definition giv...

  41. [49]

    We have the following assignments

    b ∈ [b′ l, b′ h]: Let us first define the following set Sb ≜ (a0, a1) ∈ [p0, 1 2 ] × [ 1 2 , p1] | Φ−(a1) = Φ+(a0) and m(a0, a1) = b 2 (153) It will be shown shortly that the set Sb is a singleton set in this regime. We have the following assignments. a) Primal variable assign...

  42. [50]

    (162) Using (88)-(91), all the primal variables are assigned

    b ∈ (bh, ∞): In this regime, we have a) Primal variables: a0 = a1 = 1 2 (161) c0 = d0( 1 2 − p0), c 1 = d1(p1 − 1 2 ). (162) Using (88)-(91), all the primal variables are assigned. Observe that x0 and x1 will not be zero here as well. 0 0.1 0.2 p0 0.4 0.5 0.6 0.7 0.8 p1 a0 and...

  43. [51]

    Similarly, their intersections with the lighter green dash line give (a0, a1) = ( p0, ψ1), which is the only element in Sb′ l ; again the two functions take the same value

    Their intersection with the darker green dash line is (a0, a1) = ( 1 2 , 1 2 ), which is the only element in Sb′ h ; here the two functions take the same value. Similarly, their intersections with the lighter green dash line give (a0, a1) = ( p0, ψ1), which is the only element...

  44. [52]

    In other words, Φ+ decreasing in a ∈ (0, 1 2 ] and Φ− increasing in a ∈ [ 1 2 , 1)

    Claim 1: Φ+ and Φ− are monotonic functions that increase in opposing directions in (0, 1 2 ] and [ 1 2 , 1) re- spectively. In other words, Φ+ decreasing in a ∈ (0, 1 2 ] and Φ− increasing in a ∈ [ 1 2 , 1). We prove this claim by computing the derivatives. ∂Φ+ ∂a = −(1 − 2γ +...

  45. [53]

    We next prove this claim

    Claim 2: There is only one solution (a0, a1) ∈ [p0, 1 2 ] × [ 1 2 , p1] satisfying m(a0, a1) = b 2 for b in the range [b′ l, b′ h] specified in Theorem 3. We next prove this claim. In (166) and (167) given below, we show that for different cases | 1 2 − p1| ≥ |1 2 − p0| and | ...

  46. [54]

    a′ 0 = a0′→0′ recover = a1→1 = 1 − a1 ⇒ a1 = 1 − a′ 0 (171) a′ 1 = a1′→0′ recover = a0→1 = 1 − a0 ⇒ a0 = 1 − a′ 1 (172) Similar steps for case p0 ≥ 1 2 ≥ p1

    Use the results in Theorem 2 to solve for optimal a′ 0, a′ 1, then convert back to a0, a1. a′ 0 = a0′→0′ recover = a1→1 = 1 − a1 ⇒ a1 = 1 − a′ 0 (171) a′ 1 = a1′→0′ recover = a0→1 = 1 − a0 ⇒ a0 = 1 − a′ 1 (172) Similar steps for case p0 ≥ 1 2 ≥ p1

Pith tools

Reviewed August 9, 2026 · model on record in the stance chip above.