Building a decision tree to approximate a known function (not to learn an unknown function) I have a function $f: \mathbb{D} \rightarrow \{0,1\}$ where $\mathbb{D} \in \mathbb{R}^{5000}$.

I would like to approximate $f$ using a decision tree.

Up to now I have only found literature in the context of machine learning, where $f$ is unknown, some samples $(x_i,\ y_i=f(x_i) + \mathrm{noise})$ are available and $f$ is estimated using a decision tree. That is a learning problem.

In my case I have a known (non trivial) expression for $f$ and I want to obtain the shortest binary decision tree for an arbitrarily good approximation (up to a specific error $\epsilon$). This seem to be a different problem than the learning problem (for instance, there is no regularization term to ensure generalization).

I suspect this problem to "hard". I assume some literature must exist on "no guarantees, greedy approaches" or similar, but I have not be able to find any.

Could any of you point me out some paper or book referring to this problem ?

Thanks for you answers.
For bitstring to boolean functions, people usually build binary decision diagrams instead of decision trees to represent functions compactly. If you want to find a small BDD and are willing to sacrifice correctness on a few inputs (as your question implies) then you might want to look into approximate BDDs as studied in the following two papers:

Hinsberger, U., Kolla, R., and Kunjan, T. [1997] "Approximative Representation of boolean Functions by size controllable ROBDD's"

Ravi, K., McMillan, K.L., Shiple, T.R., and Somenzi, F. [1998] "Approximation and decomposition of binary decision diagrams"

I am not sure if there is work that generalizes this for $\mathbb{R}^d \supset \mathbb{D}  \rightarrow \{0,1\}$ functions, but I would use those papers as a starting point and do a forward-reference search.