乱数を使った強化学習の実行結果が大幅に変わることはおかしくないか.

Question

前提・実現したいこと

NNのグリッドワールドの任意の位置にゴールを配置する.(これは一回だけです)
NNのグリッドワールドの任意の位置にエージェントを配置する.(これは繰り返し回数loop回です)
1番始めは, 任意のマスの上下左右は等確率で移動するようにするが,
移動の上限回数以内にゴールした場合は,ゴールから一定のステップだけ遡って
報酬を与える.(このときゴールから遠ざかるほど報酬は小さくなる.)
つまり,あるマスのある方向が,ゴールしたときに通られれば通られるほどその方向は確率が
大きくなる.(注意)繰り返し回数が終わるまで確率は更新しつづけるので上下左右を等確率で
設定するのは実行時の最初の1回だけです.)
(また繰り返し回数分エージェントは作り, それぞれのスタート位置も異なります.)
これを繰り返し回数だけやったのちに,(後半戦突入)再び繰り返し回数だけ任意の位置にエージェントを配置して
ゴールを目指すが,このときの移動は確率に基づくのでは無く,前半で設定した確率のうち一番
大きいものを移動方向として採用する.また,ゴールの位置は1行目で配置した位置と同じ位置である.
このときゴールした回数を求める.

といったことをしたいです.
拙い日本語で申し訳ありません.

発生している問題・エラーメッセージ

エラーメッセージは出ておりません.

同じnについて、ゴールの回数が実行ごとに大幅に変わってしまうことに違和感があって, 
僕のコードがおかしいと思うので指摘していただきたいです.
乱数を使っているので実行結果が変わること自体は感覚的に納得しますが
たとえば, n=5のときに実行結果が下は0から上は66まで出るのはさすがに変だと思います.

また, 報酬を与える際のやり方もうまいやり方がわかりません.(GridクラスのsetArrowメソッド)
(確率なので合計だけでなく各方向も0以上1以下に収めるべきかなと思うのですが、
例えば0.01, 0.01, 0.01, 0.97から報酬を0.97をもつ方向に0.5あげると0.97が
1を超えて0.01は0を下回りますが, 0.97を1で押さえつけてしまうと正しい評価にならないんじゃ
ないかとも思います.)

該当のソースコード

/////Main.javaです/////
import java.util.*;

public class Main{
  public static void main(String[] args){
//原則入力を受け付けますが,入力の手間を省くためここでは予め値を代入しています

    /*Scanner sc = new Scanner(System.in);
    System.out.print("マップの大きさ：");
    int n = sc.nextInt();
    System.out.print("ステップ数：");
    int T = sc.nextInt();
    System.out.print("繰り返し回数：");
    int loop = sc.nextInt();
    System.out.print("報酬：");
    double P = sc.nextDouble();
    System.out.print("エージェントの寿命：");
    int life = sc.nextInt();
    int tactics = 0;
    int cnt = 0;*/
//各変数の値は適当です.
    int n = 5;//グリッドワールドの大きさ, ここでは25(5*5)マスあることになります.
    int T = 50;//ゴールして報酬を与える際, ゴールから遡るステップ数です.
    int loop = 100;//繰り返し回数です.
    double P = 0.5;//ゴールした際に与える報酬です.
    int life = 200;//1つのエージェントがゴールを目指すときに動ける上限回数です.
    int tactics = 0;//ゴールした際に報酬を与えるかカウントするかの違いのために使います.
    //(続き)tactics == 2 のときは<前提・実現したいこと>の(後半戦)に当たります.
    int cnt = 0;//後半戦におけるゴールへの到達回数です.

    Agent.setVariable(n, T, life, P);
    Agent.setGoal();
    Grid grid = new Grid(n);

    for(tactics = 1; tactics <= 2; tactics++){
      for(int i = 0; i < loop; i++){
        boolean ans = true;
        Agent agent = new Agent();

        for(int j = 0; j < life; j++){
        //ans==1のときはゴールしたときです.
          ans = agent.askDirectory(grid, j, tactics);
          if(ans){
            if(tactics == 1){
            //報酬を与えます.
              agent.giveReward(grid, j);
            }
            //到達回数を数えます.
            if(tactics == 2) cnt++;
            break;
          }
        }
      }
    }
    System.out.println(cnt);
  }
}

