java - LinUCB exploration-exploitation 算法不会随时间改善结果

Question

我正在尝试实现以下论文中给出的算法 1。 http://www.research.rutgers.edu/~lihong/pub/Li10Contextual.pdf

这是一个典型的探索-开发算法。我使用了公式 payoff=mean+contant*standard deviation

首先，我对我拥有的一组数据运行算法，然后我从数据集中输入一条记录作为新输入，看看它是否可以预测正确的输出。但它给出了错误的输出，所以我给出了 0 奖励并重新计算了该臂的均值和标准差并继续算法。但每次它总是返回相同的 ARM 。均值也不会改变。

有人可以向我解释一下，当给出负反馈时，该算法的均值和方差是如何变化的吗？我总是获得相同值的原因是什么？

我用过java编程。代码如下。

public void LINUCB(double[] newFeature, Arm arm) {
    LOGGER.log(Level.INFO, "LINUCB");
    LOGGER.log(Level.INFO, "Arm number " + arm.getArmID());
    if (arm.isNew()) {
        arm.setFeatureMatrix(getIdentityMatrix(ConstantValues.FEATURE_DIMENSION));
        arm.setResponseVector(new double[ConstantValues.FEATURE_DIMENSION]);
    }

    double[][] invertedFeatureMatrix = invert(arm.getFeatureMatrix());
    /**The response vector is [D*M][M].  it is the multiplication of tranpose of design matrix with the user feedback provided to each trial M*/
    //TODO use gradient descent here.
    double[] theta = getSquareMatrixColumnVectorMultiplication(invertedFeatureMatrix, arm.getResponseVector());        
    double meanPayOff = getRowVectorColumnVectorMultiplication(theta, newFeature);
    System.out.print(" meanPayOff " + meanPayOff);
    double standardDeviation = calculateUCB(newFeature, arm.getFeatureMatrix());
    System.out.print(" standardDeviation " + standardDeviation);
    double payOffForArm = meanPayOff + standardDeviation;
    System.out.print(" payOffForArm " + payOffForArm);
    if (payOffForArm > maxPayOff) {
        maxPayOff = payOffForArm;
        //armWithMaxPayOff = arm;
        //indexOfArmWithMaxPayOff = armArrayList.indexOf(arm);
        maxPayOffArmID = arm.getArmID();
    }
    System.out.println(" ");
}

private double calculateUCB(double[] newFeature, double[][] featureMatrix) {
    double[] tmpColumVector = getSquareMatrixColumnVectorMultiplication(featureMatrix, newFeature);
    double tmpUCB = Math.sqrt(getRowVectorColumnVectorMultiplication(tmpColumVector, newFeature));
    double UCB = ConstantValues.ALPHA * tmpUCB;
    return UCB;
}

alpha 设置为 0.3。

Answer 1

对于每一轮，LinUCB 应该根据其特征向量更新每只 ARM 的置信上限。我认为您错误地实现了算法。

• 您正在传递一个特征和一个 ARM 。您应该检查 ARM 的特征。您的 newFeature 参数可能独立于 ARM ，在这种情况下，与上下文(在本例中为特征向量)和奖励的任何相关性都被排除在外。
• Theta 用于计算预期 yield ，假设它在 ARM 的特征向量中与系数 vector theta 成线性关系。当它应该与 ARM 的特征相乘时，您将它与 newFeature vector 相乘。
• 除非它是静态变量，否则 maxPayOff 不会跟踪所有臂的最大 UCB。它看起来像是条件语句中的局部变量，因此无法捕获所有臂的最大值。
• 最后，检查您的奖励是否在 0 和 1 之间。这是一个非常常见的错误，可能会导致奇怪的行为。