SARSA Algorithm Overview

SARSA Algorithm Overview

• SARSA is a model-free, on-policy reinforcement learning algorithm.
• It learns an action-value function (Q-function) that estimates the expected cumulative reward for taking a specific action in a given state.
• Key to SARSA is its on-policy nature; it learns by following the current policy. Actions are chosen according to the current policy and updates the Q-function based on these choices.

Core Concepts

• State (s): A representation of the environment's current configuration.
• Action (a): A choice made by the agent within the current state.
• Reward (r): Feedback from the environment for taking a specific action.
• Policy (π): A function that maps states to probabilities of taking different actions.
• Q-function (Q(s, a)): The estimated expected cumulative reward for taking action 'a' in state 's' and following the policy from that state onward.

SARSA Algorithm Steps

• Initialization:

  • Initialize Q(s, a) for all states and actions with some small random values, such as 0.
  • Initialize a policy (e.g., use an epsilon-greedy strategy to balance exploration and exploitation).

• Episode Loop:

  • Start in an initial state.
  • Action Selection: Choose an action based on the current policy.
  • Observation: Observe the next state and reward from taking the action.
  • Update Q-function:
    • Predict the next action (a') with the policy. This next action is critical for the update.
    • Update Q-function with:

      Q(s, a) = Q(s, a) + α * [r + γ * Q(s', a') - Q(s, a)]
      

      where:

• α is the learning rate (controlling the update step size).

• γ is the discount factor (weighing future rewards).

• r is the immediate reward from taking action 'a' in state 's'.

• s' is the next state.

• a' is the next action taken from the current policy.

  • Update State and Action: Set the current state to the next state and the current action to the next action.
    • Continue the loop until reaching a terminal state.

• Iteration: Repeat the episode loop multiple times to improve the Q-function estimates.

SARSA Variants

• Epsilon-greedy policy: This policy is commonly used in SARSA. The agent selects an action following a current policy with probability (1 - epsilon). With probability epsilon, the agent selects a random action, aiding in exploration of the environment and preventing the agent from getting stuck in suboptimal local optima.

Key Differences from Q-Learning

• On-policy: SARSA learns a Q-function by taking actions consistent with the policy used to find these Q-values.
• Q-Learning: Q-Learning is an off-policy algorithm, meaning it can learn the Q-function using data generated by actions that could potentially deviate from its current policy.

Advantages of SARSA

• Simpler than some other methods, potentially requiring less computation.
• Can learn in real-time environments as updates are directly connected to the policy.

Disadvantages of SARSA

• Can be slower to converge compared to Q-learning in some cases.
• On-policy methods are not necessarily optimal.