/////Agent.javaです/////
import java.util.*;

public class Agent{
  private final int UP = 0;
  private final int RIGHT = 1;
  private final int DOWN = 2;
  private final int LEFT = 3;

  private int[] history;//移動方向を保存する配列
  private int[][] start = new int[1][2];
  private int[][] tmp = new int[1][2];
  private static int[][] goal = new int[1][2];
  private static int n;
  private static int T;
  private static int life;
  private static double P;

//エージェントごとに(繰り返し回数の1回1回で)スタート位置は異なります.
  public Agent(){
    Random r = new Random();
    history = new int[Agent.life];//移動の上限回数分用意します.
    this.start[0][0] = this.tmp[0][0] = r.nextInt(Agent.n);
    this.start[0][1] = this.tmp[0][1] = r.nextInt(Agent.n);
    //System.out.println("start_x:" + this.start[0][0]);
    //System.out.println("start_y:" + this.start[0][1]);
  }

  public static void setVariable(int n, int T, int life, double P){
    Agent.n = n;
    Agent.T = T;
    Agent.life = life;
    Agent.P = P;
  }

//ゴールの位置は, 1回の実行においてすべてのエージェントに共通なのでクラス変数にします.
  public static void setGoal(){
    Random r = new Random();
    Agent.goal[0][0] = r.nextInt(Agent.n);
    Agent.goal[0][1] = r.nextInt(Agent.n);
  }

  public boolean askDirectory(Grid g, int life, int tactics){
    boolean flag = false;

//移動先がグリッドワールド以内であるとおきwhile文を抜けます.
    while(flag == false){
      int next_line = this.tmp[0][0];
      int next_row = this.tmp[0][1];
      int d = 0;
//移動方向を決めるときに, 確率的なのがtactics==1, 確率が一番大きい方向を使うのがelse(tactics==2)です.
      if(tactics == 1){
        d = g.showDirectoryLearn(this.tmp[0][0], this.tmp[0][1]);
      }else{
        d = g.showDirectoryAssess(this.tmp[0][0], this.tmp[0][1]);
      }

      switch(d){
        case UP:
          next_line--;
          break;
        case RIGHT:
          next_row++;
          break;
        case DOWN:
          next_line++;
          break;
        case LEFT:
          next_row--;
          break;
      }

      if(0<=next_line && next_line<Agent.n && 0<=next_row && next_row<Agent.n ){
        this.tmp[0][0] = next_line;
        this.tmp[0][1] = next_row;
        history[life] = d;
        flag = true;
      }
    }

    if(this.tmp[0][0] == Agent.goal[0][0] && this.tmp[0][1] == Agent.goal[0][1]){
      return true;
    }else{
      return false;
    }

  }

  public void giveReward(Grid grid, int j){
    int d = 0;
    double reward = 0;
    int next_line = Agent.goal[0][0];
    int next_row = Agent.goal[0][1];

    int target = 0;
    int idx = j;
    int t = 1;

//例えば1ステップ目でゴールしたとき, j=0. ということは1ステップ目の方向はhistory[0]に入っている.
//tは遡った回数です. Tステップだけ遡り, かつ添字は0以上のときだけ報酬を考える.
    while(idx >= 0 && t <= Agent.T){
      d = history[idx];

      switch(d){
        case UP:
          next_line++;
          break;
        case RIGHT:
          next_row--;
          break;
        case DOWN:
          next_line--;
          break;
        case LEFT:
          next_row++;
          break;
      }

      if(next_line == 0){
        target = next_row;
      }else{
        target = next_line * Agent.n + next_row;
      }
//報酬の式は[ゴールからtステップ遡るグリッドにおいて行動d(dは上下左右のどれかを表します)
//を選択したとき, d^tとして, 確率をlength_old(d^t)を次の式によりlength_new(d^t)に変更します.
//length_new(d^t) = length_old(d^t) + P * (T - t + 1)/T (t = 1, 2, ・・・, T]です.
//ここでは, +の後ろを計算してrewardに入れて, それをsetArrowを使ってグリッドに設定しに行きます.
      reward = this.P * (Agent.T - t + 1) / Agent.T;

      grid.setArrow(target, d, reward);

      idx--;
      t++;
    }
  }

}

