Analysis of approximate linear programming solution to Markov decision problem with log barrier function
Authors: Donghwan Lee
Hyukjun Yang
Bumgeun Park
Venue: ICLR 2026 Poster (2026)
Keywords: Markov decision programming
reinforcement learning
linear programming
dynamic programming
Primary area: reinforcement learning

Abstract: There are two primary approaches to solving Markov decision problems (MDPs): dynamic programming based on the Bellman equation and linear programming (LP). Dynamic programming methods are the most widely used and form the foundation of both classical and modern reinforcement learning (RL). By contrast, LP-based methods have been less commonly employed, although they have recently gained attention in contexts such as offline RL. The relative underuse of the LP-based methods stems from the fact that it leads to an inequality-constrained optimization problem, which is generally more challenging to solve effectively compared with Bellman-equation-based methods. The purpose of this paper is to establish a theoretical foundation for solving LP-based MDPs in a more effective and practical manner. Our key idea is to leverage the log-barrier function, widely used in inequality-constrained optimization, to transform the LP formulation of the MDP into an unconstrained optimization problem. This reformulation enables approximate solutions to be obtained easily via gradient descent. While the method may appear naive, to the best of our knowledge, a thorough theoretical interpretation of this approach has not yet been developed. This paper aims to bridge this gap.

Published as a conference paper at ICLR 2026
ANALYSIS OF APPROXIMATE LINEAR PROGRAMMING SOLUTION TO MARKOV DECISION PROBLEM WITH LOG
BARRIER FUNCTION
Donghwan Lee, Hyukjun Yang, & Bumgeun Park
Department of Electrical Engineering
Korea Advanced Institute Science and Technology Daejeon, 34141, South Korea {donghwan, jundo132, j4t123 (kaikkaaa ac..ai.tt.......................
ABSTRACT
There are two primary approaches to solving Markov decision problems (MDPs): dynamic programming based on the Bellman equation and linear programming (LP). Dynamic programming methods are the most widely used and form the foundation of both classical and modern reinforcement learning (RL). By con- trast, LP-based methods have been less commonly employed, although they have recently gained attention in contexts such as offline RL. The relative underuse of the L.P-based methods stems from the fact that it leads to an inequality-constran optimization problem, which is generally more challenging to solve effectively compared with Dellman-equationn-e based methods. The purpose of this paper is to establish theoretical foundation for solving L.-based MDPs in more effec- tive and practical manner. Our key idea is to leverage the log-barrier function, widely used meequllty-cconstraine tion of the MDP into unconstrained optimization problem. This reformulation enables approximate solutions to obtained easily via gradient descent. While the method may appear simple, to the best of our knowledge, a thorough thcoreti- cal interpretation of this approach has not yet been developed. This paper aims to bridge this gap.
optimization, transform the LP formula-
INTRODUCTION
There are two primary approaches to solving Markov decision problems (MDPs): dynamic pro- gramming methods (Bertsekas and Tsitsiklis 1996 Puterman 2014) based on the Bellman equation
and linear programming (LP) methods (Puterman 2014 De Farias and Van Roy 2003 Ghate and Smith 2013) Ying and Zhu 2020). Dynamic programming is by far the most widely used approach and constitutes the foundation of both classical and modern reinforcement learning (RL) (Sutton
and Barto 1998). In contrast, I.P-based methods have been employed less frequently (Wang and
Chen 2016 Chen and Wang 2016 Lee and He 2019 2018 Chen al. 2018 Serrano and Neul
2020
Neu and Okolo 2023 Nachum and Dai 2020
Bas-Serrano et al. 2021 Lu et al., 2021
2022
RL, though they have recently gained traction in contexts such offline reinforcement
learning (Ozdallar et al., 2023 Zhan et al.) 2022 Gabbianelli et al. 2024 Kamoutsi et al.) 2021 Sikchi 2024). The relative underuse of LP formulations can be attributed the fact that they result in inequality- constriiie optimization problems, which are generally more difficult to solve effectively compared Bellman- wawtaannnnnnttn-n-aaaaa based methods.
Recently, the LP formulation of MDPs has recently received renewed interest, especially in the offline-RRi RL literature (Ozdaglar et al. 2023 Zhan et al. 2022 Gabbianelli et al., 2024 Kamoutsi ct al. 2021 Sikchi et al., 2024), because it offers several advantages over Bellman salliaann-quatiio-baaee approaches. Unfortunately, ly. LP-based RL methods typically rely on primal-dual schemes (Wang
and Chen 2016 Chen and Wang. 2016: Lee and He 2019 2018 Chen et al. 2018 Serrano and
Neu 2020; and Okolo 2023) Nachum and Dail [0200] Bas Aess-Srrann et al. [021] [u et al. 2021
2022 which are known often exhibit relatively slow convergence and higher computational costs

---

Published as a conference paper at ICLR 2026
in practice compared standard RL approaches. For these reasons, we believe there is clear need to develop effective alternatives for solving the LP form.
The purpose of this paper is to establish theoretical foundation for addressing LP-based MDPs in a more effective and practical manner. The key idea is to employ the log-barrier function (Boyd and Vandenherghe 2004), widely used in ceqquality-constrimne representation of the MDP into an unconstrained optimization problem. This reformulation allows approximate solutions to be obtained efficiently using gradient descent (Nesterov 2018 Bertsekas 1999). While this approach may appear simple, to the best of our knowledge, a comprehensive theoretical interpretation has not yet been developed. This paper aims to bridge this gap.
optimization, reformulate the LP
More specifically, we investigate the single-objective function fn induced by the log-barrier formu- lation with the barrier parameter O, whose minimizer yields approximate solution, Qn, to the original MDP. This approximate solution, Q,,, corresponds an approximate optimal Q-function. We first conduct an error analysis, deriving not only an upper bound but also lower bound on the error norm, I|Q,- - Q' between the approximate solution, Q,, and the true optimal Q-function Q'. These bounds depend linearly on the log- parameter v,. which implies that both the upper and lower bounds decrease linearly as 17 becomes smaller. Beyond the error norm, we also establish error bounds for the MDP objective function J itself. In particular, our framework yields both a primal approximate solution Q,, and a dual approximate solution Ay. from which the corresponding primal policy and dual policy are derived. For each case, we derive bounds on the deviation of their objective values from the optimal objective value, and these bounds likewise diminish linearly with 7).
In addition, we establish several properties of the objective function Sn, including its convexity, properties of its domain, and properties of its sublevel set. As mentioned earlier, the approximate LP solution can be obtained via gradient descent, and we provide an analysis of the convergence behavior of this gradient descent method. Lastly, we explore the applicability and extension of the proposed theoretical foundation to deep RL. Specifically, we introduce a novel loss function, derived from the log- barrier formulation, which serves as alternative to the conventional mean-squared- error Bellman loss in deep Q-network (DQN) (Mnih et al. 2015) and deep deterministic policy gradient (DDPG) (Lillicrap al. 2015). This yields new deep RL algorithm within the DQN and DDPG frameworks. The effectiveness of the proposed method is demonstrated through comparative evaluations with standard DQN and DDPG across multiple OpenAI Gym benchmark tasks. The experimental results demonstrate that the proposed method performs on par with conventional DQN across the evaluated environments, and achieves markedly superior performance in specific tasks. In addition, experimental results show that incorporating the proposed method into DDPG yields markedly improved learning performance compared to the conventional DDPG algorithm in a wide range of tasks, Finally, the main contributions are briefly summarized follows: (1) Log-barrier LP for MDPs & error bounds: we introduce a novel log-barrier formulation of the MDP LP and derive rigorous error bounds for the approximate solution, explicitly quantifying how the approx- imation error scales with the barrier weight 17. (2) Analytic properties & convergence: We prove structural properties of the objective (convexity, local strong convexity, local Lipschitzness, convex feasible domain) and show exponential convergence of deterministic gradient descent in the tabular setting. (3) Preliminary deep-RL evaluation: we propose a deep-RL variant (log-barrier loss) and provide empirical results showing stable training and, in several enviromments, superior performance to standard deep-RL baselines.
2 RELATED WORKS
Research on MDPs has traditionally been dominated by dynamic programming (DP) methods based on the Bellman equation (Bertsekas and Tsstssklis 1996. Puterman 2014, [Sutton and Barto 1998), which underpin classical RL. algorithms and modern deep RI. methods such as DQN (Mnih et al.) 2015), but these approaches can become less flexible in large-scale or constrained settings. As an alternative, linear programming (LP) formulations of MDPs (Puterman) 2014) have been studied extensively: De Farias and Van Roy (2003) introduced approximate linear programming (ALP), which reduces the number of decision variables by using linear function approximations; Malek jet al.) (2014) further exploited the dual LP with stochastic convex optimization methods in the average-cost setting, showing performance guarantees relative a restricted policy class; Lakshmi-
2

