Budgeted Reinforcement Learning in Continuous State Space

1 Introduction

• Standard reward optimization does not control the spread of performance, a concern when failures in critical applications are costly.Risk-averse criteria have therefore considered quantities such as worst-case performance, variance, VaR, and CVaR.Source: §1 · pp. 1–2
• A single reward signal cannot control the relative balance between objectives, while CMDPs require a cost budget fixed before training.BMDPs instead take the budget as input, allowing the system designer to move the policy along the reward–cost trade-off curve in real time.Source: §1 · p. 2
• The paper reframes BMDPs for continuous states and infinite discounted horizons, then proves the optimal value function is a fixed point of a novel Budgeted Bellman Optimality operator.It uses the operator in BFTQ, a batch RL algorithm for online interaction with unknown dynamics, and scales it with convex programming, deep networks, and synchronous parallel computing.Source: §1 · p. 2
• The approach is validated in two settings with reward–cost trade-offs: a spoken-dialogue system and autonomous-driving behavior planning.The paper identifies the latter as a driving application where progress and collision avoidance can conflict.Source: §1 · p. 2

2 Budgeted Dynamic Programming

• Budgeted policies carry the budget forward as part of the dynamics, so the budget is neither fixed nor constant as in CMDPs.The formulation augments states and actions with budget variables and uses the policy’s selected next budget at the following timestep.Source: §2 · p. 2
• The Budgeted Bellman Expectation operator is a γ-contraction, and each policy’s Q function is its unique fixed point.The budgeted value functions pair reward and cost quantities.Source: §2 · p. 3
• Budgeted optimality requires respecting the cost budget, maximizing discounted reward, and minimizing discounted cost when rewards tie.The paper defines the optimal value and candidate policy sets around these priorities.Source: §2 · p. 3
• The optimal budgeted action-value function satisfies the Budgeted Bellman Optimality equation, and its greedy policy is uniformly optimal.The resulting greedy policy recovers the optimal value and action-value functions.Source: §2 · pp. 3–4
• Computing the budgeted greedy policy requires solving a nested constrained optimization program at each state and budget.The paper notes that the solution structure is concave and increasing in the budget, enabling replacement with πhull.Source: §2 · p. 4
• The Budgeted Bellman Optimality operator is not a contraction for BMDPs with at least two actions, so convergence and uniqueness of value iteration cannot be guaranteed.The authors report empirical convergence in their experiments and conjecture contraction on a restricted set of smooth Q-functions.Source: §2 · p. 4

3.1 Budgeted Fitted-Q

• The sampling operator replaces the next-state expectation with sampled transitions, avoiding the need to know the environment model.The method adapts the known-model value-iteration update to batches collected through interaction.Source: §3.1 · p. 4
• BFTQ adapts Fitted-Q to unknown BMDPs, using function approximation to generalize across continuous states and budgets.It minimizes a regression loss between a parameterized Q model and target values; the model may be linear, tree-based, or neural.Source: §3.1 · p. 4

3.2 Risk-sensitive exploration

• Risk-sensitive exploration mixes a random budgeted policy with the current greedy policy and updates the latter after each minibatch.The random policy samples feasible budget choices with expected next budget no greater than the current budget.Source: §3.2 · p. 5
• Uniformly sampling initial budgets explores the full admissible risk range rather than only reward-seeking behavior.The random policy's joint action and next-budget distribution is constrained to remain feasible.Source: §3.2 · p. 5

4 A Scalable Implementation

• The scalable implementation is designed to handle large batches of experiences efficiently.Its target computation evaluates action values for each sampled next state in a single forward pass before parallel hull calculations.Source: §4 · p. 5, §4.3 · p. 6

4.1 How to compute the greedy policy?

• The greedy policy can be computed using the top frontier of the convex hull, replacing the nested constrained optimization in the Bellman update.For a budget between two frontier points, the policy mixes those points.Source: §4.1 · p. 5, Figure 1 · p. 6

4.2 Function approximation

• A single neural network jointly approximates reward and cost Q-functions, sharing representations and evaluating all finite actions in one forward pass.The budget receives its own encoder so it is not weakly represented relative to the state input.Source: §4.2 · pp. 5–6

4.3 Parallel computing

