0
1

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?

@Puni2Samurai

C++で始める強化学習[Q学習](後編)

0
Posted at

はじめに

前回は、Q学習について用語、学習手順を解説しました。
今回はその後編として、迷路探索のサンプルコードをまじえ、学習手順の詳細を記述していきます。

サンプルコード

学習手順

Q学習は下記の手順で学習を進めていきます。

  1. 報酬の設定
  2. Q値の初期化
  3. 状態を初期状態にセット
  4. エージェントの行動を選択
  5. Q値の更新
  6. 結果に到達するまで4～5を繰り返す
  7. Q値がいい感じになるまで3に戻る

前編にて、参考にしたサイトを2つ紹介しました。
両者には処理レベルで小さな違いが見受けられましたため、以降はCQLearnType1およびCQLearnType2とクラス分けをし記述します。

////////////////////////////////////////////////////////////////
// Q学習タイプ1クラス
class CQLearnType1 : public CQLearnBase
{
public:
    // 学習
    void InitQValue();  // Q値の初期化
    void QLearn();  // Q学習のメインルーチン
    BYTE SelectDirection(POINT pt, BYTE byOld);  // 行動の選択
};

////////////////////////////////////////////////////////////////
// Q学習タイプ2クラス
class CQLearnType2 : public CQLearnBase
{
public:
    // 学習
    void InitQValue();  // Q値の初期化
    void QLearn();  // Q学習のメインルーチン
    BYTE SelectDirection(POINT pt, BYTE byOld);  // 行動の選択
};

報酬の設定

まずは、エージェントが行動した際の報酬を設定します。
良い行動が選択された場合、その行動が強化されるよう高めの報酬を設定する必要があります。
このサンプルではQ学習の環境は迷路です。迷路にとっての良い行動とは、ゴール地点に到達することです。
なので、ゴール到達の報酬(REWARD_GOAL)は、それ以外の行動(REWARD_ACT)より高めの定義値となります。

CQLearn.h
// Q学習情報
#define REWARD_GOAL          10000  // 報酬
#define REWARD_ACT               0  // 行動報酬
#define QLEARN_EGREEDY          30  // ε-Greedy発生率
#define QLEARN_RATE            0.1  // 学習係数
#define QLEARN_DISCOUNT_FACTOR 0.9  // 割引率
#define DEFAULT_LEARN_COUNT    100  // 学習回数
#define MAX_LEARN_ACT         1000  // 行動数上限

報酬以外の定義値は、以降の手順にて解説します。

Q値の初期化

Q値はエージェントが行動するに際して、価値の高い行動の指標となる値です。
ある状態で、ある行動を選択したとき、将来的にどれだけ良い結果を期待できるのか、を表しています。
しかし、学習開始の時点では、どの行動が良い結果に結びつくのか、指標となる値がありません。
そこで、とりあえずの値として、乱数により小さな値で初期化します。

// Q値初期化
void CQLearnType1::InitQValue()
{
    int i, j;

    for(i = 0; i < MYMAZE_Y_MAX; i++)
    {
        for(j = 0; j < MYMAZE_X_MAX; j++)
        {
            a_nQValueState[i][j] = GetMyRandVal(0, 99);  // 0-99の乱数で初期化
        }
    }

    nLearningCnt = 0;
}

01_init001.jpg

または、すべて0で初期化します。

// Q値初期化
void CQLearnType2::InitQValue()
{
    memset(a_nQValueState, 0, sizeof(a_nQValueState));
    nLearningCnt = 0;
}

01_init002.jpg

いずれの初期値にしろ、学習が進めば更新されていくため、どちらの手法も大して差がないように感じています。

状態を初期状態にセット

迷路という環境における初期状態とは単純で、エージェントがスタート地点に位置することです。

// 初期状態にリセット
ptCurState = pMaze->ptStart;  // スタート地点にセット
bFinish = FALSE;  // ゴール未到達
nActCnt = 0;  // 行動回数をリセット

エージェントの行動を選択/Q値の更新

次の手順は、Q学習の肝となる行動の選択とQ値の更新です。
この2つの手順を結果に到達するまで、あるいは、規定回数の行動をするまで繰り返します。

迷路における「結果に到達」とはゴール地点に到達することです。
しかし、迷路に迷い、同じ場所を行ったり来たりすることも考えられます。下手をすれば、永遠に「結果に到達」しないかもしれません。
そこで、行動の選択に回数上限を設けておきます。

// 結果が出るまで、もしくは、行動回数が上限に到達するまで学習
while((bFinish == FALSE) && (nActCnt < MAX_LEARN_ACT))
{
    nActCnt++;

    /* エージェントの行動を選択処理 */
    /* Q値の更新処理 */
}

エージェントの行動を選択

行動の選択は政策(ポリシー)にしたがって決定します。
サンプルの迷路における行動の選択とは、進行可能な隣接マスに移動することですが、どの方向に移動するかの選択方針が政策です。

