决策基础Decision foundations意思決定の基礎
从选择到规划:Bandit 与 MDPFrom Selection to Planning: Bandits and MDPs選択から計画へ:BanditとMDP
把请求交给哪个模型,与让 Agent 连续完成一项任务,看起来都在“选动作”。区别在于:这次选择,会不会改变下一步能做什么?Choosing a model for a request and guiding an agent through a task both involve actions. The important difference is whether this choice changes what can happen next.リクエストをどのモデルに渡すか、エージェントに作業をどう進めさせるか。どちらも行動を選びます。違いは、今の選択が次にできることを変えるかどうかです。
静态图Static figure静止図
先看动作的后果Start with the consequence行動の結果から考える
考虑一个简化的模型路由器:每次收到独立请求,选择一个模型,得到质量评分并支付调用费用。如果这次选择不影响下一条请求,可以把它建模为 Bandit。若先看请求长度、语言、任务类型再选择,就是 Contextual Bandit。Consider a simplified router: each independent request is assigned to a model, then receives a quality score and incurs a cost. If the choice does not change the next request, a bandit is a useful model. Conditioning the choice on length, language, or task type gives a contextual bandit.独立したリクエストごとにモデルを選び、品質と費用を評価するルーターを考えます。選択が次のリクエストに影響しなければBanditとして扱えます。長さ・言語・タスク種別も見て選ぶならContextual Banditです。
再看建表任务。先创建订单表,才能增加字段;关联字段又依赖客户表。早一步的动作改变了环境,也改变了后续动作的前提。这里需要描述状态转移和整段任务的回报,MDP 更合适。Now consider building a database. A table must exist before its fields can be added; a relation also needs its target table. Earlier actions change the environment and the prerequisites of later actions. An MDP describes those transitions and the return of the whole task.データベース構築では、表を作ってからフィールドを追加し、関連フィールドには参照先の表も必要です。先の行動が環境と後続操作の条件を変えます。この状態遷移とタスク全体の収益をMDPで表します。
先定义反馈:只看到了被选中的臂Define feedback: only the chosen arm is observed選んだ腕の報酬だけが観測される
设有 K 个臂,第 t 轮选 Aₜ,只观察奖励 rₜ;μₐ 是臂 a 的未知期望奖励。与每条数据都有正确标签的监督学习不同,未选模型会怎样回答通常没有反馈。即使环境每轮都回到同一状态,学习器的次数、均值和后验仍随历史更新;“单状态”不意味着必须永远用固定选臂概率。With K arms, round t selects Aₜ and observes only rₜ; μₐ is arm a’s unknown expected reward. Unlike fully labeled supervised data, the response of an unselected model is usually unavailable. Even if the environment returns to one state, counts, estimates, and posteriors evolve. A one-state environment does not require fixed action probabilities throughout learning.K本の腕から時刻tにAₜを選び、報酬rₜだけを観測します。μₐは腕aの未知の期待報酬です。選ばなかったモデルの回答には通常ラベルがありません。環境が毎回同じ状態でも、回数・推定値・事後分布は変わります。単一状態でも学習中の選択確率を固定する必要はありません。
观测 n 次后的样本均值可递推为 μ̂ₐ ← μ̂ₐ + (r − μ̂ₐ)/n。若模型版本或请求分布随时间变化,全部历史的等权均值会反应迟缓;常数步长 α 的更新会更重视近期,但已改变了估计假设。先判断奖励是否近似平稳,再选统计量。The sample mean after n observations updates as μ̂ₐ ← μ̂ₐ + (r − μ̂ₐ)/n. If model versions or traffic change, an equally weighted historical mean can react slowly. A constant step size α emphasizes recent evidence, but estimates a changing target under different assumptions. Check stationarity before selecting the estimator.n回の観測後の標本平均はμ̂ₐ ← μ̂ₐ + (r − μ̂ₐ)/nで更新できます。モデルや要求分布が変化すると、全履歴を等しく扱う平均は追従が遅くなります。一定のαなら直近を重くできますが、推定の前提も変わります。まず報酬が定常と見なせるか確認します。
遗憾比较的是期望,单次运气另算Regret separates expected quality from luckリグレットは期待値と偶然を分ける
令 μ* = maxₐ μₐ,差距 Δₐ = μ* − μₐ。常用期望伪遗憾为 R̄ₜ = Σₐ Δₐ E[Nₐ(T)]:把每个次优臂被选的期望次数乘上它的期望损失。它非负;而 Tμ* − Σₜrₜ 包含抽样运气,某次运行可能为负。知道最优臂也只能最大化期望,不能保证每次都赢。Let μ* = maxₐ μₐ and Δₐ = μ* − μₐ. Expected pseudo-regret is R̄ₜ = Σₐ Δₐ E[Nₐ(T)]: each arm’s expected selection count multiplied by its expected loss. It is nonnegative. By contrast, Tμ* − Σₜrₜ includes sampling luck and can be negative in one run. Knowing the best arm optimizes expectation, not every realized outcome.μ* = maxₐ μₐ、Δₐ = μ* − μₐとすると、期待擬似リグレットはR̄ₜ = Σₐ Δₐ E[Nₐ(T)]です。劣る腕の期待選択回数に期待損失を掛けて合計するため非負です。一方、Tμ* − Σₜrₜには偶然が含まれ、1回の実験では負にもなります。最良の腕でも毎回成功する保証はありません。
教学例子:三臂均值为 0.3、0.5、0.8,均匀随机的每次期望奖励为 0.5333;1000次相对最优臂的期望差约266.7。这个数可直接计算,无需虚构模拟。估计所有臂的RMSE低也不等于遗憾低:平均分配样本能估得准,却持续把流量给较差的臂。For an illustrative three-arm problem with means 0.3, 0.5, and 0.8, uniform choice earns 0.5333 in expectation per round. Over 1,000 rounds its expected gap is about 266.7. This is an analytic calculation, not a simulation result. Low estimation RMSE need not mean low regret: uniform sampling estimates every arm while repeatedly choosing inferior ones.平均0.3、0.5、0.8の3腕を例にすると、一様選択の1回当たり期待報酬は0.5333です。1000回で最良腕との差は約266.7。これは計算例であり実験結果ではありません。全腕の推定RMSEが小さくても、劣る腕を選び続ければリグレットは大きくなります。
探索,买到的是信息Exploration buys information探索で情報を得る
路由器暂时认为模型 A 比 B 好,但 B 只试过两次。一直选 A 可以利用已有经验,却可能错过更合适的 B。探索的价值来自未知:这次尝试除了交付答案,还会更新对 B 的判断。Suppose model A currently looks better than B, but B has only been tried twice. Always choosing A exploits current estimates while risking a missed opportunity. An exploratory call both answers the request and changes what the router knows about B.Aの成績がBより良くても、Bを2回しか試していなければ判断は不確かです。Aを選び続ければ既存の知識を活用できますが、Bの可能性を見逃します。探索は回答を得ると同時に、Bについての知識を更新します。
ε-greedy 偶尔随机尝试;UCB 给不确定的选项加探索奖励;Thompson Sampling 从各选项的回报后验中采样,再按本次样本选择。它们对不确定性的处理不同,没有脱离任务分布的固定冠军。ε-greedy occasionally tries a random option. UCB adds an uncertainty bonus. Thompson sampling draws from each reward posterior and chooses using those draws. They handle uncertainty differently; their ranking depends on the problem and assumptions.ε-greedyは時々ランダムに選び、UCBは不確かな選択肢にボーナスを加えます。Thompson Samplingは各報酬の事後分布からサンプルして選びます。不確実性の扱い方が異なるため、常に最良の方式はありません。
ε 与温度控制不同的探索方式ε and temperature control different explorationεと温度による探索の違い
ε-greedy以1−ε选经验均值最大的臂,以ε均匀随机。若固定ε>0且存在次优臂,即使均值已学准,也会持续探索,通常留下线性期望遗憾项。逐步减小ε能减少后期探索,但下降太快可能把早期误判锁死;“会下降”本身不是收敛证明。ε-greedy chooses the estimated best arm with probability 1−ε and uniformly explores with probability ε. With fixed ε>0 and suboptimal arms, exploration continues after estimates become accurate, generally leaving a linear expected-regret term. Decaying ε reduces later exploration, but an overly fast schedule can preserve an early mistake; decay alone is not a convergence guarantee.ε-greedyは確率1−εで推定最良腕、εで一様に選びます。ε>0を固定し劣る腕があると、推定が正確になっても探索が続き、通常は期待リグレットに線形成分が残ります。εを下げれば後半の探索は減りますが、急減すると初期の誤認を固定しかねません。減少だけでは収束保証になりません。
Boltzmann选择直接用 p(a) = exp(μ̂ₐ/τ) / Σᵦexp(μ̂ᵦ/τ)。τ大时更均匀,τ小时偏向最高均值;它按分数而非不确定性分配概率。奖励整体缩放会改变同一τ下的行为,所以温度必须和奖励尺度一起解释。它可以单独作为选臂规则,不必只作为ε-greedy的探索分支。Boltzmann selection uses p(a) = exp(μ̂ₐ/τ) / Σᵦexp(μ̂ᵦ/τ). Large τ spreads probability; small τ concentrates it on high estimates. Probability depends on estimated reward, not explicitly on uncertainty. Scaling rewards changes behavior at the same τ, so temperature and reward scale must be interpreted together. It can be the entire selection rule, rather than just an ε-greedy exploration branch.Boltzmann選択はp(a) = exp(μ̂ₐ/τ) / Σᵦexp(μ̂ᵦ/τ)を使います。τが大きいほど一様、小さいほど高い推定値に集中します。不確実性を直接使う式ではありません。報酬の尺度を変えると同じτでも挙動が変わります。また、ε-greedyの探索部分に限らず、単独の選択規則として使えます。
UCB:均值之外,加一个置信上界UCB adds an uncertainty bonusUCB:平均に不確実性を加える
在平稳、独立采样、奖励有界于[0,1]的经典设定中,先各试一次,再按 μ̂ₐ + √(2 ln t / Nₐ) 选最大者。样本少使上界宽,长期没选也会因ln t增大而重新得到机会。这里的乐观是对未知均值的乐观,不是给奖励本身增加一笔真实收入。In the classical stationary setting with independent samples and rewards bounded in [0,1], try each arm, then maximize μ̂ₐ + √(2 ln t / Nₐ). Few observations widen the bound; growing ln t can bring a neglected arm back into consideration. Optimism concerns the unknown mean, not an extra reward actually paid by the environment.定常・独立標本・報酬[0,1]という古典的設定では、各腕を一度試した後、μ̂ₐ + √(2 ln t / Nₐ)を最大化します。標本が少ないほど幅が広く、ln tの増加で長く選ばれなかった腕も再び候補になります。未知の平均に対する楽観であり、実際の報酬が増えるわけではありません。
对固定正差距的这类问题,UCB1有对数级的分布依赖期望遗憾界;差距进入常数,不能省略条件写成所有Bandit都O(log T)。例如t=100,A均值0.70试80次,B均值0.60试20次,上界约1.04与1.28,会选B。上界超过1只是宽松界,不表示预测成功概率超过100%。For fixed positive gaps under those assumptions, UCB1 has a logarithmic, distribution-dependent expected-regret bound. Gap sizes enter the constants; this is not O(log T) for every bandit problem. At t=100, arm A with mean 0.70 and 80 trials has index about 1.04, while B with mean 0.60 and 20 trials has about 1.28. B is selected. An index above one is a loose bound, not a predicted probability above 100%.この前提で正の差が固定された問題では、UCB1に分布依存の対数期待リグレット上界があります。差は定数に入り、すべてのBanditにO(log T)を保証しません。t=100でAが平均0.70・80回、Bが0.60・20回なら指数は約1.04と1.28でBを選びます。1超は緩い上界であり成功確率ではありません。
Thompson Sampling:从可能的世界中选一次Thompson sampling selects under a sampled modelThompson Sampling:仮のモデルから選ぶ
伯努利奖励的成功率q取Beta(α,β)先验。观察s次成功、f次失败后,似然为qˢ(1−q)ᶠ,与先验相乘得到Beta(α+s,β+f)。每轮给每个臂采样一个q̃ₐ,再选最大者,只更新被选臂的后验。Beta(1,1)均匀先验下,8成功2失败变成Beta(9,3),后验均值为0.75。For Bernoulli reward, use a Beta(α,β) prior over success probability q. The likelihood after s successes and f failures is qˢ(1−q)ᶠ; multiplying it by the prior gives Beta(α+s,β+f). Draw q̃ₐ for each arm, select the largest, and update only that arm. Starting from Beta(1,1), eight successes and two failures yield Beta(9,3), whose mean is 0.75.Bernoulli報酬の成功率qにBeta(α,β)事前分布を置きます。s成功・f失敗の尤度qˢ(1−q)ᶠを掛けると、事後はBeta(α+s,β+f)です。各腕のq̃ₐを引いて最大を選び、その腕だけ更新します。Beta(1,1)から8成功・2失敗ならBeta(9,3)、平均0.75です。
样本少的后验较宽,偶尔能抽到较高值,因而得到探索机会。它不是“采样奖励后才决定是否调用”,而是从未知参数的判断中采样。先验和奖励模型仍是选择:连续费用、延迟或复合质量分不能不加转换就套用伯努利共轭更新,也不存在无条件最优的算法冠军。A broad posterior can occasionally generate a high draw, creating an exploration opportunity. The algorithm samples beliefs about unknown parameters, not the outcome of a call before making it. Priors and likelihoods remain modeling choices: continuous costs, latency, or composite scores do not automatically fit a Bernoulli update. No universal winner follows from the example.標本が少なく広い事後分布からは高い値が出ることがあり、探索につながります。呼び出す前に実際の結果を知るのではなく、未知パラメータの信念をサンプルします。事前と尤度の選択は必要で、連続の費用・遅延・複合スコアにBernoulli更新をそのまま使うことはできません。
Contextual Bandit 的关键是反馈边界Contextual bandits depend on the feedback boundaryContextual Banditはフィードバックの範囲で決まる
每轮先观察上下文xₜ,再选a,学习μ(x,a)。最优比较对象也变成对每个上下文选择最优臂的策略,而不是全局固定模型。长代码请求可能偏好一个模型,短提取请求偏好另一个;把所有请求混成同一均值会掩盖这种差异。Observe context xₜ before choosing a, and learn μ(x,a). The benchmark becomes a policy selecting the best arm for each context, not one globally fixed model. Long coding tasks and short extraction tasks may favor different models; a single aggregate mean can conceal that difference.行動前に文脈xₜを観測し、μ(x,a)を学びます。比較対象も、全体で1モデルではなく文脈ごとの最良腕を選ぶ方策になります。長いコード生成と短い抽出では適したモデルが違い、全体平均だけでは差が隠れます。
“动作不影响后续上下文”是一种设定,不是从用户ID没变就能推得的事实。推荐会改变用户偏好,路由会消耗共享预算,工具动作会改变资源,这些影响可能要求状态转移模型。离线日志还只记录历史策略选过的动作;没有覆盖的动作不能凭日志直接知道效果,比较需记录选取概率并考虑支持集。No effect on future context is an assumption, not a consequence of an unchanged user ID. Recommendations may change preferences, routing may consume shared budget, and tools may alter resources. These effects can require a transition model. Logged data also reveals only historical actions; unsupported alternatives cannot be evaluated directly. Selection probabilities and action support matter for offline comparisons.将来の文脈に影響しないことは仮定であり、ユーザーIDが同じだから成立するわけではありません。推薦は嗜好、ルーティングは共有予算、ツールは資源を変え得ます。履歴には実際に選んだ行動しかなく、未選択の効果は直接分かりません。オフライン比較では選択確率と行動の被覆が重要です。
一次得分,和长期回报A reward is not the whole return直近の報酬と長期の収益
在 MDP 中,策略 π 根据状态选择动作,环境返回奖励和新状态。一次检查可能没有直接完成任何功能,却能发现字段缺失,减少后续返工。它的价值需要放在后续结果里衡量。In an MDP, policy π selects an action from the state; the environment returns a reward and a new state. A validation call may deliver no feature immediately, yet catch a missing field and prevent rework. Its value includes later consequences.MDPでは方策πが状態から行動を選び、環境が報酬と新しい状態を返します。検証だけでは機能は完成しなくても、欠けたフィールドを発見して手戻りを防げます。価値は後の結果も含めて評価します。
折扣回报把未来奖励相加:Gₜ = rₜ₊₁ + γrₜ₊₂ + γ²rₜ₊₃ + …。V(s) 衡量从状态 s 继续执行的价值;Q(s,a) 衡量先做动作 a 再继续的价值。Bellman 分解把这件事写成“本步奖励 + 下一状态的价值”。Discounted return sums future rewards: Gₜ = rₜ₊₁ + γrₜ₊₂ + γ²rₜ₊₃ + … . V(s) values continuing from state s; Q(s,a) values taking action a first, then continuing. The Bellman decomposition expresses this as immediate reward plus the value of the next state.割引収益は将来の報酬を足し合わせます:Gₜ = rₜ₊₁ + γrₜ₊₂ + γ²rₜ₊₃ + …。V(s)は状態sから続ける価値、Q(s,a)は最初にaを実行して続ける価値です。Bellman分解は「直近の報酬+次の状態の価値」と表します。
静态图Static figure静止図
Bellman 分解怎样变成规划算法From the Bellman decomposition to planningBellman分解から計画アルゴリズムへ
对固定策略,Vπ(s) = Σₐπ(a|s)Σₛ′P(s′|s,a)[r(s,a,s′)+γVπ(s′)]。先按动作和转移取平均,就是策略评估;改为选择使括号期望最大的动作,就是策略改进。值迭代把两步压成 Vₖ₊₁(s)=maxₐΣₛ′P(s′|s,a)[r+γVₖ(s′)]。有限状态、奖励有界且γ<1时,Bellman最优算子是收缩映射,迭代有明确收敛依据。For a fixed policy, Vπ(s) = Σₐπ(a|s)Σₛ′P(s′|s,a)[r(s,a,s′)+γVπ(s′)]. Averaging over actions and transitions evaluates the policy; choosing the maximizing action improves it. Value iteration combines these into Vₖ₊₁(s)=maxₐΣₛ′P(s′|s,a)[r+γVₖ(s′)]. For a finite state space, bounded rewards, and γ<1, the optimal Bellman operator is a contraction, providing a convergence argument.固定方策ではVπ(s) = Σₐπ(a|s)Σₛ′P(s′|s,a)[r(s,a,s′)+γVπ(s′)]です。平均を取るのが方策評価、最大の行動を選ぶのが改善です。価値反復はVₖ₊₁(s)=maxₐΣₛ′P(s′|s,a)[r+γVₖ(s′)]とまとめます。有限状態・有界報酬・γ<1なら最適Bellman作用素は縮小写像となり、収束を説明できます。
教学例子:立刻跳过检查得1并结束;先检查成本−0.1,下一步以0.9概率成功得2,否则得0,γ=0.9。检查的价值为−0.1+0.9×(0.9×2)=1.52,高于立即的1。已知转移时可以这样规划;未知时要通过数据估计或用TD/Q-learning学习。MDP定义问题,算法决定怎样求解;有限时域还需把剩余步数纳入状态或价值下标。Illustration: skipping validation gives 1 and terminates. Validation costs −0.1, then next-step success pays 2 with probability 0.9 and otherwise 0; γ=0.9. Its value is −0.1+0.9×(0.9×2)=1.52, exceeding 1. With known transitions this is planning; otherwise estimate the model or learn from samples with TD/Q-learning. An MDP defines the problem, not its solver. Finite horizons require remaining time in the state or value index.例として、検証を省くと即座に1で終了、検証は−0.1で次の段階に進み、確率0.9で2、それ以外は0とします。γ=0.9なら価値は−0.1+0.9×(0.9×2)=1.52です。遷移が既知なら計画でき、未知なら推定やTD/Q-learningが必要です。MDPは問題の定義です。有限時域では残り時間も状態や価値の添字に含めます。
用同一个任务检查建模Test the model against the taskタスクに照らしてモデルを確かめる
假设需求是“订单必须关联真实客户”。只给每次 API 成功返回加分,可能鼓励模型创建很多无用字段;只看最终任务通过率,又会让中间动作的贡献难以区分。奖励定义和信用分配,需要一起考虑。For “orders must reference real customers,” rewarding every successful API call can encourage useless fields. Scoring only final task success makes individual contributions harder to identify. Reward design and credit assignment need to be considered together.「注文は実在する顧客を参照する」という要求で、API成功のたびに報酬を与えると不要なフィールドまで増やしかねません。最終成功だけを評価すると、中間行動の貢献を分けにくくなります。報酬と信用割当を一緒に考える必要があります。
是否采用 Bandit,取决于实际依赖。如果模型选择会消耗共享预算、改变排队状态或影响未来可选模型,独立请求的近似就可能不够。反过来,一个只有一次选择的问题,也不需要先搭完整的多步规划系统。The bandit abstraction depends on actual dependencies. If a model choice depletes a shared budget, changes a queue, or affects future availability, independent rounds may be a poor approximation. Conversely, a one-shot decision does not require a full planning system.Banditが適切かは実際の依存関係で決まります。共有予算の消費や待ち行列の変化が将来の選択を左右するなら、各回が独立という近似は不十分です。一度だけの選択に、完全な計画システムを用意する必要もありません。
时间、约束与可见性决定扩展哪一层Time, constraints, and visibility determine the extension時間・制約・可観測性で拡張を選ぶ
若动作持续τ步,SMDP用这段累计奖励加γ^τV(s′)描述时间差异;若预算必须受限,CMDP把期望累计成本≤预算写成约束,随手加一个固定罚分并不保证满足它。持续服务可以考虑长期平均奖励,模型不确定则需明确鲁棒优化的不确定集合。不同扩展回答不同问题,不是同一种复杂度升级。For an action lasting τ steps, an SMDP uses accumulated reward over that interval plus γ^τV(s′). A CMDP explicitly constrains expected cumulative cost; an arbitrary fixed penalty does not guarantee compliance. Continuing services can use average reward, while robust planning needs a specified uncertainty set. These extensions solve different modeling problems rather than forming one ladder of complexity.τステップ続く行動なら、SMDPはその間の累積報酬とγ^τV(s′)を使います。CMDPは期待累積費用を明示的に制約し、固定罰則だけで制約充足は保証されません。継続サービスには平均報酬、不確かなモデルには不確実集合を定めたロバスト計画があります。各拡張は異なる問題を扱います。
为一个Agent选择模型时,先写清动作会改变哪些资源、能观察哪些信息、如何计时与付费、最终成功怎样验证。状态不全时转到POMDP和信念更新;模型未知时才决定如何探索与学习。这样,Bandit、规划与后训练就能对应到真实控制问题,而不是仅按算法名称选系统。When modeling an agent, specify which resources actions change, what is observed, how time and cost are counted, and how success is verified. Partial state information leads to beliefs and POMDPs; unknown dynamics motivates exploration and learning. Bandits, planning, and post-training can then be connected to the actual control problem instead of selected by name.Agentをモデル化するときは、行動が変える資源、見える情報、時間と費用、成功の検証法を先に定義します。状態が見えなければPOMDPと信念更新、モデルが未知なら探索と学習が必要です。名前から方式を選ぶのではなく、実際の制御問題に対応させられます。
延伸阅读Further reading参考資料
- Sutton & Barto · Reinforcement Learning, chapters 2–3
- Auer, Cesa-Bianchi & Fischer · Finite-time Analysis of the Multiarmed Bandit Problem
图源与文字Figures and text図と本文のソース
三语正文与图结构 · JSONTrilingual text and diagram structure · JSON3言語の本文と図の構造 · JSON