MDP、Bellman 方程与策略梯度基础

public class Main {
  static double[] solve(double[][][] p,double[][] r,boolean[] end,double gamma,double eps,int max) {
    if(p==null||r==null||end==null||p.length==0||r.length!=p.length||end.length!=p.length
       ||!Double.isFinite(gamma)||gamma<0||gamma>=1||!Double.isFinite(eps)||eps<=0||max<=0)
      throw new IllegalArgumentException("configuration");
    int n=p.length;
    double[][][] normalized=new double[n][][]; // 私有副本避免改写调用方的转移模型。
    for(int s=0;s<n;s++) {
      if(p[s]==null||r[s]==null||p[s].length==0||p[s].length!=r[s].length)throw new IllegalArgumentException("actions");
      normalized[s]=new double[p[s].length][n];
      for(int a=0;a<p[s].length;a++) {
        if(p[s][a]==null||p[s][a].length!=n||!Double.isFinite(r[s][a]))throw new IllegalArgumentException("row");
        double sum=0;
        for(double q:p[s][a]){if(!Double.isFinite(q)||q<0)throw new IllegalArgumentException("probability");sum+=q;}
        if(!Double.isFinite(sum)||Math.abs(sum-1)>1e-12)throw new IllegalArgumentException("normalization");
        for(int t=0;t<n;t++) normalized[s][a][t]=p[s][a][t]/sum; // 修正容差内的行和偏差。
      }
    }
    double[] v=new double[n];
    for(int iteration=0;iteration<max;iteration++) {
      double[] next=new double[n]; double delta=0;
      for(int s=0;s<n;s++) {
        if(end[s])continue; // 终止价值固定为零，进入终止的奖励已在R里。
        double best=Double.NEGATIVE_INFINITY;
        for(int a=0;a<p[s].length;a++) {
          double q=r[s][a];
          for(int t=0;t<n;t++) q+=gamma*normalized[s][a][t]*v[t]; // 本轮只读旧数组。
          if(!Double.isFinite(q))throw new IllegalArgumentException("overflow");
          best=Math.max(best,q);
        }
        next[s]=best;delta=Math.max(delta,Math.abs(best-v[s]));
      }
      v=next;
      if(delta<=eps*(1-gamma))return v; // 精确算术下的保守误差条件，不是浮点认证区间。
    }
    throw new IllegalStateException("iteration budget exhausted");
  }
  static void near(double a,double b){if(!Double.isFinite(a)||Math.abs(a-b)>1e-6)throw new AssertionError();}
  static void bad(Runnable r){try{r.run();}catch(IllegalArgumentException e){return;}throw new AssertionError();}
  public static void main(String[] args){
    double[][][] p={{{0,1,0},{0,0,1}},{{0,0,1},{0,0,1}},{{0,0,1},{0,0,1}}};
    double[][] r={{0,1},{2,0},{0,0}};boolean[] end={false,false,true};
    double[] v=solve(p,r,end,.9,1e-8,100);near(v[0],1.8);near(v[1],2);near(v[2],0);
    near(solve(p,r,end,0,1e-8,100)[0],1);
    double[][][] loop={{{1}}};double[][] reward={{1}};boolean[] nonterminal={false};
    near(solve(loop,reward,nonterminal,.9,1e-8,500)[0],10);
    double[][][] almost={{{1+5e-13}}};
    near(solve(almost,reward,nonterminal,.9,1e-8,500)[0],10);
    if(almost[0][0][0]!=1+5e-13)throw new AssertionError("input changed");
    near(solve(almost,new double[][]{{0}},nonterminal,1-1e-13,1e-8,2)[0],0);
    bad(()->solve(p,r,end,1,1e-8,100));
    bad(()->solve(new double[][][]{{{.5}}},reward,nonterminal,.9,1e-8,100));
    boolean exhausted=false;
    try{solve(loop,reward,nonterminal,.9,1e-8,1);}catch(IllegalStateException e){exhausted=true;}
    if(!exhausted)throw new AssertionError();
    System.out.println("PASS value, terminal, zero discount, loop, invalid model and budget checks");
  }
}