Progress

本周进度总结：

leetcode刷题：目前还有 图 的深搜和广搜、还有一些细节实现题没有刷

实验的时候对于一些生成的数据有些不明白，然后看下项亮的《推荐系统实践》相关的内容

·目前遇到的问题：

作者给出的源代码是1.4版本的tensorflow，我这边是2.7版本的，有很多API用不了，得去查文档

数据预处理的结果的格式有问题，可以读，但是处理不了。可能是处理的时候出现了编码的问题

PPT

-- 看朋友关系文章

-- 总结对比两个模型的区别（一个是朋友，一个是产品

—看深度学习的文章，总结两篇文章对问题的建模，以及如何将深度学习和bandit 结合起来

--按着pdf刷leetcode

--看C++

ppt

本周进度总结：

· 对3篇文章的建模和实验进行了总结

·好像实现了Improving Bandit Learning via Heterogeneous Information Networks: Algorithms and Applications提出的算法

ppt

本周进度总结：

实验

• 因为之前没有考虑只写那个文章中提出的算法，数据的结构最开始有点复杂，后面也没有去改。代码有时候可以运行，有时候运行不了，结果也是错的。打算重新写一下了。

AAAI文章

• 总结了一下motivation，model，algorithm design 和 experiments data

WWW文章

• 关于滑动窗口的算法那边目前没有看明白

审稿的文章

• 还没看

吴恩达深度视频

• 99/183

PPT

本周进度总结：

看了一下那篇文章以及部分的参考文献，还是有点细节方面不太明白。

• 怎么去找meta-path

• 基于真实的数据怎么做实验

吴恩达视频目前进度在60/183，笔记记在印象笔记上面了。现在看到的还是关于梯度下降、正则化方面的内容。

PPT

本周进度总结：

在有cost的条件下做了一下UCB的实验

PPT

本周进度总结：

解决关于需要多少轮时间才能得到一个准确的UCB区间的问题

还是不知道在不知道准确单子数目下如何去估计单子的分布

本周讨论被指出的问题

pdf

本周进度总结：

将上次讨论结果中的\mu改为f(\mu)。做一下实验以及regret 的bound

本周讨论被指出的问题

ppt

本周进度总结：

1.看《Federated Multi-Armed Bandits》的应用部分

2.整理之前二次效用函数的问题思路

本周讨论被指出的问题

ppt

本周进度总结：

读kdd 的文章。

模型是什么，算法是什么，证明结论的是什么。

模型有没有什么不足的， 实验数据是什么

本周讨论被指出的问题

ppt

本周进度总结：

整理了一下之前的问题（ 二次方目标函数）

关于（拉了臂才知道单子数目）这块，没想到有什么合适的方法，之前说用什么条件分布，但是不知道怎么弄

本周讨论被指出的问题

ppt

本周进度总结：

·做实验。bug应该都没有了

本周讨论被指出的问题

ppt

本周进度总结：

·做实验。对于匈牙利算法矩阵中的一些值和玩家拉臂的策略有问题

本周讨论被指出的问题

ppt

本周进度总结：

·做实验，先用集中式去算最优的分配是多少，然后比较一下用UCB的情况得到的分配。代码部分应该没有什么问题，主要的问题应该是出现于cost的取值，以及估计的参数，因为需要根据求的分布取期望，因此需要准确的估计才能得出足够良好的期望

·研究如何让玩家不通过额外的信息去进行探索

本周讨论被指出的问题

ppt

本周进度总结：

·看leader-follower和Jordan的文章，整理了一下他们问题的设定与解决

·对于UCB的内容，思考还存在哪些问题

本周讨论被指出的问题

· 先用集中式去算最优的分配是多少，然后比较一下用UCB的情况得到的分配

· 系统不给玩家信息(单子的个数，每个臂上玩家的数目)，玩家如何去进行探索。

不需要知道P(K),P(K+1)...P()的概率，只需要知道P(k>K)的概率

ppt

本周进度总结：

还没有解决算法在存在0分配时失败的概率

本周讨论被指出的问题

根据LinUCB的情况分析一下，或者想一下为什么不能用这个方法去做

ppt

本周进度总结：

