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:
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.
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:
- The strategy with the RNN can be used in all Reinforcement Learning setups (like learning to play computer games like pong etc).
- 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).