/////Grid.javaです/////
import java.util.*;

public class Grid{
  private final int UP = 0;
  private final int RIGHT = 1;
  private final int DOWN = 2;
  private final int LEFT = 3;

  private int[][] map;
  private double[][] arrow;
  private int n;

  private List<Integer> arylist = new ArrayList<>();


  public Grid(int n){
    this.n = n;
    this.map = new int[n][n];//いらないっぽいです.
    this.arrow = new double[n*n][4];//すべてのマスの上下左右4方向の確率を入れるための配列
    setArrowEqual(n);
  }

//実行時一番はじめに4方向の確率を等しくします.
  public void setArrowEqual(int n){
    for(int i = 0; i < n*n; i++){
      for(int j = 0; j < 4; j++){
        this.arrow[i][j] = 0.25;
      }
    }
  }

    public int showDirectoryLearn(int line, int row){
    int target = 0;
//エージェントのx座標(line), y座標(row)に対応するarrowの添字を見つけます.
//1行n列(map[0][n-1])に対応するのはarrow[n-1], 2行n列(map[1][2n-1])に対応するのはarrow[2n-1]
//なので, これを一般化したものです.
    if(line == 0){
      target = row;
    }else{
      target = line * this.n + row;
    }

//最初は等確率なので, やってることは0.25以下は上, 0.50以下は右という風な設定です.
    double up = this.arrow[target][0];
    double right = up + this.arrow[target][1];
    double down = right + this.arrow[target][2];
    double left = down + this.arrow[target][3];

    Random r = new Random();
    double value = r.nextDouble();
    if(value <= up){return UP;}
    if(value <= right){return RIGHT;}
    if(value <= down){return DOWN;}
    return LEFT;
  }

//tactics==2のときは確率が一番大きいものを選びます.
//ただし複数の方向が最大値をもつときはそれらの中からランダムに方向を選びます.
  public int showDirectoryAssess(int line, int row){
    int target = 0;
    int cnt = 0;
    double max = Double.MIN_VALUE;
    int ans = 0;

    if(line == 0){
      target = row;
    }else{
      target = line * this.n + row;
    }
//最大値を求めます.
    for(int i = 0; i < 4; i++){
      max = Math.max(this.arrow[target][i], max);
    }
//最大値をもつ個数を知ります.
    for(int i = 0; i < 4; i++){
      if(max == this.arrow[target][i]) this.arylist.add(i);
    }

    if(this.arylist.size() == 1){
      ans = this.arylist.get(0);
    }else{
      Random r = new Random();
      int value = r.nextInt(this.arylist.size());
      ans = this.arylist.get(value);
    }

    this.arylist.clear();
    return ans;
  }
//このやり方では, 合計確率は1ですが, ある方向が1を超えたり0を下回る可能性があり, 
//うまいやり方が見つかりません.
  public void setArrow(int target, int d, double reward){
    for(int i = 0; i < 4; i++){
      this.arrow[target][i] -= reward / 3;
    }
    this.arrow[target][d] += 4 * reward / 3;
  }
}

補足情報（FW/ツールのバージョンなど）

java version "10.0.2" 2018-07-17
Java(TM) SE Runtime Environment 18.3 (build 10.0.2+13)
Java HotSpot(TM) 64-Bit Server VM 18.3 (build 10.0.2+13, mixed mode)

Answer 1

本プログラムの結果を左右する原因にはなりません(※)が、1つだけ指摘しておきます。

コードでは乱数を必要とする場面でその都度乱数発生器を初期化している個所があります。

計算機における乱数の発生はあるseed値から始めてなんらかの演算(seed値に対してbitをかき混ぜるような演算)を施し次々に数値を生成(それを疑似的な乱数とみなす)という方法を用います。seed値が同じ値の場合は発生する乱数はまったく同一のものになります。
本来は「一連の乱数が必要となるような論理でただ１回だけ初期化された乱数発生器をずっと使い続ける」のが普通です。

一番望ましい方法は同一のスレッド内で用いる乱数発生器はただ一つにすることだと思います。

