# How can I improve this RL algorithm?

This is the task: I have a unitary target matrix $T$, to decompose using matrices from a fixed (finite) universal set $\{M_i\}$, e.g. $T = M_6M_3M_9M_0$. The set is universal in the sense that one can reach any unitary with by combining its elements appropriately.

I wrote an RL algorithm with a policy network that I feed with the target $T$ and with the current "state" (i.e. the current product of the matrices that the policy chose), which returns the index of which matrix to pick next. In pseudocode, this is what I wrote:

reward = 0 state = Identity_matrix chosen_indices = [] for(i=0,max_episode_length,i++): prob_dist = policy(state,T) k = random_int(prob_dist) state = state * M[k] reward -= 1 if ||T-state|| == 0: reward += 100 end_episode() loss = discounted_rewards * cross_entropy([prob_dist],[one_hot(k)]) minimize(loss) 

I repeat this loop for several random examples of $T$ of which I know the decomposition. But, even if I limit $T$ to be a single matrix from the set, the policy learns a couple of them and then it stops learning, i.e. when I pick a new $T$, the average episode reward remains around zero.

I tried fiddling with the learning rate, the discount factor, the width of the policy network, nothing seems to make things work. What am I doing wrong?

• This seems like an endless question, unsuited for this platform. It does not work well for reviews and discussion. Also, you need to specify what "things" and "better" mean for you here. Can you formulate a specific question?
– Raphael
Aug 3, 2017 at 22:07

Your problem is known as the membership problem for the general linear group, which might be hard (i.e., no efficient algorithm is known), depending on which field you are working over. See https://cstheory.stackexchange.com/q/38000/5038. If we take $T=0$ and are working with $n \times n$ matrices, this is called the matrix mortality problem; it is undecidable for $n \ge 3$. See also https://en.wikipedia.org/wiki/List_of_undecidable_problems#Problems_about_matrices. So, in the general case, your problem is undecidable.
• I don't think that deciding if it is possible to get any matrix $T$ is decidable in general case, even if it would be non-zero. Aug 4, 2017 at 9:27
• Very fair comment. I should have specified that $T$ is unitary, and that the set to choose from is universal, so a decomposition always exists. The problem is how to find it! Aug 4, 2017 at 22:30