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

人工知能学習1

今日は強化学習の一つであるε-greedy法で多腕バンディット問題を解きます。

これは、複数のアーム(腕)から最良のものを選択する問題です。

見えていない確率を払い戻しを元に推定していきます。

もともと、スロットマシン(バンディットマシン)での問題だったので、こう呼ばれているようです。

さて、実際に使うε-greedy法は、貪欲法と呼ばれるgreedy法を拡張したもので、greedy法が最も価値の高いものを(一定期間の学習を経たあと)選び続けるのに対し、こちらは学習しつつ最も価値の高いものを選択します。

これにより長期的に払戻額が大きくなるような選択を(最良の選択を)できる確率が高まります。

具体的なアルゴリズムは、

1.まだ選んでいない手があるならその中からランダムに選ぶ

2.確率εで全ての手の中からランダムに選ぶ

3.そうでなければ最も価値の高い手を選ぶ

となっています。

import java.util.Random;

public class e_greedy {

	public static void main(String[] args) {
		Random r = new Random();
		double e = 0.1d;//確率ε
		int gene = 100;//繰り返す(世代を重ねる)回数
		double[] table = {0.6 , 0.5 , 0.4};//確率テーブル(バンディット),払戻額は同じとします
		int[][] log = new int[table.length][2];//選んだ回数と払い戻された回数なので2
		int myarm = 0;
		for(int g = 0;g < gene;g++){//世代数分ループ
			double[] winrate = new double[table.length];//ここから勝率,上書きするので後ろから
			for(int i = 0; i < table.length;i++){
				if(log[i][0] != 0){
					winrate[i] = log[i][1] / (double)log[i][0];
				}
			}
			for(int i = 0; i < winrate.length;i++){
				if(winrate[myarm] >  winrate[i]) continue;
				if(winrate[myarm] == winrate[i] && r.nextDouble() <= 0.5d) myarm = i;
				if(winrate[myarm] <  winrate[i]) myarm = i;
			}
			if(Math.random() <= e) myarm = r.nextInt(table.length);//確率εでランダム
			
			boolean[] zerolist = new boolean[table.length];
			int countzero = 0;
			for(int i = 0; i < table.length; i++){//まだ出していない手をリストに
				if(log[i][0] == 0){
					zerolist[i] = true;
					countzero++;
				}
			}
			
			if(countzero!=0){
				while(true){	
					int tmp = r.nextInt(table.length);//乱数を出してまだ出していない手をランダムに
					if(zerolist[tmp]){
						myarm = tmp;
						break;
					}
				}
			}
			log[myarm][0]++;
			if(r.nextDouble() <= table[myarm]) log[myarm][1]++;
			System.out.println("Gene : " + g + " myarm : " + myarm);
		}
		
	}

}

greedyアルゴリズムは適当に100世代分くらい均等に選んでからそれのみを選択するという手法で簡単にできると思います。

世代の進行と最適化をグラフ出力したかったのですが断念

ライブラリの導入がめんどくさいので...Pythonなら楽そうなんだよなぁ...