根据单子的数量的效用函数给出一个可能的UCB的解释，但是没考虑到Delta的增长

关于reward的效用函数，无法确定\mu之间的\epsilon是多少

本周讨论被指出的问题

ppt

本周进度总结：

还没有写好centralized的干货，有点问题

疑惑是否还需要采用匈牙利算法

不知道和UCB结合起来是对是错

然后用musical chair同样的方法好像也可以分析出来？

下周安排

考虑上图的两个方法

先看第二个

第一个，ETC，看估计的与真实的之间的差值，然后看能否将效用函数之间的差值是否是用最优分配减去次优分配的差值的1/2，如果是的话，那么我们可以去判断这个次优的是否在合适的范围内，如果在的话，那么可以考虑那样的一个分配

第二个：UCB的方法，先设置一个epsilon，即upper bound然后看效用函数的差值是否存在在一个与epsilon有关的，然后看最后的这个epsilon是否是随着时间是递减的

问题

问题描述：首先我们是需要去估计每一个单子的分布，通过研究均值去看待。然后我们根据估计出来的均值去分配玩家，最后得到一个在此分配下的臂的奖励的均值。我们期望在最后，能够得到一个关于均值的一个不等式

一个bound \sum_{i=1}\frac{1}{T^2}\leq\frac{1}{T}

ppt

本周进度总结：

将regret分为两个case讨论一下，一个是a=b=1的情况，还有一个是a>2的情况(现在写的是>2)的情况

regret中的T_0，epsilon用之前的表达式带进去，然后说明这个是 随时间LogT或者SqrtT的

详细写了一下centralized的情况

本周讨论被指出的问题

本周进度总结：

看了一下书上关于 lower-bound的内容

分析了一下regret的upper-bound

简单加了点匈牙利算法的描述在文章上

本周讨论被指出的问题

regret分为两个case讨论一下，一个是a=b=1的情况，还有一个是a>2的情况(现在写的是>2)的情况

regret中的T_0，epsilon用之前的表达式带进去，然后说明这个是 随时间LogT或者SqrtT的

centralized 重新创建一个文件，然后把问题是如何转化的，有什么限制条件，比如Delta不是递减的会有什么情况，然后配个图例子说明一下

之后的安排

本周进度总结：

简单说明了一下分配时，单个臂上正好达到玩家个数的概率不会随时间递减

DropBox上用Latex写了一下干货

本周讨论被指出的问题

之后的安排

本周进度总结：

总结了一下优化的部分。优化分为了三个目标，每个目标的目标函数都可以表示成单个臂的目标函数，通过证明单个臂的目标函数是是单调的，然后可以采用贪心的算法去做

根据epsilon-ranking去使得 根据估计分布优化的结果和真实分布的结果一样，从而得到一个新的探索的最大时间

本周讨论被指出的问题

之后的安排

ppt

本周进度总结：

对于上周给出的三种办法

第一种没找出来

第二种好像找出一个规律，跑了下实验，也没有什么出错的地方，但是总感觉不太对

第三种，看了凸优化的一些东西。目前的想法是把原问题变成凸的对偶问题，通过强队偶的性质，通过说明对偶问题有解来说明原问题有解吗？

之后的安排

直觉上再看一下，如果把零头全部抹掉，然后多出来的几个人，看看能不能用贪心的办法把他们分配到别的地方，用启发式算法去看一下

ppt

本周进度总结：

1.对于分布的计算，没能用之前说的Indicator的方式去弄Union Bound计算，因为这样搞的好像变得太复杂？然后是根据musical chair中的一个证明方法去搞P(估计差值>epsilon|观察该奖励数发生的次数)去推关于T的一个表达式，但是最后的结果受’最不容易出现的奖励数‘的影响

2.对于玩家移动的部分跑了一下实验，大概跑10多次，所有玩家达到最优分配的那种局面

3.对于分布的这部分粗略写了下代码，然后又发现第1点证明方法时的问题，如果概率本身就小于epsilon，那么不去探索这个概率也可以

之后的安排

Part1的那部分用白板上那一块去整一下

然后对于每一个部分的解决方法，提出一个形式化的解决办法（例子就作为补充）

