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 shed some light on this and what kind of reinforcement learning algorithms/scheme I can try? Thanks a lot. Any suggestion or advice will be appreciated.

  • $\begingroup$ can you explain what $T(x)$, and $F(x)$ are? Are the rewards long term rewards or immediate? If immediate rewards, you do not need reinforcement learning. $\endgroup$ – Zhubarb Apr 25 '19 at 9:51
  • $\begingroup$ Cross posted $\endgroup$ – Esmailian Apr 25 '19 at 16:01

Note: All of this only applies if your functions $F(s')$ and $T(s')$ involve the whole word and not only the last character that was just appended (as noted by Berkan).

You basically seem to want words over the alphabet $f_1, ..., f_n$. Let us simplify for a moment (in order for me to explain what algorithm you can use). Let us assume that you form words over the alphabet $a, b, c, (, )$ and you want the computer to learn to form valid bracket expressions with as many '(' and 'a' as possible, i.e. the reward could be something like

Reward(word) = amount of 'a' in word + 2 * amount of '(' in word

What you need (according to my experience) is something called 'RNN': a recurrent neural network. Many standard libraries like tensorflow or pytorch have implementations for that. The basic idea of RNNs is as follows: First of all we extend the alphabet to make it contain a very special start symbol '<' and an end symbol '>'. Instead of just a hidden layer you have a layer that has two inputs, a 'hidden' state and the last character in the word. They produce two things as output: The next hidden state and a distribution over the alphabet (from which we sample the next character to append). Then you sample the next character you append to the word from this distribution. When starting we use an initial hidden state $h_0=0$ and the first character is always '<'. Q graphical description might be helpful here:

enter image description here

With the 'wiggly curves' underneath the alphabet over the RNN I tried to state that the RNN produces a distribution over the (enriched) alphabet. In the first case it has a high probability for the character 'b' and for the character ')' so we assume that it samples 'b'. It then uses this as an input for the 'last character' in the next iteration and it uses the hidden state output from the first iteration as the hidden state input for the next one and so forth and so forth. Along the way we compute the rewards of the current word $r(w_t)$ as described above.

We keep doing this until either the RNN samples the end symbol '>' or until it has sampled a certain fixed amount of characters (say 100). Let $T$ be the last iteration and $w_T$ be the total word that was sampled. If $w_T$ does not terminate in the 'end' symbol then we assign a final reward of -1000 or so (just to make sure the RNN learns to terminate the words in '>'). Also, if the word $w_T$ is not a valid bracket expression then the reward is -1000 as well (in order to teach the NN to produce only valid bracket expressions). After each total sampling of a complete word $w_T$ we do one gradient descent step (consisting basically as a sum of the gradients at the times $t$ where the gradient at time $t$ is weighted with $r(w_t)$).

It is mathematically a little difficult to write down (and I am certainly not an expert in NN/optimization) the gradient (you also need a log because of the Law of Large numbers forcing you to write the thing you actually want as an expectation), however, the good thing is that you actually never need to do so as the library computes the gradient for you and you only have to weight it correctly :-)

I learned this approach from this paper: Deep reinforcement learning for de novo drug design. They even provide the skeleton source (which you have to simplify and change the reward function): GitHub (it uses PyTorch).

Coming back to the Reinforcement Learning setting/setup: You can formulate that in two different ways (as a Markov Decision Automata): Either there is only one state and for each character there is one action coming and going back to that state OR you can say that the initial state is '<' and essentially, every word is a state. See the following pictures, here, '*' means: some reward.

enter image description here

In the first case, the reward actually does not depend on the whole word but rather only on the very last character being sampled (this is only a valid model if the functions $T$ and $F$ only take the very last character into account... and I assume that this is probably not what you want). Hence, we should use the second automata. Since the RNN uses the hidden state and the hidden state theoretically depends on all the word sampled so far, in the Markov Decision Process emerging from the first automata, the RNN would not give a Markovian policy. However, that is not a 'showstopper' because the optimal policy mostly is a deterministic, stationary, markovian one (see Puterman, Markov Decision Processes, Chapter 6 if I recall correctly). However, the RNN becomes markovian and everything is as expected if we go with the second automata. That is another advantage of the second one.

