[T_L] -- A -- B -- C -- D -- E -- [T_R]
         s1   s2   s3   s4   s5

import numpy as np
import matplotlib.pyplot as plt

class RandomWalk:
    """5状態のランダムウォーク環境"""

    def __init__(self, n_states=5):
        self.n_states = n_states
        # 状態: 0, 1, ..., n_states-1 (内部状態)
        # 終端状態: -1 (左端), n_states (右端)
        self.start_state = n_states // 2  # 中央から開始

    def reset(self):
        """中央状態からスタート"""
        self.state = self.start_state
        return self.state

    def step(self):
        """等確率で左右に移動"""
        if np.random.random() < 0.5:
            self.state -= 1  # 左に移動
        else:
            self.state += 1  # 右に移動

        # 終端判定
        if self.state < 0:
            return self.state, 0, True   # 左端: 報酬0
        elif self.state >= self.n_states:
            return self.state, 1, True   # 右端: 報酬1
        else:
            return self.state, 0, False  # 継続: 報酬0

    def true_values(self):
        """真の価値関数（解析解）"""
        return np.array([(i + 1) / (self.n_states + 1) for i in range(self.n_states)])


# 環境の確認
env = RandomWalk(n_states=5)
print(f"状態数: {env.n_states}")
print(f"開始状態: {env.start_state}")
print(f"真の価値関数: {env.true_values()}")

import numpy as np
import matplotlib.pyplot as plt

class RandomWalk:
    def __init__(self, n_states=5):
        self.n_states = n_states
        self.start_state = n_states // 2

    def reset(self):
        self.state = self.start_state
        return self.state

    def step(self):
        if np.random.random() < 0.5:
            self.state -= 1
        else:
            self.state += 1
        if self.state < 0:
            return self.state, 0, True
        elif self.state >= self.n_states:
            return self.state, 1, True
        else:
            return self.state, 0, False

    def true_values(self):
        return np.array([(i + 1) / (self.n_states + 1) for i in range(self.n_states)])


def td0_evaluation(env, alpha=0.1, num_episodes=100, gamma=1.0):
    """TD(0) 方策評価"""
    V = np.full(env.n_states, 0.5)  # 初期値0.5
    rms_history = []
    true_V = env.true_values()

    for episode in range(num_episodes):
        state = env.reset()

        while True:
            next_state, reward, done = env.step()

            if done:
                # 終端状態の価値は0
                V[state] += alpha * (reward + gamma * 0 - V[state])
                break
            else:
                V[state] += alpha * (reward + gamma * V[next_state] - V[state])
                state = next_state

        # RMSEの記録
        rms = np.sqrt(np.mean((V - true_V) ** 2))
        rms_history.append(rms)

    return V, rms_history


def mc_evaluation(env, alpha=0.1, num_episodes=100, gamma=1.0):
    """定数α MC方策評価"""
    V = np.full(env.n_states, 0.5)  # 初期値0.5
    rms_history = []
    true_V = env.true_values()

    for episode in range(num_episodes):
        # エピソード生成
        states = []
        rewards = []
        state = env.reset()

        while True:
            states.append(state)
            next_state, reward, done = env.step()
            rewards.append(reward)

            if done:
                break
            state = next_state

        # リターンの計算と更新（逆順）
        G = 0
        for t in range(len(states) - 1, -1, -1):
            G = gamma * G + rewards[t]
            V[states[t]] += alpha * (G - V[states[t]])

        # RMSEの記録
        rms = np.sqrt(np.mean((V - true_V) ** 2))
        rms_history.append(rms)

    return V, rms_history


# --- MC vs TD の比較実験 ---
env = RandomWalk(n_states=5)
true_V = env.true_values()

# 実験1: TD(0)の学習過程（異なるエピソード数）
fig, axes = plt.subplots(1, 2, figsize=(14, 5))

ax = axes[0]
state_labels = ['A', 'B', 'C', 'D', 'E']

# 異なるエピソード数でTD(0)を実行
for n_ep in [1, 10, 100]:
    V_td, _ = td0_evaluation(env, alpha=0.1, num_episodes=n_ep)
    ax.plot(state_labels, V_td, 'o-', label=f'TD(0), {n_ep} episodes', linewidth=2, markersize=8)