比如说，给定什么东西，然后怎样怎样得到一个东西，然后得到什么

得到的东西 差不多是下一个模块的输入了

对于Part3，最后P应该是一个单调的东西

-------------------------------------------------------------

现在有两个点可以出发去思考

1. 考虑骑手能够得到单子(目标：实际于分配的差值最小)

2. 考虑单子被浪费(目标：浪费的概率最小)

PPT

本周进度总结：

2.对于‘估计均值和分布’这部分：

·根据下面新的条件分析下： 每轮结束之后，系统会告诉所有人，本轮每个臂上有多少张单子，以及有多少个玩家

目前没有解决出来，表达式不知道怎么写比较好，而且比较复杂，其中关于#r的式子，不能把#r当作一个随机变量去看待

4.对于优化的部分：

· PPT 上加了 如果优化不唯一，每个玩家所采取的协议

之后的安排

对于分布的计算，可以先去用indicator I(X=50) 去代替PPT中的#r，然后估计在T时间内成功的概率，然后考虑I(X=49)的概率，然后进行union bound

part1,3可以跑实验看看有没有什么明晰的结果

可以从头看看之前的资料

PPT

·外卖：

1.估计均值或分布

2.估计玩家

3.优化方式（优化结果是否唯一，不唯一咋办）

4.每个玩家怎么根据信息，选择是否离开

本周进度总结：

对于第1、4点，更改了PPT，对于第4点加上了一些细节上的东西

对于第2，3点的还没有想好

本周讨论被指出的问题

‘估计均值和分布’这一部分分析不太够

有问题的话，也要描述清楚自己的问题、难点在哪里

估计分布的方法，用古典概型的方法

下周安排

1.对于‘每个玩家如何移动’这部分：

·基于第一轮最差的移动方式，去分析得到一个\delta

·(先搞别的) 计算每一轮 可以移动的玩家的个数 的期望，期望随着时间指数衰减，经t轮后，可移动人数期望小了以后，说明分配完毕

2.对于‘估计均值和分布’这部分：

·还需要分析一下达到commit的时间，回头看看以前的资料

·根据下面新的条件分析一下： 每轮结束之后，系统会告诉所有人，本轮每个臂上有多少张单子，以及有多少个玩家

3.对于‘估计玩家’这部分：

· 因此可以先不考虑这部分了

4.对于优化的部分(最后想一想)：

· ‘如果优化不唯一’怎么办

· 怎么优化

PPT内容还往里面加。下次讲的时候，简单回顾下上周的东西，然后在放上新的东西

ppt

·外卖：

1.估计均值或分布

2.估计玩家

3.优化方式

4.每个玩家怎么根据信息，选择是否离开

本周进度总结：

想外卖的第四点，基于最开始讨论的那种依概率的方法，添加了一点信息让玩家参考

改了关于match marketing的PPT，添加了一些例子

本周讨论被指出的问题

1.有些设定冗杂了，可以不用写，用到哪些写哪些（问题的输入）

2.外卖的那个需要具体的分析一下，不要想太多的方法，要在一个方法上拓展的去想，然后分析一下

3.之前对第4点有点疑问，实际上是，优化完成之后，每个臂上都有固定的人数要去占着（可以只针对空位去进行分析）

下周安排

对于第4点，根据老师给的例子改一下，再思考一下，给出细节上的东西

然后同理去做前面三点的内容（设定：1.知道每轮人数，2.知道有没有两个单子）

第三点再加一点，如果最优解不唯一怎么办

ppt外卖

pptmarket

本周进度总结：

想外卖的问题

总结match marketing

本周讨论被指出的问题

·外卖：

1.估计均值或分布

2.估计玩家

3.优化方式

4.每个玩家怎么根据信息，选择是否离开

先分成这样子，想好某一点后在想另一点，当如果实在不知道怎么办的时候，可以就先什么也不管，给他一点条件也行

设定什么的说清楚

·match marketing:

PPT重新做一下：

对于设定来说，也可以举个例子说明，比如第一个设定中，可以画一个两个小人什么的表示什么。第二个设定中，偏好是怎样子定义的

