読者です 読者をやめる 読者になる 読者になる

強化学習: ノート2

本読み 強化学習

読んでいる本(出典): Amazon.co.jp: 強化学習: Richard S.Sutton, Andrew G.Barto, 三上 貞芳, 皆川 雅章: 本

前回:ノート1 / 次回:ノート3
目次:強化学習

今日読んだページ: 26~32ページ
以下、自分の解釈・感想。

  • 前回のあらすじ:
    • 強化学習では、環境と相互作用するエージェントが、状態の価値を評価して学び、総報酬を最大化しようと行動していく。
  • 「正しい行動を直接与える(26ページ冒頭)」のイメージ(これらは強化学習ではない)。
    • 手書き数字に、「この数字だと判断すべき」正解ラベルが貼り付いている。
    • 顔認証で、正解の本人写真を与えておく。
    • スパムメールフィルタリングだったら、スパムメールの例を与えておく。
  • でも現実に、そのような正解が与えられない問題はある。じゃあどうするのか → この章の本題。
  • 探査(explore)と利用(exploit)のバランスが何に依存するかを喫茶店に喩えると、
    • いま一番お気に入りの喫茶店に行き続けることで最終的に得られる満足感の総量がどれほどあるのか。
    • 行ったことがない喫茶店の方がおいしいコーヒーを出す見込みがどれほどあるのか。
    • 自分はこの街であと何回喫茶店に行くのだろうか。
  • 練習問題 2.1 (32ページ)
    • どの程度探査に振り向けるべきかは、当然、どれだけプレイするかに依存する。



2016-02-07 修正
30ページの10本腕バンディットタスクを実装する。
「1000回スロットマシンを引く。総報酬の最大化を目指して10個のスロットマシンのうちいずれかを毎回選ぶ。」
教科書の図と違うが、最初に全てのアームを試している点が異なる。あくまで下記コードのゲーム設定。

  • 1回のタスク = 1000回アームを引く。これを2000タスク行う。
  • タスクごとに10本のアームの平均報酬はリセットされる。
  • 赤色がグリーディ、オレンジ色がεグリーディ(ε= 0.01)、黄色がεグリーディ(ε= 0.1)の結果。
    • 但し、最初にすべてのスロットマシンを1回ずつ試している。最初の10点はプロットしていない。
  • 左図が平均報酬(n回目に得た報酬の2000タスクにわたる平均)、右図が行動の最適度(n回目に引いたアームが平均報酬最大のアームであったかどうかの2000タスクにわたる平均)。
    • どちらのグラフも、赤・オレンジ・黄3つの戦略が教科書より拮抗している。
      • 右図の黄色だけは教科書と同じにみえる。
    • 教科書では、推定報酬を全て0で初期化しており、最初に全部のスロットマシンを引くことはやっていないようなので、教科書よりグリーディな戦略(赤)やほんの少し探査する戦略(オレンジ)がプレイ数の少ない段階から有利になるのは理解できる(むしろ教科書は初期値のさじ加減にみえる)。
      • といっても、合計1000回しか引けないのにスロットマシンが1000台あったら全部引いているのは悠長なので、その点は教科書の方法が純粋な戦略の比較だと思う。でも、平均報酬を0で初期化するのは、やはりさじ加減だと思う。
        (後日追記)初期値によってコントロールする手法として後の方で紹介されている(44ページの図)。

f:id:cookie-box:20160207102934p:plain:w660

n.draw <- 1000 # 1回のタスクでアームを何回引くか
labels <- c("A", "B", "C", "D", "E", "F", "G", "H", "I", "J")

# ベクトルのうち一番大きい値のラベルを返す補助関数
# ※ 同率1位があるときはランダムな選択にする
get.best.label <- function(data.hist) {
  label <- names(which.max(data.hist))
  data.hist <- data.hist[data.hist == data.hist[[label]]]
  labels <- names(data.hist)
  return(labels[[ceiling(runif(1) * length(labels))]])
}

