Adversarial Nonlinear Semi-Bandits: Hidden Interactions and Amplitude-Sensitive Regret

Semi-bandit feedback reveals every selected base-arm outcome, yet nonlinear rewards can hide information in interactions that are observed only jointly. For every order $s\le K$, we construct an $s$-way dependence whose proper marginals are unchanged and prove regret $\Omega ({\Gamma }_s(g;K)\min \{T,\sqrt{((\genfrac{}{}{0ex}{}{N}{s})/(\genfrac{}{}{0ex}{}{K}{s}))T}\})$. The finite-difference certificate ${\Gamma }_s$ measures how strongly the known link values the hidden interaction. Selected coordinates also make every interaction supported inside the chosen action observable. A M\"obius decomposition turns this fact into an amplitude-sensitive upper bound $\tilde{O}({\sum }_s{b}_s(g)\sqrt{\left(\genfrac{}{}{0ex}{}{K}{s}\right)\left(\genfrac{}{}{0ex}{}{N}{s}\right)T})$, where $b_s(g)$ is the range of an order-$s$ observable coefficient. For every fixed action size $K$, the two bounds characterize minimax regret up to logarithmic factors, uniformly over normalized nonnegative polynomial mixtures and a reflected family of monotone concave links. The characterization includes links with a weak high-order component: their rate has a linear baseline and an amplitude-weighted high-order term. Finally, at fixed reward range, we prove that semi-bandit minimax regret is asymptotically smaller than under Bernoulli scalar feedback over a continuous parameter regime. Exact aggregate feedback additionally yields a complementary polynomial-approximation envelope.