// よい例:

class Main {
  static Random random = new Random();

  ...

  void foo(Other other) {
    // Javaバージョンにかかわらず結果がtrueになる確率は概ね10%
    System.out.println(random.nextInt(10) == other.bar(10));
  }
}

class Other {
  int bar(int n) {
    return Main.random.nextInt(n);
  }
}

// 悪い例

class Main {
  int foo(Other other) {
    // メソッドが呼び出されるたびに必要となる乱数を、毎回生成した乱数発生器により求めるのはおかしい
    Random random = new Random();
    int randomNumber = random.nextInt(10);
    // randomNumberにより何か計算する
    return result;
  }
}

---

※:
Java 10.0.2時点ではRandomクラスの引数なしコンストラクターでのseed値は「いかなるスレッドからいかなるタイミングで並行して呼び出されても、各々がなるべくユニークなseed値を持つような配慮」が施されています。それゆえ乱数が必要な場面で毎回乱数発生器を生成してもそこそこランダムな値となるようになっています。

しかし例えばJava 8のRandom()は単にSystem.currentTimeMillis()をseed値にしていたため、乱数発生器を「異なるクラスごとに準備」するような論理を用いてしまうとそれぞれのクラス上にある乱数発生器のseed値が同一の値で初期化される確率が非常に高くなります。もしseed値が同一だと生成される乱数列はまったく同一のものになります。

それを防ぐためには

• 同一のスレッドではただ一つの乱数発生器を用いる
• 乱数発生器を生成する際に自前でなるべくユニークな値となるようなseed値を用いるように工夫する

といった配慮が必要でした。java10ではそのような工夫が必要なくなり、複数の個所で乱数発生器が必要な場面でも引数なしコンストラクターRandom()でよくなりちょっと使いやすくなりました。逆に言えばそういう場面の使い勝手がよくなっただけにすぎず、乱数発生器の使い方の基本は依然として「必要な乱数列を得るためにただ一つの乱数生成器を用いるべき」であることには変わりはありません。

Comments

[退会済みユーザー]

回答ありがとうございます.
そういう作法というか, きちんとした乱数の使い方を知りませんでした.
Main.javaで
Random r = new Random();
をして, このrを各クラスファイルのメンバ変数に設定しなおしました.
今更気づいたのですが, Random()を使うことで実行時の時刻に乱数列が左右されるので
毎回cntの値が変わることは当たり前かなと思い, seedを自分で指定してみました.
(例えば, long seed = 20; Random r = new Random(seed);のようにです)
このとき, seedの値によって, nとの相関が取れたり取れなかったりして(これも
当たり前っちゃ当たり前ですが...)nと回数の関係がseedに左右されるのはおかしな
話だと思うのですが, どう思われますか...?

[KSwordOfHaste]

コメント遅くなりましたが・・・

自分が回答したために混乱させてしまったなら申し訳ないのですが、自分の指摘は先頭に書いたように、「本プログラムの結果を左右する原因にはならない」ものであり乱数の発生のさせかたが普通ではないので「それはそれで直しておいた方が今後のためによいと思う」といった程度のことでしかありません。

自己解決されたようで何よりですが、解決したということは原因はswordoneさんが指摘しておられる「確率の扱いの問題」だったのだと思います。おそらく乱数生成の部分は自分の指摘を反映しようがしまいが結果には大きな違いは出ないと思います。

Answer 2

「報酬」とやらを、確率の値として加減しているのが変に思います。
ただ単にスコアとして加算記録し、そのスコアの合計の大小で方向を決定するというのはどうでしょう。
例えばゴールから10ステップ前に戻った場所での選択方向に50-10=40ポイント加算し、
ある地点での上下左右の方向のそれぞれのスコアが50,100,150,200とかなら、一番大きい右に移動する、といった具合に。

関係ないですが、配列の使い方が変です。
Agentのgoalとかtmpとかstartをnew int[1][2]で生成していますが、最初の[1]が無駄です。
またGridで2次元にし、グリッドの位置を1次元変換していますが、それなら3次元使ったほうがわかりやすいです。
1次元変換するにしても、lineが0か否かで場合分けするのが無駄です。0でも同様の計算ができますから。

