=================================================================================

In a reinforcement learning problem, if we are dealing with an environment where the outcomes of actions are uncertain or not precisely known, then the transition probabilities P_s,a​ cannot be known. In such cases, we may need to employ model-free reinforcement learning approaches, where we don't explicitly model the transition probabilities and instead learn them through interaction with the environment.

An empirical estimate of the transition probability, P_s,a​, can be given by,

          ------------------------ [3676a]

where,

• P_s,a​(s') is the estimated probability of transitioning from state s to state s' when taking action a.
• N_s,a,s' is the number of times the agent observed the transition from state s to state s' when taking action a.
• N_s,a​ is the total number of times the agent took action a in state s.

Equation 3676a is a maximum likelihood estimate (MLE) of the transition probability in the sense that it is derived from observed frequencies of events in the data. The idea is that, in a model-free setting, you can estimate the transition probabilities based on the frequency of observed transitions during the agent's interactions with the environment. The more times the agent takes action a in state s and observes the resulting transition to state s', the higher the estimate of the transition probability. This ratio in Equation 3676a is a form of empirical estimation based on the observed data. Note that this kind of estimation is applicable when the agent is learning from experience and does not have explicit knowledge of the transition probabilities. The estimation becomes more accurate as the agent gathers more data through interactions with the environment.

However, P_s,a​(s') in Equation 3676a can lead to a situation where the ratio is 0/0 if N_s,a​​ = 0 (i.e., no instances of action a in state s) and N_s,a,s' = 0 (i.e., no instances of the transition from s to s' when taking action a). In such cases, a common practice is to use a default or smoothing value to avoid division by zero. The choice of the default value depends on the context and the characteristics of the problem. In many cases, 1/|S| is used as a default value, where |S| is the total number of states in the environment. This approach is a form of Laplace smoothing or add-one smoothing, where a small constant is added to all observed counts to ensure that no probability estimate is exactly zero. Then, we can modify Equation 3676a to,

          ------------------------ [3676al]

This modification helps prevent division by zero and provides a more robust estimate, especially in cases where the agent has limited data and encounters unseen state-action pairs.

Two common model-free reinforcement learning methods are Q-learning and Monte Carlo methods:

1. Q-Learning:

   • Q-learning is a model-free reinforcement learning algorithm that learns the optimal action-value function Q(s, a) without explicitly modeling the transition probabilities.
   • It uses a Q-table (or a Q-function in the case of function approximation) to estimate the expected cumulative reward of taking action a in state s.
   • The update rule for Q-learning is:

             ------------------------ [3676b]

   where,

             R is the immediate reward obtained after taking action a in state s.

             s' is the next state after taking action a in state s.

             α is the learning rate.

             γ is the discount factor, emphasizing the importance of future rewards.

             Q(s, a) is the Q-value for state s and action a.

             max_a'Q(s', a') represents the maximum Q-value over all possible actions in the next state s'.

   The Q-value for a state-action pair is updated to be a weighted sum of its current value and the estimated future rewards. The goal of Q-learning is to converge to the optimal Q-function, denoted as Q(s, a), which represents the maximum expected cumulative reward achievable by following the optimal policy from state s after taking action a.

   • Repeat:

     • Repeat steps 2-4 for multiple episodes or until convergence.
2. Monte Carlo Methods:
   • Monte Carlo methods estimate state values by averaging the returns observed from multiple episodes.
   • In Monte Carlo methods, we don't need a model of the environment; instead, we sample sequences of states, actions, and rewards by interacting with the environment.
   • The value of a state is updated after the completion of an episode based on the observed returns.

In both cases above, these model-free methods are advantageous when we don't have access to the dynamics of the environment. They rely on the observed data (state-action pairs and associated rewards) to iteratively improve their estimates of the optimal policy or value function.

============================================