• BFTQ distributes sample collection across workers because the greedy policy remains fixed within each minibatch.The target computation also distributes convex-hull calculations across CPUs, yielding linear speedup with multiprocessing.Source: §4.3 · p. 6

5 Experiments

• The experiments assess exploration strategies in corridors and compare BFTQ against FTQ(λ), which approximates BMDPs with a finite set of CMDPs.A single BFTQ training corresponds to ten FTQ(λ) policy trainings.Source: §5 · p. 6

5.1 Environments

• The three simulated environments cover corridor exploration, spoken dialogue slot-filling, and autonomous driving with reward-cost trade-offs.In highway-env, the cost is the proportion of episode time spent driving on the opposite lane.Source: §5.1 · p. 7

5.2 Results

• Risk-sensitive exploration produces trajectories across both corridors and good budgeted-policy performance across risk budgets, unlike risk-neutral exploration, which concentrates on the risky route and performs poorly at low risk.Figure 2 presents collected trajectories and the resulting policy performance.Source: §5.2 · p. 7, Figure 2 · p. 8
• BFTQ performs almost as well as FTQ(λ) on slot-filling and highway-env despite requiring only one model.BFTQ provides better control of expected policy cost and lower extra-seed variance overall; highway-env also shows cost underestimation, with E[Gc|β = 0] ≃0.1.Source: §5.2 · pp. 7–8, Figure 3 · p. 8

6 Discussion

• The authors state that no existing algorithm combines solving large unknown BMDPs with continuous states.Their Algorithm 2 is presented as addressing these features together.Source: §6 · p. 8
• Prior unknown-CMDP methods keep constraint thresholds fixed before training, unlike BMDPs' real-time budget adjustment.The cited CMDP approaches include online algorithms and batch methods.Source: §6 · p. 8
• Earlier BMDP solutions either approximate the problem with finitely many CMDPs or use dynamic programming limited to finite states and known dynamics.The finite-CMDP route requires expected-cost evaluation through environment interaction; this solution uses one model and avoids supplementary interaction.Source: §6 · pp. 8–9

7 Conclusion

• On two practical tasks, the solution performs similarly to Lagrangian relaxation while using one model and an interpretable β instead of tuning λ.The implementation exploits value-function structure and tools from deep distributed reinforcement learning.Source: §7 · p. 9

Appendices

• Appendix A contains proofs, Appendices B and C describe scalable BFTQ and risk-sensitive exploration, and Appendix D presents a Lagrangian-relaxation alternative.Appendix E provides experiment-visualization and reproduction assets, while Appendix F addresses the reproducibility checklist.Source: Appendices · p. 12

A.1 Proposition 1

• The policy Bellman expectation operator is a γ-contraction and has a unique fixed point equal to Qπ.The proof invokes the Banach fixed-point theorem.Source: §A.1 · p. 12

A.2 Theorem 1

• The greedy policy for Q* belongs to the arg max of the budgeted optimality expression in (17).The supplied proof passage identifies the greedy policy as an optimizer of that expression.Source: §A.2 · p. 13

A.3 Proposition 2

• The proof identifies Q* as a fixed point of the expectation operator for its greedy policy, then recovers V* from that policy's action values.The argument uses the fixed-point uniqueness result from Proposition 1.Source: §A.3 · p. 13

A.4 Theorem 2

• For at least two actions, the proof constructs a counterexample to contraction; the one-action case is contractive.With |A| = 1, the optimality operator equals the policy operator, which Proposition 1 establishes as a contraction.Source: §A.4 · p. 14

A.5 Remark 2

• When Q's reward-cost relationship is L-Lipschitz with L < 1/γ − 1, the Budgeted Bellman operator is a γ(L + 1)-contraction on Lγ.The proof bounds changes in the optimal value by (L + 1) times changes in Q, yielding γ(L + 1) < 1.Source: §A.5 · pp. 15, 17

A.6 Proposition 3

• The single-step CMDP reduction permits replacing the action-distribution search with mixtures of two deterministic policies.The resulting candidate values are convex combinations of Q(s, a1) and Q(s, a2).Source: §A.6 · pp. 17–18
• The top frontier F is both non-decreasing and concave, and the optimal q* lies on its convex edge within FQ.The passage defines FQ as the intersection of the frontier F and the value set Q.Source: §A.6 · p. 18

