Reproduce “Analysis of approximate linear programming solution to Markov decision problem with log barrier function” on OpenResearch

Turn your favorite coding agents into research agents that review literature, develop hypotheses, and run experiments.

Universal app for Apple silicon and Intel. Requires macOS 11 or later.

About this paper

Donghwan Lee, Hyukjun Yang, Bum Geun Park

Researchers at KAIST developed a log-barrier reformulation for Linear Programming (LP) solutions to Markov Decision Problems, providing a comprehensive theoretical foundation and enabling gradient-based approximate solutions. This approach demonstrated enhanced stability, reduced bias, and robustness to off-policy sampling when applied to deep reinforcement learning algorithms like DQN and DDPG.

Key insights

  • The log-barrier objective function is strictly convex with a Lipschitz continuous gradient within its domain, ensuring exponential convergence of gradient descent in the tabular setting.
  • Upper and lower bounds for the approximation error, $|| ilde{Q}_ eta - Q^*||_\infty$, and policy objective value deviation are established, showing linear dependence on the barrier parameter $\eta$, implying improved accuracy as $\eta \to 0$.
  • The LP formulation's inherent minimization objective acts as an implicit regularizer, mitigating Q-value overestimation bias and improving stability in actor-critic methods like DDPG.

Summary by alphaXiv.

Tip: change arxiv.org to autoarxiv.org in any arXiv abstract link to open the paper here.