<jupyter_start><jupyter_text>Q-LearningThis is classified as an Reinforcement Learning method which is based on learning due experimentation by the agent. There is no policy, it will be "discovered" by the agent as it "observes" the environment. In other words no model is needed in Q-Learning.  The subject to experimentation is called agent, it can ocupy a set of states and make a set os actions. When the agent make an action the states is changed and a reward is provided to it. With each transition a function (Q) measures the quality of the action based on the rewards. The agent then creates some kind of memory stored in the Q matrix. Every time a final state is reached an episode ends and there is nothing else for the agent to learn. A typical Q function is like this:  $Q^{'}(s_{t},a_{t}) = (1-\alpha)Q(s_{t},a_{t}) + \alpha(R_{t} + \gamma MAX(Q(s_{t+1},a_{t+1}))) $,  where $Q^{'}(s_{t},a_{t})$ is the updated quality value, $Q(s_{t},a_{t})$ is the old quality value, $\alpha$ is the learning rate, $\gamma$ is the exploration factor, $R_{t}$ is the reward matrix and $MAX(Q(s_{t+1},a_{t+1}))$ is the maximum value of the possible actions for the next state.Let us check the meaning and how the above equation can be constructed. In each time step we can see the amount of information store in memory as  $\frac{\partial Q}{\partial t} = R + \gamma\frac{\partial Q}{\partial x}$,  where $x$ is a point in space $ X \equiv S \times A$ and $\frac{\partial Q}{\partial x}$ can be seen as the gradient of $Q$, a tangent vector of the space of configurations. The $\lambda$ is a proportionality coeficient. It is possible to rewrite this equation taking $t = x^{0}$ and $x = x^{1}$,$ \frac{\partial Q}{\partial x^{0}} - \gamma\frac{\partial Q}{\partial x^{1}} = R $or in a more general way considering Q as a real valued contravariant vector, where $M \equiv X \times T$ has a Minkowskian metric$\eta_{ab} = \begin{pmatrix} 1 & 0 \\0 & -\gamma^{2} \end{pmatrix}$  and$\partial_{a} = \begin{pmatrix} \partial_{0} & 0 \\0 & -\gamma\partial_{1} \end{pmatrix}$  we have$ \partial_{a} Q^{a} = R $ or $div (Q) = R$.This way $R$ represents the reward time and spatial evolution. The meaning of the above equation is that of a continuity equation and $R$ works as an information source. $Q^{a}$ is some kind of information field 1-tensor.From this we can develop the whole information theory even with a general metric tensor to compute curvatures. By integration we obtain  $  \Delta Q =\int_{T}(R + \gamma\frac{\partial Q}{\partial x^{1}})dx^{0}$and doing it numerically$  Q^{'} = Q + R\Delta t + \gamma\frac{\partial Q}{\partial x}\Delta t$.So the time step is linked to the learning rate and to get the same equation we add the term $(1-\alpha)$ to control how much of the past stored infirmation we retain to the future.   Example: Agent in a mazeThe most basic example is the agent seen as a robot or a lab rat trying to find the exit of a maze, which is the environment. Let us create a simple maze with X marking where the agent must learn to go and let us put some traps too. If the agent (let us call it the Obot, o) reaches the X or a trap T an episode ends.<jupyter_code>import random
from random import randint
import pandas as pd
import numpy as np
# mostra a posição
def printTable(p):
  table = pd.DataFrame(np.zeros((4,4),dtype=int),columns=None)
  table.iloc[3,3]='X'
  table.iloc[3,1]='T'
  table.iloc[0,3]='T'
  T = pd.DataFrame({'linhas':[0,1,2,3,0,1,2,3,0,1,2,3,0,1,2,3],'colunas':[0,0,0,0,1,1,1,1,2,2,2,2,3,3,3,3]})
  table = table.replace(0,'_')
  table.iloc[T['linhas'][p],T['colunas'][p]] = 'o'
  print(table.to_string(index=False,header=False))
  print('')
printTable(np.random.randint(0,16))<jupyter_output>_  _  _  T
_  _  _  _
_  _  _  _
_  T  _  o<jupyter_text>We can use that function to see the agent's position.Now we define the reward in each point, giving a good (high value) reaerd in the exit and a bad (low value) in the traps.Remember that rows are states and columns are actions. In the matrix below there is one row and one columns for each point (or pixel) in the maze. We name our pixels like this:<jupyter_code>| 0 4  8 12|
| 1 5  9 13|
| 2 6 10 14|
| 3 7 11 15|<jupyter_output><empty_output><jupyter_text>-  The exit pixel (15) can be reached by actions coming from pixels 14, 11 and of course in pixel 15 (if it begins there it must stay there), so we put high values in those pixels with the higher in 15.-  To finish we set the value -1 for impossible actions (example: from pixel 0 it cannot go to pixel 6 in one movement) and 0 to others.  We will have something like this:<jupyter_code>R = np.array([[-1,  0, -1, -1,  0, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1],
              [ 0, -1,  0, -1,  0, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1],
              [-1,  0, -1,  0, -1,  0, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1],
              [-1, -1,  0, -1, -1, -1, -1,  0, -1, -1, -1, -1, -1, -1, -1, -1],
              [ 0, -1, -1, -1, -1,  0, -1, -1,  0, -1, -1, -1, -1, -1, -1, -1],
              [-1,  0, -1, -1,  0, -1,  0, -1, -1,  0, -1, -1, -1, -1, -1, -1],
              [-1, -1,  0, -1, -1,  0, -1,  0, -1, -1,  0, -1, -1, -1, -1, -1],
              [-1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1,  0, -1, -1, -1, -1],
              [-1, -1, -1, -1,  0, -1, -1, -1, -1,  0, -1, -1,  0, -1, -1, -1],
              [-1, -1, -1, -1, -1,  0, -1, -1,  0, -1,  0, -1, -1,  0, -1, -1],
              [-1, -1, -1, -1, -1, -1,  0, -1, -1,  0, -1,  0, -1, -1,  0, -1],
              [-1, -1, -1, -1, -1, -1, -1,  0, -1, -1,  0, -1, -1, -1, -1, 20],
              [-1, -1, -1, -1, -1, -1, -1, -1,  0, -1, -1, -1, -1,  0, -1, -1],
              [-1, -1, -1, -1, -1, -1, -1, -1, -1,  0, -1, -1,  0, -1,  0, -1],
              [-1, -1, -1, -1, -1, -1, -1, -1, -1, -1,  0, -1, -1,  0, -1, 20],
              [-1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, 50]])
Rtable = pd.DataFrame(data=R)
Rtable<jupyter_output><empty_output><jupyter_text>Now we are able to set the parameters gamma and alpha together with a matrix to Q. Since in the begining the agent has no memory Q has value zero for every point of the maze.<jupyter_code># discount factor
gamma = 1.
# learning rate
alpha = 0.5
# set Q matrix to zero
Q = np.zeros((16,16))<jupyter_output><empty_output><jupyter_text>The strategy to make the training is as follows:1-  We put the agent inside the maze in a random place: if it fall in a trap is over and the episode ends; if not, it chooses an action randomly and the state changes if the change is allowed (value >=0 in the R matrix);  2-  Now we compute a new value of Q in that point using our equation. Remember that at this point the agent must look around him and verify where there is a higher Q value to use in the equation.  3-  The agent repeat this process until it finds the exit or a trap and an episode ends.  4-  In order to learn something the agent needs maybe a lot of episodes. It is good to set a maximum number of step for each episode in case the agent gets stuck.  Let us see how to do that:<jupyter_code># learning
def agentLearn(episodes):
    for i in range(episodes):
        s = randint(0,15)
        path = [s]
        while True:
            a = randint(0,15)
            if R[s,a]>=0:
                if a==7 or a==12:
                    print("It's a trap!")
                    path.append(a)
                    printTable(a)
                    break
                else:
                    Q[s,a] = (1.-alpha)*Q[s,a] + alpha*(R[s,a] + gamma*max(Q[a,]))
                    s = a
                    path.append(s)
                    printTable(s)
                    if s==15:
                        print("EXIT!")
                        printTable(s)
                        break
        print('Path:',path)
agentLearn(1)
# check how the "memory" is going
Qtable = pd.DataFrame(data=Q,dtype=int)
Qtable<jupyter_output><empty_output><jupyter_text>With the agentLearn() function we can see its path on the maze, but it is not necessary to do that all the time. Let us change it a little to run a lot of episodes so we can check the Q matrix evolution.<jupyter_code># learning
def agentLearnFast(episodes):
    for i in range(episodes):
        s = randint(0,15)
        while True:
            a = randint(0,15)
            if R[s,a]>=0:
                if a==7 or a==12:
                    break
                else:
                    Q[s,a] = (1.-alpha)*Q[s,a] + alpha*(R[s,a] + gamma*max(Q[a,]))
                    s = a
                    if s==15:
                        break
    return Q
# set Q matrix to zero
Q = np.zeros((16,16))
# learning
Q = agentLearnFast(200)
# check how the "memory" is going
Qtable = pd.DataFrame(data=Q,dtype=int)
Qtable<jupyter_output><empty_output><jupyter_text>It seems that after 100 episodes the agent learned something. It is time to see how good it became in leaving the maze. Now when the agent is put in the maze it will search his memory for the action which has a higher quality based on the currently state (if there is a draw between actions the choice is random). If it had enough training the exit should be found easily.<jupyter_code># exiting the maze
def agentExit(Q):
  n = 0
  nmax = 30
  s = randint(0,15)
  while True:
    ns = random.choice(list(filter(lambda kv: kv[1] == max(Q[s,]), enumerate(Q[s,]))))[0]
    if R[s,ns]>=0:
        s = ns
        n +=1
        print(s)
        if s == 7 or s == 12:
            print("It's a trap!")
            break
        elif s == 15: 
            print("EXIT!")
            break
        if n == nmax: 
            print("LOST!")
            break
  print('Total steps:',n)
agentExit(Q)<jupyter_output>10
11
15
EXIT!
Total steps: 3
{'fraction_non_alphanumeric': 0.14127423822714683, 'fraction_numerical': 0.044218733969426494, 'mean_word_length': 2.4433062522077003, 'pattern_counts': {'":': 0, '<': 27, '<?xml version=': 0, '>': 31, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 64, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'chain_length': '7', 'dir': 'jupyter-structured-clean-dedup', 'id': '108928', 'license': 'MIT', 'n_tokens_mistral': 3522, 'n_tokens_neox': 3378, 'n_words': 1426, 'path': 'TemporalDifference/QLearning/QLearning-Theory_example.ipynb', 'repo_name': 'onimaru/Reinforcement_Learning', 'size': '9747'}