# 1回のタスク
Task <- function(epsilon, rands) {
  # 各アームの平均報酬の設定
  rewards.mean <- rands$rewards.mean.arms
  names(rewards.mean) <- labels
  # i 回目に指定のラベルのアームを引いたときの報酬
  Draw <- function(label, i) {
    return(rewards.mean[[label]] + rands$var[[i]])
  }
  # 過去の行動の結果をためる用
  rewards.hist <- list()
  for (label in labels) {
    rewards.hist <- c(rewards.hist, list(c()))
  }
  names(rewards.hist) <- labels
  # タスク開始
  labels.all <- c()
  rewards.all <- c()
  # 最初はすべての行動を試す (仮)
  for (i.draw in 1:length(labels)) {
    label <- labels[[i.draw]]
    labels.all <- c(labels.all, label)
    reward <- Draw(label, i.draw)
    rewards.hist[[label]] <- c(rewards.hist[[label]], reward)
    rewards.all <- c(rewards.all, reward)
  }
  # その後は探査 or 利用しながら行動
  for (i.draw in (length(labels)+1):n.draw) {
    label <- NA
    values <- sapply(rewards.hist, mean)
    label.optimum <- get.best.label(values)
    if (epsilon == 0) { # 利用
      label <- label.optimum
    } else {
      if (rands$explore[[i.draw]] < epsilon) { # 探査
        labels.cand <- labels[labels != label.optimum]
        label <- labels.cand[[ceiling(runif(1) * length(labels.cand))]]
      } else { # 利用
        label <- label.optimum
      }
    }
    labels.all <- c(labels.all, label)
    reward <- Draw(label, i.draw)
    rewards.hist[[label]] <- c(rewards.hist[[label]], reward)
    rewards.all <- c(rewards.all, reward)
  }
  return(list(labels.all, rewards.all))
}

# 報酬の分散用/探査 or 利用の選択用/探査用の乱数の取得用
GetRands <- function() {
  return(list(
    rewards.mean.arms=rnorm(length(labels), mean=0.0, sd=1.0),
    var              =rnorm(n.draw, mean=0.0, sd=1.0),
    explore          =runif(n.draw)
  ))
}
n.task <- 2000 # タスクを何セット試行するか

result.greedy  <- list(mean.reward=rep(0.0, n.draw), optimal.degree=rep(0.0, n.draw))
result.eps0.01 <- list(mean.reward=rep(0.0, n.draw), optimal.degree=rep(0.0, n.draw))
result.eps0.1  <- list(mean.reward=rep(0.0, n.draw), optimal.degree=rep(0.0, n.draw))
for (i.task in 1:n.task) {
  rands <- GetRands()

  result <- Task(0, rands) # greedy
  optimal.degree <- ifelse(result[[1]]==labels[[which.max(rands$rewards.mean.arms)]], 1, 0)
  result.greedy[[1]] <- result.greedy[[1]] + result[[2]]
  result.greedy[[2]] <- result.greedy[[2]] + optimal.degree
  
  result <- Task(0.01, rands) # epsilon-greedy (0.01)
  optimal.degree <- ifelse(result[[1]]==labels[[which.max(rands$rewards.mean.arms)]], 1, 0)
  result.eps0.01[[1]] <- result.eps0.01[[1]] + result[[2]]
  result.eps0.01[[2]] <- result.eps0.01[[2]] + optimal.degree
  
  result <- Task(0.1, rands) # epsilon-greedy (0.1)
  optimal.degree <- ifelse(result[[1]]==labels[[which.max(rands$rewards.mean.arms)]], 1, 0)
  result.eps0.1[[1]] <- result.eps0.1[[1]] + result[[2]]
  result.eps0.1[[2]] <- result.eps0.1[[2]] + optimal.degree
}
result.greedy[[1]] <- result.greedy[[1]] / n.task
result.greedy[[2]] <- result.greedy[[2]] / n.task
result.eps0.01[[1]] <- result.eps0.01[[1]] / n.task
result.eps0.01[[2]] <- result.eps0.01[[2]] / n.task
result.eps0.1[[1]] <- result.eps0.1[[1]] / n.task
result.eps0.1[[2]] <- result.eps0.1[[2]] / n.task

# プロット (最初の10回は決定論的にラベル選択しているのでトリム)
par(mfrow=c(1,2))
# 平均報酬
y.all <- c(result.greedy[[1]][11:n.draw], result.eps0.01[[1]][11:n.draw], result.eps0.1[[1]][11:n.draw])
plot(c(11, n.draw), c(min(y.all), max(y.all)), xlab="Steps", ylab="Average Reward", type="n")
lines(11:n.draw, result.eps0.1[[1]][11:n.draw],  col="gold",       lwd=2)
lines(11:n.draw, result.eps0.01[[1]][11:n.draw], col="darkorange", lwd=2)
lines(11:n.draw, result.greedy[[1]][11:n.draw],  col="tomato",     lwd=2)
# 行動の最適度
y.all <- c(result.greedy[[2]][11:n.draw], result.eps0.01[[2]][11:n.draw], result.eps0.1[[2]][11:n.draw])
plot(c(11, n.draw), c(min(y.all), max(y.all)), xlab="Steps", ylab="Optimal Degree", type="n")
lines(11:n.draw, result.eps0.1[[2]][11:n.draw],  col="gold",       lwd=2)
lines(11:n.draw, result.eps0.01[[2]][11:n.draw], col="darkorange", lwd=2)
lines(11:n.draw, result.greedy[[2]][11:n.draw],  col="tomato",     lwd=2)