# Looking for an RL solution for sequence generation

I am looking for a proper reinforcement learning solution for the following problem:

Suppose I have a pool of candidate functions f \in Pool(it's like f1, f2, ... fn), and I am trying to synthesize several sequences of functions, each sequence contains arbitrary amount of f.

Given a sequence s, when deciding whether to extend s by appending a new function f and forming a new sequence s' = sf, I have the following reward scheme:

1. when F(s') = true, reward += 1

2. when T(s') = true, reward += 3

3. every time the sequence grows by one, I try to penalize by reward -= 0.5

In other words, I don't want each sequence s to be too long, but also will consider cases when special property F and T are satisfied.

I view this as a learning problem, and envision it can be solved by reinforcement learning techniques, such as DQN or so. But I am a newbie to this field and find it difficult for me to formalize this problem. Could anyone can shed some lights on this and what kind of reinforcement learning algorithms/scheme I can have a try? Thanks a lot. Any suggestion or advice will be appreciated.

To formulate your problem as an RL problem, we first need to index the functions from $$1$$ to $$n$$. This way, there would be $$n+1$$ actions in total, i.e. \begin{align*} a^i=\left\{\begin{matrix} \text{stop} && i=0\\ \text{add } f_i && 1\le i\le n \end{matrix}\right. \end{align*} Accordingly, state $$s_t$$ would be represented by a sequence of $$t$$ actions, where a final state ends with action $$a^0$$. Also, the reward at step $$t$$ (after doing action $$a_t$$) would be as follows $$r_t = \left\{\begin{matrix} -0.5 + 1_{F(s_ta_t)=True} + 3_{T(s_ta_t)=True} & a_t \neq a^0\\ 0 & a_t = a^0 \end{matrix}\right.$$

To prepare such a representation for a neural network, we need to represent the actions with one-hot encoding. Here is an example,

s = [
[0, 0, 0, 1, 0]  #a^1
[0, 0, 1, 0, 0]  #a^2
[0, 0, 0, 0, 1]  #a^0
]


which represents a final state with three actions (and four functions).

The tricky part of your problem is the ever-changing representation of the state. As an opposite example, for those video games that are studied in DQN paper, each state is a constant number of fixed-sized 2D images.

To solve this design challenge, we can opt for one of these two approaches (among possibly many others):

1. Limit the final length of states to $$T$$ and add a "not taken" action for those steps that are not taken (yet). For example,

 s = [
[0, 0, 0, 0, 1, 0]  #a^1
[0, 0, 0, 1, 0, 0]  #a^2
[0, 0, 0, 1, 0, 0]  #a^2
[1, 0, 0, 0, 0, 0]  #not taken
[1, 0, 0, 0, 0, 0]  #not taken
]


for four functions and $$T=5$$. This way, we end up with a total of $$n+2$$ symbols for representing each state.

2. Using a recurrent neural network (RNN, LSTM, etc.) to encode the variable-length states to a fixed length representation; this is similar to encoding variable-length sentences to a fixed length representation in NLP tasks.

The problem is now completely formulated as an RL problem along with taking some implementation challenges into consideration.

From this point onward, we can do RL by, for example, designing a 1D Dense network on top of RNN representations, or a 2D Dense or Convolutional network on top of fixed-length 2D representations (with $$m \times (n+2)$$-sized kernels that only move along actions, not along $$n+2$$ dimensions of one-hot encoding) that receives the representation of state $$s$$, denoted as $$\phi(s)$$, and outputs $$Q(s, a)$$ for each of $$n+1$$ actions, the same as DQN paper (see Algorithm 1: deep Q-learning with experience replay).

Extra notes

1. You may take a look at this post for feeding variable-length multi-dimensional sequences to LSTM using Keras.