Comments

[退会済みユーザー]

いつも回答ありがとうございます.
報酬の与え方について, 加減から加算のみに変えてみました。
ご指摘いただいて変更を加えたところは
変数については
・goal, tmp, startを[1][2]から[2]へ
・arrowを[n*n][4]から[n][n][4]へ
メソッドについては
・GridクラスのsetArrowメソッドを
public void setArrow(int line, int row, int d, double reward){
this.arrow[line][row][d] += reward;
}

・GridクラスのshowDirectoryLearnメソッドを
public int showDirectoryLearn(int line, int row){
double sum = 0;
for(int i = 0; i < 4; i++){sum += this.arrow[line][row][i];}

double up = this.arrow[line][row][0];
double right = up + this.arrow[line][row][1];
double down = right + this.arrow[line][row][2];
double left = down + this.arrow[line][row][3];

Random r = new Random();
double value = r.nextDouble() * sum;
if(value <= up){return UP;}
if(value <= right){return RIGHT;}
if(value <= down){return DOWN;}
return LEFT;
}

です.
ただ, こうした場合であってもcntが実行ごとに大きくばらついてしまうのですが,
そういうものなのでしょうか?

Answer 3

##問題
実行毎に結果が「大きく」異なる
##原因
Randomクラスの引数なしコンストラクタRandom()は現在時刻を利用するため
実行毎に得られる乱数列が異なる
##考えた解決法
0. seed値を指定して乱数列を得れば,実行毎すべてで等しい結果が得られる -> x
(理由) どのseed値であればうまい結果が得られるのか分からない

1. Random()クラスのRandom()を使うが, 以前のただの100回繰り返しではなく

100回繰り返しを複数回行って平均をとることで, 実行時刻による結果の差異を減らす -> o
(理由) 同じグリッドワールドの結果の差異に以前のような大きな開きがなく, グリッドワールドの
サイズが大きくなるとゴール回数も減る(のでおそらくこれでいいかなと)
##プログラムの変更点

• 繰り返し100回を行い, それを結果とした -> 繰り返し100回を100回行い, その平均を結果とすることにした

KSwordOfHasteさんのコメントより

• 乱数を使うたびに乱数生成器を作っていた -> Main.javaの序盤1回だけにした

swordoneさんのコメントにより

• goal, tmp, startが二次元配列だった -> 一次元配列にした
• arrowが二次元配列だった -> 三次元配列にした
• 報酬の与え方について, ゴールするときに通った方向はプラスの報酬,

通らなかった方向はマイナスの報酬だった -> 通った方向にプラスの報酬のみにした(追記1)

Main.javaです/////////////////////////////////////////////////////////////////////

import java.util.*;

public class Main{
  public static void main(String[] args){
    int n = 5;
    int T = 5;
    int loop = 100;
    int cntAverage = 100;
    double P = 10;
    int life = 10;
    int level = 0;
    int cntAssess = 0;
    int[] goal = {0, 0};
    Random r = new Random();

    Agent.setVariable(n, T, life, P, r, goal);
    Grid grid = new Grid(n, r);

    for(level = 1; level <= 2; level++){
      for(int i = 0; i < cntAverage; i++){
        for(int j = 0; j < loop; j++){
          boolean ans = true;
          Agent agent = new Agent();
          for(int k = 0; k < life; k++){
            ans = agent.askDirectory(grid, k, level);
            if(ans){
              agent.giveReward(grid, k);
              if(level == 1){break;}
              if(level == 2){cntAssess++; break;}
            }
          }
        }
      }
    }

    System.out.println("cntAssess average:" + cntAssess / cntAverage);
  }
}

Grid.javaです///////////////////////////////////////////////////////////////

import java.util.*;

public class Grid{
  private final int UP = 0;
  private final int RIGHT = 1;
  private final int DOWN = 2;
  private final int LEFT = 3;
  private int[][] map;
  private double[][][] arrow;
  private int n;
  Random r;
  private List<Integer> arylist = new ArrayList<>();

  public Grid(int n, Random r){
    this.n = n;
    this.map = new int[n][n];
    this.arrow = new double[n][n][4];
    this.r = r;
    setArrowEqual(n);
  }