对于一篇文章，可能就是一个 输入（问题）->[]->输出的结果，可以形象表示一下这样的东西

下周安排

ppt外卖

pptmarket

⚪本周进度总结：

想外卖问题

kaggle问题

⚪本周讨论被指出的问题

设定1条件下，如果玩家已经知道每个社群有多少个单子了，那么如何让玩家无通信的情况下去调整

⚪下周安排

ppt

⚪本周进度总结：

总结了一下三篇文章

看书《模型思维》

⚪本周讨论被指出的问题

给定好准确的假设。找到估计分布的方法

⚪下周安排

⚪本周进度总结：

整理了一下Selfish Robustness and Equilibria in Multi-Player Bandits的情况。如何自私、如何解决

看了几篇发生collision后奖励不为0的情况

Multi-User Multi-Armed Bandits for Uncoordinated Spectrum Access(ICNC)

Decentralized Multi-Player Multi-Armed Bandits with Non-Zero Rewards on Collisions

Bandit Learning in Decentralized Matching Markets (Michael Jordan)

⚪本周讨论被指出的问题

⚪下周安排

几篇放在一起 Musical Chair GoT SIC self-robust

怎么估计

均值怎样，怎样估计

完成分布式的方法

问题和方法怎么对上的

⚪本周进度总结：

看了<SIC -MMAB: Synchronisation Involves Communication in Multiplayer Multi-Armed Bandits> 去了解No sensing的情况， 关于说明碰到selfish 失效的情况还没看

看了几篇以前mpmab的文章的前面几段，主要是去了解对 认知无线电 实际问题是怎样建模的

看了一些别的多智体应用方面的东西，但是没想好如何通过bandit的办法去解决

⚪本周讨论被指出的问题

没有很系统的分析文章

没有很好的理解是怎样selfish的

如果只有两个人，那么有一个selfish的怎么办

⚪下周安排

<selfish那篇>

解决的问题是啥（本文自私的场景，想要避免的问题）

（自私的目的，用哪些数据来检测）

如何解决（这篇是惩罚、能有别的方式吗）

<sic-mmab那篇>

提炼一下no sensing的情况，解决哪些问题，如何解决

<collision的情况>

可能是优势互补的(1+1>2)

也可能是竞争的(r=0)

也可能是线性的(每个人平均分配)

提炼了一下PPT

准备1218补修的考试

● 阅读game of throne 并复现，最后实验结果的形状好像和文章中有一点不同

● 看了MCMC方法的一些内容

MCMC是一种采样方法，可以从非线性的分布中进行采样。

在MCMC的基础下，M-H采样可以使得马尔科夫链更快收敛到最快的状态

对于多元随机变量，可以采用Gibbs采样

对于game of throne，根据Payoff-based learning模型来使得GoT阶段达到马尔可夫稳定的状态，从而找到一个解

在根据其他条件的限制，使得GoT阶段的解在概率上为最优解

● 做了几道leetcode

● 看了计算机网络的网课

● 阅读 Multi-Player Bandits – a Musical Chairs Approach

·复现了static情况的代码，与文章后面给出的图不是很一致。后来在github上找到一个同样是MC的代码，跑了一下人家的，情况和我的是差不多。

·写static情况的代码的时候没有考虑好对于dynamic的情况，代码里数据的存储结构得改一下，运算的代码也得改一下

●只是粗略看了一遍Sampling-based optimization

感觉section3跟目前的研究有点关系。

● 阅读distributed multi player bandits a game of thrones approach

·还没有去看证明部分，对实验结果是如何表现的还不明白。对于baseline arm 的选择也存疑,还有最后归一化的分母也存疑

● 阅读Bandits Algorithms 36.1

● 阅读lec3-lec5

· lec3和36.1讲述的内容差不太多，采用一种类似UCB的思想，去计算regret，之前疑惑的地方是在U(A*)为什么和U(A)是同分布的了，目前好像有点明白了

· 但是lec3和36.1得到的regret bound最后还会受到臂个数K的影响，不适合在线学习，因此需要引入新的方法

· lec4和lec5则介绍了这些方法。通过定义epsilon-dependent，得到了时间序列中，满足一些条件的臂的个数，最后得出了regret-bound