Doo

DOOConfig

Configuration for DOO algorithm.

Fields:

• delta::Function: Diameter function δ(h) providing upper bound on cell diameter at depth h. Should be a decreasing function of depth. NOTE: User will define this based on specific problem structure.
• degree::Int: Degree for child generation (default: 1)
• strict::Bool: If true, expand children along single branch at a time (default: false)
• value_transform::Function: Transform loss to value for maximization (default: loss -> -loss)

Theoretical Notes:

• DOO convergence depends on how well δ(h) bounds the actual cell diameters
• δ(h) should decrease at rate matching the partition refinement
• For binary splits: δ(h) = 0.5^h is typical
• For p-adic polydiscs: δ(h) depends on prime and radius shrinkage

Note: DOO does not need an explicit max_depth parameter. The tree search naturally terminates when the polydisc children() function returns empty at the precision boundary of the p-adic field.

DOONode{S,T,N}

Node in the DOO (Deterministic Optimistic Optimization) tree.

Fields:

• polydisc::ValuationPolydisc{S,T,N}: Region represented by this node
• depth::Int: Depth in tree (root has depth 0)
• position::Int: Position index among siblings
• parent::Union{DOONode{S,T,N}, Nothing}: Parent node reference
• children::Vector{DOONode{S,T,N}}: Expanded children
• value::Union{Float64, Nothing}: Evaluated function value (after value_transform)
• is_expanded::Bool: Whether node has been expanded

DOOState{S,T,N}

State for DOO optimization.

Fields:

• root::DOONode{S,T,N}: Root of search tree
• total_samples::Int: Total function evaluations performed
• next_branch::Int: Branch index for strict mode
• step_count::Int: Number of optimization steps taken
• leaves::Vector{DOONode{S,T,N}}: Vector of unexpanded leaf nodes

Note: leaves vector currently requires O(N) scan to find maximum b-value. TODO: Replace with PriorityQueue from DataStructures.jl for O(log N) performance.

b_value(node::DOONode, config::DOOConfig)

Compute the b-value (optimistic upper bound) for a node.

Formula: b(h,j) = value + δ(h)

where:

• value = value_transform(loss) is the transformed function value at the node
• δ(h) is the diameter bound at depth h

The b-value represents the best possible value that could be achieved within the node's region, assuming the function could vary by at most δ(h).

Returns: Float64 b-value (Inf for unexplored nodes)

doo_descent(loss::Loss, param::ValuationPolydisc{S,T,N},
            state::DOOState{S,T,N}, config::DOOConfig) where {S,T,N}

Perform one step of DOO optimization.

Algorithm:

1. Select leaf with maximum b-value (optimistic upper bound)
2. Remove selected leaf from leaves list
3. Expand selected leaf (generate and evaluate children)
4. Add new children to leaves list
5. Update state (step count, next_branch for strict mode)
6. Return best-valued node's polydisc as new parameter

Returns: (new_param::ValuationPolydisc, updated_state::DOOState, converged::Bool).

doo_descent_init(param::ValuationPolydisc{S,T}, loss::Loss,
                 next_branch::Int, config::DOOConfig) where {S,T}

Initialize DOO optimizer.

Creates the initial search tree with root node, evaluates root, and returns an OptimSetup configured for DOO optimization.

Arguments:

• param: Initial parameter polydisc (becomes root of search tree)
• loss: Loss function with eval and grad methods
• next_branch: Initial branch index for strict mode
• config: DOO configuration

Returns: OptimSetup instance ready for optimization via step!()

expand_node!(node::DOONode, loss::Loss, config::DOOConfig, state::DOOState)

Expand a node by generating and evaluating its children.

Algorithm:

1. Generate child polydiscs (using children() or childrenalongbranch())
2. Create child nodes
3. Evaluate loss at each child
4. Transform loss to value
5. Update parent's children list
6. Increment sample counter

Returns: Vector of newly created child nodes (empty if node cannot be expanded)

get_all_leaves(state::DOOState)

Get all leaf nodes (expanded or not) in the tree by traversing from root.

This differs from state.leaves which only tracks unexpanded leaves.

get_best_node(state::DOOState)

Get the node with the best (highest) value evaluated so far.

Since value = value_transform(loss), higher value means lower loss. This returns the node corresponding to the best solution found.

get_best_value(state::DOOState)

Get the best value found so far (after value_transform).

get_leaf_count(state::DOOState)

Get number of unexpanded leaf nodes currently in the leaves list.

get_tree_size(state::DOOState)

Get total number of nodes in the DOO tree (including root and all descendants).

select_best_leaf(state::DOOState, config::DOOConfig)

Select the unexpanded leaf with maximum b-value.

This implements the selection step of DOO: choose the leaf node that has the highest optimistic upper bound on its potential value.

Returns: DOONode with maximum b-value, or nothing if no leaves available

Performance: O(N) where N is number of leaves. TODO: Use PriorityQueue for O(log N) selection.