Two closing remarks:

  1. The strategy with the RNN can be used in all Reinforcement Learning setups (like learning to play computer games like pong etc).
  2. If the stuff with the RNN is a little "too heavy" from your gut feeling then you should start with http://karpathy.github.io/2016/05/31/rl/. He basically uses the same strategy of 'rolling' over the sequence of states and sampling the next action but using a regular neural net. He also explains where the log in the gradient comes from (using non mathematical terms and without a formal proof however).
  • $\begingroup$ Dear Fabian. Thank you so much for your great answer! I appreciate it very much. One followup question regarding the performance of "RL" formulation and "RNN" formulation. So AFAICS, both of them need "training" and some fine tuning. But the differences lays that RL is unsupervised training while RNN is supervised, right? And I can expect RNN can generally outperform RL regarding the same problem, right? $\endgroup$ – lllllllllllll Apr 25 '19 at 20:22
  • $\begingroup$ Also, regarding "All of this only applies if your functions 𝐹(𝑠′) and 𝑇(𝑠′) involve the whole word and not only the last character that was just appended (as noted by Berkan).". That makes sense to me (although previously I ignored this critical assumption). Could you shed some lights on further explaination or theory behind this assumption such that I can learn more about that? Thank you! $\endgroup$ – lllllllllllll Apr 25 '19 at 20:23
  • $\begingroup$ " in the Markov Decision Process emerging from the first automata, the RNN would not give a Markovian policy." Could you please shed some lights on what does that mean? $\endgroup$ – lllllllllllll Apr 25 '19 at 20:47

