Edwin K.P. Chong, Sept. 30, 2026, ECE Graduate Seminar

Main ideas and lessons

• Problem setting: sequential decision-making / control

  • Making decisions step-by-step in time is framed as control in electrical engineering and as stochastic optimal control / Markov decision theory (Markov Decision Processes, MDPs) in computer science.
  • A key distinction:
    • Traditional control often uses continuous state/action spaces.
    • Many AI decision problems use discrete state/action spaces, though the underlying framework is shared.

• Motivation: AI “black-box” decision makers lack performance guarantees

  • Modern AI methods often rely on approximations (e.g., neural networks) that may be hard to interpret.
  • While empirical success is common (e.g., Deep Blue, Watson, AlphaGo/AlphaZero, ChatGPT), the talk highlights an open question:
    • How close are these approximate controllers to the true optimum?
  • The talk’s goal is to derive computable performance bounds for such approximate (“black-box”) decision makers relative to optimal control policies.

• Core goal of the work: certified approximation quality

  • Given a black-box approximate decision program (or policy), the aim is to compute a certificate, such as:
    • “This controller is guaranteed to achieve at least 60% (or another fraction) of the optimal performance.”
  • Even loose (weak) bounds are argued to be far better than no guarantees, especially for high-risk applications.

---

Methodology / framework presented (as an approach)

1) Model the decision process as stochastic optimal control / MDP

Represent a dynamical system in state-space form:

• State at time (k): (x_k) (with known initial (x_0))
• Control actions: (u_k) chosen from feasible actions (U_k(x_k))

• State transition: [ x_{k+1} = H_k(x_k, u_k) ] (general form; linear/nonlinear not assumed)

• Policy (control law): mapping from state to action [ \pi_k: x \mapsto u ]

Add a reward function:

• Reward at time (k): (r_k(x_k, u_k))

---

2) Define the optimal objective (stochastic control / finite horizon)

Goal: maximize the expected cumulative reward over a horizon of (h) steps:

• maximize over policy tuple ((\pi_0, \pi_1, \dots, \pi_{h-1}))
• subject to action feasibility and system dynamics

This corresponds to an MDP formulation (or a POMDP if partial observations are used, which can be converted to an MDP via state augmentation).

---

3) Use Bellman’s optimality principle (dynamic programming)

• Define:
  • Optimal policy (\pi^*)
  • Optimal state trajectory (x_k^*), actions (u_k^*)
  • Expected value-to-go (W_k^*(x_k)) (or equivalent notation)

Bellman structure: at time (k), the optimal action maximizes

• one-step reward + expected value-to-go

However, the exact dynamic program is intractable due to the curse of dimensionality.

---

4) Approximate dynamic programming (ADP) / approximate value-to-go

• Replace optimal value-to-go (W^*) with an approximation (\hat{W}).
• Obtain an approximate dynamic programming policy:
  • same Bellman-like structure, but using “hats” (approximations instead of stars/optimal).

The speaker connects this to modern AI methods (e.g., neural-network approximations trained via reinforcement learning, in the style of AlphaGo/AlphaZero-like approaches).

---

5) Compute a performance certificate for the approximate policy

Typical desired certificate forms:

• Ratio bound: performance of ADP (\ge B) times optimal performance
• or difference bound (discussed conceptually)

Key technical strategy:

• Instead of directly knowing the optimal value, derive an upper bound on the optimal objective using quantities tied to the approximate scheme.
• This reduces certification to controlling approximation error.

---

6) Introduce an approximation-error quantity and assumptions

The framework relies on:

• An approximation error (\varepsilon_k) that upper-bounds deviation from Bellman consistency (in expected-value terms)
• A feasibility-related technical condition:
  • feasibility sets at the optimal state/time relate appropriately to those at the approximate state/time

---

7) Ensure bounds are practically computable (not just theoretical)

The talk emphasizes computational feasibility:

• Avoid exponential dependence on horizon
• Avoid requiring full optimal value/policy computation
• Use a computable method to evaluate the needed approximation-error bounds

Intuition for what is not computable:

• anything involving “stars” (optimal objects),
• full dynamic programming over exponential trees,
• max over all policies, etc.

Intuition for what is computable:

• evaluation of actions under a single policy,
• expectations along a tractable rollout,
• expressions that use hatted (approximate) quantities.

---

8) Turn approximation-error control into the final bound

Under the approximation-error assumption:

• derive a bound upper-bounding the optimal value using terms involving (\hat{W}), (\hat{Q}), and (\varepsilon_k)
• convert it into a ratio certificate for ADP performance

---

Examples used to illustrate the theory (applications)

Example 1: Robot guidance (where optimal is computable)

• Problem: navigate from a source/origin to a destination
• Use LQG-style formulation where the optimal solution is computable (via Riccati-type equations)
• Compare:
  • neural-network controller performance
  • computed theoretical bound (certificate)

Result: the certificate verifies performance even if it is looser than the true gap.

---

Example 2: Pendulum stabilization (optimal not computable)

• Cast as an optimal control / stabilization task
• Use reinforcement learning (described as “PO” in subtitles)
• Vary neural network size (e.g., hidden layer neurons such as 16, 32, 128)
• Use certificates to claim qualitative guarantees like:
  • larger networks → better guaranteed fraction of optimal (e.g., ~70%, ~80%, ~90% suggested by plotted certificate curves)

Since the true optimum is intractable, the talk emphasizes certificates rather than verified optimality gaps.

---

Example 3: Sensor coverage (submodularity enables stronger structure)

• Task: place sensors to maximize detection coverage probability over a region
• Coverage modeled by spatial decay; objective relates to event detection probability
• The objective can be proven submodular
• Submodular optimization yields known universal greedy guarantees (including a 63% benchmark)

Compare:

• the talk’s certificate-based method vs. another submodular bound (e.g., “greedy curvature bound”)

Result: the certificate often exceeds the 63% baseline and can be substantially higher in some plotted parameter regimes (reaching near ~90%+). Two cases were considered:

• homogeneous sensors
• non-homogeneous sensors

---

Main takeaways / conclusions

• The talk introduces a framework for computable performance guarantees for approximate dynamic programming methods.
• The guarantees rely on measurable/derivable expected approximation error quantities that do not require knowing the optimal policy.
• The approach targets what modern AI decision/control methods already do:
  • approximate planning/control with neural networks or other approximators,
  • while adding formal certification of performance relative to optimal.

---

Speakers / sources featured

Speakers

• Professor Edwin K. P. Chong (main presenter; department seminar speaker)

Sources / referenced works (mentioned in the subtitles)

• Garwitz Kasparov (Deep Blue defeated him, 1997)
• Watson (IBM; Jeopardy)
• DeepMind / AlphaGo / AlphaZero (game-playing examples)
• Blackbox Society: The Secret Algorithms That Control Money and Information (book; quote used)
• “Neurodynamic Programming” (1996) by Dimitri Bertsimas and John Tsitsiklis
• Textbook (2017) by Bertsekas
• Submodular optimization with greedy universal bounds (classic result)
  • “universal bound of 63%” (attributed to older submodular literature; subtitles reference a “published in the ’70s” context)
• Conforti and Cornuéjols (1984) (subtitles mention a 1984 result for submodular-related bounding)
• Christo… Cassandra and Lynn Santi (2022) (sensor coverage citation referenced as a paper studied for submodular coverage)
• Conforti and Khachiyan (1980) (referenced for a “greedy curvature bound” comparison)

Note: Some citations may have transcription/name ambiguities from auto-generated subtitles; the items above are the explicitly named ones.