CQLearnType1では、基本的にはQ値の高い方向に進もうとします。
Q値が高い＝価値の高い行動のため、理にかなっているように思えます。
しかし、学習開始の時点では、Q値を乱数で初期化しています。乱数のいたずらにより、良からぬ行動に高いQ値がセットされている可能性もあるのです。
そこで、一定の確率でランダムに行動を選択する方針を採用します。
これをε-Greedy法といいます。サンプルでは、前述のQLEARN_EGREEDYにて30%の確率に定義しています。

////////////////////////////////////////////////////////////////
// 進行方向の選択
BYTE CQLearnType1::SelectDirection(POINT pt, BYTE byOld)
{
    /* (中略) */

    ////////////////////////////////////////////
    // 進行方向の選択
    ////////////////////////////////////////////
    LONG lRand;
    lRand = GetMyRandVal(0, 99);

    // ε-Greedy法により進行方向を選択
    if(lRand < QLEARN_EGREEDY)
    {
        lRand = GetMyRandVal(0, nCount - 1);

        // 進行可能な方向をチェック
        for(i = 0, nCount = 0; i < MYMAZE_DIRECTION::MAX; i++)
        {
            // チェックする方向が後方ではなく、かつ、壁ではない
            if((byOld != byCheck[1][i]) && ((byCur & byCheck[0][i]) == 0))
            {
                if(lRand == nCount)
                {
                    byNext = byCheck[0][i];
                    break;
                }

                nCount++;
            }
        }
    }
    // Q値に従い進行方向を選択
    else
    {
        // 進行可能な方向のQ値をチェック
        for(i = 0, nCount = 0; i < MYMAZE_DIRECTION::MAX; i++)
        {
            // チェックする方向が後方ではなく、かつ、壁ではない
            if((byOld != byCheck[1][i]) && ((byCur & byCheck[0][i]) == 0))
            {
                // Q値の大きい行動を採用
                if(nCount <= nQValNext[i])
                {
                    nCount = nQValNext[i];
                    byNext = byCheck[0][i];
                }
            }
        }
    }

    return byNext;
}

もう一方のCQLearnType2では、完全に乱数で決定する政策です。

////////////////////////////////////////////////////////////////
// 進行方向の選択
BYTE CQLearnType2::SelectDirection(POINT pt, BYTE byOld)
{
    /* (中略) */

    // 進行方向を乱数で選択
    LONG lRand = GetMyRandVal(0, nCount - 1);
    for(i = 0, nCount = 0; i < MYMAZE_DIRECTION::MAX; i++)
    {
        // チェックする方向が壁ではない
        if((byCurPos & byCheck[i]) == 0)
        {
            if(lRand == nCount)
            {
                byNext = byCheck[i];
                break;
            }

            nCount++;
        }
    }

    return byNext;
}

始めのうちはCQLearnType2のように「乱数だけで行動を選択する政策でいいじゃん」と思っていました。
全ての行動を網羅しなければ、どの行動が最適か分からないわけですから、一定の割合でしか乱数を使用しないε-Greedy法が非効率に感じたのですね。
実際、迷路の形状や初期のQ値によっては、なかなか最短経路を学習しないケースに遭遇しました。
しかし、学習が進んでいくうちに、Q値に従う分だけ最適な行動を選択する頻度が上がっていくのです。

学習対象の環境によって、どちらの政策が適しているのか？
ε-Greedy法を採用する場合は乱数の発生率をどのくらいに設定するのが最適か？
試行錯誤を繰り返して見つけ出すしかないのでしょうかね？

Q値の更新

行動が選択された後は、その行動の価値を評価します。
具体的には、ゴール地点に到達した行動には大きな報酬を付与します。
また、ゴールに近づく行動も価値が高くなるようQ値を更新し、ゴール地点に近づくほど高く評価します。
その計算式が下記になります。参考にしたサイトによって、微妙に式が異なりますが意味するところは同じです。

CQLearnType1は下の計算式を採用。
Q(s,a) = Q(s,a) + α(r + γ * MAX(Q(s',a')) - Q(s,a))

CQLearnType2は下の計算式を採用。
Q(s,a) = (1 - α) * Q(s,a) + α(r + γ * MAX(Q(s',a')))

