<jupyter_start><jupyter_text>OpenAI Gym (Value iteration algorithm)https://www.kaggle.com/charel/learn-by-example-reinforcement-learning-with-gym  Setup<jupyter_code>import gym
import numpy as np<jupyter_output><empty_output><jupyter_text>Look at the Taxi-v2 env<jupyter_code>env = gym.make('Taxi-v2')
env.env.s = 26
env.render()
env.close()<jupyter_output>+---------+
|R:[43m [0m| : :[34;1mG[0m|
| : : : : |
| : : : : |
| | : | : |
|[35mY[0m| : |B: |
+---------+<jupyter_text>__Actions__:- 0: move south- 1: move north- 2: move east - 3: move west - 4: pick up passenger- 5: drop off passenger__Rendering__:- blue: passenger- magenta: destination- yellow: empty taxi- green: full taxi- |: wall- other letters: locations  Value iteration algorithm* The value iteration algorithm is centered around the game states;* It has to know all environment states/transitions upfront (__model-based__ method);* The core idea of the algorithm is to calculate the value (expected long term maximum results) of each state.  Bellman Equation$V^{\ast}(s) = \max \limits_{a} \{ R(s, a) + \gamma \sum_{s'} {P(s'|s, a) V^{\ast}(s')} \}$  - R(s, a): Reward of action a in state s.- P(s'|s, a): Probability of going to state s' given action a in state s. The Taxi game actions are deterministic =>  P(...) = 1 always.- $\gamma$: Discount factor between 0 and 1. Higher $\gamma$ means a higher focus on long term rewards.<jupyter_code>env = gym.make('Taxi-v2')
NUM_ACTIONS = env.action_space.n
NUM_STATES = env.observation_space.n
print(f'NUM_ACTIONS: {NUM_ACTIONS}')
print(f'NUM_STATES: {NUM_STATES}')
v = np.zeros(NUM_STATES)
pi = np.zeros(NUM_STATES, dtype=int)
gamma = 0.9
significant_improvement = 0.01
def best_action(env, s):
    best_a = None
    best_value = float('-inf')
    
    for a in range(NUM_ACTIONS):
        env.env.s = s
        s_next, reward, _, _ = env.step(a)
        value = reward + gamma * v[s_next]
        if best_value < value:
            best_value = value
            best_a = a
    
    env.env.s = s
    return best_a

def value_iteration(env):
    iteration = 0
    while True:
        max_change = 0
        env.reset()
        
        for s in range(NUM_STATES):
            v_old = v[s]
            
            # choose best_action for state s
            best_a = best_action(env, s)
            
            # step with best_action
            env.env.s = s
            s_next, reward, _, _ = env.step(best_a)
            v[s] = reward + gamma * v[s_next]
            
            # save best_a for state s
            pi[s] = best_a
            
            # update max_change
            max_change = max(max_change, abs(v_old - v[s]))
            
        iteration += 1
        if max_change < significant_improvement:
            print(f'{iteration} iterations done')
            break
            
def solve_game(env, pi, s=404):
    total_reward = 0
    done = False
    
    env.reset()
    env.env.s = s
    env.render()
    
    while not done:
        a = pi[s]
        s, r, done, _ = env.step(a)
        env.render()
        print(f'reward: {r}')
        total_reward += r
        
    print(f'total reward: {total_reward}')
value_iteration(env)
solve_game(env, pi)<jupyter_output>+---------+
|[35mR[0m: | : :[34;1mG[0m|
| : : : : |
| : : : : |
| | : | : |
|[43mY[0m| : |B: |
+---------+

+---------+
|[35mR[0m: | : :[34;1mG[0m|
| : : : : |
| : : : : |
|[43m [0m| : | : |
|Y| : |B: |
+---------+
  (North)
reward: -1
+---------+
|[35mR[0m: | : :[34;1mG[0m|
| : : : : |
|[43m [0m: : : : |
| | : | : |
|Y| : |B: |
+---------+
  (North)
reward: -1
+---------+
|[35mR[0m: | : :[34;1mG[0m|
|[43m [0m: : : : |
| : : : : |
| | : | : |
|Y| : |B: |
+---------+
  (North)
reward: -1
+---------+
|[35mR[0m: | : :[34;1mG[0m|
| :[43m [0m: : : |
| : : : : |
| | : | : |
|Y| : |B: |
+---------+
  (East)
reward: -1
+---------+
|[35mR[0m: | : :[34;1mG[0m|
| : :[43m [0m: : |
| : : : : |
| | : | : |
|Y| : |B: |
+---------+
  (East)
reward: -1
+---------+
|[35mR[0m: |[43m [0m: :[34;1mG[0m|
| : : : : |
| : : : : |
| | : | : |
|Y| : |B: |
+---------+
  (North)
reward: -1
+---------+
|[35mR[0m: | :[43m [0m:[34;1mG[0m|
| : : : : |
| : : : : |
| | : |[...]
{'fraction_non_alphanumeric': 0.22534878221801843, 'fraction_numerical': 0.02884842752423741, 'mean_word_length': 2.1543624161073827, 'pattern_counts': {'":': 0, '<': 13, '<?xml version=': 0, '>': 12, 'https://': 1, 'lorem ipsum': 0, 'www.': 1, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'chain_length': '3', 'dir': 'jupyter-structured-clean-dedup', 'id': '553738', 'license': 'MIT', 'n_tokens_mistral': 1822, 'n_tokens_neox': 1700, 'n_words': 347, 'path': '2018-2019/assignment 8 (DQN & PGT)/dqn/tutorials/OpenAI_Gym_1_Value_Iteration.ipynb', 'repo_name': 'Tudor67/Neural-Networks-Assignments', 'size': '4229'}