Maximizing stochastic set function under a matroid constraint from decomposition

In this work, we focus on maximizing the stochastic DS decomposition problem. If the constraint is a uniform matroid, we design an adaptive policy, namely Myopic Parameter Conditioned Greedy, and prove its theoretical guarantee $$f(\varTheta (\pi _k))-(1-c_G)g(\varTheta (\pi _k))\ge (1-e^{-1})F(\pi ^*_A, \varTheta (\pi _k)) - G(\pi ^*_A,\varTheta (\pi _k))$$ f ( Θ ( π k ) ) - ( 1 - c G ) g ( Θ ( π k ) ) ≥ ( 1 - e - 1 ) F ( π A ∗ , Θ ( π k ) ) - G ( π A ∗ , Θ ( π k ) ) , where $$F(\pi ^*_A, \varTheta (\pi _k)) = \mathbb {E}_{\varTheta }[f(\varTheta (\pi ^*_A)) \vert \varTheta (\pi _k)]$$ F ( π A ∗ , Θ ( π k ) ) = E Θ [ f ( Θ ( π A ∗ ) ) | Θ ( π k ) ] . When the constraint is a general matroid constraint, we design the Parameter Measured Continuous Conditioned Greedy to return a fractional solution. To round an integer solution from the fractional solution, we adopt the lattice contention resolution and prove that there is a $$(b, \frac{1-e^{-b}}{b})$$ ( b , 1 - e - b b ) lattice CR scheme under a matroid constraint. Additionally, we adopt the pipage rounding to obtain a non-adaptive policy with the theoretical guarantee $$F(\pi )-(1-c_G)G(\pi ) \ge (1-e^{-1}) F(\pi ^*_A) - G(\pi ^*_A) - O(\epsilon )$$ F ( π ) - ( 1 - c G ) G ( π ) ≥ ( 1 - e - 1 ) F ( π A ∗ ) - G ( π A ∗ ) - O ( ϵ ) and utlize the $$(1,1-e^{-1})$$ ( 1 , 1 - e - 1 ) -lattice contention resolution scheme $$\tau $$ τ to obtain an adaptive solution $$\mathbb {E}_{\tau \sim \varLambda } [f(\tau (\varTheta (\pi )))- (1-c_G) g(\tau (\varTheta (\pi )))] \ge (1-e^{-1})^2F(\pi ^*_A,\varTheta (\pi )) - (1-e^{-1}) G(\pi ^*_A,\varTheta (\pi )) -O(\epsilon )$$ E τ ∼ Λ [ f ( τ ( Θ ( π ) ) ) - ( 1 - c G ) g ( τ ( Θ ( π ) ) ) ] ≥ ( 1 - e - 1 ) 2 F ( π A ∗ , Θ ( π ) ) - ( 1 - e - 1 ) G ( π A ∗ , Θ ( π ) ) - O ( ϵ ) . Since any set function can be expressed as the DS decomposition, our framework provides a method for solving the maximization problem of set functions defined on a random variable set.