---

Published as a conference paper at ICLR 2026
narayanan al. (2017) proposed the linearly relaxed ALP (LRALP), which alleviates computational load by projecting constraints into a lower-dimensional subspace while controlling approximation error. More recent developments have advanced convex formulations such convex Q-learning (Lu et al. 2021 2022), logistic Q-learning (Bas-Serrano et al. 202T), and primal-dual algorithms (Wang and Chen 2016 Lee and He 2018 Serrano and Neu 20200] Neu and Okolo (022) with growing attention in offline RL where environment interaction is limited (Nachum and Dail 2020; Zhan et al.,
2022 Ozdaglar et al., 2023) Gabbianelli et al. 2024). In parallel, optimization and RL communities have explored barrier-based techniques: the log lor-barrier method is classical tool in convex opti- mization (Boyd and Vandenberghe 2004; Nesterov 2018 [ertsekas 1999), and has recently been adapted for safe RI., e.g., Zhang al. (2024a b) introduced constrained soft actor-critic variant us- ing a smoothed log-barrier for stable constraint handling continuous control tasks. Despite these advances, existing L.P-based approaches have not leveraged barrier functions to resolve inequality- constrained formulations, and existing barrier-base RL methods have not been applied to the LP representation of MDPs. Our work closes this gap by introducing log-barrier reformulation of the LP approach to MDPs, yielding an unconstrained objective amenable to gradient- optimization while retaining the structural advantages of LP formulations.
3 PRELIMINARIES
3.1 MARKOV DECISION PROBLEM
We consider the infinite-horizon discounted Markov decision problem (Puterman 2014) and Markov decision process, where the agent sequentially takes actions to maximize cumulative discounted re- wards. In a Markov decision process with the state-space S := {1.2. |S]] and action-space A := f1,2..... .. [A[], where [S] and |A| denote cardinalities of each set, the decision maker lects an action a E A at the current state E S, then the state transits to the next state s' E S with probability P(s'|s, a), and the transition incurs reward ((s,,,,") E R, where P(s'|s, a) is the state transition probability from the current state 8 E S to the next state s' E under ac- tion E A. and r(s, a, s') is the reward function. For convenience, we consider a deterministic reward function and simply write r(Sk, G 8k+1) =: Tk+1, k E 10, A deterministic pol- icy, π S - A, maps state s E S an action (s) E A. The objective of the Markov decision problem is to find an optimal policy, n², such that the cumulative discounted rewards over infinite time horizons is maximized, i.e., n" == arg maxxee E 1 2 |rr++1 m].. where y E [0, the discount factor, θ is the set of all deterministic policies, (sg, ao. $1, ai..... is a state-action trajectory generated by the Markov chain under policy म, and B[-|T] is an expecta- tion conditioned on the policy æ. Moreover, Q-function under policy is defined as Q" (s. E E 7 7 s0 = s, 0g a, (s,a) E S x A, and the optimal Q-function is defined as (s) = Q=" (s, for all (s,a) E x A. Once Q* is known, then an optimal policy can be retrieved by the greedy policy (s) arg max,e.4 (s a). Throughout, we assume that the Markov decision process is ergodic so that the stationary state distribution exists. In this paper, we define upper bound of the reward function as [r(s, a, s')l S Tmaxs (s, a, 8') AxS.
3.2 LP FORMULATION OF MDP BASED ON Q-FUNCTION
In this paper, for the sake of clarity and brevity, the majority of technical proof's are presented in Appendix.
well known that a Markov decision problem (MDP) can be formulated as linear program (LP) (Luenberger et al. 1984 Puterman, 2014). While the LP formulation is typically expressed in terms of the value function (Puterman, 2014), one can also consider an LP formulation based on the Q- f-uuctio... To this end, let us consider the following LP:
Σ ((s,a)((s,a)
min AA
(I)
(K.))ESAA
subject to R(s. a) + ty
Σ P(s))s Q(s,a), ".a.a')eSAAA KES
where R(s, a) is the expected reward conditionend on (s, a) E S x A, p denotes any probability distribution over S x A with strictly positive support. For convenience, in this paper, we define the
3

---

Published as a conference paper at ICLR 2026
following Bellman operators
(TQ)(s,)):= :=((s,a) +y
Σ p
s'ES
== (FQ)(s,add)= +7
Σ #'ES
Note that we can always find a strictly feasible solution of the above LP. For instance, if we choose Q(s, a) Tmarte 0, (s, a) 8x with any > 0, then a(s,a)+77)))) +++ P(s'|s, (s', aa)- Q(s,a) = R(),a) Tmax E < O. The LP formulation in Equation (1) constructed on the basis of the Q-function (Lee and He 2019 2018 8) has not been extensively studied compared to the LP formulation based on the value function. Although the LP formulation involving the Q-function was considered in Lee and He 2019 2018), it differs significantly from the LP discussed above. In particular, the L.P in Lee and Hel (219 2018) involves not only the Q-function but also an addi- tional value function, thereby employing a somewhat more indirect approach compared to the above formulation. Accordingly, we begin by briefly introducing several theoretical properties and inter- pretations of this formulation, prior to presenting our main results. As a preliminary but fundamental result, it is straightforward to show that the solution of the above LP is unique and corresponds to the optimal Q-function, Q" (Section A). addition, the dual (Boyd and Vandenberghe, 2004 Chap- ter 5) of the above LP can be derived in the following form (Section B
1-7
Lemma 1, The dual problem of the L.P in Equation (1) is given by
Σ
as, a, ((s,))
max X20
(ESAA
subject to
X(s,a,)) -7
Σ (iJ)ESXA
=(sl = ((s,a)
(3)
EA
The original LP in Equation (1) referred to the primal LP (or primal problem), while the above LP in [Equation (2) is called the dual LP (or dual problem). The variable Q in the primal LP is referred to the primal variable, while the variable À in the dual LP is called the dual variable. We can examine several important properties and interpretations of the dual LP. For instance, the optimal dual variable X corresponds probability distribution, which represents the stationary llate-actionneet-eee next-action distribution under the optimal policy x constructed from the dual variable as follows:
T" *-1s)) ==
('(1.)
(s E.cA (F.0))
(*( E.cA (s.a)
EoeA (s,a)
where \' a) = Ee'Ed 2"(s, a')). We note that when the optimal policy is determinis- tic, then the above policy becomes one-hot vector indicating the optimal action (Chen and Wang 2016). Similarly, if Q" is the primal optimal solution (the solution of Equation (D), then (*(s) arg max (s, a) likewise induces optimal policy, Additional details can be found in Appendix (Sections C and
4 LOG-BARRIER FUNCTION APPROACH
In the previous section, we provided a brief discussion of the LP formulation in Equation (1) based on the Q-function. We now turn to the main results of this paper. First of all. note that Equation (1)
involves inequality constraints. A common approach to handling such constraints is to introduce the Lagrangian together with Lagrange multipliers, or dual variables (Bertsekas) 1999 Boyd and Vandenberghe| 2004).. One then seeks the primal and dual variables through first-order primal-dual iterations (Kojima et al. 1989). However, this method typically suffers from slow convergence and does not, in general, guarantee convergence in many practical settings (Applegate et al. 2021) Another practical and widely used approach to handling inequality constraints is the use of barrier functions, most notably the fog-barries function (Boyd and Vandenberghe/ 2004]. This method imposes large (or even infinite) penalty on variables that violate the inequality constraints, thereby forcing the iterates to remain within the feasible region while enabling the optimization problem to
4

---

Published as a conference paper at ICLR 2026
be solved. In this paper, apply the log-barrier function to the LP formulation in Equation (1) and we undertake an in-depth study and interpretation of this barrier- based approach to solving MDPs. This line of research represents approach that has not yet been addressed in the existing literature.
The log-barrier function a classical tool in constrained optimization used to handle inequality constraints. For constraint of the form g(x) 0, the log-barrier introduces penalty term (p(=)) == -n In)(((())) where ? > 0 is a barrier parameter. This function approaches infin- ity g(x) gets close zero, and thus, prevents the iterates from leaving the feasible region. As " decreases, the solution of the barrier-augmented problem converges to the solution of the original constrained optimization problem. Moreover, one can prove that the log-barrie function (p()) == In( (-x) is strictly convex in its domain {ar E : I < 0}. Using the log reg-barrie function, the inequality constraints can integrated into a single objective function as follows:
fQ(2)= = Σ (SxA)
Q(s
Σ (3.0.'))SAAXA
w(s, a a'), ((FQ) -((s))))).)))((.))))))
where 1) > 0 is the barrier parameter (weight) and wiss d') > 0, (s, SSXXXA are weight parameters of the inequality constraints, which are introduced order to consider random sampling approaches in stochastic implementations later. For instance, in the deep-RI. variant later, w should be interpreted as the empirical distribution of state-action pairs induced by the replay buffer or by mini-batch sampling. Moreover, objective function fnj has the following domain:
also set wss, a, a') for all (s,a, E xxxxxxxx A. The
D = fo f
(FF) & RISIIA!
((s, < <0, 3).
which can be also seen as the strictly feasible set. Moreover, it can be shown that D is convex, open, bounded below, and unbounded above. Moreover, the objective function fn is strictly convex in D. To proceed, let us define the level set of the objective function for >> 0
L. {Q E D: (Q) c].
We can also establish that L. is convex, closed, bounded, and fn is strongly convex and has Lipschitz continuous gradient in Le with any > O. The detailed theoretical analysis is given in Sections E
G
The introduction of the log-barrier function enables reformulate the MDP unconstrained optimization problem. Consequently, a natural approach to address this problem is to employ gradi- ent descent. For this purpose, first establish the closed-form forem expression of the gradient presented in the following lemma, which can be proved via direct calculations.
Lemma 2. The gradient of fr(Q) Q
is given by
p(s..) p(s,a)+1 +7 (v =
Σ
Σ an(s,a,a') a'EA
(d(A))SSA
for (s, a) E A, where (n Q[s.a))
qu((s,,a))
Using the closed-form gradient obtained above, we can gain insight into the solution of the opti- mization problem. To this end, us assume that Q,, a minimizer of (Q(
Q == arg min (Q)
The corresponding first-order optimality condition, vef( 0, is given by
(val(9)lo=o)) (s, =p(s, a) +
Σ
,, P(s)s, - Σ (x,,aaa')
(d(x))
a'ES
=0, (s, S A.
where \s)))a,'')= ((..0) (FQ.))((PQQ,),...))))
qp((s.000))
As mentioned earlier, since f,, is strictly convex over the domain, this first-order condition consti- tutes the necessary and sufficient condition for the optimal solution. We observe that the above
5

---

Published as a conference paper at ICLR 2026
equation is exactly identical the equality constraints in the dual problem with X, the dual vari- ables. In other words, An approximates the true optimal dual variable X Therefore, from the above solution 2 we can consider two types of policies. Interpreting the solution as an approximate solution to the LP formulation of the MDP, we may derive greedy policy based on Q,, as well as a policy constructed from the approximate dual variable X, which also depends on Qn. Hereafter, we refer to the policy induced by the primal optimal solution Qn the primal 17-policy, and the policy induced by the dual optimal solution X, as the dual 17-ollcy. particular, the primal n-policy, which is deterministic, can be written as
(+) arg max (s,
and the dual 17-policy, which is stochastic, can be written as
(n(1.1) (x.0)
(x.2))) Σ A,(s,))
An Al) Σ (,(s,a)
(-1s) =
Σ OEN
..A
where as) as, a, d'). By minimizing the above objective function, we can obtain an approximate solution of the primal LP. Since the objective function is strictly convex, the approx- imate solution can be efficiently found with gradient descent algorithm. We can prove that, under certain mild conditions, this gradient descent with a constant step-size converges exponentially Qn (Sections H andd]] D
Next, note that the minimizer of the log-barrier-basee -aaee objective funetion provides only an approx- imate solution to the LP formulation of the MDP, rather than an exact one. Nevertheless, by de- creasing the barrier parameter r). the solution is permitted to approach the boundary of the inequality constraints, i.e., the equality constraints, and thus progressively converges to the exact LP solution. In the limit as 7 + 0, the solution converges to the true solution of the MDP. Building on this insight, we can express the error between Qn, and Q" as a function of 17. The following theorem establishes such an error bound between Q, and Q", and, in addition, presents bound on the Bellman error corresponding to Q., (Section
Theorem 1. We have
w(s,a,a) (ES
Σ
1. min u(s,a,a') < Qn -00n-101__ 10. s (6xxxx)
mi
(1+72
w(a.aaa)
min w(s, a(s,a,a) 0 122--17 -o--Tr@ (sxx,"))SxAxA
2. 17(1 71
From the above result, ity error and the Bellman error. Both bounds depend on and are shown to be linear functions of 1)- Hence, as - O, the upper and lower bounds of the error norms decrease linearly, i.e., Q, Q"- Moreover, these bounds also reveal the interplay between the bounds and other hyperparameters. In the above result, we established bounds on the norm of the error. In addition, we can also de- rive upper and lower bounds on the MDP objective function itself. The following theorem presents such bounds for the objective functions corresponding to the primal p-loicyy and the dual pollicy,, expressed relative to the optimal objective value J (Section K)
establish both upper and lower bounds the loo -nom of the optimal-
Theorem 2. We have
1. Jx 1
Σ
W/ a(s,,,a' J
(Na,)))ESxA
n(1+7)
Σ v(s.aaa)
2. J=
J < Jr
m(14) Σ
w(s.a,")
3.
$ Jr - - <n
E
w(s,a,e²)
(SSAAA)

---

Published as a conference paper at ICLR 2026
The above theorem shows that the upper and lower bounds of the objective functions corresponding to the primal 17 p-policy and the dual 77-pliccy also depend linearly on 1). Hence, as r7 - 0, the objective functions associated with both the primal and dual 17-policies converge to the optimal objective value J
POLICY EVALUATION
Although the primary focus of this paper is computing the optimal Q-function, the proposed framework is equally applicable to policy evaluation. In this section, we therefore provide brief account of its application the policy evaluation setting. To this end, let us assume given policy m and consider the problem of finding its corresponding Q-function Q". This problem can be solved through the following LP:
Σ p(s, (ssa)Q(s,a)
min QERISI
(s,))SXA
subject to (T")) < Q(s,a), (s, E 8 A,
where R(s, a) is the expected reward conditioned on (s,a) E 8 A. p denotes any probability distribution over S x A with strictly positive support, and
(TT))(s = R(s, a) +7
Σ (')SSA
P(s'ls, P(s(ss.0)m(d())))((s.c)
(
Then, analogous to the case of finding the optimal Q-function, we can derive the following results through a similar theoretical analysis. In particular, we can prove that the unique optimal solution of the above LP is Q". Moreover, let us consider the objective function with bor-barrier function
(Q)
Σ Q(s,a)p(8;,) +1
Σ
a( ((T*Q)(s, a) Q(x,a))
(s.a)ESXA
(sa))SxA
where v 0 is weight parameter and w(s,a) > 0, (s. S A weight parameters of the inequality constraints. Then, we can prove that the corresponding optimal solution Q arg men J (Q) approximates Q-. Many of the analytical results established in the previous section can be applied in a similar manner. For brevity, all related details are provided in Section
DEEP RL VARIANTS
Thus far, we have provided a theoretical analysis of the approximate solution to the LP formulation of MDPs using the log- log-barrier function. Although the primary focus of this paper is on theoretical analysis with tabular setting, this section we further explore the potential extension of the proposed framework to deep RL. In particular, we introduce a novel DQN algorithm inspired by the idea of standard DQN (Mnih et al., 2015). Note that when a deep neural network is used, the model becomes nonlinear function of the parameters 0, and the precise theoretical results derived for the tabular setting no longer apply directly. Nevertheless, the tabular analysis in the previous sections provides useful intuition and insights deep RL extensions. Similar to the conventional DQN framework, we employ an experience replay buffer and mini-batch sampling B. Furthermore, in the definition of fny the probability density is replaced with samples from the mini-batch, which leads to the following loss function:
L(0) B
Σ
(Qe(s. + no(r 2Qo(s' Qo(ss
(s..r.
where B is a mini-batch uniformly sampled from the experience replay buffer D, |B] is the size of the mini-batch, Qo deep neural network approximation of Q-function, 0 E I is the parameter to be determined, and (s,a, is the transition sample of the state-action-reward. next state. The loss function can be seen as a stochastic approximation of fy, where p and w can be set to probability distributions corresponding to the replay buffer. However, this stochas- tie approximation is generally biased because it approximates a function in which the state tran- sition probabilities appear outside the log-barries function. In fact, by applying Jensen's 's in- equality, we can show that the above loss function essentially an unbiased stochastic approx- imation of an upper bounding surrogate funciton of f, (Section M). However, note that in the

---

Published as a conference paper at ICLR 2026
deterministic case, the upper surrogate function coincides with the true objective function with zero Jenson gap. In this setting, L(Ø) becomes an unbiased stochastic approximation of fn- For example, dynamical system expressed as Sk+1 = f(s;, a&) is deterministic, and hence the upper hound coincides with fn- Therefore, the loss function T. can be regarded as an un- biased stochastic approximation of fn as follows: fn(Qo) (ssa))SxA Qo(s, a)p(s, + L(0). Another
" (=s,,a")) w(s, a, d') (r(s,a, a, [(s a)) + 7Qu(J (s.)), .), - Qa(s, difference from the conventional DQN is that the algorithm proposed in this paper does not employ larget variables, and hence the update of target variables is also omitted. Apart from this distinc- tion, the remaining components are similar to those of standard DQN. The overall pseudocode of the algorithm and implementation details for stabilization of the algorithm are summarized in [Section N
Next, we briefly discuss the extension of policy evaluation, previously introduced. to the deep RL setting. In partieular, we consider its potential application DDPG (Lillierap al. 2015). Here, the policy is deterministic, and the following loss function can be formulated:
Trente (0; xx)
Σ (s,a,T.*")EB
(Qo(s, mp(r + Rols' (x(6)) - Qo(s,))).
B
where " denotes the deterministic policy being learned, and X is its parameter vector. A discussion similar to that of the preceding loss function applies here, and the corresponding modified DDPG algorithm along with its implementation details is provided in [Section O Finally, we note that we can heuristically apply several alternative choices (e.g., SoftPlus) instead of the log-barrier func- tion. While these alternatives often yield reasonable performance, the proposed method typically performed better in our experiments.
7 EXPERIMENTS
To validate the performance of the proposed method, we conduct experiments in both discrete and continuous control environments. We implement deep RL. variant described in Section 6 naming our algorithms Log-barrier DQN and Log-barrier DDPG, respectively. For discrete con- trol tasks, compare our algorithm with the standard DQN (Mnih et al. [2115), and for continuous
control tasks, we benchmark it against the standard DDPG (Llliccrap et al. 2015). Additional al-
gorithmic details are provided in [Section N and Section O in Section P
with detailed hyperparameters listed
Log-Barrier DQN For our DQN experiments, we chose five environments form the Gymna- sium library (Acrobot-vl, CartPole-v1, Lunarl MountainCar-v0, and Pendulum-v1). For MountainCar-v0, we replace the original sparse reward with a dense shaping reward, and for Pendulum-vl we discretize the continuous action space to enable DQN training. As shown in Fig- ure the results reveal a remarkable point that the Log-barrier DQN demonstrates rapid adaptation and significant stability in the CartPole environment, where the agent's survival is threatened by critical angle criterion. We hypothesize that this is due to the sharp decision boundary between states where the agent survives and states where the episode is terminated. Standard DQN, which relies on Bellman updates with an mean square error (MSE) loss, can suffer from error propagation across this boundary. In contrast, the proposed approach, which uses the IP form, can globally mitigate this hazard. Instead of estimating value from neighboring states, our method directly minimizes its objective while satisfying the LP constraints.
In the continuous control experiments, we applied the proposed method for the policy evaluation task DDPG. The resulting DDPG variant demonstrated superior performance on four complex MuJoCo environments (Ant, Walker2d, HalfCheetah, Humanoid), while showing no significant advantage on the simpler Hopper task, as shown in Figure 2] We attribute this success to fundamental property of critic update mechanism of the proposed algorithm. We conjecture that the core of the advantage arises from the fact that the LP form inherently a minimization objective, which naturally counteracts the Q-value overestimation bias prevalent in actor-critic methods. Stan- dard DDPG critics learn by minimizing the MSE to a target value, a process that simply follows the target without regard for its potential bias. If the target is inflated, the critic learns an inflated value, leading to a feedback loop of compounding overestimation. In contrast, the proposed approach min- imizes the value function itself, subject to the constraints of Bellman consistency. This systematic
Log- Barriarrier DDPG
8

---

Published as a conference paper at ICLR 2026
AC Acobbe--11
CantPolev1
LunanLanderog
NoumainCr-00
Penduuu--11
-000
-200
202
-433
-300
2200
-400
305
-200
-033
-250
-000
-200
Epiabb
D0N
Log bonter DQN
Figure 1: Learning curves comparing the Log-barrier DQN and standard DQN the Gymnasium control environments. Each curve represents the average return over 10 random seeds, with the shaded area indicating one standard deviation from the mean.
search for the tightest and lowest possible Q-values that still satisfy the dynamics acts powerful, implicit regularizer against optimistic value estimates. This results in a more conservative and stable critic, which provides more reliable gradient the actor, leading superior final performance. Consequently, this allows the proposed method to overcome the limitations standard DDPG, and successfully solve environments such as Ant and Humanoid that were previously thought to be beyond its capabilities.
AntrvS
HallCheetah-v55
Hopper-u5
Humanoid-vs
Wallerrddv55
6000
3002
5000
5000
2003
4000
4000
4200
3000
3002
2000
2002
1002
1002
Id5
DDPG
Log barrier DDPG
Figure 2: Learning curves comparing the Log-barrier DDPG and standard DDPG on the Mujoco continuous control environments. Each curve represents the average return over 8 random seeds, with the shaded area indicating one standard deviation from the mean.
CONCLUSION
In this paper, we have developed theoretical framework for solving MDPs via their LP formulation using log-barrier term. Reformulating the I.P into a single objective fnz we have showed that gradient descent efficiently produces approximate solutions Q, and prove error bounds (including I1 - oo) that scale linearly with the barrier parameter 77. We have also characterized primal and dual approximate solutions, their induced policies, and proved structural properties of fy (e.g., convexity, local strong Sonvexity/L.ppscitzeess
together with exponential convergence of gradient descent in the tabular setting. Practically, we have derived a novel log-barrier loss for deep RL and evaluate it in DQN and DDPG: the method matches standard DQN in most cases and outperforms conventional DDPG in several tasks. While experiments are limited scope and the approach requires careful hyperparameter tuning, the empirical results support the promise of the log barrier formulation: fuller lcrge-scale validation and robustness improvements remain important directions for future work.


Reviews:
[{"review_id": "GqWT64Ush8", "reviewer": "Reviewer_UmFB", "summary": "The paper reformulates the Q-LP for discounted MDPs using a log-barrier to combine all Bellman inequality constraints into a single unconstrained objective. For this unconstrained optimization problem, the paper studies its theoretical results and proves that both the upper and lower bounds scale linearly with the barrier parameter. They also propose barrier-style DQN/DDPG variants and report empirical gains on several MuJoCo tasks.", "questions": "1. The main theoretical results show that the upper and lower bounds scale linearly with $\\eta$, but the proposed algorithm only uses a fixed $\\eta$. Are there any potential concerns on using a decreasing sequence of $\\eta$ in the practical algorithm?\n\n2. If possible, would you list the technical contributions of the paper, such as new frameworks or proof techniques?", "limitations": "", "rating": 4, "confidence": 3, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "1. Theoretical soundness: Provides a clean log-barrier reformulation of the Q-LP, with proofs of convexity/strong-convexity on sublevel sets, Lipschitz gradients, exponential gradient-descent convergence, and linear-in-$\\eta$ upper/lower bounds.\n\n2. Conceptual clarity: The problem is well specified and the pipeline—Q-LP → barrier objective → first-order conditions → approximate duals/policies—is presented coherently and is easy to follow.\n\n3. Practical algorithmic instantiation: The barrier idea is instantiated with minimal changes to standard DQN/DDPG, making it straightforward to implement.", "weaknesses": "At present, I do not find the contributions sufficient for ICLR. As a theory-focused paper, the motivation and insights feel limited. That said, I may be missing something, and I am happy to adjust my score if the concerns below are addressed.\n\nIn particular, my main concerns are as follows:\n\n1. Motivation and positioning. The motivation for introducing a log-barrier is not fully convincing. I appreciate that the LP formulation of MDPs is less explored, but it remains unclear what concrete advantages the log-barrier brings over standard alternatives. In Section 4, the paper asserts that Lagrangian or primal–dual methods can be slow or lack convergence guarantees, but no references are provided and there are no experimental comparisons. I suggest to expand this discussion with specific contrasts in performance metrics such as convergence speed, required assumptions, dependence on $|\\mathcal{S}|$, $|\\mathcal{A}|$, computational cost, and practical stability.\n\n2. Empirical support and ablations. The advantages over standard DQN/DDPG in Section 7 are stated but not theoretically grounded, and some claims read as conjectural. The paper also lacks ablation studies. It would help to include controlled synthetic simulations/experiments where the barrier variants have a clear, interpretable edge, compared to standard benchmark methods. \n\n3. The theoretical results do not appear to extend to the deep RL setting in Section 6, as the Q function is not guaranteed to be convex as a function of $\\theta$. I suggest to add some discussions for the neural settings.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "ccQvobHzUR", "reviewer": "Reviewer_Khvy", "summary": "The paper proposes a new approach to solving the Bellman optimality equation in tabular Markov decision processes.\nInstead of addressing the problem iteratively via dynamic programming, the authors formulate it as an LP.\nThey then reformulate the LP—with its inequality constraints—into an unconstrained optimization problem using a log-barrier, and obtain a solution by gradient descent.\nLeveraging the convexity of the log-barrier function, the paper shows that the resulting objective is strongly convex (and hence strictly convex), which in turn justifies the effectiveness of gradient-descent–based optimization.\nMoreover, by establishing the relationship between the approximation error of the proposed solution and the barrier parameter, the paper demonstrates convergence toward the optimal solution.\nEmpirically, the authors validate the approach by modifying the DQN objective with a log-barrier term and evaluating performance across several environments.", "questions": "1. On line 128, $\\pi^\\ast$ is defined as the greedy policy with respect to the optimal value, whereas on line 182 it is described via a probabilistic policy induced by the dual optimal variables. If $\\pi^\\ast$ is deterministic, can it still be represented in the form given on line 182 through $\\lambda^*$?\n\n2. As I understand it, $w$ functions like a hyperparameter, similar to $\\eta$. Beyond the uniform choice (e.g., $w = 1/(|S||A|^2)$), what alternatives are reasonable, and what implementation differences would they entail? How is this parameter chosen in the actual experiments?\n\n3. I do not fully understand the claim that standard DQN struggles with error propagation at sharp decision boundaries, while the log-barrier LP approach avoids this issue (line 396-401). Could the authors provide experimental evidence that directly supports this explanation?\n\n4. Intuitively, the log-barrier imposes a strong penalty for violating Bellman constraints, controlled by $\\eta$. Would using other penalties such as hinge or softplus lead to different empirical behavior or performance?\n\n5. Why does the proposed method underperform (or perform less favorably) on the Hopper task? What characteristics of Hopper differentiate it from the other tasks in ways that affect the method?\n\n6. Figure 3 suggests that smaller $\\eta$ yields tighter bounds. In practice, should $\\eta$ therefore be set as small as possible? What criteria were used to select the barrier parameter in Tables 1 and 2?\n\n[Minor]\n\n1. On line 209 the log-barrier function is denoted by $\\phi$, whereas in Eq. (4) it is written as $\\varphi$.", "limitations": "", "rating": 4, "confidence": 3, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "1. In terms of originality, this work investigates an LP-based route that has been relatively underexplored for solving the Bellman optimality equation. In particular, it introduces a new method that applies log-barrier techniques from convex optimization and develops a corresponding theoretical foundation.\n\n2. While I have not thoroughly verified every proof in the appendix, the paper provides convergence guarantees for the proposed method. This foundation appears promising for subsequent research in the RL community on LP-based planning and related topics.\n\n3. The manuscript is written clearly and is relatively easy to follow. The experimental section supports the claimed advantages of the method.", "weaknesses": "1. Motivation of the proposed approach should be supplemented. In one sentence, the proposed approach can be viewed as: cast the Bellman optimality equation as a constrained LP, convert it to an unconstrained problem with a log-barrier, and solve it by gradient descent. Although the theoretical foundation is established, the motivation for preferring this route over classical DP is not fully developed. A discussion comparing convergence speed and computational complexity to DP-based methods would strengthen the case for the approach.\n\n2. More direct empirical validation should be added. Additional experiments could more directly isolate the contribution of the log-barrier loss. As the authors note, the log-barrier DQN differs from standard DQN not only in its loss but also, for example, in not using a target network. Hence, it is not entirely clear that the observed results are driven by the barrier term itself. A tabular setting directly comparing the proposed method to DP would provide more definitive evidence of its utility.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "pP881yMSPn", "reviewer": "Reviewer_csmF", "summary": "This paper introduces a log-barrier-based reformulation of the LP formulation for MDPs, replacing the inequality constraints with a single-objective function fη. The authors provide a thorough theoretical analysis of the approximation error, convergence and policy performance, and extend the framework to deep reinforcement learning (RL) via novel DQN and DDPG variants with empirical validation on Gymnasium and MuJoCo tasks.", "questions": "1. How does the computational cost of the log-barrier approach scale with the size of the state and action spaces? Are there any extreme settings where the method becomes computational costly?\n\n2. What is the performance of log-barrier function method compared to other LP-based or primal-dual RL methods in terms of sample efficiency and computation time?", "limitations": "", "rating": 8, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. The use of log-barrier functions to transform the LP formulation of MDPs into an unconstrained problem is innovative and a comprehensive theoretical interpretation has not been widely explored in the RL literature.\n\n2. The paper provides a comprehensive theoretical foundation, including error bounds, convergence analysis and policy performance guarantees. The proofs are detailed and well-structured in the appendix.\n\n3. The paper is well-organized with a clear statement of formulation and a clear presentation of analysis.\n\n4. The authors evaluate the proposed method on both discrete and continuous control real-world tasks, demonstrating the competitive or improved performance over standard DQN and DDPG.", "weaknesses": "In general, broader evaluation on more real-world datasets is needed to strengthen the claims.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "x9UblSdK07", "reviewer": "Reviewer_fCTj", "summary": "This paper proposes a novel framework for solving Markov Decision Problems (MDPs) through a linear programming (LP) formulation augmented with a log-barrier function.\nThe authors show that this reformulation converts the constrained LP into an unconstrained optimization problem, which can then be efficiently solved using gradient descent.\nTheoretical results include upper and lower error bounds on the approximate Q-function and policy performance, both shown to scale linearly with the barrier parameter.\nThe framework is extended to deep reinforcement learning, yielding new variants of DQN and DDPG that replace the standard Bellman loss with a log-barrier–based objective.\nExperimental results demonstrate competitive or superior performance in several OpenAI Gym and MuJoCo tasks.", "questions": "How sensitive is the convergence behavior to the choice of the barrier parameter $\\eta$ and step-size in practice?\nCould adaptive or annealing strategies improve stability?\n\nCan the proposed approach be generalized to constrained RL or safe RL problems where inequality constraints are inherent to the objective?\n\nHave the authors considered how the proposed loss compares, in practice, to other convex formulations such as convex Q-learning or logistic Q-learning?", "limitations": "", "rating": 8, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The application of log-barrier methods to the LP formulation of MDPs is original and fills a gap in reinforcement learning literature, connecting classical optimization theory to RL in a principled way.\n\nExtending the framework to DQN and DDPG variants demonstrates the practical potential of the theoretical findings.\n\nThe empirical results show tangible benefits in stability and performance, particularly in complex continuous-control tasks.", "weaknesses": "The experiments are confined to a few benchmark environments.\nBroader testing (e.g., across more complex or stochastic settings) would strengthen the empirical claims.\n\nThere is little analysis isolating the contribution of the log-barrier term relative to standard LP or Bellman-based objectives.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Poster)