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.