B Risk-Sensitive Exploration

• The exploration algorithm divides episodes among W workers and collects transitions into a batch D.At each step it may sample an action-budget pair uniformly from ΔAB under its exploration branch.Source: B Risk-Sensitive Exploration · p. 19

D The Lagrangian Relaxation Baseline

• The Lagrangian baseline finds the optimal deterministic policy by line-searching λ values calibrated to budget β.Its purpose is to avoid a calibration phase.Source: D The Lagrangian Relaxation Baseline · pp. 19, 21

C Scalable Implementation of BFTQ

• The scalable BFTQ procedure evaluates Q(S′, A, eB) in one forward pass, distributes data across workers, and prunes dominated points.The network uses an additional encoder for the budget alongside the state input.Source: D The Lagrangian Relaxation Baseline · p. 20

E.1 Examples of different exploration strategies

• Risk-neutral epsilon-greedy and risk-sensitive exploration trajectories are shown in separate rows, with each animation representing a different seed.The animations display the collected trajectories in intermediate sub-batches.Source: §E.1 · p. 21

E.2 Examples of BFTQ policies executions

• With β = 0, the highway agent stays in its lane and moves slowly; at β = 1, it overtakes aggressively, while β = 0.2 yields intermediate behavior.The examples show budget-dependent behavior in the simulated highway environment.Source: §E.2 · p. 21

Slot-filling

• At β = 0, the slot-filling policy avoids ask_num_pad and can fail by reaching the dialogue limit; at β = 0.5, it may use ask_num_pad to verify uncertain slots.The table caption identifies the examples as dialogues from safe (β = 0) and risky (β = 0.5) policies.Source: Slot-filling · pp. 21–22, Table 1 · p. 22
• The Corridors animations show a gradual shift from the safest path toward the higher-reward, higher-cost lane as the budget increases, a process the passage says a deterministic policy could not achieve.The animations use different seeds.Source: Slot-filling · p. 22

E.3.2 Algorithm parameters

• The appendix provides environment and algorithm parameter tables, notes that regulation weight is decisive in slot-filling, and supplies commands for running experiments across seeds.It reports a shallow grid search for classic neural-network parameters and says most parameters have little influence on results.Source: §E.3.1 · p. 23, §E.3.2 · pp. 23, 25, Table 2 · p. 23

E.3.1 Environments Parameters

• The appendix lists the state representations for Corridors, Slot-Filling, and Highway-Env, including dialogue scores and acts for slot-filling and vehicle positions and velocities for highway driving.The state descriptions also specify Corridors states as the agent’s two-dimensional coordinates.Source: §E.3.1 · p. 23

E.3.3 Instructions for reproducibility

• Reproducing the experiments requires conventional Python libraries and the Figure 9 commands on Linux; the reported hardware is an NVIDIA GeForce GTX 1080 Ti and Intel Xeon E7.The passage names pycairo, numpy, scipy, and pytorch as required libraries.Source: §E.3.3 · p. 25, Figure 9 · p. 25

• The checklist directs readers to Section 1, Section 2, Section 3, Appendix B, and Appendix C for the mathematical setting, algorithm, and/or model, and to Section 4.3 for complexity analysis.Source: F The machine learning reproducibility… · p. 25
• The theoretical checklist reports a proof sketch in Appendix A.5 and an assumption that the program is feasible for any state.The checklist also points to Appendix A for a complete proof of the claim.Source: F The machine learning reproducibility… · p. 26
• For empirical results, the checklist says the paper describes data collection, evaluation runs, measures, and hyperparameters, with simulated data requiring no preprocessing or train-validation split.It says the complete dataset is used for training and testing occurs in the true environment, as in classical online learning.Source: F The machine learning reproducibility… · p. 26
• The checklist says the supplementary materials include two environments and source code, while a third environment is fetched from a public repository.It points to Appendix E.3.3 for environment and code details.Source: F The machine learning reproducibility… · pp. 25–26
• The checklist states that figures use 95% confidence intervals and that the novel approach exhibits less variability.It points to Section 5.2 for the intervals and variability result.Source: F The machine learning reproducibility… · p. 26