1

我正在为（PO）MDP 编写一个工具箱，并且看到出现了一个不好的模式。尤其是在实施强化学习算法时，我倾向于重复自己。请参阅以下伪算法：

arguments: epsilon

v <- initial V values
c <- initial C values

while not good-enough
   delta <- 0.0
   if in-place
        v_old <- copy(v)
    else
        v_old <- reference to v
    for s in ss
        a = some_value(s,old_v)
        old_v <- v_old[s]
        v[s] = c*a*v_old[s]
        delta = max(delta,old_v-v[s])
    if delta < epsilon
        good-enough <- true

return v

现在看看这个几乎相同的算法：

arguments: epsilon,gamma

v <- initial V values
c <- initial C values

while not good-enough
    delta <- 0.0
    if in-place
        v_old <- copy(v)
    else
        v_old <- reference to v
    for s in ss
        a,o = get_a_and_o(s)
        old_v <- v_old[s]
        v[s] = c*v_old[s]*exp(o-a)
        delta = max(delta,old_v-v[s])
    if delta < epsilon(/1-gamma)
        good-enough <- true

return v

这些算法之间有一些简单的区别，但我重复了很多次。现在我的问题是：你如何抽象出这两个示例算法之间的共同部分（适用于实际算法）？

我看过一种方法（在 python 中），你给算法一个 pre、一个 post 和一个循环函数，它们分别在每次迭代之前、之后和为每个迭代调用，并传递一个算法状态字典来保存变量。但是这种方法似乎不是很好。有什么建议么？

4

3 回答 3

1

显然，这两种算法有很多共同点：整体工作流程/步骤几乎相同，唯一的区别是步骤中​​发生的具体情况。这是功能方法大放异彩的地方：您希望替换特定功能/评估，同时保持整体结构完整。

无需详细说明，查看您的代码，您可以看到：

  1. 他们使用相同的输入 V
  2. 在每次迭代中，使用 V 和一些参数，生成 V 的更新值
  3. 在每次迭代中，使用新旧 V 以及一些参数，评估一个条件 - 新 V 是否足够好，或者算法是否应该继续？

这是一个关于如何处理它以避免重复的草图：

您可以将 2. 改写为“在每次迭代中，我们将对 V 的当前值应用一个函数，这将返回一个更新后的值 V'” - 显然，该函数具有签名Updater: fun 't -> 't（Updater 函数接受类型 t，并返回相同类型的输出）。

类似地，第 3 步可以表述为“在每一步，我们将对 (V, V') 对应用一个函数，它会告诉我们是或否这是否足够好” - 这个函数需要一个类似的签名Finished: fun ('t * 't) -> bool. （给定一个 't 类型的两个项目的元组，评估并给我一个真/假答案）。

您现在可以提取 Updater 和 Finished 函数的细节，并将它们作为参数传递给主算法（我们称之为循环搜索），如下所示：

let Search (Updater: fun 't -> 't) 
           (Finished: fun ('t * 't) -> bool) 
           currentV: 't =
    v' = v
    while not Finished (v, v')
        v' <- Updater v
    return v

（上面的示例实际上并不完全正确，但传达了精神。您通常会将其写为函数式的递归，如下所示：

let rec Search (Updater: fun 't -> 't) 
               (Finished: fun ('t * 't) -> bool) 
               currentV: 't =
    if Finished (v, v') 
        then return v'
    else
        Search Updater Finished v'

现在不必重写整个循环，您可以定义要应用于更新步骤和完成步骤的特定函数，并且您的代码重复消失了 - 整个循环/结构保持不变，您只需编写完全具体到手头的问题。

我在这里做了很多手，希望这会有所帮助。如果您有兴趣，我可以提供 F# 或 C# 中的代码示例，说明有关工作代码的想法。

于 2012-11-30T20:00:27.627 回答
1

面向对象的方法是创建一个基类，其中包含算法的公共部分，但不包含特定于应用程序的部分（即 pre、post 或 loop 函数）。相反，它只是调用了它自己没有实现的虚拟方法。

然后，当您想实例化一个实际用例时，您将创建该基类的子类，其中仅包含基类代码需要调用的虚拟方法的实现。

于 2012-11-30T18:09:14.613 回答
0

Use first-class functions: Encapsulate the different argument types in another class (an array, tuple, etc.) and pass a function called, perhaps, calculateDeltaFunction to your function and then call it, i.e.,

def oneDeltaWay(s, myAlgorithmArgs) : 
  ...first example...

def anotherDeltaWay(s, myAlgorithmArgs) : 
  ...second example...

def commonStructure(calculateDeltaFunction, functionSpecificArgs) :
  ... common code ...  
  for s in ss
    delta = calculateDeltaFunction(s, functionSpecificArgs)
    if delta < epsilon(/1-gamma)
       good-enough <- true
  ...etc...

commonStructure(oneDeltaWay, firstTypeOfArgs)
commonStructure(anotherDeltaWay, secondTypeOfArgs)
于 2012-11-30T20:16:11.667 回答