notebooks/RL_multi_task_contextual_MDP.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 文脈つきMDP\n",
    "\n",
    "参考：\n",
    "* [Contextual Markov Decision Processes](https://arxiv.org/abs/1502.02259)：もっと良い論文あるかも．問題設定だけなら参考になる．\n",
    "\n",
    "通常のMDPではダイナミクスや報酬関数を固定しますが，問題によってはMDPがなんらかの文脈（context）に依存することがあります．\n",
    "例えば映画広告の推薦アルゴリズムを考えるとき，ユーザーの年齢，職業，性別など，様々な要素によってそのMDPは変化するはずです．\n",
    "Contextual MDPでは文脈がついたMDPを扱います．\n",
    "\n",
    "具体的には，文脈つきMDPは次で定義されます．\n",
    "\n",
    "---\n",
    "\n",
    "**文脈つきMDP**\n",
    "\n",
    "文脈つきMDPは$(\\mathcal{C}, \\mathcal{S}, \\mathcal{A}, \\mathcal{M}(c))$で定義され，ここで$\\mathcal{C}$は文脈の空間です．\n",
    "$\\mathcal{M}$は文脈を何らかのMDPにマップする関数です：$\\mathcal{M}(c)=\\left(\\mathcal{S}, \\mathcal{A}, p^c(y \\mid x, a), r^c(x), \\mu^c\\right)$．\n",
    "\n",
    "---\n",
    "\n",
    "簡単に言うと，文脈つきMDPは同じ状態行動空間のMDPの集合になります．\n",
    "例えば$|\\mathcal{C}|$が$K$で有限であれば，文脈つきMDPは$K$個のモデルを用意すれば解けます．\n",
    "一方で，$K$が軌跡の数に従って増える場合などで難しくなります．\n",
    "例えば，ターゲティング広告問題を考えてみましょう．\n",
    "ターゲティング広告は通常，ユーザーをグループ化して，そのグループのニーズや習慣をターゲットとして広告を構築します．つまり，ユーザーの数が増えるほどクラスの数も増え，MDPの数$K$が増えることになります．\n",
    "\n",
    "---\n",
    "\n",
    "**一般的な問題設定**\n",
    "\n",
    "文脈は$K$個あるとし，エピソードの数を$T$とします．各エピソード（$e_1, \\dots, e_T$）のホライゾンを$H$として，初期状態は$\\mu^c$に従ってランダムにサンプルされるとします．\n",
    "各エピソードでは文脈$c\\in \\mathcal{C}$が一つ選択され，ダイナミクスや報酬はその文脈に従うとします．\n",
    "このとき，次のリグレットによってエージェントの性能を評価します．\n",
    "\n",
    "$$\n",
    "\\text { Regret }=\\sum_{t=1}^T J_t^*-\\sum_{t=1}^T \\sum_{h=1}^{H} r_{t, h}\n",
    "$$\n",
    "\n",
    "ここで，$J^*_t$は$t$番目の軌跡における最適な価値とします．$r_{t, h}$は$t$個目の軌跡の$h$ステップ目の報酬です．\n",
    "\n",
    "---\n",
    "\n",
    "## 文脈付きMDPに含まれる問題\n",
    "\n",
    "* Contextual Hidden Markov Model：文脈によって観測の分布が変化する\n",
    "* POMDP：文脈付きMDPの複雑版．\n",
    "* Multi-model RL：ダイナミクスや報酬が複数のモデルの凸なコンビネーションからなる問題\n",
    "* State representation：与えられた観測から，適切な状態空間を構築する問題．\n",
    "* ロバストMDP：Contextual MDPにおいて最悪ケースの性能を最大化するもの\n",
    "\n",
    "他にも色々ありそう．多分マルチタスクRLも近いはず．\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 文脈付きMDPの解き方\n",
    "\n",
    "詳しい内容は省略しますが，次の4つの手順で文脈付きMDPにおけるリグレットが最小化できます．\n",
    "\n",
    "1. 観測した軌跡を$K$個のモデルに分類します．これは例えば次のようなやり方で分類できます．\n",
    "    * $t$個目の軌跡における状態行動$(s, a)$について，その遷移確率の推定を$\\hat{p}_t(\\cdot | s, a)$とします．\n",
    "    * 軌跡のあり得る分類の仕方$\\left\\{C_k\\right\\}_{k=1}^K$を考えて，$\\hat{p}_k(\\cdot \\mid s, a)$をクラス中の代表とし，$\\sum_{k=1}^K \\sum_{t \\in C_k} \\max _{s, a}\\left\\|\\hat{p_t}(\\cdot \\mid s, a)-\\hat{p}_k(\\cdot \\mid s, a)\\right\\|_1$が最小化されるような分類を探します\n",
    "2. こっから先がよくわからない．．．この論文は問題設定だけ抑えておけば十分かも．\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": []
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "\n",
    "次の定義を導入します．\n",
    "\n",
    "---\n",
    "\n",
    "$$\n",
    "\\begin{aligned}\n",
    "& M_1=\\left(\\mathcal{S}, \\mathcal{A}, p_1(y \\mid x, a), r(x), \\mu\\right) \\\\\n",
    "& M_2=\\left(\\mathcal{S}, \\mathcal{A}, p_2(y \\mid x, a), r(x), \\mu\\right)\n",
    "\\end{aligned}\n",
    "$$\n",
    "\n",
    "を遷移だけ異なる２つのMDPとします．\n",
    "もし任意の$(s, a)$について\n",
    "\n",
    "$$\n",
    "\\left\\|p_1(\\cdot \\mid s, a)-p_2(\\cdot \\mid s, a)\\right\\|_1 \\leq \\epsilon\n",
    "$$\n",
    "であれば，$\\mathcal{M}_2$は$\\mathcal{M}_1$の$\\varepsilon$近似モデルと呼びます．\n",
    "\n",
    "また，\n",
    "\n",
    "$$\n",
    "\\begin{aligned}\n",
    "& X_1=\\left(\\mathcal{C}_1, \\mathcal{S}, \\mathcal{A}, \\mathcal{M}_1(c)\\right) \\\\\n",
    "& X_2=\\left(\\mathcal{C}_2, \\mathcal{S}, \\mathcal{A}, \\mathcal{M}_2(c)\\right)\n",
    "\\end{aligned}\n",
    "$$\n",
    "\n",
    "を２つの文脈つきMDPとして，$|\\mathcal{C}_1|=|\\mathcal{C}_2|$とします．もし任意の$c \\in \\mathcal{C}_1$について，$\\mathcal{M}_2$が$\\mathcal{M}_1(f(c))$の$\\varepsilon$近似モデルであるような関数$f: \\mathcal{C}_1 \\leftrightarrow \\mathcal{C}_2$が存在するとき，$X_2$を$X_1$の$\\varepsilon$近似文脈つきMDPと呼びます．\n",
    "\n",
    "---\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "language_info": {
   "name": "python"
  },
  "orig_nbformat": 4
 },
 "nbformat": 4,
 "nbformat_minor": 2
}