machine-learning - 在 Q 学习中具有两个以上动作的玻尔兹曼探索

Question

我在 Q-learning 中使用 Boltzman 探索，每个状态至少有 10 个动作。我知道只有两个动作，玻尔兹曼探索可以非常简单地应用如下：

1. 使用玻尔兹曼探索方程计算两个动作的 pr1 和 pr2。
2. 生成一个随机数r
3. 假设pr1>pr2。如果 r<=pr1，采取对应概率 pr1 的动作。如果 r>pr1，则采取对应于 pr2 的动作。

但是，我怎样才能用 10 个动作做到这一点？在每个决策步骤，我都会更新所有动作的概率。这给了我最佳动作概率最高的所有动作的概率分布。在这种情况下如何使用玻尔兹曼探索来选择动作？

Answer 1

也许有更好的方法来做到这一点，但主要思想是：

def weighted_choice(weights):
    r = uniform(0, sum(weights))
    for i, weight in enumerate(weights):
        r -= weight
        if(r < 0):
            return i

其中 weights 是 pr1,pr2,.. 的列表，返回值是获胜动作的索引

Answer 2

以下是关于加权随机抽样的精彩讨论：飞镖、骰子和硬币。

这是我对 Vose 的 Alias 方法的实现：

class WeightedRandom
{
    private alias : array[int];
    private prob  : array[double];

    private random : Random;

    public this(p : array[double], random : Random)
    {
        this.random = random;

        def n = p.Length;

        alias = array(n);
        prob  = array(n);

        def small = Queue(n);
        def large = Queue(n);

        def p = p.Map(_ * n : double);

        foreach (x in p with i)
            (if (x < 1.0) small else large).Enqueue(i);

        while (!small.IsEmpty && !large.IsEmpty)
        {
            def s = small.Dequeue();
            def l = large.Dequeue();
            prob[s]  = p[s];
            alias[s] = l;
            p[l] = p[l] + p[s] - 1;
            (if (p[l] < 1.0) small else large).Enqueue(l);
        }

        while (!large.IsEmpty)
            prob[large.Dequeue()] = 1.0;

        while (!small.IsEmpty)
            prob[small.Dequeue()] = 1.0;
    }

    public NextIndex() : int
    {
        def i = random.Next(prob.Length);
        if (random.NextDouble() < prob[i])
            i;
        else
            alias[i];
    }
}