  public void setArrowEqual(int n){
    for(int i = 0; i < n; i++){
      for(int j = 0; j < n; j++){
        for(int k = 0; k < 4; k++){
          this.arrow[i][j][k] = 0.25;
        }
      }
    }
  }


  public int showDirectoryLearn(int line, int row){
    double sum = 0;
    for(int i = 0; i < 4; i++){sum += this.arrow[line][row][i];}

    double up = this.arrow[line][row][0];
    double right = up + this.arrow[line][row][1];
    double down = right + this.arrow[line][row][2];
    double left = down + this.arrow[line][row][3];
    double value = this.r.nextDouble() * sum;

    if(value <= up){return UP;}
    if(value <= right){return RIGHT;}
    if(value <= down){return DOWN;}
    return LEFT;
  }


  public int showDirectoryAssess(int line, int row){
    int cnt = 0;
    double max = Double.MIN_VALUE;
    int ans = 0;

    for(int i = 0; i < 4; i++){
      max = Math.max(this.arrow[line][row][i], max);
    }

    for(int i = 0; i < 4; i++){
      if(max == this.arrow[line][row][i]) this.arylist.add(i);
    }

    if(this.arylist.size() == 1){
      ans = this.arylist.get(0);
    }else{
      int value = this.r.nextInt(this.arylist.size());
      ans = this.arylist.get(value);
    }

    this.arylist.clear();
    return ans;
  }

  public void setArrow(int line, int row, int d, double reward){
    this.arrow[line][row][d] += reward;
  }
}

Agent.javaです////////////////////////////////////////////////////////////////////


import java.util.*;

public class Agent{
  private final int UP = 0;
  private final int RIGHT = 1;
  private final int DOWN = 2;
  private final int LEFT = 3;
  private int[] history;
  private int[] start = new int[2];
  private int[] tmp = new int[2];
  private static int[] goal = new int[2];
  private static int n;
  private static int T;
  private static int life;
  private static double P;
  private static Random r;

  public Agent(){
    history = new int[Agent.life];
    this.start[0] = this.tmp[0] = Agent.r.nextInt(Agent.n);
    this.start[1] = this.tmp[1] = Agent.r.nextInt(Agent.n);
  }

  public static void setVariable(int n, int T, int life, double P, Random r, int[] goal){
    Agent.n = n;
    Agent.T = T;
    Agent.life = life;
    Agent.P = P;
    Agent.r = r;
    Agent.goal[0] = goal[0];
    Agent.goal[1] = goal[1];
  }

  public boolean askDirectory(Grid g, int life, int level){
    boolean flag = false;

    while(flag == false){
      int next_line = this.tmp[0];
      int next_row = this.tmp[1];
      int d = 0;
      if(level == 1){
        d = g.showDirectoryLearn(this.tmp[0], this.tmp[1]);
      }else{
        d = g.showDirectoryAssess(this.tmp[0], this.tmp[1]);
      }

      switch(d){
        case UP:
          next_line--;
          break;
        case RIGHT:
          next_row++;
          break;
        case DOWN:
          next_line++;
          break;
        case LEFT:
          next_row--;
          break;
      }

      if(0<=next_line && next_line<Agent.n && 0<=next_row && next_row<Agent.n ){
        this.tmp[0] = next_line;
        this.tmp[1] = next_row;
        history[life] = d;
        flag = true;
      }
    }

    if(this.tmp[0] == Agent.goal[0] && this.tmp[1] == Agent.goal[1]){
      return true;
    }else{
      return false;
    }
  }

  public void giveReward(Grid grid, int j){
    int d = 0;
    double reward = 0;
    int next_line = Agent.goal[0];
    int next_row = Agent.goal[1];
    int idx = j;
    int t = 1;

    while(idx >= 0 && t <= Agent.T){
      d = history[idx];
      switch(d){
        case UP:
          next_line++;
          break;
        case RIGHT:
          next_row--;
          break;
        case DOWN:
          next_line--;
          break;
        case LEFT:
          next_row++;
          break;
      }

      reward = this.P * (Agent.T - t + 1) / Agent.T;
      grid.setArrow(next_line, next_row, d, reward);
      idx--;
      t++;
    }
  }
}