SewiGの日記

■ [Programming] Q学習 (Q-Learning)

Q学習は強化学習の一手法です。ある状態と、そのとき選択することのできる行動をセットで考え、セットに対する評価値をQ値と呼びます。そして、このQ値が大きくなるような行動を選択していくのがQ学習の流れになります。

例えば以下のようなマルコフ決定過程があるとします。

Q値の初期値は0として、S35の状態からS47に移るような行動を取った場合に報酬(>0)が与えられ、初期状態に戻るという問題を考えます。状態S35で行動aを取ったら報酬が与えられた場合、次のエピソードでは状態S35における各行動のQ値をみると行動aが最大になっているので、状態S35では行動aを取ります。そして状態S35に移るような行動を取った状態へと報酬が伝播していき充分なエピソード経過後は初期状態から終了状態までの状態行動対のQ値が高くなります。詳しい解説は参考文献*1をどうぞ。

基本的なアルゴリズムは以下のようになります。行動選択でε-greedy方策を使用すると、適度に探索が行われるので局所解にはなりにくいので使いましょう。

public void step() {
	// 行動選択
	currentAction = selectAction(currentState, currentAction);
	
	int oldState = currentState;
	int oldAction = currentAction;
	
	// 行動実行
	double r = executeAction();
	
	// Q値の更新
	double currentMaxValue = qValue[currentState][0];
	currentAction = 0;
	for (int i = 1; i < maxAction; i++) {
		if (qValue[currentState][i] > currentMaxValue) {
			currentMaxValue = qValue[currentState][i];
			currentAction = i;
		}
	}
	qValue[oldState][oldAction] += learningRate*(r + discountRate*qValue[currentState][currentAction] - qValue[oldState][oldAction]);
	
	// 状態の更新
	stateChange(oldState, oldAction);
}