Answering the three comments on the first answer:

  1. I do not understand what you mean by 'RL': This approach (using RNN' is one way of solving an RL problem. The RNN-training consists of two steps, yes. In the case of the bracket language it would consist of teaching it in a somewhat intermediate mode to generate only valid bracket expressions and then fine tune it towards producing valid bracket words with desirable properties (like having many brackets and/or a's and so forth). The intermediate part looks like this: We need a fixed training set of 'valid' expressions, i.e. for example <(aaa(b)c)>. Then we still cycle through the word using the hidden states and the output distributions and so forth but we do not sample a single character but we use cross entropy in order to measure 'how far off' the produced distribution over characters is from the one that actually comes next in the word. Then we do the usual thing: gradient descent. This is intermediate because we still cycle through the word like in the RL-step but it is also supervised because we know the 'actual' final word that the RNN is supposed to sample. In the second step, we actually use an RL-like prodcedure as described above and let it produce new words and punish it if it produced words with no desirable properties and we encourage it if it produces words with desirable properties. This is also "supervised" (at least I would not call it unsupervised) because you know the rewards!

  2. Let us assume that the functions $T,S$only look at the very last character. Then the automata sketched in the answer actually models the problem well. This can still be considered as a reinforcement learning problem but it is a very simple one: You do not need any fancy RNN or so... Just sample every character once, see what reward you get and then exclusively produce words that consist of the character giving the highest reward. In RL, people tend to use this example as a toy example nevertheless. This is called multi armed bandit. The multi armed bandit is nevertheless interesting however, because the rewards are probabilistic (i.e. random variables). However, if the functions take into considerations the different interactions between characters, then it is about the "path that you went" in order to arrive at this particular word rather than just about the character that you just appended and the problem becomes more complicated but also interesting.

  3. A Markov Decision Process (MDP) is a collection of random variables $(S_t, A_t, R_t)_{t \in T}$ where $T$ is either all of $\mathbb{N}_0$ or a finite set $\{0,1,2,...,M\}$ such that the random variables satisfy some properties (for example: at least every finite vector of them like $(S_0, A_0, R_0, S_1, A_1, R_1, ..., S_N, A_N, R_N, S_{N+1})$ needs to have a common density). Then we call $\pi_t(a_t|s_t) := p(a_t|s_t)$ the policy at time $t$, $\Delta_t(s_{t+1}|s_t,a_t)$ the transition probabilities and $\text{rew}_t(r_t|s_{t+1},s_t,a_t) := p(r_t|s_{t+1}, a_t, s_t)$ the rewards. One major assumption is that $\Delta_t$ actualy does not depend on $t$ and also that $\text{rew}_t$ does not depend on $t$. When we talk about RL in a very (the only in fact) clean, mathematical way, we talk about manipulating the policy $\pi = (\pi_t)_{t \in T}$ in such a way that some quantity gets maximized. Usually, that quantity is as follows: Given $\gamma \in (0,1)$, we want to maximize $$v_0(s) := E[\sum_{k=0}^\infty \gamma^k R_k | S_0=s]$$ A Markov Decision Automata (MDA) is an automata with actions, reward distributions and transition probabilities on the edges. What is the relationship between MDPs and MDAs? Can we ever construct (i.e. does it exist) something complicated like an MDP, a potentially infinite sequence of random variables that satisfy a lot of properties? Turns out that we can and that MDPs are exactly the trajectories of runs along MDAs. What do I mean by that? Well, let us assume that we are given an MDA together with a policy. Then we can actually create an MDP from that: First we construct an infinite sequence of iid random variables $\Delta_{a_t, s_t}$ that are distributed as given by the edge from the state $s_t$ using action $a_t$. We also create iid random variables $R_{s_{t+1}, a_t, s_t}$ that are distributed as given on the edge leading from state $s_t$ to $s_{t+1}$ using action $a_t$. We also create random variables $P_{t, s_t}$ distributed as $\pi_t(\cdot|a_t)$ describes. We also assume that we are given the initial distribution (i.e. random variable) for $S_0$. Given the random variable $S_t$ we define $S_{t+1}, A_t, R_t$ as follows: Then we put $A_t(\omega) = P_{t, S_t(\omega)}(\omega)$, $S_{t+1}(\omega) := \Delta_{\pi_t(A_t(\omega), S_t(\omega))}(\omega)$, $R_t(\omega) := R_{S_{t+1}(\omega), A_t(\omega), S_t(\omega)}(\omega)$. It can be shown that this weird collection of random variables then indeed is an MDP. For a sketch of the proof you might want to check out the simpler case of Markov Processes: https://mathoverflow.net/questions/292942/markov-processes-construction-of-the-state-variables. That is what I mean by 'the MDP emerging from the MDA'. Given an MDP, a policy $\pi$ is called markovian iff. $p(a_t|s_t, a_{t-1}, r_{t-1}, s_{t-1}, ..., r_0, a_0, s_0) = p(a_t|s_t)$, i.e. iff. the choice of the next action only depends on the current state $s_t$ but not on the past. If we try to use the simple MDA and then we nevertheless want to use an RNN then due to the hidden state, the policy $\pi_t$ at time $t$ depends on the whole word sampled so far and not only on the current state (which is the non informative state $s_0$ all the time!). So it actually depends on all the actions (i.e. chosen characters) $a_0, a_1, ..., a_{t-1}, a_t$ in order to make the decision about the next character $a_{t+1}$, i.e. it is non-markovian.

To understand 3 completely you must have some basic knowledge about probability theory (what is the precise definition of a random variable? Does every random variable have a density? Why do we describe discrete random variables with integrals instead of sums, etc) and you should definitely read Puterman, Markov Decision Processes, Chapter 6

  • $\begingroup$ thank you so much Fabian. This is a fantastic answer and it addresses many confusions. $\endgroup$ – lllllllllllll May 5 '19 at 8:58

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.