ax.plot(state_labels, true_V, 'k--', label='True $V^{\\pi}$', linewidth=2, markersize=8)
ax.set_xlabel('State', fontsize=12)
ax.set_ylabel('$V(s)$', fontsize=12)
ax.set_title('TD(0) Learning Progress', fontsize=13)
ax.legend(fontsize=10)
ax.grid(True, alpha=0.3)

# 実験2: MC vs TD の収束速度比較
ax = axes[1]

# 複数回の実験で平均を取る
num_runs = 100
num_episodes = 100

alphas_td = [0.05, 0.1, 0.15]
alphas_mc = [0.01, 0.02, 0.04]

for alpha in alphas_td:
    rms_all = np.zeros(num_episodes)
    for run in range(num_runs):
        _, rms_history = td0_evaluation(env, alpha=alpha, num_episodes=num_episodes)
        rms_all += np.array(rms_history)
    rms_all /= num_runs
    ax.plot(rms_all, label=f'TD(0), α={alpha}', linewidth=2)

for alpha in alphas_mc:
    rms_all = np.zeros(num_episodes)
    for run in range(num_runs):
        _, rms_history = mc_evaluation(env, alpha=alpha, num_episodes=num_episodes)
        rms_all += np.array(rms_history)
    rms_all /= num_runs
    ax.plot(rms_all, '--', label=f'MC, α={alpha}', linewidth=2)

ax.set_xlabel('Episodes', fontsize=12)
ax.set_ylabel('RMS Error', fontsize=12)
ax.set_title('MC vs TD(0): Convergence Speed', fontsize=13)
ax.legend(fontsize=9, loc='upper right')
ax.grid(True, alpha=0.3)

plt.tight_layout()
plt.show()

import numpy as np
import matplotlib.pyplot as plt

# RandomWalk クラスは上で定義済みとする

def td_lambda_evaluation(env, alpha=0.1, lam=0.8, num_episodes=100, gamma=1.0):
    """TD(λ) 方策評価（後方ビュー、適格度トレース）"""
    V = np.full(env.n_states, 0.5)
    rms_history = []
    true_V = env.true_values()

    for episode in range(num_episodes):
        state = env.reset()
        # 適格度トレースの初期化
        e = np.zeros(env.n_states)

        while True:
            next_state, reward, done = env.step()

            if done:
                # TD誤差（終端状態の価値は0）
                delta = reward + gamma * 0 - V[state]
            else:
                delta = reward + gamma * V[next_state] - V[state]

            # 適格度トレースの更新
            e *= gamma * lam
            e[state] += 1  # 訪問した状態のトレースを増加

            # 全状態の価値関数を更新
            V += alpha * delta * e

            if done:
                break
            state = next_state

        rms = np.sqrt(np.mean((V - true_V) ** 2))
        rms_history.append(rms)

    return V, rms_history


# --- 異なるλの比較実験 ---
env = RandomWalk(n_states=5)
true_V = env.true_values()

num_runs = 100
num_episodes = 100

fig, axes = plt.subplots(1, 2, figsize=(14, 5))

# (1) 異なるλでの収束速度
ax = axes[0]
lambda_values = [0.0, 0.2, 0.4, 0.6, 0.8, 1.0]
colors = plt.cm.viridis(np.linspace(0, 1, len(lambda_values)))

for lam, color in zip(lambda_values, colors):
    rms_all = np.zeros(num_episodes)
    for run in range(num_runs):
        _, rms_history = td_lambda_evaluation(
            env, alpha=0.1, lam=lam, num_episodes=num_episodes
        )
        rms_all += np.array(rms_history)
    rms_all /= num_runs
    ax.plot(rms_all, label=f'λ={lam}', linewidth=2, color=color)

ax.set_xlabel('Episodes', fontsize=12)
ax.set_ylabel('RMS Error', fontsize=12)
ax.set_title('TD(λ): Effect of λ on Convergence', fontsize=13)
ax.legend(fontsize=10)
ax.grid(True, alpha=0.3)

# (2) 最適αとλの関係
ax = axes[1]
alphas = np.arange(0.01, 0.5, 0.02)
lambdas = [0.0, 0.4, 0.8, 0.95, 1.0]
colors2 = plt.cm.plasma(np.linspace(0, 1, len(lambdas)))

for lam, color in zip(lambdas, colors2):
    avg_rms = []
    for alpha in alphas:
        rms_final = 0
        valid_runs = 0
        for run in range(50):
            _, rms_history = td_lambda_evaluation(
                env, alpha=alpha, lam=lam, num_episodes=50
            )
            # 最後の10エピソードの平均RMS
            rms_final += np.mean(rms_history[-10:])
            valid_runs += 1
        avg_rms.append(rms_final / valid_runs)
    ax.plot(alphas, avg_rms, label=f'λ={lam}', linewidth=2, color=color)

