Sparse linear systems are normally solved by using solvers like MINRES, Conjugate gradient, GMRES.

Efficient preconditioning, i.e., finding a matrix P such that PAx = Pb is easier to solve than the original problem, can drastically reduce the computational effort to solve for x. However, preconditioning is normally problem-specific and there is not ONE preconditioner that works well for every problem.

I thought this would be an interesting problem to apply RL since there are certain norms (e.g. condition number of matrix PA) to measure if P is a good preconditioner, but I could not find any research in this field.

Is there a specific problem why RL could not be applied?

  • 2
    $\begingroup$ Why would you do that? $\endgroup$ – Martin Thoma Oct 13 '18 at 8:48
  • $\begingroup$ You are right, I was wondering about a different question and went to far. I will restate my question. $\endgroup$ – timudk Oct 13 '18 at 18:19

Reinforcement Learning is a method for learning to perform beneficial actions in an environment. One way this is accomplished is by learning to predict useful actions as a function of the observed state of the environment. Another is by learning to predict the expected utility gain of doing an action in a particular observed state. Usually the fact that the agent executes a sequence of actions is exploited to learn more rapidly.

In contrast, the problem you describe is to solve a linear system of equations, which is to say, to learn some hidden values $x$ such that $Ax = b$ for known $A$ and $b$. Gradient decent is a natural way to solve this problem because it is easy to calculate the gradient, and, since the matrices and vectors have the same dimensionality, it is reasonable to expect that the optimization surface is smooth with a single global minima.

While RL techniques could be applied to solve this problem (I guess by predicting values of X in response to inputs b?), none of the usual features that privilege the RL approach over a standard supervised learning approach are present (there's no sequential relationship between datapoints, there's just a list of constraints essentially).

| improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.