Q(s,a): s(現在の状態)のとき、a(選択された行動)の場合のQ値です。
MAX(Q(s',a'): s'(選択された行動後の状態)から、a'(選択可能なすべての行動)のうち最も大きいQ値です。
r(報酬): 行動に対して与えられる評価値です。
α(学習率): 学習の速度です。学習率が低い方が長期的に安定した学習となる傾向があります。
γ(割引率): 未来に得られる報酬の重視度です。ゴール地点に近づく行動を重視するということです。Q学習は結果に到達する一連の行動が重要なのだから、基本は高めの設定でいいのかな？

CQLearnType1のQ値更新処理

////////////////////////////////////////////////////
// Q値の更新
////////////////////////////////////////////////////
// 進行可能な方向なしの場合、Q値更新なし
if(byDirection == 0)
{
    bFinish = TRUE;
}
// ゴール地点に到達の場合、報酬付与
else if(ptCurState.x == pMaze->ptGoal.x && ptCurState.y == pMaze->ptGoal.y)
{
    bFinish = TRUE;
    nQValTemp = a_nQValueState[ptCurState.y][ptCurState.x];
    a_nQValueState[ptCurState.y][ptCurState.x]
        = nQValTemp + QLEARN_RATE * (REWARD_GOAL - nQValTemp);
}
// 結果に到達していない場合、次の状態を元にQ値更新
else
{
    // 選択可能な行動のうち、Q値が最大の値を取得
    int nQValMax = GetMaxQValue(ptCurState, pMaze->byMaze[ptCurState.y][ptCurState.x]);

    // Q値更新
    nQValTemp = a_nQValueState[ptCurState.y][ptCurState.x];
    a_nQValueState[ptCurState.y][ptCurState.x]
        = nQValTemp + QLEARN_RATE * (QLEARN_DISCOUNT_FACTOR * nQValMax - nQValTemp);
}

CQLearnType2のQ値更新処理

////////////////////////////////////////////////////
// Q値の更新
////////////////////////////////////////////////////
// 選択可能な行動のうち、Q値が最大の値を取得
int nQValMax = 0;
if(bFinish == FALSE)
{
    nQValMax = GetMaxQValue(ptNextState, pMaze->byMaze[ptNextState.y][ptNextState.x]);
}

// Q値更新
int nQValTemp = a_nQValueState[ptNextState.y][ptNextState.x];
a_nQValueState[ptNextState.y][ptNextState.x]
    = (1 - QLEARN_RATE) * nQValTemp + QLEARN_RATE * (nReward + QLEARN_DISCOUNT_FACTOR * nQValMax);

報酬について、サンプルではゴール地点に到達した場合のみ付与しています。
「もし、スタートとゴールの中間地点にも小さな報酬地点を設定していれば、ゴールに誘導しやすく効率的な学習ができたのでは？」と、記事を書きながら思いつきました。

学習率や割引率について、サンプルでは参考サイトの値をそのまま使用しています。

この報酬設計こそがQ学習の肝となることを、サンプルの動作を繰り返す中で体感していきましたが、では、どのような値に設定するのが適切なのか、正直分からないままだったりします。
きっと、学習対象となる環境により適切な値というものは異なり、試行錯誤していく必要があるのでしょう。

02_proc001.jpg

02_proc002.jpg

Q値がいい感じになるまで繰り返す

上記の手順を充分に学習するまで繰り返します。

03_result001.jpg

03_result002.jpg

CQLearnType1とCQLearnType2のいずれも、ゴールに到達するまでの経路が高いQ値となっています。
これをもって、学習が充分に進んだと言えるでしょう。

結論:報酬設計が肝

機械学習は、漠然と「データを食わせておけば勝手に学習するんでしょ？」と思っていました。
甘かったです。
人間だって栄養価の高いものを食べても、体がそれを吸収するかは別な話なわけで。
AIも、適切に学習するよう導かなければ、なかなか賢くなっていきません。
何を報酬とするのか？その量は？タイミングは？
考えることは色々とあるのですね。

さいごに(なるほど、分からん)

軽い気持ちで機械学習に手を出しましたが、AI作成には、ある種のスキルが必要なのだと感じています。

僕は以前、ゲーム開発会社でオンラインゲーム/ソーシャルゲームの開発に従事していました。
当時の職場に「将来は数学者になりたかった」という後輩がいました。
その後輩は、企画側から「パーティ編成がこんな感じで、平均レベルがこのくらいのとき、10ターンでぎりぎり倒せるくらいのBOSSのパラメーターを作成して」と頼まれると、なにやらメモを取り始めるのです。
そのメモを覗きこんでみると、何を意味しているのか数式を書きつづっているのですね。
そして、しばらくして「このパラメーターで」と、だいたいオーダーどおりの数値を提出していました。

我々プログラマーは機能要件をアルゴリズムに落とし込むわけですが、AI作成においては要件や設計を数式に落とし込むスキルが必要なのかな、と。
Q学習における報酬付与でも数式が登場しました。
Q学習以外でも、分類や回帰、深層学習のニューラルネットワークといった機械学習でも、様々な数式が登場します。
しかし、その数式を見ても、僕には意図が理解できないのです。
「何故この学習に、この要素が必要で、この数値を用い、この計算式になるのか？」と。

今回におけるQ学習の報酬設計にも、最適解を導く数式が存在するのかもわかりません。
ですが、僕では、おそらくその解に手が届かないでしょう。
前途は多難ですが、これからも、のんびりと機械学習を学んでいこうと思います。

0
1
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
Sign upLogin
0
1

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?