ax.set_xlabel('α (step size)', fontsize=12)
ax.set_ylabel('Average RMS Error\n(last 10 episodes)', fontsize=12)
ax.set_title('TD(λ): Sensitivity to α', fontsize=13)
ax.legend(fontsize=10)
ax.set_ylim(0, 0.6)
ax.grid(True, alpha=0.3)

plt.tight_layout()
plt.show()

import numpy as np
import matplotlib.pyplot as plt

# RandomWalk クラスは上で定義済みとする

def batch_td0(env, episodes_data, alpha=0.01, gamma=1.0, max_iter=1000, theta=1e-6):
    """バッチTD(0): 同じデータを繰り返し使って収束するまで学習"""
    V = np.full(env.n_states, 0.5)

    for iteration in range(max_iter):
        V_old = V.copy()

        for episode in episodes_data:
            for t in range(len(episode) - 1):
                state, reward = episode[t]
                next_state = episode[t + 1][0]

                if next_state < 0 or next_state >= env.n_states:
                    # 終端状態
                    V[state] += alpha * (reward + gamma * 0 - V[state])
                else:
                    V[state] += alpha * (reward + gamma * V[next_state] - V[state])

            # 最後のステップ
            last_state, last_reward = episode[-1]
            if 0 <= last_state < env.n_states:
                V[last_state] += alpha * (last_reward - V[last_state])

        if np.max(np.abs(V - V_old)) < theta:
            break

    return V


def batch_mc(env, episodes_data, alpha=0.01, gamma=1.0, max_iter=1000, theta=1e-6):
    """バッチMC: 同じデータを繰り返し使って収束するまで学習"""
    V = np.full(env.n_states, 0.5)

    for iteration in range(max_iter):
        V_old = V.copy()

        for episode in episodes_data:
            # リターンの計算
            states = [s for s, r in episode if 0 <= s < env.n_states]
            rewards = [r for s, r in episode]

            G = 0
            for t in range(len(episode) - 1, -1, -1):
                state, reward = episode[t]
                G = gamma * G + reward
                if 0 <= state < env.n_states:
                    V[state] += alpha * (G - V[state])

        if np.max(np.abs(V - V_old)) < theta:
            break

    return V


def generate_episodes_data(env, num_episodes):
    """エピソードデータの生成"""
    episodes = []
    for _ in range(num_episodes):
        episode = []
        state = env.reset()

        while True:
            next_state, reward, done = env.step()
            episode.append((state, reward))
            if done:
                episode.append((next_state, 0))
                break
            state = next_state
        episodes.append(episode)

    return episodes


# --- バッチ学習での比較 ---
env = RandomWalk(n_states=5)
true_V = env.true_values()

num_runs = 100
batch_sizes = [1, 5, 10, 20, 50, 100]

fig, ax = plt.subplots(figsize=(10, 6))

rms_td_batch = []
rms_mc_batch = []

for n_episodes in batch_sizes:
    rms_td = 0
    rms_mc = 0

    for run in range(num_runs):
        # 同じデータでMCとTDを比較
        episodes_data = generate_episodes_data(env, n_episodes)

        V_td = batch_td0(env, episodes_data, alpha=0.001, max_iter=500)
        V_mc = batch_mc(env, episodes_data, alpha=0.001, max_iter=500)

        rms_td += np.sqrt(np.mean((V_td - true_V) ** 2))
        rms_mc += np.sqrt(np.mean((V_mc - true_V) ** 2))

    rms_td_batch.append(rms_td / num_runs)
    rms_mc_batch.append(rms_mc / num_runs)

ax.plot(batch_sizes, rms_td_batch, 'o-', label='Batch TD(0)', linewidth=2, markersize=8)
ax.plot(batch_sizes, rms_mc_batch, 's-', label='Batch MC', linewidth=2, markersize=8)
ax.set_xlabel('Number of Episodes in Batch', fontsize=12)
ax.set_ylabel('RMS Error', fontsize=12)
ax.set_title('Batch TD(0) vs Batch MC', fontsize=14)
ax.legend(fontsize=12)
ax.grid(True, alpha=0.3)
plt.tight_layout()
plt.show()