2
$\begingroup$

I encountered a question about solving CNF SAT using reinforcement learning: A state is a partial substitution to the variables, and each action is choosing an empty variable and set its value (to True or False). If the formula is satisfied the reward is 2, and if it's not, the reward is 0. The discount factor is $\gamma \in (0, 1)$

Does Q-Learning can solve the problem and converge to an optimal plan for any CNF formula? and what about other RL algorithms?

I think it will converge, but I am not sure if I am right.

Improve this question
$\endgroup$
1
  • $\begingroup$ So long as this can be modeled as a MDP process with finite state and action spaces, by TD based Q-learning's convergence theorem based upon stochastic approximation theory it's provably convergent albeit may be very slow since its combinatoric state space could be huge while reward is extremely sparse (need some heuristic search help such as A* or SAT solver or add some intermediate reward shape) and SAT is the first known NP-complete problem. But what makes you doubt it cannot be modeled as model-free RL? $\endgroup$
    – Double Knot
    Feb 24 at 4:02

0

Reset to default

You must log in to answer this question.